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

李二超，齐款款

兰州理工大学 电气工程与信息工程学院，兰州730050

静态环境下的移动机器人路径规划是指在已知环境中，按照一定的算法，根据目标函数（如距离最短等），寻找一条从起点到终点的安全且最优路径[1]。

二维静态环境下机器人路径规划算法有很多，如A*算法、遗传算法、粒子群算法和蚁群算法，其中，A*算法速度快但转折点较多，随着环境复杂度的增加，搜索代价呈指数增长[2]，遗传算法在种群初始化、算法迭代等环节代价函数建模困难，路径搜索效率低，耗费较大的计算和存储资源，在复杂环境下的路径规划效率低下，需要较长时间才能规划出可行路径，且路径并非最短[3]，粒子群算法简单易行，通用性强，但在算法初期局部搜索能力较差，后期易陷入局部最优等[4]，而选择蚁群算法的原因是，蚁群算法是一种启发式的随机搜索算法，该算法由模拟自然界蚂蚁行为而来，并通过信息素的积累产生的正向反馈来寻找最优路径，随着环境复杂度的增加，路径搜索代价不会指数增长，且具有较强的鲁棒性，优良的并行分布式计算能力、无中心控制、易于与其他算法融合的优点[5-6]，但无法找到最短路径，收敛速度慢，路径搜索盲目性大、且路径拐点较多。针对以上蚁群算法的缺陷，不同的学者有着各自的改进方法。张苏英等人[7]采用双向蚁群算法，但并未使用相遇条件，即起点蚂蚁搜索路径完成后，终点蚂蚁才开始进行路径搜索，虽然能提高全局搜索能力，但并不能缩减算法运行时间。文献[8]采用初始信息素不平等分布的同时，在启发函数中引入转角因子，能够较快得到拐点较少的最优路径。王红君等人[9]使用冗余点的删除策略，能够减少路径上的拐点数目。陈英俏[10]采用信息素非均匀分布的并行双向蚁群算法，相遇条件为信息素相遇，即在同一栅格出现双向不同的信息素视为相遇，同时在启发函数中引入信息素相互引导策略，加强了信息素作用，减少了算法运行时间。Luo等人[11]使用伪随机概率转移公式提高了算法的全局搜索能力和收敛速度。徐义晗等人[12]采用建立方向信息素矩阵的双向蚁群算法，能够提高路径搜索速度和路径的多样性。王晓燕等人[13]利用人工势场法求得的初始路径信息对蚁群算法的启发函数进行改进，增强路径的引导作用，减小路径搜索的盲目性。文献[14]采用双向蚁群算法路径搜索策略，能够加快算法运行速度和提高全局搜索能力，但仍然是一小步的搜索，路径转折点依然较多。文献[15]通过改进信息素增强系数，信息素挥发因子，建立信息素因子和启发式因子的互锁关系，减少了算法的迭代次数，提高了算法的收敛速度。本文算法与双向蚁群算法（如文献[14]）相比，优势在于减少路径搜索的节点数（有效顶点数少于环境总栅格数），打破传统总是一小步的路径搜索方式以及转移角度45˚整数倍的限制，动态调节挥发系数，得到的路径拐点较少，路径更短。

传统蚁群算法存在很多的缺陷，针对传统蚁群算法无法找到最短路径，路径搜索盲目性大，收敛速度慢，拐点多问题，提出基于改进双向蚁群算法的机器人路径规划。首先，改进路径搜索方式，即基于障碍物有效顶点编码的路径搜索，不再使用传统的从当前栅格中心到下一栅格中心一步步的路径搜索，而是从当前障碍物有效顶点到下一可选障碍物有效顶点的大步的路径搜索，结合双向蚁群算法路径搜索策略，能够加快收敛速度且能够找到拐点相对更少的最短路径。其次，由于采用障碍物有效顶点编码的路径搜索，启发式函数也随之做了改进，即当前障碍物有效顶点到下一可选障碍物有效顶点的欧氏距离的倒数，并在公式分母中加入调节参数，有助于找到更短路径。同时，引入伪随机（随机概率和任一性概率）的状态转移策略，能够降低传统算法路径搜索的盲目性。最后，为防止信息素积累过多，自适应调节信息素挥发系数的同时，设置信息素浓度的取值范围。

