基于改进蚁群算法的多机器人路径规划研究

顾军华，孟慧婕，夏红梅，董永峰

（1.河北工业大学 计算机科学与软件学院，天津 300401；2.河北工业大学 河北省大数据计算重点实验室，天津 300401；3.河北工业大学 河北工业大学学报编辑部，天津 300401）

基于改进蚁群算法的多机器人路径规划研究

顾军华1,2，孟慧婕1,2，夏红梅2,3，董永峰1,2

（1.河北工业大学 计算机科学与软件学院，天津 300401；2.河北工业大学 河北省大数据计算重点实验室，天津 300401；3.河北工业大学 河北工业大学学报编辑部，天津 300401）

针对蚁群算法在机器人路径规划过程中存在的收敛速度慢、效率较低、容易陷入局部最优等缺点，提出了一种多步长的改进蚁群算法．该算法实现了多步长路径规划；同时在概率公式中加入了拐点参数，使路径更加平滑；并且提出了新的信息素奖励惩罚机制．将改进的蚁群算法应用于具有3个优化目标的多机器人路径规划中，采用碰撞预测策略和路径协调策略完成多机器人间的协调避碰．仿真结果表明，改进的蚁群算法规划的路径更短、更平滑，效率更高，验证了该算法在多机器人路径规划中的有效性和可行性．

多机器人；路径规划；改进蚁群算法；多步长；拐点参数；协调避碰

0 引言

多机器人路径规划问题是多移动机器人系统中最基本的问题之一，它的任务是为每个机器人规划一条从起点到终点的最优路径，并且保证机器人和机器人之间、机器人和障碍物之间没有碰撞．目前众多学者已针对此问题展开了大量研究．文献[1]将全局目标点映射到视野域附近作为局部子目标，再由两组蚂蚁相向搜索视野域内的局部最优路径，在此基础上进行与其他机器人的碰撞预测与避碰规划，但是在动态不确定环境中规划路径所需的时间较长．文献[2]采用集中式和分布式相结合，融合免疫协同进化算法与人工势场法进行全局和局部规划．文献[3]提出了基于双层模糊逻辑的多机器人路径规划，考虑障碍物的距离和目标的角度，同时为了提高避碰的效率提出改变机器人的速度，但是机器人缺少对全局环境的了解，难以保证多机器人规划出的路径全局最优．蚁群优化算法因其并行性、鲁棒性、易于与其他算法相结合的优点[4]，广泛应用于移动机器人路径规划问题[5-6]．许多学者针对路径规划问题对基本的蚁群算法进行了改进．文献 [7]提出了蚁群算法和模糊控制相结合的方法，但该方法比较复杂，较难掌握．文献 [8]提出根据目标点自适应调整启发函数，信息素更新时参考狼群分配原则，同时引入粒子群算法改进蚁群算法的参数，优化了蚁群算法的性能．文献 [9]改进了期望值，更新信息素采用自适应方式，并在更新信息素时引入拐点，但是该方法由于步长的单一，对路径长度的改进不是特别明显．

本文提出一种多步长的改进蚁群算法．首先用栅格法进行建模，采用多步长缩短了路径长度，在概率公式中加入了拐点参数使路径更加平滑，提出了新的信息素奖励惩罚机制避免陷入局部最优．然后将改进的蚁群算法应用到3个机器人的路径规划中，主要分为2步：1）各个移动机器人采用改进的蚁群算法，独自规划一条初始路径（忽略其他机器人）；2）如果在视野域范围内发现其他机器人，进行局部避碰协调规划．最后先在单机器人情况下将改进的蚁群算法和文献[9]中提到的改进蚁群算法进行比较，然后把改进后的算法应用到多机器人中，完成仿真实验．

1 环境描述

多个机器人的工作环境为二维静态环境，有N个机器人Ri，i∈ (1,2,……,N)；机器人的起点和终点分别为Si和Gi，起点和终点各不相同；机器人之间能进行基本的通信；所有机器人的速度相同，状态可以为匀速运动和暂停；机器人的大小相同．

采用栅格法进行建模，它能够方便处理障碍物的边界问题，栅格模型如图1所示，左下方为原点，向右为x轴，向上为y轴，栅格的边长为1．黑色部分表示有障碍物的栅格（障碍栅格），当障碍物小于一个栅格时，按照占一个栅格处理，白色部分为不存在障碍物的栅格（自由栅格）．把障碍物外扩一个机器人的最大直径，移动机器人在栅格之间的移动可以近似成一个质点．

