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

曾明如，徐小勇，刘 亮，罗 浩，徐志敏

南昌大学 信息工程学院，南昌 330031

在机器人众多研究领域中，路径规划是其中一个重要研究对象，其任务是在一定性能指标要求下，在机器人运动环境中寻找出一条从起始位置到目标位置的最优或次优无碰撞路径。目前常用路径规划算法主要有蚁群算法、神经网络算法、遗传算法等，虽然这些算法能够在一定程度上解决问题，但都存在一些不足，如遗传算法搜索能力差和收敛性能差[1]，粒子群算法易出现早熟收敛慢的问题[2]。

越来越多的学者对路径规划问题研究时更注重多种智能算法相结合[3-7]，不同的智能算法相结合，优势互补，可提高算法性能。本文综合人工势场算法和蚁群算法的优点提出人工势场蚁群算法。利用人工势场中的势场力、蚁群算法中机器人与目标位置的距离及势场力启发信息影响系数来重新构造综合启发信息，并以蚁群搜索机制进行全局路径规划。仿真结果表明势场蚁群算法路径规划能找到更优路径和收敛速度更快。

1 基本蚁群算法和人工势场算法简介

1.1 传统蚁群算法简介

蚁群算法是模拟蚁群觅食行为的一种优化算法。假设蚁群中蚂蚁的总数为M，各蚂蚁在栅格环境下移动，并且根据状态转移规则选择下一个栅格，假设在时刻t时，蚂蚁k位于栅格i，那么蚂蚁k选择下一栅格j的概率为：

式中V表示蚂蚁k可以选择的下一栅格的集合；α为信息素浓度的启发因子，α越大，表明蚂蚁k越趋向于选择多数蚂蚁走过的路径；β表示能见度启发因子，反映了能见度信息对蚂蚁选择下一步位置所起作用的大小，β值越大，表明蚂蚁k越趋向于选择距离终点近的栅格；τij(t)表示t时刻路径(i,j)上的信息素浓度；ηij(t)表示t时刻路径(i,j)上的启发信息，其定义为：

其中G为目标栅格，d(j,G)表示栅格j到G的欧式距离。

蚁群经过某个栅格时会留下信息素，而信息素会随着时间的推移而消逝，所以每只蚂蚁走完一个栅格后，要进行局部信息素更新，更新公式如下：

式中p(0＜p＜1)是信息素残留程度；Q是常数；Lse是蚂蚁走过的路径长度：

w是蚂蚁k在本次循环中走过的步数，di是蚂蚁k的走过的边长。

1.2 人工势场算法简介

人工势场算法[8]实质是对机器人运行环境虚拟一个抽象势场，该势场由两部分场叠加而成，一部分为目标位置形成的引力场；另一部分为已知环境中障碍物形成的斥力场。人工势场中的斥力场和引力场均为矢量，斥力场矢量方向背离障碍物位置，引力场矢量方向指向目标位置。最后通过求合力来控制机器人的运动。

2 人工势场蚁群算法

蚂蚁在觅食过程中，一方面能够在所经过的路径上留下一种叫信息素的物质，另一方面能够感知路径上信息素的强度并沿着信息素强度高的路径运动。大量蚂蚁组成的群体觅食行为便体现为一种正反馈现象：越短的路径走过的蚂蚁就越多，留下的信息素浓度就越高，后面的蚂蚁选择该路径的概率就越大，从而达到以最短路径搜索食物的目的。但在路径规划初期的信息素浓度差异较小，蚁群算法正反馈作用不明显，路径选择存在盲目性，较为耗时，收敛速度较慢，在复杂的环境下易陷入局部最优，出现早熟收敛的情况[9-14]。人工势场算法的势场力可引导机器人朝目标栅格前进，且其只受环境信息的影响，路径搜索初期和后期不存在差异[15]。

本文融合两者的优点，提出一种新的算法——人工势场蚁群算法：把人工势场算法的势场力引入到蚁群算法的启发信息中，势场力启发信息可以降低路径规划初期蚁群算法的正反馈作用不明显导致的搜索的盲目性。但考虑到人工势场算法易出现目标不可达及易陷入局部稳定的问题，且随着迭代次数的增加，蚁群的正反馈作用增加，引入势场力启发信息的影响参数，该参数会随着迭代次数的增加，逐渐减弱人工势场算法的影响，突出蚁群算法的正反馈作用。提高了算法的收敛速度，解决了易陷入局部最优的缺点，同时避免了目标不可达和局部稳定情况的产生。

2.1 势场力信息

