胡章芳，罗 磊，吕元元，罗 元

(重庆邮电大学 光电工程学院，重庆 400065)

0 引 言

路径规划是移动机器人自主导航系统中具有重要意义的研究课题。路径规划方法可分为全局路径规划和局部路径规划。蚁群优化(ant colony optimization，ACO)算法是一种典型的全局路径规划算法[1-2]，如果静态环境中存在路径，总能通过它的启发函数找到一条通向目标的最优路径。由于蚁群算法路径规划是边探索边前进的过程，所以该路径规划算法计算上既复杂又缓慢[3]。文献[4]提出了一种借鉴狼群分配原则对蚁群信息素进行更新的算法，避免搜索陷入局部最优。文献[5]提出了一种新的动态搜索诱导算子来提高蚁群算法的性能，但是该算法初期需要设定较大阈值，不利于算法收敛，无法快速得到最优解。文献[6]提出了简化A*算法来优化初始信息素设置以达到加快蚁群算法收敛速度的目的，但是在环境地图改变时，无法对路径进行及时调整。文献[7]提出了一种结合粒子群算法的改进蚁群算法，通过粒子群优化(particle swarm optimization，PSO)算法对蚁群算法关键参数的启发，使得机器人在运动过程中选择避免与障碍物碰撞的最优路径。此外，人工势场(artificial potential field，APF)算法[8]是最常用的局部路径规划方法之一，它具有计算速度快，使用方便等优点。但是，人工势场算法也存在局部最优问题，当局部最优问题发生时，机器人可能被困在与目标无关的另一个位置。在APF被Knatib[9]第一次提出之后，研究者们尝试各种方法解决局部最优问题。文献[10]介绍了一种基于APF的移动机器人导航方法。在该方法中，新的排斥力被应用于解决局部最优问题。当机器人感知范围内存在障碍物时，除了原本有的力外，还会产生一种新的排斥力，这个力可以使机器人能平滑地避开障碍物。文献[11]介绍了一种结合人工势场算法的萤火虫算法，利用人工势场法作为初始化引导因子对萤火虫算法参数进行初始化，加快算法在初期的搜索时间。

为了解决蚁群算法存在的问题，本文将人工势场的影响因素引入到蚁群算法的转移概率函数以及启发函数中，并利用对数函数模型对信息素更新策略进行改进。本文与改进前的蚁群算法以及文献[12]提出的改进蚁群算法进行对比。最后，将改进的算法应用到实际机器人上，替换原有的路径规划算法，结果表明，本文算法一定程度上提高了路径规划的效率，具有一定的实用性。

1 问题描述

1.1 环境建模

移动机器人通常在路径规划之前，利用自身携带的传感器对周围环境进行数据采集，然后，通过数据融合建立环境模型。栅格地图描述环境信息的方法具有简单有效、易于实现等特点，在路径规划中得到了广泛的应用[13]。本文采用二维栅格地图法来建立环境地图。栅格地图分为2种状态：占据态和空闲态，如图1，当栅格地图被障碍物占据时，就用黑色方块表示；当栅格未被占据时，该区域机器人可以通行，用白色方块表示。

图1 栅格地图Fig.1 Grid map

本文为了便于研究和开展实验，对栅格地图做了如下假设。

1)当单个栅格中障碍物覆盖率大于等于0.5时，就假设当前栅格内全被障碍物覆盖；当障碍物的覆盖率小于0.5时，就假设当前栅格未被占用。

(1)

2)地图是在考虑机器人安全距离下建立的，机器人在栅格地图中以质点的形式存在，且只能在栅格地图中移动。

3)当机器人所处位置周围栅格没有障碍物时，它向周围任意方向移动的概率是相等的。

1.2 蚁群算法

蚁群是根据先前蚂蚁留下的信息素量的多少来参照转移概率自主选择到达食物源的最优路径即最短路径[14]。

(2)

(2)式中：τij(t)表示t时刻栅格i与j之间的信息素含量；Aa表示蚂蚁在地图内允许行走的节点。

路径上的信息素更新方式表示为

τij(t+Δt)=(1-ρ)·τij(t)+Δτij(t)

(3)

(4)

(5)

(6)

(3)—(6)式中：ρ表示信息素的挥发因子，ρ∈(0,1]；Q表示为常数的信息素强度；dij表示栅格i到栅格j的欧氏距离；Lm表示此次循环结束时蚂蚁所走过的路径总长度。

2 改进蚁群算法

2.1 人工势场算法

通常，人工势场算法包含了2个场[16]：①由目标点产生的引力场Uatt(pm)；②由障碍物所产生的斥力场Urep(pm)。总场强Utot(pm)是引力场和斥力场的矢量叠加。

Utot(pm)=Uatt(pm)+Urep(pm)

(7)

(7)式中：pm=(xm,ym)T是机器人在笛卡尔坐标系下的位置矢量；合力Ftot(pm)是合势场函数的负梯度，表示为

Ftot(pm)=-∇Utot(pm)=

