改进蚁群算法在移动机器人路径规划中的应用

1.安徽工程大学电气工程学院，安徽芜湖,241000；

2.安徽科技学院动物与科学学院，安徽滁州,233100

改进蚁群算法在移动机器人路径规划中的应用

王学梅1，陈其工1，王 正2

1.安徽工程大学电气工程学院，安徽芜湖,241000；

2.安徽科技学院动物与科学学院，安徽滁州,233100

对基于蚁群算法移动机器路径规划的因素进行分析研究，建立环境栅格图模型。每一步路径的选择概率由状态转移概率公式确定，用遗传算法控制优势路径的数目以避免算法陷入局部最优值。路径上的信息素浓度更新用信息素更新法则进行调整，通过信息素放大机制对信息素浓度值进行适当倍数的放大，用粒子群算法对以上算法涉及到的重要参数进行优化和选择。仿真结果图清晰地显示改进后的蚁群算法在移动机器人路径规划上的效率和适应能力都有了明显的改善。

改进蚁群算法；移动机器人；路径规划；信息素；粒子群算法

近年来，随着机器人研究的不断发展，移动机器人路径规划技术也取得了长足进步，学者们提出了多种路径规划算法，如神经网络法、人工势场法、遗传算法、粒子群优化算法等。但路径规划的核心思想却始终如一，那就是寻找一条从起始点到目标点的最优路径，这其中包括用时最短、路径最短、避开所有障碍物且通过必须要经过的指定点[1-4]。

针对传统蚁群算法机器人路径规划出现的问题，本文通过信息素放大机制成功解决了蚁群算法自身收敛速度慢问题；同时，为了克服由于搜索机制导致算法容易陷入局部最优的困境，也将遗传算法融入其中。由于粒子群算法(Particlc Swarm Optimization，简称PSO)能很好地对参数进行优化，因此，将其加入到改进蚁群算法中，以进一步确保算法的稳定性和优越性，最终完成路径规划研究和仿真实验。

1 蚁群算法的改进

人们通过观察研究发现，蚂蚁的觅食工作是分工协作、合理有序的，彼此间通过自身散发出的信息素进行交流，且在走过的路径上留下这种物质作为标记。某一路径上通过的蚂蚁越多，留下的信息素的浓度也就越高(忽略挥发掉的部分)，在有限的区域范围内蚂蚁彼此间能感觉到这种化学物质，并且哪里的信息素浓度高就自觉地向那个方向移动，因此，信息素浓度越高的路径，被选择的概率也就越大。群体中的个体之间就是这样通过信息素相互交流，最终探索到一条从蚁穴到食物源的最短的路径而获取食物[5-6]。

1.1 路径选择概率公式

蚁群算法中状态转移概率公式定义为:

(1)

式中，α和β分别表示τij(t)和ηij(t)对整个概率影响的大小； τij(t)表示t时刻路径i与路径j上残留的信息素浓度，ηij(t)表示后续栅格点的启发信息强度函数；allowedα表示蚂蚁k下一步可以选择的栅格号组成的集合。

与此同时，后续栅格的概率选择公式ηij(t)为：

其中，dij表示从路径i到路径j的距离。

由于自然状态下群体中蚂蚁搜索到的各路径上信息素浓度差异很小，导致算法的搜索效率低下，收敛速度慢[7]，效果不尽人意。

1.2 用遗传算法避免蚁群算法陷入局部最优

由于蚁群算法自身的缺陷，使得算法容易陷入局部最优，本文采用遗传算法中的轮盘算法[8]来避免蚁群算法陷入局部最优值。按照群体中每一个体对环境适应能力的大小，以不同的概率向下一代进行复制。具体操作过程如下：

步骤1根据适应度函数：

其中，n代表蚂蚁在模拟环境中所经过的路径上所包含的栅格数目，每个蚂蚁个体所经过的路径长度用字母d表示。依次计算出群体内每个个体的适应值，得相应的累计值为Hi，最后一个累计值为Hn；

步骤2得出均匀分布的适应度随机数W∈[0，Hn];

步骤3依次用Hi与步骤2中产生的随机数W进行比较，若Hi≥W，则i被选为复制对象；若Hi≤W，则i被删除；