图1 栅格法环境模型Fig.1 Grid environment model

设序号为i的栅格对应的坐标为(xi，yi)，则序号编码与坐标对应关系如式 (1)所示．其中当mod(i,20) ==0，即i为20的整数倍时，将xi设为19.5．

2 蚁群算法

2.1 基本蚁群算法

蚁群算法是一种典型的路径规划算法．每只蚂蚁在搜索路径的过程中，基于其获取的环境信息（主要是其它蚂蚁在其走过路径上留下的信息素浓度），按照若干简单规则进行实时路径规划，找到1条从起点到终点的最优无碰撞路径．虽然每只蚂蚁表现出简单的行为，但是蚂蚁群体中大量蚂蚁通过与环境相互作用，就会呈现出复杂且灵活多样的行为．

2.1.1 转移概率

设蚂蚁数量为M，假设第m(m=1,2,…,M)只蚂蚁位于序号为i的栅格处，蚂蚁m根据节点的信息素强度和启发信息选择下一节点j，转移概率公式如式 (2)所示

2.1.2 信息素更新

蚁群经过某个栅格时会留下信息素，随着时间的推移信息素会逐渐消逝，每一代的所有蚂蚁完成寻径以后，要对信息素进行更新，更新公式如式 (4)所示．

其中：Mij为经过路径(i,j)的蚂蚁集合；为第m只蚂蚁留给节点i、j间的信息素增量，如式 (6)所示，Q为一适当常数，Lm为本次循环中蚂蚁m走过的路径长度．

2.2 改进的蚁群算法

针对基本的蚁群算法效率低和容易陷入局部最优的缺点，本文提出了几点改进：多步长、概率公式加入拐点参数以及信息素更新方式的改进等．

2.2.1 多步长

基本的蚁群算法路径规划时，蚂蚁只能选择相邻的栅格作为下一节点，如图2所示，蚂蚁当前所处的栅格为34，基本蚁群算法只可以选择周围的8个栅格，可选集合为 {23,24,25,33,35,43,44,45}．改为多步长后可以选择周围的24个栅格作为下一节点，蚂蚁可以从34栅格一步移动到26栅格．

如图3所示蚂蚁从栅格i到栅格j时，基本的蚁群算法选择的最优路径可能为路径1，改为多步长以后最优路径为路径2，可见多步长缩短了路径的长度．采用多步长时，需要将选择的下一节点和路过的节点都加入到禁忌列表中．

图2 多步长示意图Fig.2 Multi step diagram

图3 多步长蚁群和基本蚁群路径长度比较Fig.3 Comparison of multi-step ant colony and basic ant colony path length

2.2.2 概率公式

为了使所寻路径更加平滑，加入拐点参数gdij作为蚂蚁选择下一节点的一个依据．路径中拐角分为锐角、直角和钝角3种，假设蚂蚁位于节点i，由节点i运动到下一可行节点j时拐角为A，拐点参数对应的值如式(7)所示，其中A的角度越大被选中的概率越大，改进后的概率公式如式(8)所示．为了避免陷入局部最优，采用轮盘赌法选择节点．

2.2.3 信息素更新

基本蚁群算法中，最差蚂蚁释放的信息素将导致算法的搜索陷入局部最优，为了避免局部最优和提高收敛速度，本文提出了新的信息素奖励惩罚机制，对本次迭代的最优路径给予奖励，增大其释放的信息素量，对最差路径进行惩罚，改进的信息素浓度更新公式如式 (9)～式 (11)所示，M_bij和M_wij分别为经过本次迭代最优路径和最差路径的蚂蚁，Lbest和Lworst分别为本次迭代的最优路径长度和最差路径长度．

3 基于改进蚁群算法的多机器人路径规划

3.1 代价函数的设计

为机器人Ri规划连接起点到终点的路径，要求机器人同障碍物、其他机器人之间没有碰撞，并且所有机器人完成路径所付出的总代价最小．本文考虑路径长度、路径平滑度和暂停时间3个优化指标，多机器人的代价函数如式 (12)～式 (15)所示