Fatt(pm)+Frep(pm)

(8)

(8)式中：Fatt(pm)是目标点产生的引力；Frep(pm)是障碍物产生的斥力；Ftot(pm)是作用于机器人的斥力与引力2个力的合力，人工势场示意图如图2。其中，pg=(xg,yg)T和p0=(x0,y0)T是目标点和障碍物所在的坐标位置，νm是机器人当前的速度。

图2 人工势场示意图Fig.2 Schematic diagram of artificial potential field

2.2 改进蚁群算法

基于势场导向的改进蚁群算法是在原有蚁群算法基础上对利用势场影响因素对路径规划进行了优化。由于蚁群算法的启发函数是由蚂蚁当前位置到下一位置的距离所决定的，这不利于蚂蚁对障碍物的提前预见(只有当蚂蚁临近障碍物时，才能进行避障)，算法的初始阶段都是蚁群在进行“盲目”地搜索，使得整个路径规划过程存在许多交叉路径。因此，在蚁群算法的初期就建立势场的影响，使得蚁群能在算法开始时就向着目标点方向移动，并且，建立的势场可以让蚂蚁在一开始就能对已知的障碍物进行提前预见。因此，在寻路的过程中可以大大减少对不必要的路径的探索，有效地减少路径搜索上的时间消耗。

2.2.1 人工势场的建立

人工势场的建立主要分为2个部分：①对目标点引力场的建立；②对已知障碍物的斥力场的建立。

引力和斥力可以分别表示为

(9)—(10)式中：katt和krep分别为引力和斥力的系数因子，用于调节整个势场的影响权重；dt为障碍物势场所能影响到的最大距离，一般是一个栅格的范围；d0和dg分别为机器人到障碍物和目标点的欧式距离。

(11)

(12)

由(9)—(10)式可知，目标点对机器人起点处的引力场最大，机器人越靠近障碍物，所受的斥力场影响越大。图3是引力场和斥力场的示意图。

图3 引力场和斥力场示意图Fig.3 Schematic diagram of gravitational field and repulsive field

建立势场模型后，计算蚂蚁所处位置在势场中所受合力与相邻栅格方向的最小夹角，如图4，将蚂蚁所在栅格附近8个栅格每45°划分一个方向(以X轴方向为0°顺时针依次增加)。

图4 栅格夹角计算示意图Fig.4 Schematic diagram of grid of angle calculation

假设蚂蚁所受合力方向的角度为ϑ，蚂蚁向下一个相邻栅格转移的角度为ω。且蚂蚁转移方向与合力方向夹角不超过180°。则

ϑ=∠(Fatt+∑Frep)

(13)

φ=ϑ-lω

(14)

l=|sin(ω-ϑ)|

(15)

(14)—(15)式中，l∈(0,1]为动态权重因子。势场影响函数为

q(t)=exp(φ)

(16)

2.2.2 蚁群算法的改进

由蚁群的转移概率(2)式可知，初始状态启发函数和信息素更新机制是对蚁群寻路影响最大的2个因素。原有的蚁群算法的启发函数只考虑了待转移节点与目标点之间的距离dij而忽略了障碍物的影响，所以使得算法有时会陷入局部最优。原有蚁群算法的信息素更新策略可以改善后期的全局搜索能力，但是不可避免地会降低算法前期的收敛速度。因此，本文主要是对蚁群算法的启发函数和信息素更新策略进行适当的改进。

1)启发函数的改进。由于人工势场算法具有计算速度快的优点，在考虑障碍物存在的环境时，将人工势场中待转移节点到目标点的欧式距离djg引入到蚁群算法的启发函数中。改进后的启发函数表示为

(17)

(17)式中：ζ∈(0,1]为启发调整因子；NCmax为最大迭代次数；NC为当前迭代次数；djg为待转移节点j到目标点的欧式距离；dij为当前点i到目标点的欧式距离。算法初期，迭代次数NC较小，整个启发函数的影响作用就较大；相反，算法后期，迭代次数接近最大迭代次数，削弱了启发函数对路径探索的影响。

2)信息素更新策略的改进。传统蚁群算法信息素更新策略中路径上残留的信息素是固定的，总的信息素含量只与蚂蚁当次循环走过的总的路径长度有关。为了平衡算法后期探索效率，对信息素更新进行如下改进。

τij(t+Δt)=

(18)

算法前期，NC较小，路径上基本没有信息素残留，总的信息素含量受Δτij(t)的影响大；算法后期，在最优路径上残留的信息素含量增加，减弱了蚂蚁前期对无效路径探索所留下的信息素对整个路径规划的影响。使得整个算法的收敛速度更快。

2.2.3 算法改进步骤

改进算法的流程图如图5。

图5 改进算法流程图Fig.5 Improved algorithm flow chart

具体的算法步骤如下。

步骤1初始化算法中的各项参数，包括蚂蚁的个数M，迭代的最大次数N，以及α，β，γ等各因子。

步骤2初始化路径规划任务。

