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

朱颢东，孙 振，吴 迪，申 圳

(郑州轻工业学院 计算机与通信工程学院 河南 郑州 450002)

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

朱颢东，孙 振，吴 迪，申 圳

(郑州轻工业学院 计算机与通信工程学院 河南 郑州 450002)

针对蚁群算法应用于移动机器人路径规划时存在易于陷入局部最优解、收敛速度慢的问题，提出了一种适用于静态障碍环境下基于改进蚁群算法的移动机器人路径规划方法。该方法改进了节点间的状态转移规则，增加了得到最优路径的概率；自适应调整启发函数，提高了算法的搜索效率；基于狼群法则对信息素进行更新，有效避免了算法陷入局部最优解；动态调整了衰减系数，在后期增加了蚂蚁对最优路径的选择概率，加快了算法的收敛速度。仿真实验表明，与其他算法在相同环境下比较，该改进算法在路径规划结果相同的情况下具有较快的收敛速度；且改进算法在不同复杂程度环境中均得到了最优路径，也表明了该算法的有效性和可靠性。该算法具有良好的寻优能力，可以适用于不同复杂环境中的移动机器人路径规划。

移动机器人；蚁群算法；路径规划

0 引 言

移动机器人路径规划是近年来机器人研究领域的重要分支和研究热点之一。移动机器人路径规划是指移动机器人在有障碍物的环境中，找到一条从起始点到目的点最优的无碰路径[1-2]。路径规划问题具有复杂性、多约束性和多目标性等特点。传统的路径规划算法有Dijkstra，A*算法等，Dijkstra是一种经典的最短路径搜索算法，它是一种贪心算法，虽然能很好地规划出路径，但是由于该算法是以起始点向外层层扩展，直到搜索到目的节点为止，需要遍历节点，计算复杂度高，效率比较低；A*算法是一种启发式算法，它是通过估价函数来确定当前点到目标点的距离和搜索方向，在复杂的环境中一个不理想的估计函数容易导致搜索不到路径或者规划路径效果不理想。近年来，在移动机器人路径规划方法中，国内外专家学者提出了许多仿生智能优化算法[3]，如：遗传[4]、人工鱼群[5]、蛙跳[6]、神经网络[7]以及蚁群[8]等算法。

1992年，Marco Dorigo在博士论文中提出了蚁群算法，通过观察蚂蚁寻找食物源时发现路径的行为而获得启发。传统的蚁群算法主要是解决旅行商问题(travelling salesman problem，TSP)，文献[9]借鉴最大-最小蚁群系统的方法，限制了信息素的值域范围，有效地避免了算法陷入局部最优解问题。文献[10]构建了权重可调的引力概率函数，并且把它作为启发因子，有效地提高了算法的收敛速度。文献[11]改进了算法的信息素更新规则，并加入拐点作为评价路径质量的参数之一，提高了算法的效率。文献[12] 分析了影响蚁群优化中的关键参数，自适应地设置了算法参数，调高了算法的精度和效率。文献[13]提出了一种基于人工势场法的移动机器人路径规划方法，定义了一种新的引力函数，有效地提高了路径规划的性能。文献[14]提出了自适应调整启发函数、路径平滑策略，有效地提高了路径的质量。目前，不少算法在求解机器人全局路径问题中存在着局限性，遗传算法由于运算进化代数众多，规划路径时占用大量的存储空间，导致运算速度较慢。人工鱼群算法虽然具有较快的收敛速度，但是很难得到精确的解，规划出的路径质量不理想；混合蛙跳算法易于陷入局部最优解，求解精度较低，而且收敛速度较慢，限制了该算法在路径规划领域的应用；神经网络算法虽然具有较强的学习能力，但是当机器人在复杂的环境中，很难用数学公式来描述。人工势场法是以其数学计算上的简单明了而被广泛应用到路径规划中，但是，人工势场法存在局部极小点和目标不可达等问题。而蚁群算法是一种模拟进化算法，具有自组织性、较强的鲁棒性、分布式计算、寻优能力强、易于和其他算法相结合等优点，非常适合应用到移动机器人路径规划问题。

因此，论文提出利用改进蚁群算法规划移动机器人路径，并提出了动态调整挥发系数、自适应调整启发函数等策略，能够在不同复杂程度的环境中得到全局最优路径，提高了算法的搜索速率，并加快了算法的收敛速度，通过在Matlab软件中仿真实验，表明了该算法是有效和可行的。

1 问题描述与建模

