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

俞烨+贺乃宝+高倩+姚灵灵

摘 要：针对移动机器人路径规划中的不足，文中提出了一种改进蚁群算法的路径规划方法。算法中通过对距离启发因子、初始信息素分配策略、信息素更新规则以及全局信息素挥发因子进行改进，可有效避免陷入局部最优解并提高算法的收敛速度。实验证明，改进蚁群算法在避免局部最优以及寻找最优解能力方面具有良好的效果。

关键词：移动机器人；路径规划；蚁群算法；信息素更新

中图分类号：TP391.9 文献标识码：A 文章编号：2095-1302（2017）03-00-04

0 引 言

移动机器人路径规划是机器人学的一个重要研究领域，是指移动机器人在有障碍物的工作环境中，按照某一性能指标（如工作代价最小、行走时间最少、行走路线最短等）搜索一条从起始状态到目标状态的安全的、无碰的最优或次优路径。目前，常用于移动机器人路径规划的算法主要有人工势场法、A*算法、神经网络法、模糊推理法、遗传算法等。人工势场法存在局部最优点和障碍物附近目标不可达问题。A*算法虽然对比较简单的地图搜索速度非常快，也能找到最优路径，但全局性较差，启发函数选择不当容易陷入死循环。神经网络法虽然能收敛到最优路径，但环境改变后必须重新学习，在环境信息不完整或环境经常改变的情况下难以应用。模糊推理法虽然避开了其它算法中存在的对环境信息依赖性强等缺点，但适应能力比较差。遗传算法虽然具有鲁棒性强、全局优化等优点，但计算速度不快，容易提前收敛[1-3]。

蚁群算法是一种模拟进化算法，具有正反馈、自组织、分布式计算、较强的鲁棒性等优点，因此在众多优化问题中得到了广泛应用，尤其在机器人路径规划应用中成效显著[4-6]。文献[5]提出了一种融入遗传算子并利用交叉和变异操作来扩大搜索空间的改进蚁群算法；文献[6]提出根据目标点自适应调整启发函数来提高算法收敛速度的路径搜索方法；文献[7]提出一种蚂蚁落入陷阱回退策略和相遇策略的路径寻优策略；文献[8]提出一种改进信息素更新方式、引入最大最小蚁群系统以及改进状态转移规则的路径规划方法。

尽管上述方法都能在一定程度上找到问题的最优解或次优解，但在实际应用中也或多或少存在一定的缺陷，如所得路径虽然是最短路径，但存在个别不必要的尖峰，在一定程度上忽视了路径平滑性的要求，与实际情况也有一定出入。抑或所得路径虽然最短，但路径中转弯过多，机器人在实际运行过程中耗能较大，达不到能源节約的要求。为此，在传统蚁群算法的基础上，本文提出一种改进蚁群算法，可有效改善传统蚁群算法中的不足，并且通过实验取得了良好的效果。

1 环境建模

环境建模的目的是建立一个便于计算机编程模拟路径规划过程的地图模型。环境建模是机器人路径规划的首要环节，由于栅格法的地图创建和维护比较容易，而且简单明了，大大减小了建模的复杂性，因此本文采用栅格法对环境进行建模。

设机器人的工作空间为一个二维区域，该二维区域分布着许多大大小小的障碍物，这些障碍物的大小和位置已知，同时假定机器人路径规划过程中障碍物都静止。如图1所示，障碍物面积占据半个或半个栅格以上的，该栅格设定为黑色，标记为障碍栅格，反之设定为白色，标记为自由栅格。为了便于标记机器人的位置，将地图中的栅格按图1进行编码，按照从左到右、从上到下的顺序依次对栅格编号。

假设机器人外接圆直径为R，为保证机器人能够在栅格环境中无碰撞运动，取R作为栅格单元的边长。设工作环境是长为X，宽为Y的方形区域，从左上角开始将栅格区域划分为m行n列个边长为R的栅格[7]。

为提高机器人运动的灵活性和可靠性，我们对机器人作如下约定：

（1）机器人的中心位置用质点表示，同时对障碍物的尺寸按机器人的半径作适当扩展，以保证机器人能够无碰撞地运动。

（2）机器人每次运动只能从一个栅格的中心位置移动到另一个栅格的中心位置，且只能位于自由栅格内部；

（3）机器人的下一位置只能是与当前位置相邻的八个栅格的自由栅格中；

（4）为避免没必要的局部最优，某一栅格的上下左右栅格中有三个是障碍栅格，此栅格就默认为障碍栅格，如图1所示的38号栅格，这样机器人就不会走该无效栅格了。

基于以上约定，栅格中心坐标和该栅格序号N之间有如下关系：

式中，mod表示取余操作，int表示取整操作[8]。

2 蚁群算法基本原理