其中：函数f1x，f2x，f3x分别表示路径长度、路径平滑度和暂停时间；li表示机器人Ri规划的路径长度；turni为机器人Ri走过路径的拐点余弦的平均值，为机器人Ri整条路径的拐点个数；cos Aij为机器人Ri第j个拐角的余弦值，；Ti表示机器人Ri暂停的时间．为多个机器人规划路径时，要求式 (12)的代价尽可能小，即多个机器人的路径尽可能短、行走的路径尽可能平滑以及暂停时间尽可能短．

本文多机器人路径规划的主要思想是，首先，在不考虑其他机器人的情况下，根据上文提到的改进蚁群算法为每个机器人规划1条无碰最优路径，然后，在安全距离内发现其他机器人时，利用通信和协调策略实现机器人之间的避碰．

3.2 多机器人路径规划的步骤

多机器人路径规划的流程如图4所示，具体步骤如下：

1）初始化机器人的工作环境，多个机器人的起点Si，终点Gi，视野域半径radius，机器人的半径r，蚂蚁个数M，迭代次数k等；

2）不考虑其他机器人，根据改进的蚁群算法为机器人Ri规划1条全局无碰最优路径；

3）若Ri移动到目标点，输出全局无碰最优路径，退出；

4）传感器在视野域范围内是否探测到其他机器人Rj，否，转至7）；

5）碰撞预测，判断Ri和Rj之间是否会发生碰撞，否，转至7）；

6）路径协调策略；

7）沿局部无碰路径移动；

8）返回3）．

图4 多机器人路径规划流程图Fig.4 Flow chart of multi robot path planning

3.3 碰撞预测

机器人Ri在视野域范围内检测到机器人Rj，如图5所示，2个机器人进行通信，互相交换路径信息．如果路径有交叉点，定义Ri到交叉点的距离为L_Ri，Rj到交叉点的距离为L_Rj，若L_RiL_Rj＞2r，则各机器人按照原路径运动，否则执行局部避碰操作．

图5 碰撞预测Fig.5 Collision prediction

3.4 路径协调

由代价函数式 (12)可知，多机器人路径规划主要考虑路径长度、路径平滑度和暂停时间3个指标，本文采用暂停策略进行路径协调．

以机器人Ri为例，利用碰撞预测策略，探测到在某一时刻t机器人Ri和Rj发生碰撞，t 1时刻的协调避碰策略具体如下：

比较2个机器人的坐标值，x坐标大的机器人暂停一步，如果x坐标相等则比较y坐标，y坐标大的暂停一步．

4 仿真实验

为了验证改进蚁群算法的有效性，用Matlab进行了仿真，并将基本蚁群算法、文献 [9]中改进的蚁群算法和本文改进的蚁群算法进行了比较．设蚂蚁数量M=50，迭代次数．

4.2 仿真1

对单个机器人进行仿真，在环境和参数完全相同的情况下，对基本蚁群算法、文献 [9]中改进的蚁群算法和本文改进的蚁群算法进行比较，分别运行20次，得出平均结果．机器人的起点为S=1，终点G=400．图6、图7和图8分别各自的收敛曲线．

图6 基本蚁群算法收敛曲线Fig.6 Convergence curve of basic ant colony algorithm

图7 文献 [9]改进蚁群算法收敛曲线Fig.7 Convergence curve of literature[9]improved ant colony algorithm

图8 本文改进蚁群算法收敛曲线Fig.8 Convergence curve of this paper improved ant colony algorithm

表1为3种算法之间的比较，经过分析可以得出，改进后的蚁群算法路径更短、更平滑，且收敛速度较快，改进的蚁群算法优于基本蚁群算法和文献 [9]中的改进蚁群算法．

表1 3种算法性能比较Tab.1 Performance comparison of the three algorithms

4.2 仿真2

对3个机器人进行仿真，采用改进的蚁群算法分别为机器人规划路径，机器人Ri的起点栅格序号分别为（1,381,201），终点栅格序号分别为（400,20,115），图9、图10分别为文献 [9]中的改进蚁群算法和本文的改进蚁群算法为3个机器人规划出的路径．其中R1和R3，R2和R3的路径虽然有交点，但是经过计算不会在同一时刻到达交点，2种方法规划的路径中，R1和R2的交点坐标分别为（7.5,10.5）、（7.833 3,10.833 3），会发生碰撞，机器人R1在交点的前一节点暂停一步．