机器人路径规划中重要的问题之一是环境建模。建模就是根据已知机器人周围的环境信息，通过提取和分析，将现实中物理空间转换为机器人可以理解的空间，通过建立良好的环境模型，有效地减少了路径搜索过程中的麻烦。论文中主要用栅格法对机器人的二维环境进行划分，从左到右，从上到下对栅格进行编号，论文中以10×10的栅格环境为例来说明，如图1所示。

图1 栅格坐标与序号关系Fig.1 Grid coordinate relates with serial number

图1中，坐标原点0在左下方，水平从左向右为x轴正方向，垂直从下到上为y轴正方向，栅格的大小由移动机器人自身的大小和它运动步长决定，为了简化计算路径的长度，一个栅格的边长为机器人的运动步长，即一个单位长度。序号与坐标的对应关系如下

(1)

(1)式中：Ni表示栅格的序号；N表示每一列的栅格数量；mod表示取余数；ceil表示向后取整数。

为了建立机器人可以理解的环境，根据环境地图建立相应的矩阵来表示每个栅格的状态(可行栅格和障碍栅格)，在下面矩阵中，0代表可行栅格；1代表障碍栅格，每一个障碍可能占用一个或多个栅格，若障碍物占用不足一个栅格，视为占用一个完整栅格；机器人被视为一个点状机器人；将障碍物以机器人半径的大小进行膨化，确保机器人可以安全地通过障碍物边界。10×10的棚格环境可用矩阵表示为

(2)

2 基于改进蚁群算法的路径规化

研究表明蚂蚁会在经过的路径上会留下信息素，并且可以在一定范围内感知信息素进而引导自己的运动，因此，蚁群会表现出一种正反馈现象：越多的蚂蚁经过一条路径，就会在这条路径上释放越多的信息素，后面的蚂蚁选择这条路径的概率就越大，蚂蚁之间就是通过这种信息素的交流来选择路径，进而找到食物源[3]。蚁群算法具有局部寻优能力强、自组织性等优点，能很好地应用到路径规划中，但传统蚁群算法存在容易陷入局部最优解、收敛速度慢等问题，为了提高蚁群算法的搜索效率和路径规划质量，论文对传统蚁群算法做了以下改进。

2.1 改进节点状态转移规则

蚂蚁会根据启发函数η和路径上的信息素浓度τ来选择下一步的可行节点，设定蚂蚁的种群数量为m，假设当前蚂蚁k在节点i处，比较q和q0的大小，按照(3)式的概率进行选择下一步可行节点j。

(3)

(4)

2.2 自适应调整启发函数

在传统的蚁群算法中，启发函数η是2个节点之间距离的倒数。A*算法是一种启发式算法，表示为f(n)=g(n)+h(n)，其中，g(n) 表示从初始节点到当前节点的实际代价；h(n) 表示当前节点到目的节点的估计代价，在g值一定的情况下，h值越小，f值就越小，能保证最短路经的搜索向着目标点方向进行。由启发式A*算法获得启发，下一可行节点j和目标点之间的距离可用于启发函数ηij，即dij和djt被用于启发函数上，即为

(5)

(5)式中：dij是当前节点i和可行节点j间的欧氏距离；djt是可行节点j和目的节点t间的欧式距离，把目的节点引用到启发函数中，加强了路径搜索的方向性，减少了算法的搜索空间，有效提高搜索的效率。但是过早的引入方向性启发信息，使得初始的搜索空间太小从而导致算法容易陷入局部最优解；在初始阶段引进起始节点S和当前节点i之间的距离dsi，作为衡量搜索空间大小的标准，随着后期扩大搜索空间后，方向启发信息将会被引进。启发函数为

(6)

(6)式中：dst是起始节点和目的节点的欧式距离；阀值ε是一个常数，由dst的长度具体决定。

2.3 改进信息素更新方式

在传统的蚁群算法中，最差蚂蚁的信息素经过正反馈之后可能导致算法搜索陷入局部最优解，为了避免这个问题，论文借用狼群法则对信息素进行更新，在一次循环中，找到经过局部最优的路径和局部最差路径的蚂蚁，分别增加和减少释放信息素浓度的量[3]，各条路径按照(6)-(8)式进行信息素浓度更新。

(7)

(8)

(9)

2.4 动态调整衰减系数

在全局路径规划中信息素的衰减系数ρ起到重要作用，当环境复杂时，一个比较大的衰减系数会增加信息素的正反馈，减少搜索空间以至于降低了找到最优路径的可能性；一个比较小的衰减系数会增加搜索时间。随着时间和迭代次数的增加，传统蚁群算法容易陷入局部最优解，为了避免这个问题，减少算法搜索时间并且能够保证找到最优路径，论文提出动态地设置衰减系数，表示为