蚁群算法是由意大利学者M.Dorigo等人于20世纪90年代初提出的一种新模拟进化算法，真实地模拟了自然界蚂蚁群体的觅食行为。该算法最初成功应用于解决著名的旅行商问题，并取得了较好的结果。蚁群算法的基本原理如下：蚂蚁k（k=1，2，...，m）根据各条路径上的信息素浓度来决定它下一步转移的方向，设Pkij（t）表示t时刻蚂蚁k从节点i转移到节点j的概率，计算公式如下：

式中， τij（t）为t时刻节点i与节点j连接路径上的信息素浓度； ηij（t）为启发函数，ηij（t）=1/dij表示蚂蚁k从节点i转移到节点j的期望程度；allowk（k=1，2，...，m）为蚂蚁k待访问节点的集合，蚂蚁刚开始寻优时，allowk中有（n-1）个元素，即包含除蚂蚁k出发节点的其他所有节点，随着蚂蚁寻优的进行，allowk中的元素不断减少，直至访问到目标节点。α为信息素重要程度因子，其值越大，表示信息素的浓度在转移中起的作用越大；β为启发函数重要程度因子，其值越大，表示启发函数在转移中的作用越大，其状态转移概率越接近贪心规则。

此外，在蚂蚁释放信息素的同时，各条路径上的信息素也会逐渐消失，设参数ρ（0<ρ<1）表示信息素的挥发程度。因此，当所有蚂蚁完成一次循环后，各个节点连接路径上的信息素浓度需要实时更新，即

式中，Δτkij表示第k只蚂蚁在节点i与节点j连接路径上释放的信息素浓度；Δτij表示所有蚂蚁在节点i与节点j连接路径上释放的信息素浓度之和。其中，Δτij按下式进行更新：

式中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；Lk为第k只蚂蚁经过路径的长度[9，10]。

3 改进的蚁群算法

3.1 距离启发因子的改进

在传统蚁群算法中，距离启发因子ηij=1/dij，采用此启发公式全局性不强，只考虑到下一步要选择距离最近的节点，往往会因为贪图这一小步而选择了偏离目标节点的方向，从而形成局部最优解或无效解。因此，本文从全局出发，增加目标节点对下一节点的影响，改进公式如下：

式中，dis（i，j）表示节点i到节点j的距离，dis（j，E）表示节点j到目标节点E的距离，w是一个参数，w∈（0，5），参数w的选择决定了蚂蚁更倾向于选择距离目标节点更近的节点。因此，概率公式改进为：

通过对距离启发因子的改进，蚂蚁在寻优时可以同时兼顾本节点到下一节点的距离以及下一节点到目标节点的距离，并且更加倾向于选择距离目标节点更近的节点，使得蚂蚁在寻优时全局性更强，更好地避免了局部最优。

3.2 初始信息素分配策略

在传统蚁群算法中，将每条路径信息素浓度初始化为一个常数，这就为蚂蚁初期寻优带来极大的隐患，导致初期搜索过慢，效率低下。因此，本文做出如下改进：适当加大起点与终点连线附近区域的信息素浓度，减小与起点和终点连线相对的两个对角区域的信息素浓度。因为往往最优路径就在起点与终点连线的附近区域形成，而其对角区域形成的基本不会是最优路径。这样的初始信息素浓度分配为蚂蚁初期搜索提供了导向，提高了蚂蚁初期的搜索效率。

3.3 信息素更新方式的改进

蚂蚁在搜寻最优路径时依靠最重要的一个因素就是信息素浓度，因此信息素浓度的更新方式对搜索效率以及最优解的好坏显得极为重要。

蚂蚁每移动一次称为一次搜索，经过n次搜索后，所有蚂蚁就完成了一次迭代。当蚂蚁每完成一次搜索，就对其走过路径上的信息素进行局部更新，更新公式如下：

当所有蚂蚁完成一次迭代后，对接近当前最优路径的部分较优路径进行信息素加强，对远离当前较优路径的较差路径进行信息素减弱，全局更新公式如下：

通过局部和全局信息素更新，蚂蚁能够对最优路径搜索更有导向性的同时又能探索未走过的路径，使得蚂蚁避免局部最优的同时又能提高寻优效率。

3.4 信息素揮发因子的改进

在传统蚁群算法中，全局信息素挥发因子ρ是一个常数，可能导致算法陷入局部最优解，影响算法的性能。因此，本文对其做出改进，使其全局信息素挥发因子ρ随时间服从正态分布，即在搜索初期和末期，信息素挥发因子较小，信息素浓度也相对较高。在这期间，路径搜索相对单一，路径之间差别较小，信息素给予蚂蚁的导向性较强，使得蚂蚁沿着信息素浓度较高的路径搜索，没必要去探寻一些较差路径；而在搜索中期，信息素挥发因子较大，信息素浓度相对较低，信息素给予蚂蚁的导向性相对较弱，使得蚂蚁有较多的概率去搜索其他未走过的路径，避免局部最优。

3.5 算法步骤

用于移动机器人路径规划的改进蚁群算法步骤如下：