步骤3根据机器人传感器提取环境信息，建立包含障碍物的栅格地图。

步骤4计算蚂蚁所在位置受到势场的引力、斥力，并建立人工势场模型。

步骤5根据蚂蚁所处位置以及(17)式启发函数，建立蚂蚁可移动的栅格表，并根据(18)式更新路径上的信息素。

步骤6根据(16)—(18)式计算蚁群转移概率，来确定下一步的搜索方向，并更新禁忌表。

(19)

步骤7判断当前蚂蚁是否完成路径搜索。若没有，则进入步骤4继续进行；否则根据(18)式进行信息素更新。

步骤8判断是否达到最大迭代次数并判断是否到达目标位置。若达到最大迭代次数，但未到达目标位置，则进入步骤9；若未达到最大迭代次数，但到达目标位置，则进入步骤10；若未达到最大迭代次数，且未达到目标位置，则进入步骤4，继续循环。

步骤9该次算法失败，重新手动调整参数进行路径规划。

步骤10绘制整个算法的迭代次数图和最佳路径图，算法结束。

3 仿真与实验

3.1 仿真分析

为了验证本文所提出的算法的全局路径规划的可行性，在MATLAB 2016b软件中对改进前后的算法进行了仿真对比实验，实验采用的计算机配置为Intel Core i3-6100双核CPU，最高主频3.70 GHz，内存4 GB。实验选取了20×20栅格范围内的2类不同的环境作为代表，如图6[17]，为了保证结果的准确性，分别进行了多次独立重复实验。仿真的起点为地图左上角栅格，目标点为地图右下角栅格。

图6 2类环境栅格地图Fig.6 Two types of environment grid maps

由图7，图8可知，改进后的ACO算法初期不会进行“盲目”的搜索，可以避免路径陷入局部最优情况的出现，并且算法初期就有着不错的收敛特性，相对于改进前的算法有着更平滑的轨迹，更优的路径长度。算法改进前后多次试验平均用时如表1。可以看出，改进后的ACO算法有着更高的探索效率。

图7 障碍物分散环境下算法改进前后实验结果Fig.7 Experimental results in sparse environment

图8 障碍物集中环境下改进前后算法实验结果Fig.8 Experimental results in dense environment

表1 算法改进前后平均用时对比Tab.1 Average time before and after algorith improvement is compared

为了进一步证明本文算法的优势，本文还与文献[12]所提出的改进算法进行了实验对比。得到的结果如图9。

对比图9a和图9b可以看出，本文的在最优路径上基本与文献[12]一致，但是从图9c的对比结果可以看出，本文算法在初期收敛速度明显优于文献[12]的改进蚁群算法。与文献[12]对比结果如表2，并且从表2的结果可知，在相同的平均最优路径长度的情况下，本文的改进算法耗费的时间更短，性能更优。

表2 与文献[12]对比结果Tab.2 Results of literature[12] comparison

图9 与文献[12]对比结果Fig.9 Results of literature[12] comparison

3.2 实验验证

为了进一步验证所提出的算法路径规划可行性，将提出的改进算法移植到基于ROS(机器人操作系统)开发实际的机器人上进行实验，该机器人使用Hokuyo激光雷达进行建图。如图10，是由本实验室自己开发的机器人以及搭建的约25 m2的实际环境。

图10 实际机器人模型与环境Fig.10 Real robot model and environment

机器人首先是利用激光雷达采集环境数据，通过ROS中的amcl和gmapping定位建图包进行定位与建图[18]，建立的栅格地图如图11，其中，A点为路径规划起点，B点为目标点。最后，利用本文提出的算法替换move_base包中原有的global_planner和local_planner[19]算法实现路径规划。

图11 建立的栅格地图Fig.11 Building grid map

算法改进前后机器人实际运动轨迹对比结果，如图12。

图12 路径规划结果对比Fig.12 Comparison of path planning results

由图12可看出，改进后的蚁群算法路径长度更优。表3是多次实际路径规划试验得到的平均时间，从结果可以看出，改进后的算法路径搜索时间缩短约52%。

表3 实际环境路径搜索平均时间对比Tab.3 Comparison of average time of real environment path search

4 结 论

本文对蚁群算法的启发函数和信息素更新策略进行了适当的改进，并且引入人工势场算法对蚁群算法的转移概率函数进行改进，有效地解决了蚁群算法在探索初期会进行“盲目”搜索的问题，并且减少了算法会陷入局部最优情况的出现，加快了蚁群算法后期的探索收敛速度，使得整个算法在耗时方面有了明显的改善。仿真实验结果表明，本文的改进算法收敛速度明显快于传统蚁群算法，并且，通过与文献[12]的对比结果可以看出，本文的算法在性能上更优。最后，本文还将提出的改进算法移植到实际的机器人上进行实验。结果表明，本文提出的改进算法能很好地完成路径规划任务，并且有着更优的轨迹。综上，本文提出的改进算法具有一定的理论参考价值与实际应用意义。