(9)

3 算法流程

步骤1初始化参数。生成已知环境中的障碍物栅格地图，设置栅格的序号。设定种群个数m，起始点S，目的点T，蚁群最大迭代次数Nmax，栅格的行数M和列数N，设置信息素的影响权值α和启发式信息影响权值β。

步骤2所有蚂蚁进行路径选择。将m只蚂蚁放到起始点，蚂蚁k(k=1,2,3,…,m)从起始点S出发，并将起始点添加到禁忌表tabuk中，按照(3)式寻找下一个可行节点j，若j∈allowedk，选择下一个栅格j，并将当前节点j添加到禁忌表tabuk中。

步骤3判断蚂蚁是否到达目的点T。若蚂蚁到达目的点T，则记录蚂蚁走过的栅格序号和长度，若没有到达目的点T，则继续搜索下一节点，直到找到目的点T为止。若某个蚂蚁k陷入停滞，则剔除蚂蚁k。如果本代中所有蚂蚁都搜索完毕，转到步骤4。

步骤4更新信息素。计算本代中所有蚂蚁得到的可行路径的长度，找出本次循环中到达目的节点的局部最优和最差蚂蚁，按照(6)式对每个栅格进行信息素更新。

步骤5判断是否达到最大的迭代次数Nmax。若算法达到最大迭代次数，则输出当前群体中最短的路径的长度，否则，清空禁忌表tabuk，令N=N+1，转到步骤2，继续搜索，直到达到最大的迭代次数Nmax，算法结束，输当前群体中最短路径的长度。

4 算法仿真

使用Matlab软件对改进蚁群算法进行了仿真实验，比较了仿真结果，并对仿真结果进行了分析。

1)用论文提出的算法和文献[11]所提出的算法进行比较，在文献[11]中的栅格环境(20×20)进行仿真实验，设置相同的蚁群数量100，通过仿真实验，文献[11]和本文改进算法中路径规划图分别如图2、图4所示，文献[11]和本文算法迭代图分别如图3、图5所示。

图2 文献[11]中最优路径规划结果Fig.2 Result of optimal path planning in reference[11]

由于论文中将目标节点引用到启发函数，以加强算法搜索的方向性，减少了搜索空间，有效提高了算法的搜索效率；自适应地调整了衰减系数，随着迭代次数的增加衰减系数而增加，直到达到最大值，前期一个较小的衰减系数可以增加搜索空间，以便找到最优解；后期一个较大的衰减系数增加了信息素的正反馈，使得在后期越来越多的蚂蚁倾向于经过最优路径，可以有效地避免算法陷入局部最优解，同时使得算法更快的收敛于全局最优解，提高了算法搜索效率和收敛速度。因此，从以上仿真结果可以看出，在相同的复杂程度(20×20)和相同障碍物情况下，论文提出的算法和文献[11]中提出的算法规划最优路径长度相等，质量(具有相同拐点)相同，但是算法收敛速度略高于文献[11]，表明本文提出的算法具有一定的优越性。

图3 文献[11]中算法迭代曲线Fig.3 Iterative curve of algorithm in literature[11]

图4 本文改进蚁群算法最优路径规划结果Fig.4 Result of optimal path planning based on improved algorithm in the paper

图5 本文改进蚁群算法迭代曲线Fig.5 Iterative curve of improved algorithm in the paper

2)在不同复杂程度的静态环境中仿真实验，实验数据分别设置为种群数量m=50，最大迭代次数为100，ρmin=0.1，ρmax=0.5，α=1.1，β=7。实验结果如下。

①在10×10栅格环境中进行仿真试验，路径规划结果如图6所示，路径长度为13.90，算法迭代如图7所示。

图6 10×10栅格环境中路径规划结果Fig.6 Result of path planning in the 10×10 environment

图7 10×10栅格环境中改进算法迭代曲线Fig.7 Iterative curve of improved algorithm in the 10×10 environment

②在20×20的栅格环境进行仿真试验，路径规划结果如图8所示，路径长度为29.21，算法迭代如图9所示。

图8 20×20栅格中环境路径规划结果Fig.8 Result of path planning in the 20×20 environment

图9 20×20栅格环境中改进算法迭代曲线Fig.9 Iterative curve of improved algorithm in the 20×20 environment

③在30×30的栅格环境进行仿真试验，路径规划结果如图10所示，路径长度为43.36，算法迭代如图11所示。

