机器人空间路径规划的ACO算法特性分析

杨连花，常肖

(长安大学道路施工技术与装备教育部重点实验室，陕西西安 710064)

机器人空间路径规划的ACO算法特性分析

杨连花，常肖

(长安大学道路施工技术与装备教育部重点实验室，陕西西安 710064)

为进一步研究机器人的移动空间路径规划方法，分析蚁群算法的主要系数对路径规划的影响，根据蚁群优化算法的主要特点，对机器人的移动空间信息采用栅格法进行全局描述。对蚁群优化算法的主要系数如蚁群数量m和信息素蒸发系数ρ等进行选择，以路径长度和迭代次数为目标，仿真分析其对规划路径的长度和路径规划效率的影响，找到最佳匹配系数组。仿真结果表明：合理选择算法系数能够缩短机器人的移动空间路径规划长度,且能提高路径规划效率。

移动机器人；蚁群优化算法；路径规划；影响系数

路径规划是对移动机器人(mobile robot，MR)进行研究的主要内容之一，是指当工作空间中存在障碍物时，移动机器人能搜索到一条从给定起点到终点的工作路径，使其在移动过程中可以安全、无碰撞地躲避所有障碍物，同时经过的路径最短，这是控制机器人工作的基础[1]。当前，存在大量针对全局路径规划的算法，栅格、人工势场等是其中几种较为常见的算法。应用栅格法进行路径规划时，随着空间的增大，计算所需的存储空间急剧增大，导致决策速度降低[2]；而应用人工势场法进行路径规划时，又极易出现局部最佳解和锁死问题[3]。在智能控制算法迅速成熟的基础上，逐渐出现了如免疫[4]、A*优化[5]、蚁群优化[6]、粒子群[7]、遗传优化[8]和人工鱼群[9]等算法。

蚁群优化(ant colony optimization，ACO)算法作为一种启发式搜寻优化工具，具备良好的算法结合兼容性、分布式精简计算、健壮性好等优势。针对移动机器人的路径规划问题，本文采用ACO算法，计算并重点仿真分析蚂蚁个数m和信息素蒸发系数ρ这两个重要影响系数对规划路径结果和效率的影响。

1 机器人工作空间

1.1 路径规划选择

在对移动机器人进行研究过程中，移动机器人的路径规划是非常重要的研究方向之一[10]。路径规划的目的是使机器人在整个移动过程中，能够避开每个障碍物[11]。依照对空间信息的熟悉程度，该问题可以分为己知环境信息的全局路径规划和未知环境信息的局部路径规划[12]。根据已获得的空间信息，全局规划可以为移动机器人进行路径规划，并且获得的空间信息精确度决定了路径规划的准确性[13]。全局规划通常能够得到最佳路径，但必须提前获取空间的精确信息，计算量庞大[14]。而局部规划只需获取机器人目前的局部空间信息，就能让其具备优良的规避特性[15]。仅仅根据局部空间信息进行路径规划，偶尔会出现局部极点，不能确保机器人顺利移动至终点[16]。

本文中机器人对空间环境具备一定的熟悉程度，故采用全局路径规划对移动机器人的路径规划进行研究。

1.2 环境建模

假设机器人的工作空间为二维空间(记为RS)，在RS中的障碍物即为机床。当机器人行走时，障碍物为不发生变化的静止物体，对移动机器人的工作环境进行模拟。按栅格法编号RS空间，机器人按栅格变换位置。可行栅格为无障碍物的栅格，不可行栅格为存在障碍物的栅格，所有的栅格组成了栅格集。栅格标识方法有编号法[17]和直角坐标法[18]，这里选择编号标识法对机器人工作空间进行模拟。

依次按照由左至右、由下至上的次序，把机器人移动空间用数字1,2,3,…,n标记，每个栅格用单个数字表示。通过将障碍物膨胀，使障碍物在占原有栅格的同时，再多占几个栅格，但按单个栅格计算，从而避免机器人与障碍物发生碰撞。该标识方法能够使真实情况和环境模型相符合，且简单实用，在路径规划时使机器人移动畅通无阻。设置栅格序号集S={1,2,3,…，N}。由所述关系可知，g(0,0)的序号设置为1，g(1,0)的序号设置为2，直到g(X,Y)的序号设置为n。在不属于同一栅格内的前提下，规定起点、终点都为任意位置且都属于S。

2 蚁群优化算法

2.1 基本原理

基于蚁群的共同行为，搜寻路径时能够找到最佳结果的基本原理是:在蚁群通过的路径上遗留信息素的方式，让之后通过的蚁群分析信息素的强度以选取通道。当蚁群搜寻到从没涉足的交叉口时，它将随意选取通道通过且留下信息素，路径距离跟遗留信息素的数量呈反比。过一段时间后，遗留在短距离路径上的信息素将会连续累积，而遗留在相对长距离的路径上的信息素就会渐渐蒸发甚至消失。通过这样的方式，蚁群最终能够搜寻到一条最佳路径。蚁群工作示意图如图1所示。