1 环境建模

机器人工作环境为静态栅格地图，如图1所示。黑色栅格代表障碍物，用1表示，白色栅格代表自由栅格，用0表示。地图按照从左到右，从下到上的顺序依次编号1、2、…，栅格序号与坐标一一对应，坐标与栅格编号的关系表达式如式（1）：

图1 栅格地图Fig.1 Grid map

其中，i代表栅格序号，Nx栅格地图的行数，Ny栅格地图的列数，mod是求余运算，ceil是向上取整运算。

将障碍物进行膨化处理，如图2所示。最里面黑色正方形为原始障碍物，当不规则障碍物不满一个栅格时，将其填充为一个栅格，白色部分为障碍物的膨化，宽度为机器人半径，最外层黑色部分为安全距离，整体构成障碍物，此时把机器人看作质点来处理，假设膨化后的正方形边长为1，即式（1）中的a=1。本文研究的目标为路径最短。

图2 障碍物膨化处理Fig.2 Expansion treatment of obstacles

2 传统蚁群算法

状态转移概率公式如式（2）所示：

式中，j∈allowedm为待选节点集合；τij(t)为信息素浓度；ηij(t)为启发信息，用当前节点i到下一节点j的欧式距离的倒数表示；α和β分别表示信息素因子和启发式因子。

信息素更新公式如式（3）~式（5）所示：

式中，τij(t+1)为更新后的信息素浓度；ρ为信息素挥发系数；Δτij(t)为所有蚂蚁信息素浓度之和；Q为信息素强度；Lm为蚂蚁所走的路径长度。

3 改进蚁群算法

3.1 障碍物有效顶点

障碍物有效顶点定义及条件：

（1）栅格地图最外围边界上的所有点都不可能成为障碍物的有效顶点。

（2）由当前小栅格与相邻的三个小栅格组成的“田”字形中，当且仅当只有一个障碍物时，田字格的中心点为障碍物的有效顶点。

必须同时满足以上条件才能成为障碍物的有效顶点。例如在图3中栅格13、14、19和20四个小栅格组成“田”字形较大栅格9个点中，点（0，2）、（0，3）和（0，4）为栅格地图最外围边界上的点，不满足条件（1），不是障碍物的有效顶点，分别以点（1，2）、（1，4）和（2，4）为中心的田字格中分别有3个障碍物、无障碍物和2个障碍物，不满足条件（2），不是障碍物的有效顶点，点（1，3）、（2，2）和（2，3）满足上述的两个条件，故为障碍物的有效顶点。图3中有14个障碍物有效顶点，用红色的五角星表示，红色三角形分别为起点（S）和终点（E），定义为广义的障碍物有效顶点（起点和终点分别是有效顶点连接路径的首端和末端），因此图中共有16个有效顶点。

图3 障碍物有效顶点示意图Fig.3 Diagram of effective vertex of obstacles

基于障碍物有效顶点的路径搜索需要对每个有效顶点进行编码，以便于路径的识别和搜索，从下向上，从左向右依次进行编号（起点和终点编号为1和2除外），例如图3中的16个有效顶点，以先后顺序从1编号到16，顺序为S→E→（1，3）→（2，1）→（2，2）→（2，3）→（2，5）→（3，1）→（3，2）→（3，3）→（3，5）→（4，3）→（4，4）→（5，2）→（5，3）→（5，4）。

3.2 改进双向搜索策略

双向蚁群算法路径相遇条件不同于文献[14]信息素相遇条件，即有效顶点相遇条件，具体如图4所示。

图4 障碍物有效顶点路径规划仿真示意图Fig.4 Simulation diagram of effective vertex path planning of obstacles

蚂蚁平均分成两组，一组放在起点位置，从起始点（S）向目标点（E）进行搜索（正向搜索），一组放在目标点位置，从目标点向起始点进行搜索（反向搜索），采用轮流交替从两个方向进行搜索，即先从起点派出一只蚂蚁向目标点进行一步路径搜索（此时的一步并非传统算法的一小步，有可能是多步），然后从目标点派出一只蚂蚁向起点进行一步路径搜索。