图10 30×30栅格环境中路径规划结果Fig.10 Result of path planning in the 30×30 environment

通过在不同的静态栅格环境(从简单到复杂的栅格环境)中进行多个仿真试验，表明算法不仅在简单的环境中可以规划出最优路径，而且在复杂的环境中也可以规划出最优路径，并且算法迭代次数较少，收敛速度较快，即该算法在路径规划中适用于不同复杂程度的环境，具有可行性和有效性。

图11 30×30栅格环境中改进算法迭代曲线Fig.11 Iterative curve of improved algorithm in the 30×30 environment

5 结束语

传统蚁群算法在移动机器人路径规划问题中存在收敛速度慢、易陷入局部最优解、路径效果不理想等问题。针对这些问题，论文对节点间的状态转移规则、启发函数的自适应调整、信息素更新方式、衰减系数的动态调整进行改进，通过在相同的环境中和文献[11]中的算法比较，在得到路径质量相同的情况下，论文提出的算法可以通过较少的迭代次数找到最优路径和较快的收敛速度；通过在不同复杂程度的环境中进行多个仿真实验，该算法都能规划出理想的路径，表明了该算法的可行性和有效性。通过对比试验和试验仿真，表明了论文提出的算法具有一定的优越性。论文中主要是针对移动机器人在静态环境中全局路径规划，没有考虑到存在有限个动态障碍物的情况，这也是论文的不足之处及后续的研究重点。

[1] 李成兵,郭瑞雪,李敏.改进蚁群算法在旅行商问题中的应用[J].计算机应用,2014,34(S1):131-132. LI Chengbing, GUO Ruixue,LI Min. Application of improved ant colony algorithm in travelling salesman problem[J]. Journal of Computer Applications,2014, 34(S1):131-132.

[2] 张琦,马家辰,谢伟,等. 基于改进蚁群算法的移动机器人路径规划[J].东北大学学报:自然科学版,2013,34(11):1521-1524. ZHANG Qi, MA Jiachen, XIE Wei, et al. Improved Ant Colony Algorithm-Based Path Planning for Mobile Robot[J]. Journal of Northeastern University: Natural Science, 2013, 34(11):1521-1524.

[3] RAJA P, PUGAZHENTHI S. Optimal path planning of mobile robots: A review [J]. International Journal of Physical Sciences,2012,7(9): 1314-1320.

[4] 潘桂彬,潘丰,刘国栋.基于改进混合蛙跳算法的移动机器人路径规划[J].计算机应用,2014,34(10)：2850-2853. PAN Guifeng, PAN Feng, LIU Guodong. Path planning for mobile robots based on improved shuffled frog leaping algorithm[J]. Journal of Computer Applications, 2014,34(10)：2850-2853.

[5] 段俊花,李孝安. 基于改进遗传算法的机器人路径规划[J]. 微电子学与计算机,2005,22(1):70-72. DUAN Junhua, LI Xianan. Robot Path Planning Based on Improved Genetic Algorithm[J]. Microelectronics & Computer,2005, 22(1):70-72.

[6] 聂黎明,周永权. 基于人工鱼群算法的 机器人路径规划[J].计算机工程与应用,2008,44(32):48-50. NIE Liming, ZHOU Yongquan. Path planning of robot based on artificial fish-swarm algorithm[J].Computer Engineering and Applications, 2008,44(32):48-50.

[7] 王爱民,史庆国,吕晨亮.机器人路径规划的神经网络算法及优化[J].河北工业大学学报.1999,28(6):13-16. WANG Aimin, SHI Qingguo, LV Chenliang. Path Planning and Optimizing Algorithm of Robot Based on Neural Network[J]. Journal of Hebei University of Technology. 1999,28(6):13-16.

[8] 柳长安, 鄢小虎, 刘春阳,等，基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5)：1220-1223. LIU Changan,YAN Xiaohu,LIU Chunyang, et al. Dynamic Path Planning for Mobile Robot Based on Improved Ant Colony Optimization Algorithm[J]. Acta Electronica Sinica, 2011,39(5)：1220-1223.

[9] 张毅,高永琪,牛兴江. 一种改进蚁群优化算法的仿真研究[J].武汉理工大学报:交通科学与工程版,2013,37(6)：1330-1332. ZHANG Yi, GAO Yongqi, NIU Xingjiang. Simulation Research with an Improved Ant Colony Algotithm[J]. Journal of Wuhan University of Technology: Transportation Science & Engineering, 2013,37(6)：1330-1332.