a) 信息素设置 b)T=0时刻蚁群数目 c)T=1时刻蚁群数目图1 蚁群工作工程图

假设蚁穴的位置为A，食物源的位置为E，障碍物的位置为B、C、D、H。当蚁穴和食物源之间有障碍物时，蚁群能智能地从A通过C或H抵达E，或从E通过C或H抵达A，BCD长度为1，BHD长度为2，如图1a)所示。从计算简便的角度出发，假设在单个时间内蚁群遗留下的信息素设置为1，且信息素残留的时间也设置为1，设置A点与E点之间分别存在30只蚂蚁。在开始时，路径BC、BH、CD、HD上没有留下信息素，在A与E之间的蚁群会随意选取其通过的通道。根据统计学原理，蚁群选取路径BC、BH、CD、HD几率相等，如图1b)所示。当历时单个时间后，BCD遗留信息素增多，而BHD遗留信息素减少，如图1c)所示。数量为20的蚁群由B、C和D点抵达E。随着这种循环的继续，蚁群认同BCD的几率会提高，最后蚁群将绝对认同BCD路径，进而搜寻到A和E之间的最短路径。

图2 ACO算法执行流程图

2.2 算法执行步骤

算法的执行流程如图2所示。

步骤如下：

1)由0和1构成的矩阵代表机器人的栅格式移动空间信息，可通过栅格设置为0，障碍物栅格设置为1。可通过路径节点设置初始化D={0,1,…，n-1}，假设信息启发因子为α、蚁群数量为m、信息素蒸发系数为ρ、期望启发因子为β、迭代次数为Nc。假设蚂蚁k(k=1,2,…，m)目前所通过的栅格点禁忌表为Bk，将其初始化为Φ。把蚂蚁放置于起点S，分别对起点S和终点E的栅格号进行选取。

2)根据状态，单个蚂蚁由i栅格行走至相邻j栅格的概率[19]

3)蚂蚁k每移动一次，把节点j添加至禁忌表Bk里，以修改Bk。

4)重复步骤2)～3)，直到没有循环完毕的蚂蚁移动至终点，计算每只蚂蚁移动的路径距离且进行存储。

5)更新信息素

τij(t+1)=ρτij(t)+Δτij(t,t+1),

6)选取、输出本次循环中的最佳路径并存储,否则重复步骤4)～5)。

3 ACO算法中模拟系数的选取

图3 空间路径规划

至今仍没有严谨的理论基础来判定ACO算法中的最佳系数配置 ，最佳系数配置主要依赖于仿真结果的统计数据和经验值。针对ACO算法在模拟计算中存在的问题，研究α，β，ρ,m,Q等系数的最佳配置相当重要。研究如图3所示环境下的路径规划，其中阴影栅格代表障碍物占用。

3.1 蚁群数量

在ACO算法中，随着蚁群数量的增大，算法的稳定性和蚁群的空间搜寻能力会随之增加。但在实际应用中，随着蚁群数量的增多，反而会减慢算法收敛速度，使搜寻过的路径上的相关信息量受到影响，并使其变化趋于平均，从而使信息正反馈功能降低。相反，随着蚁群数量的减少，在搜寻大规模空间的最佳路径时，减少未搜寻路径上的有关信息量，甚至使其完全消失，从而提高了ACO收敛速率，但降低了蚁群搜寻的随机性，使路径搜寻的全局性减弱，降低了ACO 的稳定性。在本文中，设置蚁群优化算法中，α=1，β=5，ρ=0.5,Q=100,在仿真分析时，选择蚁群数量m分别为10、20、30、40、50、60、70、80、90、100、110、120、130、140、150、160、170、180、190、200，仿真结果如图4所示。

由图4可知，蚁群数量m基本按具备正分数指数的幂函数递增规律来影响收敛迭代次数。随着m的增加，ACO算法的稳定性得到提高，但当m增加至临界点之后，蚁群搜寻收敛速度降低，信息量波动趋于稳定。同时也可得出，当蚁群数量为50时，搜寻迭代次数和路径长度均为最小值。

a) 对路径长度的影响 b) 对迭代次数的影响图4 蚁群数量对ACO的影响

3.2 信息蒸发素系数

a) 对路径长度的影响 b) 对迭代次数的影响图5 信息素蒸发系数对ACO的作用

