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

　　摘 要：针对机器人在静态环境下全局路径规划存在无法找到最短路径，收敛速度慢，路径搜索盲目性大，拐点多等问题，提出一种改进双向蚁群算法。以栅格地图为机器人运行环境，对障碍物有效顶点进行定义、编码和运用，同时结合以相同障碍物有效顶点为相遇条件的双向蚁群算法，双向交替进行路径搜索，能够快速地找到更短路径，得到的路径拐点更少;引入改进的状态转移规则，能够加快搜索速度;在启发函数中引入可调常数因子，在以障碍物有效顶点为路径搜索的节点，每走一步相当于传统算法的一步或多步行走;动态调整挥发系数并设置信息素浓度范围，能够避免陷入早熟。通过与其他算法仿真对比，验证了改进算法的可行性、有效性和优越性。

　　本文源自李二超; 齐款款， 计算机工程与应用 发表时间：2021-06-03

　　关键词: 移动机器人;路径规划;蚁群算法;双向路径搜索;障碍物有效顶点

　　静态环境下的移动机器人路径规划是指在已知环境中，按照一定的算法，根据目标函数(如距离最短等)，寻找一条从起点到终点的安全且最优路径[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)。

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

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

　　2 传统蚁群算法

　　状态转移概率公式如式(2)所示。 [ ( ) ] * [ ( ) ] , [ ( ) ] * [ ( ) ] ( ) 0 , m ij ij m m is is i j s a llo w e d t t j a llo w e d t t t o th e r w is e p        (2) 式中： m j a llo w e d 为待选节点集合; ( ) ij  t 为信息素浓度; ( ) ij  t 为启収信息，用当前节点 i 到下一节点 j 的欧式距离的倒数表示;和分别表示信息素因子和启収式因子。

　　信息素更新公式如式(3)、式(4)和式(5)所示。 ( 1) (1 ) ( ) ( ) ij ij ij     t t t      (3) 1 ( ) = ( ) n m ij ij m   t t    (4) , ( , ) ( ) = 0 , m i j m Q i j  t L  蚂 蚁 m 经 过 了 路 径未 经 过 (5) 式中， ( 1) ij  t 为更新后的信息素浓度;为信息素挥収系数; ( ) 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 个有效顶点。

　　基于障碍物有效顶点的路径搜索需要对每个有效顶点进行编码，以便于路径的识别和搜索，从下向上，从左向右依次进行编号(起点和终点编号为 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 所示。

　　蚂蚁平均分成两组，一组放在起点位置，从起始点(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 改进转移概率公式

　　式中，dij 表示当前有效顶点与下一有效顶点之间的欧氏距离。a，b 为正数。road0ij 表示正向搜索，road1ij 表示反向搜索。

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

　　3.4 改进挥发系数

　　式中： m in 为挥収系数的最小值，T 为最大迭代次数， t 为当前迭代次数。

　　3.5 信息素限制策略

　　为防止算法陷入局部收敛，对信息素浓度进行限制。 m in m in m in m a x m a x m a x

　　4 改进蚁群算法流程

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

　　5 实验仿真与分析

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

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

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

　　5.2 30×30 复杂的环境

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

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

　　6 结束语

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