当正向搜索一步后，判断与反向搜索的路径有无相同有效顶点，若有，则结束搜索，若没有，则从目标点派出一只蚂蚁向起点进行一步路径搜索，判断与正向搜索的路径有无相同有效顶点，若有，则结束搜索，若没有，则从起点派出一只蚂蚁向终点进行一步路径搜索，再进行判断有无相同的有效顶点，如此反复进行，直到相遇在相同的有效顶点然后从相同的有效顶点分别向起点和终点回溯，形成一条完整的路径并记录。

图4为某两只蚂蚁路径搜索仿真示意图，起点和终点分别编号为1和2，分别加入到road0和road1路径集合中。有一只正向搜索的蚂蚁在起点，根据有效顶点的邻接矩阵可知，下一步有2个可选的有效顶点4和8，再根据状态转移规则，选择有效顶点4，并加入road0集合（此时集合中有1和4两个元素），判断与反向路径无相同的有效顶点，此时反向搜索的蚂蚁从终点出发，根据有效顶点的邻接矩阵，下一步有8个可选的有效顶点5、7、10、11、13、14、15和16，再根据状态转移规则，选择有效顶点13，并加入road1集合（此时集合中有2和13两个元素），判断与正向路径无相同的有效顶点，此时执行正向的路径搜索，根据有效顶点的邻接矩阵，下一步有8个可选的有效顶点5、6、7、8、9、10、12和13，再根据状态转移规则，选择有效顶点9，并加入road0集合。判断与反向路径无相同的有效顶点，此时反向搜索的蚂蚁从终点出发，根据有效顶点的邻接矩阵，下一步有7个可选的有效顶点4、5、9、10、11、12和16，选择有效顶点4，并加入road1集合，判断与正向路径有相同的有效顶点4，则结束搜索，此时road0：S→4→9，road1：E→13→4，最终路径roadlast：S→4→13→E（具体编号规则见上文）。

3.3 改进转移概率公式

改进的启发函数如式（6）所示：

式中，dij表示当前有效顶点与下一有效顶点之间的欧氏距离。a,b为正数。roadxij表示正向或反向搜索，其中x=0,表示正向搜索，x=1,表示反向搜索。

启发函数的改进，相应的转移概率也跟着改变，并引入任一性概率。具体改进转移概率公式如式（7）、（8）所示：

式中，q为[0，1]之间的随机数，q0由反复实验来确定的常数，范围为（0，1），randj为在可选有效顶点中任选其一。

3.4 改进挥发系数

改进的挥发系数能够实现动态调节，如式（9）所示：

式中，ρmin为挥发系数的最小值，T为最大迭代次数，t为当前迭代次数。

3.5 信息素限制策略

为防止算法陷入局部收敛，对信息素浓度进行限制，信息素大小限制范围如式（10）所示：

式中，τmin为信息素最小值，τmax为信息素最大值。

4 改进蚁群算法流程

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

图5 改进蚁群算法流程图Fig.5 Flow chart of improved ant colony algorithm

5 实验仿真与分析

为验证改进算法的可行性、有效性和优越性，在MATLAB 2016a上进行仿真实验。从以下几个方面进行实验验证：在稍微复杂的栅格地图环境中，在相同的参数条件下，将单独改进的单向有效顶点（方案1）、双向有效顶点（方案2）、双向有效顶点+改进启发函数（方案3）、双向有效顶点+改进状态转移规则（方案4）和双向有效顶点+改进挥发系数（包括限制信息素范围）（方案5）依次和传统算法进行仿真对比，然后将整体改进方法分别与传统算法和文献[16]进行仿真对比分析，验证改进方法的可行性以及改进算法的优越性。在大型复杂栅格地图环境下，将改进算法与传统算法和文献[16]算法（使用文献参数）进行对比分析，验证改进算法的优点。

仿真参数设置分别为：

蚂蚁数目为80，最大迭代次数为100，α=1,β=2,Q=50,q0=0.4,a=1.5,b=2。以下结果都是算法运行50次的平均值。

5.1 20×20复杂环境

方案1~5、传统算法、文献[16]算法和本文算法最优路径图分别如图6~13所示，以及仿真结果数据如表1所示。

表1 20×20复杂环境下的仿真结果Table 1 Simulation results under 20×20 complex environment