步骤4重复步骤2和步骤3，直到所需要的个体数目被复制满为止。

通过轮盘算法对个体适应值的筛选，使算法的早熟问题得到了很好的解决。为了使算法优势更加明显，用上一代种群中适应度大的个体来代替新种群中适应度小的个体，增加了新种群中优势路径的数目,显著提高了算法的效率及全局最优解的搜索概率。

2 粒子群算法对参数的优化

设M为信息素浓度放大倍数，信息素浓度和启发函数对转移概率的影响程度分别用α和β表示，信息素挥发系数为ρ，启发系数为ε。显然最能影响算法性能的因素是参数的选取,而人们通常根据经验选取参数值，这样就使得算法具有很强的主观性，导致算法容易陷入局部最优；由于粒子群算法搜索速度快、效率高、算法简单，适合于实值型处理，因此选择其对改进蚁群算法的重要参数进行优化选择。

2.1 粒子群优化群算法

粒子群优化算法是由电子工程学博士R.Eberhart和社会心理学博士J.Kennedy受自然界鸟类寻找食物的自然现象的启发于1995年发表的两篇论文中提出的。由于PSO算法对非线性多峰值问题和没有特殊方法可用或者使用特殊方法也得不到满意结果的问题有很好的应用前景，因此PSO已广泛应用于调度、组合优化、信号处理、数据挖掘等现代化应用领域。

定义算法在Q维的空间搜索，参与搜索的粒子数为m，粒子l在某一时刻它的位置和速度分别记为xl和vl则：

xl=(xl1,…,xlq,…,xIQ)

vl=(vl1,…,vlq,…,vIQ)

其中，1≤l≤m,1≤q≤Q。

在解空间中，pl=(pl1,pl2,…,pIQ)表示粒子l所经历的最好位置，群体中适应度最好的粒子g的位置记为pg=(pg1,pg2,…,pgQ)，则粒子群的进化方程式为：

(2)

(3)

其中，w为惯性衡量值；c1和c2为影响机器人自适应学习功能的参数；r1和r2为常数，且取值范围为0≤r1≤1，0≤r2≤1；k为遍历搜索的次数。粒子的位置用字母X表示，且其变化范围为X∈[Xmin,Xmax]；速度用字母V表示，其变化范围记为V∈[Vmin,Vmax],若由式(2)和式(3)计算出的值超过了这个范围，则设置其为边界值。

2.2 对参数进行优化

改进蚁群算法的相关参数用粒子群算法进行优化选择的具体操作步骤如下：

步骤1参数初始化。对遍历搜索次数最大值kmax，惯性衡量值w，粒子个数m，影响机器人自适应学习功能的参数c1和c2进行初始化。

步骤2当前粒子群的位置信息用改进蚁群算法中放大后的信息素浓度值和启发函数表示，起始位置和初速度在位置可变范围内随机选取。

步骤3将当前群体中适应度最好的粒子的位置和本次循环中每个粒子在解集中的最好位置求出。

步骤4粒子群中每个粒子i的速度Vi按(2)式进行更新。若Vi小于Vmin，则Vi为Vmin；若Vi大于Vmin，则Vi为Vmax。

步骤5粒子群中每个粒子i的位置Xi按式(3)对其进行更新。若Xi小于Xmin，则Xi为Xmin；若Xi大于Xmin，则Xi为Xmax。

3 用改进的蚁群算法对机器人动态路径进行规划

在用蚁群算法寻找机器人工作环境中最优路径的过程中，如果传感器检测到机器人将与环境中移动的障碍物相碰，机器人则选择离动态障碍物最近的安全栅格作为新的移动路径。根据传感器探测反馈的环境信息，确定动态障碍物在模拟环境空间中的运动范围，在避开障碍物的前提下，机器人循着信息素浓度高的路径前进[9]。用粒子群算法对改进蚁群算法中的重要参数的最优组合进行确定，基于以上对算法的改进，新路径规划的操作步骤如下：

步骤1初始化参数。对最大迭代次数Kmax、种群个数为Nnum、信息素浓度放大倍数M进行初始化；S和E分别为算法的起点和终点，设Nnum只蚂蚁的起始位置全部在起始点S，且起始时每条路径上的信息素浓度都为0。

