基于改进人工蚁群的智能巡线机器人路径规划

刘二根，谭茹涵，陈艺琳，郭 力

（华东交通大学1. 理学院； 2. 系统工程与密码学研究所，江西 南昌 330013）

随着疫情的持续蔓延，“无接触式”一词成为了当下热点。生产生活中部分工作已由机器人替代人执行，抗疫机器人可以在一线检测来访人员体温，安防机器人能提醒司机扫码登记，送餐机器人在隔离区提供远程配送等，在特殊时期，智能巡线机器人的投入使用在人与人的安全距离上多建立了一道防线。而路径规划是智能机器人的关键技术之一。

路径规划是指机器人在规划好的环境中搜索出一条或路径长度最短，或耗时最短的最优路径，还应根据对环境信息的把握，遵循一定的性能要求，使得路径与障碍物无碰撞。 蚁群、人工势场、遗传算法、A*、Dijkstra 等是常用的路径规划算法。 Khatib 等[1]提出人工势场算法，是传统算法中较成熟且高效的规划方法，但容易陷入陷阱和局部极小点，徐小强等[2]采用人工势场法规划路径，障碍物和必经点分别对机器人产生排斥力和吸引力，在此过程中,机器人对障碍物的斥力比较敏感，使得路径易在目标点附近游离，无法达到目标点。 张驰等[3]将势场算法结合蚁群，重建启发函数，更新了信息素规则，从局部最优解中解脱。 王小会等[4]通过嵌入Dijkstra 算法实现一种经过必经点的最短路径。 曹祥红等[5]利用Dijkstra 算法搜索到全局路径后，导入ACO 算法进行路径优化，提高了效率，但没有考虑陷阱的情况。Hart[6]提出了A*算法，引入估价函数，如果估价函数等于最短距离，那么搜索将严格按照最短路径进行，此时的搜索效率最高。 罗汉杰等[7]选择曼哈顿距离作为估价函数，计算出最佳路径，但未对轨迹做平滑处理，无法满足现实情况下的机动性。 余文凯等[8]利用K-Means 对地图进行分区处理，根据聚类结果，对评价函数和节点选择方式进行改善，改善了平滑度，搜索效率更高。蚁群算法1991 年由Dorigo 提出，吸收了蚂蚁的行为特性，根据信息素浓度进行路径的选择，算法鲁棒性较强，设置简单，但收敛速度慢，没有考虑地形的因素。 左敏等[9]引入自适应迁移概率函数，提高了算法的收敛速度，但没考虑平滑度的需求。

基于对路径规划问题中障碍物的绕过、路径平滑度、寻路效率等因素的考虑，采用A* 结合ACO 算法的组合模型对机器人路径进行规划，利用A* 算法的全局搜索能力，找出两点之间最合适的路径，在进行多点规划时，采用改进后的蚁群算法求解多点之间最优路径。

1 全局路径规划

1.1 环境建模

在仿真环境中， 障碍物是不可避免的参数，本实验采用栅格法对环境进行模拟，将环境划分为二值网格单元见图1，其中栅格大小暂定为1，实际行驶过程中会根据机器人大小进行设定。 将巡线地图设为60×60 的栅格图，其中黑色区域为地图中的障碍物区域，白色区域为安全区域。 其中的散点代表着巡线机器人要巡视的地点。

图1 环境仿真栅格图Fig.1 Environment simulation grid

1.2 A*算法原理

A* 为一种多角度进行搜索的全局寻路算法，选取在当前位置周围F 值最小的点为路径的下一步。 F 为代价函数，计算公式为

式中：G 为从起点移动到指定位置的移动代价,取横向及纵向为10，对角线为14；H 为从指定位置移动到终点的估算成本，其中路径忽略障碍物，当前选用Manhattan 方法进行估算

计算当前位置横或纵向移动到达终点所经过的方格数。

A*算法规定了路径的角度，传统算法有8 个角度对外扩展。 具体步骤如下：

①设定open 表存放当前点可能要经过的下一个点，设定close 表存放不能经过的点；

②搜索与八个位置对应相邻的栅格，将当前位置设置为父节点，设为点A；

③排除掉障碍物和已经走过的位置，剩余位置设置为子节点，都放入open 列表中，进行F 值的计算，将子节点中F 值最小的点，设为点B，加入close 列表；

④将B 点设置为父节点后重复操作；

⑤当发现此点的子节点已经在open 列表中，假设为点C，则检查由点A 直接到点C 是否会比A-B-C的路线更优，若是，则退回一步，重新将A 设置为父节点，此时B 点已进入close 列表，不会参与进行下一点的路径选择。