在传统蚁群算法的启发信息中引入人工势场算法的势场力启发信息，人工势场力信息使机器人在移动过程中迅速地规避障碍物，向着目标栅格移动，势场力启发信息是由机器人受到的人工势场中势场合力构造而成，该部分启发信息可为：

式中，a＞1为常数，Ftot表示移动机器人受到的势场合力，θ表示势场合力Ftot与移动机器人可行路径方向的夹角。对启发信息中的势场合力Ftot理论推导如下：假设移动机器人当前所处位置为P，目标位置为G，本文斥力势场函数可用式：

与传统的斥力函数：

相比，引入了当前位置与目标位置的距离，在新斥力函数的作用下，保证了整个势场在目标位置处全局最小。从而解决了人工势场算法易陷入目标不可达和局部稳定的问题。

其中

图1 新的势场函数下机器人受力示意图

吸引势场函数为：

机器人在复杂工作环境移动时，在势场合力的作用下快速规避障碍物向着目标位置移动，与蚁群算法中的距离启发信息结合，能够更加快速地实现路径规划目的。

2.2 势场蚁群算法的势场力分析

由势场蚁群算法理论可知，机器人在栅格环境移动过程中，一方面受到机器人与目标位置的启发作用，另一方面受到人工势场中的势场力作用。针对不同栅格环境下机器人与障碍物位置关系，分别对机器人进行受力分析，具体分析如图2。

根据栅格环境模型理论可知，机器人在自由栅格内进行下一步移动时有八个方向可供选择，为研究方便仅讨论比较两个最优可行路径方向。图中①，②是其可行的方向，θ1，θ2为合力与可行方向的夹角。

图2（A），当前位置与目标位置之间没有障碍物，此时所受的势场合力仅为目标位置产生的吸引力，由式（1）及（6）可知，合力与可行路径方向夹角越小，ηF(t)值越小，对应的转移概率越大，机器人更有可能选择该路径，对机器人受力分析，势场合力Ftot与两条可行路径的夹角θ1＜θ2，则其下一步沿着路径①的方向移动。

图2（B）和（C），机器人当前位置与目标位置之间存在简单的障碍物，对机器人受力分析，势场引力与斥力的合力Ftot与两条可行路径的夹角θ1＜θ2，则机器人在势场力的启发下沿着更优路径①的方向移动。

图2（D），机器人当前位置与目标位置之间存在较为复杂的障碍物，障碍物距离机器人当前位置最近的有两个位置，均对机器人产生斥力作用，则势场斥力合力Frep再与势场引力Fatt合成形成综合势场力Ftot，经分析知Ftot与两可行路径的夹角θ1＜θ2，在势场力的引导下机器人向着更优路径①的方向移动。

经过上述理论分析，势场蚁群算法的势场力可以引导机器人快速地避过障碍物朝目标位置移动。

2.3 势场力启发信息影响系数χ

势场力启发信息影响系数χ主要用来加强或降低人工势场力启发信息在路径规划过程中的影响作用，其值随蚁群迭代次数的增加而减小，为下式：

式中，Nmax为最大迭代次数，Nm为当前迭代次数。由公式（16）看出：在势场力启发信息影响系数χ的作用下，势场蚁群算法在路径规划初期的启发信息主要依靠势场力启发信息，这样既能使蚂蚁迅速找到到达目标位置的次优解，又能避免由于初期缺乏信息素而产生大量劣质解的情况。随着蚂蚁循环次数的增加，需要降低势场力启发信息的作用，否则蚂蚁过度集中于势场分布的梯度方向上，导致这些路径上的信息素浓度过强，从而减弱对更为优质路径的探索，路径搜索过早收敛，出现早熟现象。势场力函数影响系数χ同样能够有效地解决这种现象。

2.4 传统蚁群算法启发信息

传统蚁群算法启发信息ηd(t)，如下：

人工势场蚁群算法的综合启发信息构造如下：

在综合启发信息ηij(t)作用下，机器人可有效避免与障碍物的碰撞，避免在初期盲目的搜索，机器人能快速地搜索路径。

3 算法步骤

势场蚁群算法应用于路径规划的具体实现步骤为：

步骤1基于栅格法对机器人的移动空间进行环境建模，设置机器人起始栅格、目标栅格及障碍物栅格。

步骤2初始化势场蚁群算法相关参数，包括人工势场的引力场常量Katt、斥力场常量Krep、障碍物斥力的作用范围d0；蚁群搜索机制的蚂蚁数量m、迭代次数Nmax、启发因子α,β、信息素浓度Q以及信息素浓度挥发系数ρ等。