（1）环境建模。对环境进行栅格坐标建模，黑色代表障碍栅格，白色代表自由栅格，机器人能在自由栅格中任意行走；

（2）初始信息素分配。初始信息素按照起点与终点连线附近区域浓度较大，起点和终点连线相对两个对角区域的信息素浓度较小的原则进行分配；

（3）初始化各参数。对信息素重要程度因子α、启发函数重要程度因子β、局部信息素挥发因子ε、最大迭代次数Nmax等参数进行初始化，全局信息素挥发因子ρ随时间服从正态分布；

（4）所有蚂蚁置于起始点，准备搜索；

（5）选择下一节点。根据概率公式（6）选择所要行走的下一节点；

（6）局部信息素更新。当所有蚂蚁都完成一次搜索后，根据式（7）进行局部信息素更新；

（7）判断所有蚂蚁是否都完成一次迭代，若完成，转（8），否则转（5）；

（8）全局信息素更新。当所有蚂蚁都完成一次从起点到终点的搜索，则按式（8）进行全局信息素更新，输出本次最优路径；

（9）判断是否达到最大迭代次数，若达到，转（10），否则转（4）；

（10）寻优结束，输出最优路径。

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

4 仿真

为了验证上述改进蚁群算法的有效性及可行性，采用20×20栅格环境下的机器人路径规划问题进行验证，在Matlab2010b环境下进行编程仿真。如图1所示，机器人的起始点坐标为（0.5，19.5），目标点坐标为（19.5，0.5），障碍物覆盖率为27%，算法中出现的参数设置：α=1，β=6，ε=0.4，Nmax=200，m=32，参数w取0.35，常数δ取3.2。

分别采用传统蚁群算法和改进蚁群算法在Matlab环境下进行编程仿真，其仿真结果对比见表1所列。

通过表1的数据不难看出，改进蚁群算法最短路径、迭代次数以及运行时间方面都优于传统蚁群算法和文献[7]所提蚁群算法，尤其在迭代次数和运行时间这两个重要参数上优势明显，有效提高了算法的收敛速度和效率。传统蚁群算法、文献[7]所提蚁群算法以及本文算法搜索到的最优路径对比如图3、图4和图5所示。

从以上最优路径对比可知，传统蚁群算法在搜索初期陷入了局部最优，虽然最终也找到了一条最优路径，但路径质量不如改进蚁群算法；文献[7]所提蚁群算法虽然寻找到的最优路径较传统蚁群算法短，但还是在一定程度上陷入了局部最优；而改进蚁群算法最优路径明显优于传统蚁群算法。

为了更好地验证并改进蚁群算法在收敛速度和最短路径上的优势，本文给出各代路线的平均距离和最短距离的对比曲线，分别如图6、图7和图8所示。

从以上三图可以看出，传统蚁群算法要迭代61次左右才能收敛到最优解，文献[7]所提蚁群算法也要迭代43次左右才能收敛到最优解，而改进蚁群算法只要迭代23次左右就能收敛到最优解，收敛速度明显提高，且最短路径相比传统蚁群算法和文献[7]所提蚁群算法都较优。仿真结果证明，本文所提的改进蚁群算法具有较明显的有效性和可行性。

5 结 语

本文提出了一种改进蚁群算法的移动机器人路径规划方法，通过对距离启发因子、初始信息素分配策略、信息素更新规则以及全局信息素挥发因子的改进，有效避免了算法陷入局部最优解的同时又提高了算法的收敛速度。最后通过仿真实验验证了算法的有效性及可行性，在对比传统蚁群算法的情况下，改进蚁群算法在寻找最优解的能力及效率上明显优于传统蚁群算法。

参考文献

[1]宋红生，王东署.基于改进蚁群算法的移动机器人路径规划[J].机床与液压，2012，40（20）：120-125.

[2]万晓凤，胡伟，郑博嘉，等.基于改进蚁群算法与Morphin算法的机器人路径规划方法[J].科技导报，2015，33（3）：84-89.

[3]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.

[4]徐利超，张世武.基于改进蚁群算法的障碍环境下路径规划研究[J].智能工程，2013（7）：61-64.

[5]潘杰.基于改进蚁群算法的移动机器人路径规划[J].中国矿业大学学报，2012，41（1）：108-113.

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

[7]尉朝闻，黎田.机器人路径规划的一种改进蚁群算法[J].科技信息，2010（35）：107-108.

[8]赵开新，魏勇，王東署.改进蚁群算法在移动机器人路径规划中的研究[J].计算机测量与控制，2014，22（11）：67-70.

[9]何娟，涂中英，牛玉刚.一种遗传蚁群算法的机器人路径规划方法[J].计算机仿真，2010，27（3）：170-174.

[10]裴振兵，陈雪波.改进蚁群算法及其在机器人避障中的应用[J].智能系统学报，2015，10（1）：90-96.

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