图6 方案1的最优路径图Fig.6 Optimal path diagram of scheme 1

图7 方案2的最优路径图Fig.7 Optimal path diagram of scheme 2

图8 方案3的最优路径图Fig.8 Optimal path diagram of scheme 3

图9 方案4的最优路径图Fig.9 Optimal path diagram of scheme 4

图10 方案5的最优路径图Fig.10 Optimal path diagram of scheme 5

图11 传统算法的最优路径图Fig.11 Optimal path graph of traditional algorithm

在验证改进算法整体改进的优越性前，设置梯度方案，即由于改进算法的特殊性，不能直接将某一个改进的点加入传统算法进行比较，而是在单向有效顶点路径搜索基础上设置梯度方案，验证改进点的可行性。梯度方案为方案1~5，分别对应单独添加有效顶点，单独使用有效顶点，双向有效顶点+改进启发函数，双向有效顶点+改进转移规则和双向有效顶点+改进挥发系数。

经仿真数据可知，在最优路径、拐点数和收敛速度方面，单向有效顶点都优于传统算法，验证有效顶点的可行性和优越性，在单向基础上添加反向，即双向有效顶点，在最优路径、拐点数和收敛速度方面进一步改善，说明双向搜索的优越性，然后在双向的基础上分别加入改进启发函数、改进转移规则和改进挥发系数，在拐点数和算法运行时间上，再一次改善，在最短路径或者最短路径的稳定性上也得到相应的改善，验证改进点可行性和有效性。

最后将整体改进算法与传统算法和文献[16]算法进行比较，三种算法都能找到各自的最短路径，分别为27.932 0、35.071 1和29.799 0，由此可知，改进算法找到的路径最短，在拐点数和收敛速度方面占有较大优势，总之，改进算法得到的最短路径、拐点数和收敛速度都优于传统算法和文献[16]算法。

图12 文献[16]的最优路径图Fig.12 Optimal path graph of reference[16]

图13 本文算法的最优路径图Fig.13 Optimal path graph of proposed algorithm

图15 文献[16]算法最优路径图Fig.15 Optimal path of algorithm in reference[16]

5.2 30×30复杂的环境

为进一步验证改进算法也能适用于更加复杂环境，因此在复杂环境下进行仿真。传统算法、文献[16]算法和本文算法的最优路径图分别如图14~16所示，以及三种算法仿真结果数据如表2所示。

图14 传统算法的最优路径图Fig.14 Optimal path graph of traditional algorithm

表2 30×30复杂的环境下三种算法的仿真结果Table 2 Simulation results of three algorithms in 30×30 complex environment

通过比较仿真数据，改进算法得到的路径最短为41.061 1，拐点数最少为2，路径几乎接近起点和终点的连线，且它们的平均值和标准差最小，文献[16]次之，传统算法最大，平均值和标准差的大小能够反映在最小值附近的波动大小以及稳定性，也可以反映该最小值出现机会的大小，如在50次的运行结果中，传统算法找到的最短路径59.899 5出现1次，相应的平均值和标准差较大，改进算法找到的最短路径41.061 1出现32次，相应的平均值和标准差较小。由于传统算法盲目性大，启发信息较弱，在路径搜索时，拐点较多，有时出现回环交叉，远离目标行走，导致路径长度增加。在收敛速度和算法运行时间方面，改进算法和文献[16]算法都优于传统算法，其中改进算法稍逊于文献[16]算法。

图16 本文算法最优路径图Fig.16 Optimal path graph of proposed algorithm

6 结束语

在静态的全局路径规划中，本文对传统蚁群算法的不足，提出了一种改进双向蚁群算法。双向蚁群算法结合障碍物有效顶点进行路径搜索，能够快速找到最优解且得到的路径拐点相对较少；改进的启发函数与当前有效顶点和下一可选有效顶点有关，能够实现一步或多步行走（相对于传统算法）；改进的状态转移规则能够加快收敛速度；改进的挥发系数能够避免陷入早熟。基于以上的改进，本文算法能够很好地适用于不同尺度和不同复杂程度的栅格地图。总之，从小型简单的栅格地图中，已经证明了改进算法的优越性，在大型复杂栅格地图中能够明显地验证改进算法可行性、有效性和优越性。