在ACO优化时，蚁群具备记忆能力，随着时间推移，蚁群遗留的信息渐渐蒸发。ACO算法中，蚁群对空间的搜寻能力及蚁群搜寻的收敛速度直接受到信息素蒸发系数ρ的影响。ρ过大，将大大增加二次搜寻路径的概率，导致从未被蚁群搜寻过的路径上的信息素蒸发甚至完全消失，使得蚁群的空间搜寻能力降低；相反，当ρ较小时，虽然蚁群对路径的空间搜寻能力与随机性有所提高，但却降低了蚁群搜寻的收敛速度[7]。仿真分析时，设置m=100，α=1,β=5,Q=100,信息素蒸发系数ρ分别为0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9。计算结果如图5 所示。

由图5可知，当信息素蒸发系数ρ=0.6时，搜寻迭代次数和路径长度均为最小值。

图6 最佳路径选择结果

4 基于ACO算法路径规划仿真分析

本文通过设计并实现机器人的空间最佳规划系统来探索ACO的有效性。基于Matlab 软件仿真前提下，采用ACO优化算法对机器人进行空间路径规划。仿真时，设序号1为空间信息的起始点栅格位置，序号400为终点栅格位置。设定m=50，Nc=100，α=1,β=5，ρ=0.6。仿真结果如图6、 7所示。

图7 仿真结果曲线

由图6可见，蚁群可以搜寻到一条从起始点开始避开所有障碍物的空间最佳路径，即在该环境下移动机器人可以搜寻到的最短路径。由图7可见，基于ACO算法的机器人空间搜寻模型在计算初期发生一定波动，但随着时间的推移，计算所得的路径长度越来越短，且在整体上呈收敛趋势。在计算中后期，最佳路径因随机搜寻的数目降低而趋于稳定。因信息素浓度的正反馈机制的存在，使得所搜寻的路径在第31次算法迭代时收敛至最佳。

5 结论

1)针对机器人路径规划问题，采用栅格法对空间环境进行全局空间信息描述，并基于蚁群优化的路径规划方法对机器人进行路径规划。结果证明该方法不仅实现简单，而且具备良好的算法结合兼容性，可用于解决环境已知情况下的机器人路径规划问题。

2)通过仿真分析ACO算法的蚂蚁数量、信息素蒸发系数这2个重要系数对规划路径效率及路径规划结果的影响，结果表明蚁群数量基本按具备正分数指数的幂函数递增规律来影响迭代次数。随着蚁群数量的增长，ACO的稳定性提高。但当m增长到临界点后，则蚁群搜寻收敛速率减慢，信息量波动趋于稳定。确定m=50时，规划结果最优；当信息素蒸发系数增加时，会使已搜寻过的路径被二次计算的概率增大，导致没有被搜寻到的路径上的信息素减少甚至完全蒸发，从而使ACO的全局搜寻能力降低。当信息素蒸发系数减小时，虽然能够提高ACO的整体搜寻能力和随机性，但却减小了ACO的收敛速度。最终确定ρ=0.6时，规划结果最优。

[1]刘玲.基于智能计算的移动机器人路径规划方法研究[D].长沙:湖南大学,2007. LIU Ling.Research on path planning for mobile robot based on intelligent computing[D].Changsha: Hunan University,2007.

[2]史恩秀,陈敏敏,李俊,等.基于蚁群算法的移动机器人全局路径规划方法研究[J].农业机械学报,2014,45(6):53-57. SHI Enxiu,CHEN Minmin,LI Jun,et al.Research on global path planning for mobile robot based on ant colony algorithm[J].Journal of Agricultural Machinery,2014,45(6):53-57.

[3]于振中,闫继宏,赵杰,等.改进人工势场法的移动机器人路径规划[J].哈尔滨工业大学学报,2011,43(1):50-55. YU Zhenzhong,YAN Jihong,ZHAO Jie,et al.Improved artificial potential field method of path planning for mobile robot[J].Journal of Harbin Institute of Technology,2011,43(1):50-55.

[4]叶兆莉,袁明新,程帅,等.移动机器人的一种烟花爆炸式新免疫规划算法[J].计算机仿真,2013,30(3):323-326,375. YE Zhaoli,YUAN Mingxin,CHENG Shuai,et al.New fireworks explosive immune planning algorithm for mobile robots[J].Computer Simulation,2013,30(3):323-326,375.

[5]王殿君.基于改进A*算法的室内移动机器人路径规划[J].清华大学学报(自然科学版),2012,52(8):1085-1089. WANG Dianjun.Indoor mobile-robot path planning based on an improved A*algorithm[J].Journal of Tsinghua University (Science and Technology),2012,52(8):1085-1089.

[6]张志协,曹阳.基于改进型蚁群算法的最佳路径问题求解[J].计算机系统应用,2012,38(10):76-80. ZHANG Zhixie,CAO Yang.Optimal path problem solving based on improved ant colony algorithm[J].Computer System Application,2012,38(10):76-80.