从图2 中A* 算法的路径选择可以明显看出路径结果角度生硬，转折点过多，不够平滑。 对此路径进行平滑处理：遍历路径上的点，若是两点之间无障碍物，则可直接连接。 基于此条平滑准则，需要对两点之间经历的栅格进行判断，判断其是否有障碍物。

1.3 障碍物判断

图2 A* 算法寻路结果图Fig.2 A* algorithm path finding result

①计算两点之间直线方程f；

②由于栅格是以整数坐标为中心， 上下左右距离中心0.5 个位置的正方形， 取距起点纵坐标0.5 个位置为第1 个测量点， 每距离1 个位置进行测量，生成列表y=［y1，y2，…，y3］；

③基于直线方程，生成列表x=［x1，x2，…，x3］；

④判断y 中每2 个相邻的值间隔几个栅格

num=math.ceil（x［i］-）-math.floor（x［i-1］） ( 3 )其中，math.ceil 是向上取整，math.floor 是向下取整。

图3 一条直线经过的栅格Fig.3 A grid with a straight line

平滑后的A* 算法不仅能使路径更流畅，还能成功脱离“陷阱”，由图中可看出，在某个障碍物附近徘徊的线条平滑后成功出逃。

图4 不同A* 算法结果比较Fig.4 Comparison of results for different A* algorithms

2 最优路径规划

2.1 实验蚁群算法原理

蚁群算法是一种启发式优化算法，蚁群在寻找食物时，总是能找到一条从食物到蚁穴的最短路径，信息素在其中发挥了很大作用，蚂蚁走过的路径都会留下信息素，剩余的蚂蚁选择路径时会受信息素的浓度影响，在岔路口时，倾向于选择浓度更高的一侧。

在A*算法找到全局路径后， 构建信息素矩阵， 信息素矩阵中的元素会在迭代过程中随着路径不断变化，迭代完成后，信息素浓度最高的路径就是最优的结果。

传统蚁群算法对信息素处理分为全局和局部两种，全局处理是在蚂蚁循环完整个路径后，对整个信息素矩阵进行更新，局部信息素处理是在蚂蚁每完成一步后更新信息素。本实验引入双信息素策略，局部与全局同时进行，能有效克服传统蚁群易陷入局部最优解的问题。

2.2 算法描述

1） 设置蚂蚁数量，输入必访问点列表，设置迭代次数，初始化点之间的距离矩阵，信息素矩阵，启发函数矩阵；

2） 将蚂蚁放在不同点上，尽量保证蚂蚁的起始点不同，并记录下蚂蚁访问的点下标，将其加入禁忌表，表示下次不会再重复访问此点；

3） 根据状态转移概率对下一次访问点做出选择

式中：α 为信息启发式因子；β 为期望启发式因子；τ 为信息素浓度；η为启发式信息，取值为

一般取为点间距离的倒数；

4） 在自然界中，蚂蚁遗留的信息素会随着时间流逝而挥发，模拟此过程，更新信息素矩阵，蚂蚁移动到下一点后，对信息素进行局部更新

5） 重复以上步骤，一直到路径形成闭环，即蚂蚁回到起始点。 对表现最优的精英蚂蚁采用全局信息素更新策略

式（6）中：ρ 为人为定义的信息素挥发率，一般位于0～1 之间，由于实验所用到的地图较小，选择较低的挥发率能达到较好的实验结果，故选取ρ 为0.1。 全局更新策略不作用于所有蚂蚁，只对每次循环中的精英蚂蚁（路径最短）使用，这样做可以减少迭代次数，加快搜索效率。

3 实验与比较

采用局部信息素更新策略的蚁群算法称为蚁量模型，而使用全局信息素更新策略的蚁群算法称为蚁周模型。 分别对蚁量模型、蚁周模型及双信息素蚁群算法进行实验，对改进蚁群算法的两种信息素加以权重，经过多次实验，确定全局信息素权重为1，局部信息素权重为2。

图5 不同ACO 算法结果对比图Fig.5 Comparison grid of results for different ACO algorithms

表1 基于不同数目必经点算法所用时间结果比较Tab.1 Comparison of time results for algorithms based on different number of required points s

从算法时间比较表来看， 双信息素策略对算法时间影响不大，与另两类蚁群算法相比，时间差距在0.5 s 内。 在效率对比图上有15 个点以及20个点的三种蚁群算法最优解进化过程， 可以看出改进蚁群算法比两种传统算法收敛更快， 且传统算法易陷入局部最优，改进算法得到的路径更优。

图6 效率比较图Fig.6 Comparison chart of efficiency

5 结论

本文利用A* 算法得到绕过障碍物的全局路径，平滑后成功绕过“陷阱”，且得到结果更优的全局路径，再引进双信息素改进传统蚁群算法，有效克服了蚁群算法易陷入局部最优解的缺陷，使得性能显著提升，且必经点越多，路径越复杂，优化效果越明显。