步骤3将m只蚂蚁放置于起始位置。

步骤4蚂蚁在公式（17）的综合启发信息下，根据转移概率规则公式（1）选择下一步到达位置，将该位置存储在禁忌表tabuk中。

步骤5判断m只蚂蚁是否到达目标位置，若是，计算每只蚂蚁搜索路径长度，找出当前搜索的最优路径，否则转向步骤4。

步骤6 按照公式（3）、（4）和（5）对每条路径上的信息素浓度进行更新。

步骤7判断是否达到最大迭代次数，若已达到则算法终止，输出各条搜索路径长度，找出最优路径，否则转向步骤3。

4 仿真

为了验证改进后的势场蚁群算法理论在路径规划上的可行性与优越性，在20×20栅格环境模型下对该算法进行仿真，并与常规势场蚁群算法和基本蚁群算法进行比较，仿真过程中的相关参数采用蚁群算法路径规划选定的参数m=20，α=1，β=7，ρ=0.3，Q=100，基于势场蚁群算法、蚁群算法、常规蚁群算法在相同环境下的路径规划仿真图及收敛曲线如图3～8所示。

图3 基本蚁群算法的爬行图

图4 基本蚁群算法的收敛曲线

图5 文献[4]提出的势场蚁群算法的爬行路径图

图6 文献[4]提出的势场蚁群算法的收敛曲线

图7 本文的人工势场蚁群算法的爬行图

图8 本文的人工势场蚁群算法的收敛曲线

为了便于比较势场蚁群算法的优越性，在两种栅格环境下多次实验，记录相关数据。

表1 相同栅格环境下的算法相关数据

通过仿真图及记录的相关数据可以看出，论文中提及的算法在路径规划上能够更快地在复杂环境下无碰撞搜索到最优路径，进一步论证了势场蚁群算法理论分析的正确性。

5 结论

针对人工势场法、蚁群算法的不足，本文提出了势场蚁群算法。该算法改进了势场算法中的斥力函数的构成，利用人工势场中的势场力、蚁群算法中机器人与目标位置的距离及势场力启发信息影响系数来重新构造综合启发信息，并以蚁群搜索机制进行全局路径规划。新启发信息可有效地降低路径规划初期蚁群搜索的随机性和盲目性，使机器人快速朝目标位置移动，随着迭代次数的增多，新启发信息中的势场力影响系数可有效减弱势场力的作用，突出蚁群算法的正反馈作用。仿真结果表明势场蚁群算法路径规划能找到更优路径和收敛速度更快。

[1]马永杰，云文霞.遗传算法研究进展[J].计算机应用研究，2012，29（4）：1201-1206.

[2]那日苏，李强，乌力吉.基于仿生学改进的粒子群算法[J].计算机工程与应用，2014，50（6）：61-63.

[3]Bu Q，Wang Z，Tong X.An improved genetic algorithm for searching for pollution sources[J].水科学与水工程，2013，6（4）.

[4]罗德林，吴顺祥.基于势场蚁群算法的机器人路径规划[J].系统工程与电子技术，2010（6）：1277-1280.

[5]王强，张安，吴忠杰.改进人工势场法与模拟退火算法的无人机航路规划[J].火力与指挥控制，2014，39（8）：70-73.

[6]李擎，王丽君.一种基于遗传算法参数优化的改进人工势场法[J].北京科技大学学报，2012，34（2）：202-206.

[7]杨帆，胡春平，颜学峰.基于蚁群系统的参数自适应粒子群算法及其应用[J].控制理论与应用，2010，11：1479-1488.

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

[9]王越，叶秋冬.蚁群算法在求解最短路径问题上的改进策略[J].计算机工程与应用，2012，48（13）：35-38.

[10]丁博，于晓洋，孙立镌.基于遗传-蚁群算法的CAD产品快速建模[J].计算机工程与应用，2013，49（15）：10-13.

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

[12]周之平，华路.复杂环境路径规划的改进蚁群算法[J].计算机工程与设计，2011，32（5）：1773-1776.

[13]何少佳，刘子扬.基于惯性蚁群算法的机器人路径规划[J].计算机工程与应用，2012，48（15）：245-248.

[14]张殿富，刘福.基于人工势场法的路径规划方法研究及展望[J].计算机工程与科学，2013，35（6）：88-95.

[15]于振中，闫继宏，赵杰，等.改进人工势场法的移动机器人路径规划[J].哈尔滨工业大学学报，2011，43（1）：50-55.