[10] 孙纯哲,桂贵生,韩东,等. 基于蚁群算法的移动机器人路径规划研究与应用[J].合肥工业大学:自然科学版,2006,29(10):1208-1211. SUN Guizhe, GUI Guisheng, HAN Dong, et al. Algorithm for mobile robot path planning based on the ant colony algorithm and its application[J].Journal of Hefei University of Technology: Natural Science Edition, 2006,29(10):1208-1211.

[11] 万晓凤,胡伟,方武义,等.基于改进蚁群算法的机器人路径规划研究[J].计算机工程与应用,2014,50(18):63-66.

WANG Xiaofeng, HU Wei, FANG Wuyi,et al. Research on path planning of robot based on improved ant colony algorithm[J].Computer Engineering and Applications, 2014, 50(18)：63-66.

[12] 刘道华, 熊炎, 李为华,等. 蚁群参数自适应调整的优化设计[J].计算机应用研究,2011,28(3):905-908. LIU Daohua, XIONG Yan, LI Weihua, et al. Ant Colony optimization with self-adaptive parameter adjusting[J].Application Research of Computers, 2011,28(3):905-908.

[13] YIN L ,YIN Y X , LIN C J. A new potential field method for mobile robot path planning in the dynamic environments[J]. Asian Journal of Control,2009,11(2): 214-225.

[14] WANG Y T，LI J J. A route planning optimization model based on improved ant colony algorithm[C]//IEEE.2009 Eigth IEEE/ACIS International Conference on Computer and Information Science. ShangHai:IEEE Press, 2009: 82- 86.

朱颢东(1980-),男,河南虞城人,副教授,博士,硕士生导师,主要研究方向为智能信息处理、计算智能。E-Mail:zhuhaodong80@163.com。

孙 振(1989-),男,河南新乡人,在读硕士研究生,主要研究方向为智能信息处理、模式识别。

吴 迪(1990-),男,河南南阳人,在读硕士研究生,主要研究方向为智能信息处理、图像处理。

申 圳(1989-),男,河南唐河人,在读硕士研究生,主要研究方向为图像处理、模式识别。

(编辑：刘 勇)

Path planning for mobile robot based on improved ant colony algorithm

ZHU Haodong, SUN Zhen, WU Di, SHEN Zhen

(School of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, P.R. China)

In order to solve the problem that the ant colony algorithm was used in path planning for mobile robot, and is easily falls into local optimum and has a slow convergence speed, the paper proposes a method that the improved ant colony algorithm was used in path planning for mobile robot in the static environment. The method improves the transition rule of node state to increase the probability of searching optimal path. An adaptive heuristic function improves the searching efficiency of the algorithm. Updating the pheromone avoids falling into local optimum based on the assignment rule of wolves. Dynamical adjustment of the decay parameter increases the probability of choosing the optimal path by ants at a later stage, thus accelerating the convergence speed. The simulation results show that the improved algorithm has faster convergence speed under the condition of the same result of path planning when compared to other algorithm in the same environment. The improved algorithm obtains the optimal path in the environments of different complexity levels and it shows the efficiency and feasibility of the improved algorithm, which has good optimization ability and can be applied to path planning for mobile robot in the environments of different complexity levels.

mobile robot; ant colony algorithm; path planning

10.3979/j.issn.1673-825X.2016.06.017

2015-06-18

2016-03-10

朱颢东 zhuhaodong80@163.com

国家自然科学基金(61201447);河南省高等学校青年骨干教师资助计划项目(2014GGJS-084);河南省科技创新杰出人才计划项目(134200510025);河南省教育厅科学技术研究重点项目 (13A520367);郑州轻工业学院校级青年骨干教师培养对象资助计划项目(XGGJS02);郑州轻工业学院博士科研基金(2010BSJJ038);郑州轻工业学院研究生科技创新基金

Foundation Items：The National Natural Science Foundation of China (61201447);The Youth Backbone Teachers Funding Planning Project of Colleges and Universities in Henan Province of China(2014GGJS-084);The Technology Innovation Outstanding Talents Plan Project of Henan Province of China(134200510025);The Science and Technology Research Key Project of Education Department of Henan Province of China (13A520367);The Youth Backbone Teachers Training Targets Funded Project of Zhengzhou University of Light Industry of Henan Province of China(XGGJS02);The Ph.D.Research Funded Project of Zhengzhou University of Light Industry of Henan Province of China (2010BSJJ038) ;The Science and Technology Innovation Fund Project of Postgraduate of Zhengzhou University of Light Industry

TP301

A

1673-825X(2016)06-0849-07