[7]李擎,徐银梅,张德政,等.基于粒子群算法的移动机器人全局路径规划策略[J].北京科技大学学报,2010,32(3):397-402. LI Qing,XU Yinmei,ZHANG Dezheng,et al.Global path planning method for mobile robots based on the particle swarm algorithm[J].Journal of University of Science and Technology Beijing,2010,32(3):397-402.

[8]石铁峰.改进遗传算法在移动机器人路径规划中的应用[J].计算机仿真,2011,28(4):193-195,303. SHI Tiefeng.Research on path planning for mobile robot based on improved genetic algorithm[J].Computer Simulation,2011,28(4):193-195,303.

[9]周利坤,刘宏昭.自适应人工鱼群算法在清罐移动机器人路径规划中的应用[J].机械科学与技术,2012,31(7):1085-1089. ZHOU Likun,LIU Hongzhao.An adaptive artificial fish school algorithm for path planning of mobile tank-clearing robot[J].Mechanical Science and Technology,2012,31(7):1085-1089.

[10]BRADEN E Stenning,TIMOTHY D Barfoot.Path planning with variable-fidelity terrain assessment[J].Robotics and Autonomous Systems,2012,60(9):1135-1148.

[11]游维.一种未知动态环境下移动机器人路径规划研究[D].湘潭:湘潭大学,2009. YOU Wei.An unknown dynamic environment for mobile robot path planning research[D].Xiangtan :Xiangtan University,2009.

[12]张晓.全方位移动平台的设计以及定位和路径规划[D].北京:北京工业大学,2013. ZHANG Xiao.Design and positioning and path planning of the mobile platform[D].Beijing :Beijing University of Technology,2013.

[13]张鹏飞.自主移动机器人路径规划与运动控制的研究与实现[D].西安:西安理工大学,2008 ZHANG Pengfei.Research and implementation of path planning and motion control of autonomous mobile robot[D].Xi′an :Xi′an University of technology,2008.

[14]邸建华.用于水下机器人路径规划的优化算法研究[D].哈尔滨:哈尔滨工程大学,2009. DI Jianhua.Optimization algorithm for path planning of underwater robot[D].Harbin: Harbin Engineering University,2009.

[15]黎田.基于改进蚁群算法的移动机器人路径规划[D].西安:西安科技大学,2011. LI Tian.Research of path planning for mobile robots based on improved ant colony algorithm[D].Xi′an: Xi′an University of Science and Technology,2011.

[16]王丽.移动机器人路径规划方法研究[D].西安:西北工业大学,2007. WANG Li.Research on path planning method of mobile robot[D].Xi′an: Northwestern Polytechnical University,2007.

[17]夏梁盛,严卫生.基于栅格法的移动机器人运动规划研究[J].计算机仿真,2012,12(29):229-233. XIA Liangsheng,YAN Weisheng.Study on mobile robot motion planning based on grid method[J].Computer Simulation,2012,12(29):229-233.

[18]杨杰,贺利乐,李荣丽,等.基于改进势场栅格法的移动机器人路径规划[J].煤矿机械.2012,33(8):74-76. YANG Jie,HE Lile,Li Rongli ,et al.Based on the improved potential field grid method for path planning of mobile robot[J].Coal Mine Machinery,2012,33 (8): 74-76.

[19]徐进.基于蚁群算法的移动机器人路径规划算法研究[D].北京:北京化工大学,2009. XU Jin.Research on path planning algorithm of mobile robot based on ant colony algorithm[D].Beijing: Beijing University of Chemical Technology,2009.

(责任编辑：郎伟锋)

ACO Algorithm Characteristic Analysis of Robot′s Space Path Planning

YANGLianhua,CHANGXiao

(KeyLaboratoryofRoadConstructionTechnologyandEquipment,MinistryofEducation,Chang′anUniversity,Xi′an710064,China.)

In order to further research the path planning method of robot′s mobile space and analyze the influence of main coefficients of ant colony algorithm on path planning,the mobile spatial information of the robot is described by the grid method according to the main characteristics of ant colony optimization algorithm.With the path length and the number of iterations as the goal,the key parameters such as the number of ant colony and information pheromone evaporation coefficients of the ant colony optimization algorithm are selected to simulate and analyze their influence on the length and efficiency of the path planning to get the best array of path.The simulation results show that the reasonable selection of algorithm parameters can achieve the short path planning length of the robot′s mobile space and the high path planning efficiency.

mobile robot; ant colony optimization algorithm; path planning; influence parameter

2016-05-26

杨连花(1991—)，女，河南原阳人，硕士研究生，主要研究方向为机械设计及理论，E-mail：1245201067@qq.com.

10.3969/j.issn.1672-0032.2016.04.013

TP242.6

A

1672-0032(2016)04-0081-06