步骤2蚂蚁下一步到达的栅格根据自适应启发函数确定。

步骤3在蚂蚁k到达终点E后，按信息素更新公式对路径上的信息素进行更新。

步骤4合理选择和调整放大倍数M，对更新后的信息素浓度按放大倍数M进行放大。

步骤5对循环次数进行判断。若循环次数已达到最大值，则将当前群体中用时最短的路径栅格的序号和长度输出；否则返回起点S，程序转步骤2。

步骤6机器人在沿着通过以上步骤搜索到的最优路径前进时，如果传感器检测到将与环境中的动态障碍物相撞，则机器人调整前进方向后沿着信息素浓度大的栅格重新探索到一条避开动态障碍物的路径，否则，机器人一直走到指定目标点，终止算法。

4 仿真实验与分析

改进后蚁群算法[10]性能的仿真实验在Matlab软件中进行。工作环境的栅格图是长为20个栅格、宽也为20个栅格正方形，每个小栅格的面积为10×10个单位，定义传统蚁群算法中蚂蚁数和最大循环次数分别25和200。用于对改进蚁群算法的重要参数进行优化粒子群算法中粒子数为30，循环次数的最大值为100，惯性衡量值w为0.65，影响机器人自适应学习功能的参数c1和c2都选为1.5，放大倍数M=3。

仿真图中，坐标系以X轴向右为正方向，Y轴向上为正方向，假设动态障碍物为正方形物块，且其长和宽都为10个单位。

由图1和图2的仿真实验结果可以看出，改进的蚁群算法减少了搜索的盲目性，缩短了搜索时间，提升了算法的性能。

5 结束语

路径规划一直是机器人研究领域的关键性问题之一，如何找到一条快速、高效、便捷、安全性能高的路径，一直是机器人研究工作者们的愿望。传统蚁群算法是受蚂蚁觅食一步步探索路径的启示抽象得到的，因此算法的搜索效率低下且容易陷入局部最优。本文通过对信息素浓度值进行适当倍数的放大，扩大了不同路径上信息素浓度的差距，有效地提高了搜索速度。考虑到这样容易导致算法陷入局部最优的值，采用遗传算法进行优化，适当选择遗传算子，从而提高了新种群中的合适的路径数目，成功避免了算法陷入局部最优且提高了算法的收敛速度。仿真实验结果表明，该路径规划方法是可行的，且效果明显。

[1]付涛，王大镇，弓清忠，等．改进神经网络自适应滑模控制的机器人轨迹跟踪控制[J]．大连理工大学学报，2014(5)：523-530

[2]殷路，尹怡欣．基于动态人工势场法的路径规划仿真研究[J]．系统仿真学报，2009，21(11)：3325-3328

[3]浦定超.基于遗传算法的移动机器人路径规划的研究[D].合肥：合肥工业大学电器与自动化工程学院，2010:16-28

[4]史恩秀，陈敏敏，李俊，等.基于蚁群算法的移动机器人全局路径规划方法研究[J].农业机械学报，2014,45(6):53-56[5]杨学峰．蚁群算法求解TSP问题的研究[D]．长春：吉林大学计算机科学与技术学院，2010：14-16

[6]杨沛，古德祥．蚁群的信息系统[J]．昆虫知识，2001，38(1)：23-25

[7]Gutjahr W J.A graph-based ant system and its convergence[J].Future Generation Computer Systems,2000,16(8):873-888

[8]崔建军．基于遗传算法的移动机器人路径规划研究[D]．西安：西安科技大学电气与控制工程学院，2010：42-44

[9]郝靳.基于改进的蚁群算法实现的茶树种植分析系统[D].长春：吉林大学软件学院，2014：15-23

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

(责任编辑：汪材印)

10.3969/j.issn.1673-2006.2016.03.027

2015-11-15

国家自然科学基金资助项目“网络控制系统中基于时延在线预测的动态调度策略研究”(61172131)。

王学梅(1984-)，女，安徽滁州人，在读硕士研究生，主要研究方向：移动机器人路径规划。

TP18

A

1673-2006(2016)03-0107-04