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

侯欣蕾+于莲芝

摘要：针对蚁群算法进行机器人路径规划时存在搜索空间大、效率低、容易陷入局部最优解、易出现死锁现象等问题，提出了一种改进的蚁群算法。在蚁群算法基础上，只对较优蚂蚁路径进行信息素浓度更新；针对U型障碍物，提出了蚂蚁回退策略，以及一些仿真实验策略改进。仿真结果表明：改进后蚁群算法能快速搜索到最优路径，有效避免死锁现象，与其它算法相比，具有良好的路径寻优能力与避障性能。

关键词：移动机器人；路径规划；改进蚁群算法

DOIDOI：10.11907/rjdk.172054

中图分类号：TP319

文献标识码：A 文章编号：1672-7800（2017）012-0162-03

Abstract：When the ant colony algorithm（ACA） is used in mobile robot path planning， there are many problems such as large search space、inefficiency、easy to fail into locale optima、prove to deadlock and so on， an improved ant colony algorithm for robot path planning. At first， on the basic of ACA， phenomenon concentrations are updates only for the ant paths； Then the ant back off strategy is put forward for the U type obstacle； last some improvements in simulation experiments. Experiments proof： the improved ACA can fast search to optimal path and it can effectively avoided the deadlock phenomenon， compared with others algorithm， it has good route optimization ability and obstacle avoidance performance.

Key Words：mobile robot； path planning； an improved ant colony algorithm

0 引言

移动机器人研究包括路径规划、导航定位、路径跟踪与运动控制等技术，其中路径规划是机器人研究领域基础与核心。国内外学者提出了栅格法、人工势场法等路径规划方法[1-2]。栅格法一般用于机器人全局路径规划，但随着机器人工作环境复杂程度不断提高，栅格存储空间需求也会增大，从而降低搜索效率。人工势场法通常应用于机器人局部路径规划，但也存在致命缺陷：局部极小点、目标不可达。随着神经网络、遗传算法、模糊控制等智能算法的提出与发展，许多学者将人工智能算法应用于路径规划，虽然可以提高求解速度，但存在算法复杂、搜索空间大等问题[3]。如何高效解决复杂环境下机器人路径规划问题依然是研究热点。

受大自然中蚂蚁觅食行为启发，Marco Dorigo于1992年在博士论文中首次提出了蚁群算法。因为机器人路径规划类似蚂蚁觅食行为，所以可使用蚁群算法进行机器人路径规划。使用蚁群算法进行路径规划，存在搜索时间长、局部最优解与死锁现象[4]。因此，本文主要研究改进蚁群算法在机器人路径规划中的应用。

1 环境建模

机器人工作环境通过分形算法可以等效为二维平面的有限区域AS。鉴于AS可以为任意形状，因此，在机器人环境建模时，需要在AS边界向外补充障碍物栅格，使机器人工作环境补充为正方形或长方形[5]。使用栅格法划分机器人工作环境AS，划分栅格分为3种：白色栅格、黑色栅格、混合栅格。如图1所示，白色栅格表示自由栅格，黑色栅格与混合栅格表示障碍物栅格，机器人可在自由栅格之间移动，且障碍物位置与大小均不发生改变。在建立的栅格空间上，按照从左到右，从上到下顺序，依次为栅格标号，记为数字1，2，3，…，n，每一个数字都代表一个栅格；以栅格空间左下方为坐标原点，从左到右为X轴正方向，从下到上为Y轴正方向，栅格长度为单位长度，建立平面直角坐标系XOY。栅格序号与栅格坐标对应关系如下：

机器人路径规划过程中，为避免机器人与障碍物发生碰撞，对障碍物边界进行膨化处理，向外扩展机器人最大长度1/2，则机器人可以等效為质点，其大小与尺寸忽略不计。上述方式划分机器人工作空间能够使环境模型与真实情况相符，使机器人路径规划畅通无阻。机器人路径规划起始位置与终止位置为任意栅格且都属于AS（不在同一个栅格内且不是障碍栅格）。

2.1.3 迭代循环

完成每轮信息素更新后，将全部蚂蚁放到机器人路径规划起始点，重新开始新一轮路径规划，N次迭代完成后，从中选出一条最优路径。

2.2 蚁群算法改进

对机器人进行路径规划时，使用蚁群算法可规划出一条从起始点到终止点安全、无碰撞的最优路径，但也存在搜索时间过长、效率低、易出现死锁等现象[4，8]。针对上述问题，本文对蚁群算法作出以下改进，使机器人能够在更短时间内搜索出更短更平滑的路径。

2.2.1 蚂蚁回退策略