表2是3个机器人在环境和参数完全相同时，采用本文的改进蚁群算法和文献 [9]中的算法进行50次仿真实验的平均数据．可以看出，本文改进蚁群算法规划出的路径更短更平滑．

表2 本文算法和文献 [9]算法性能比较Tab.2 Performance comparison between algorithm in this paper and literature[9]algorithm

图9 文献 [9]算法多机器人规划路径示意图Fig.9 Multi-robotplanning path diagram of document[9]algorithm

图10 本文算法多机器人规划路径示意图Fig.10 Multi-robotplanning path diagram in this paper

5 结论

本文针对蚁群算法的缺点，对算法进行了改进．步长选择不再局限于1个栅格，从而缩短了路径的长度；在概率公式中加入拐点参数，改善了路径的平滑度；信息素更新时加入奖励惩罚机制，避免陷入局部最优．然后将改进的蚁群算法应用到3个机器人的路径规划问题中，成功避免了机器人之间的碰撞，到达最终目的地．仿真结果表明改进的蚁群算法的收敛性、路径长度和平滑度得到了较好的改善．

[1]朱庆保．全局未知环境下多机器人运动蚂蚁导航算法 [J]．软件学报，2006，17（9）：1890-1898．

[2]肖国宝，严宣辉．一种新型协作多机器人路径规划算法 [J]．计算机科学，2013，40（4）：217-220．

[3]高翔，苏青．基于双层模糊逻辑的多机器人路径规划与避碰 [J]．计算机技术与发展，2014，24（11）：79-82．

[4]夏小云，周育人．蚁群优化算法的理论研究进展 [J]．智能系统学报，2016，11（1）：27-36．

[5]DENG X，ZHANG L，LUO L．An improved ant colony optimization applied in robot path planning problem[J]．Journal of Computers，2013，8 （3）：585-593．

[6]TANG B W，ZHU Z X，FANG Q，et al．Path planning and replanning for intelligent robot based on improved ant colony algorithm[J]．Applied Mechanicsand Materials，2013，390：495-499．

[7]Wenbin C，Qingbao Z，Jun H．Path planning based on biphasic ant colony algorithm and fuzzy control in dynamic environment[C]//Intelligent Human-Machine Systems and Cybernetics（IHMSC），2010 2nd International Conference on．IEEE，2010，1：333-336．

[8]柳长安，鄢小虎，刘春阳，等．基于改进蚁群算法的移动机器人动态路径规划方法 [J]．电子学报，2011，39（5）：1220-1224．

[9]万晓凤，胡伟，方武义，等．基于改进蚁群算法的机器人路径规划研究 [J]．计算机工程与应用，2014，50（18）：63-66．

[责任编辑 田 丰]

Research on multi-robots path planning of robot based on improved ant colony algorithm

GU Junhua1,2，MENG Huijie1,2，XIA Hongmei2,3，DONG Yongfeng1,2

(1.School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China;2.Hebei Province Key Laboratory of Big Data Calculation,Tianjin 300401,China;3.Editorial Department of Journal of Hebei University of Technology, Hebei University of Technology,Tianjin 300401,China)

The basic ant colony algorithm has problems of slow convergence speed,inefficiency and easy to fall into local optimization in the process of robot path planning.Aiming at these problems,an improved ant colony algorithm is proposed. Multi-step path planning is realized by this proposed algorithm.In order to make the path smoother,the inflection point is added in the probability formula.This article proposed anew pheromone reward punishment mechanism.The improved ant colony algorithm is applied to the multi-robot path planning with three optimization goals.Collision prediction strategy and path coordination strategy is applied to solve the problem of coordination and obstacle avoidance between mobile robots.The simulation results show that the path planned by improved ant colony algorithm is shorter,smoother and more efficient,which verifies the effectiveness and feasibility of the proposed algorithm in multi robot path planning.

multi-robot;path planning;improved ant colony algorithm;multi-step;inflection point parameter; coordinated collision avoidance

TP242

A

1007-2373(2016)05-0028-07

10.14081/j.cnki.hgdxb.2016.05.005

2016-10-11

天津市应用基础与前沿技术研究计划（13JCQNJC00200，14JCYBJC18500）；河北省高等学校科学技术研究项目（ZD20131097）；河北省自然科学基金（F2015202311）

顾军华（1968-），男（汉族），教授．通讯作者：董永峰（1977-），男（汉族），副教授．