使用蚁群算法进行机器人路径规划过程中，蚂蚁k遇到U型障碍物时，容易陷入死锁现象，导致蚁群算法停滞。一旦出现此类情况，假设此时定义蚂蚁k死亡，就会影响到算法鲁棒性与适应度。因此，本文采用蚂蚁回退策略来杜绝这类现象发生。蚂蚁移动过程中遇到U型障碍物时，首先判断蚂蚁是否落入陷阱，如果落入陷阱，则蚂蚁回退到上一节点，同时将蚂蚁所在节点从禁忌表中移除，按照状态转移概率公式继续选择下一转移节点，然后判断是否陷入陷阱，直至蚂蚁回退到逃出陷阱为止。endprint

在蚁群算法中加入蚂蚁回退策略可保证所有蚂蚁都能顺利完成路径搜索，即使蚂蚁遇到U型障碍物也不会死亡，进一步保障了算法鲁棒性与适应度，提升算法性能。

2.2.2 较优蚂蚁路径信息素更新

假设在每轮路径搜索结束后，只对较优蚂蚁路径进行信息素更新，而其余路径信息素则会因信息素挥发逐渐降低，将增大路径上信息素差异，使蚂蚁在搜索路径过程中更倾向于信息素浓度较大路径，蚂蚁能够较快集中在较优路径邻域，缩短算法求解时间，提高算法效率。

使用蚁群算法进行路径规划时，由于路徑规划起始位置与终止位置已知，且蚂蚁同时从起始位置出发进行路径搜索，所以能够在较短时间内能找到终止位置的蚂蚁就是较优蚂蚁，反之则为较差蚂蚁。因此，在算法实现中，须找到前面几只蚂蚁的路径，对其进行信息素更新，加大较优路径与较差路径信息素浓度差异，使蚂蚁在选择路径时更加倾向于较优路径，大大地降低路径搜索时间，提高机器人路径规划搜索效率。

2.2.3 仿真策略改进

使用改进后蚁群算法进行机器人路径规划，采取以下策略：

（1）限制蚂蚁下一步栅格选择范围。路径搜索过程中，蚂蚁移动到当前栅格时，下一步可选择栅格只能是与当前栅格相邻且没有访问过的无障碍物栅格。

（2）使用“轮盘赌”方法选择下一栅格。通过“轮盘赌”方法结合状态转移概率公式，增大蚂蚁选择随机性，提高蚂蚁全局搜索能力，可有效防止算法过早收敛。

（3）校正搜索成功的蚂蚁路径。蚂蚁在栅格之间移动可能会走弯曲路径，通过对弯曲路径的处理，可以进一步缩短搜索路径总长度，使搜索路径达到最优。

2.3 改进后蚁群算法流程

改进后蚁群算法流程如图2所示。

3 实验结果

将机器人工作空间划分为20×20栅格，起始位置为（1，1），终止位置为（20，20）。算法参数设置：蚂蚁数目m=50；迭代次数N=100；信息素挥发系数=0.3。

本文使用改进蚁群算法进行路径规划，搜索得到最优路径如图3所示，最短路径收敛速度如图4所示。

本文比较了A*算法、蚁群算法、改进蚁群算法性能，结果如表1所示。

由表1可知，改进蚁群算法可快速搜索到最优路径，有效避免死锁现象，具有良好路径寻优能力与避障性能。

4 结语

本文针对机器人路径规划中存在问题，改进了蚁群算法，只对路径较优蚂蚁进行信息素更新，大量减少信息素更新计算量，在一定程度上提高算法收敛速度；校正搜索成功的蚂蚁路径，拉直蚂蚁在相邻栅格之间多走的弯曲路径，缩短搜索路径长度；处理U型障碍物，提出了蚂蚁回退策略，避免陷入局部最优解与死锁现象。大量仿真实验证明，改进后蚁群算法能够快速搜索到最优路径，有效避免死锁现象，与其它算法相比，具有良好路径寻优能力与避障性能。

参考文献：

[1] 欧阳鑫玉，杨曙光.基于势场栅格法的移动机器人避障路径规划[J].控制工程，2014（1）：134-137.

[2] 温素芳，郭光耀.基于改进人工势场法的移动机器人路径规划[J].计算机工程与设计，2015（10）：226-230.

[3] 朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010（7）：4-10.

[4] 周明秀，程科，汪正霞.动态路径规划中的改进蚁群算法[J].计算机科学，2013（1）：320-322.

[5] 罗荣贵，屠大维.栅格法视觉传感集成及机器人实时避障[J].计算机工程与应用，2011（24）：237-239.

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

[7] 康冰，王曦辉，刘富.基于改进蚁群算法的搜索机器人路径规划[J].吉林大学学报，2014（4）：167-173.

[8] XIONG W， WEI P.A kind of ant colony algorithm for function optimization[C].Proceeding of the 1st International Conference on Machine Learning and Cybernetics，2002：552-555.

（责任编辑：何 丽）endprint