基于有效拐点和最短最小路径的蚁群路径规划方法

褚凯轩 常天庆 王全东 闫晓东

(1.陆军装甲兵学院兵器与控制系， 北京 100072； 2.军事科学院评估论证研究中心， 北京 100091)

0 引言

路径规划是移动机器人在具有障碍物的环境约束下，根据给定的起点和终点，应用算法准则，找到一条最优或接近最优的、安全、无障碍路径[1-2]。路径规划主要包括环境建模和路径规划算法两部分。

栅格图法是环境建模的经典方法[3]，栅格图将地图切割成相同大小且相互连接的栅格，每个栅格对应相应位置信息，能在考虑全局优化的基础上兼顾较小的计算量, 对特定感知系统的假设参数不敏感，具有较强的鲁棒性[4]，目前被广泛运用于机器人、自动驾驶的运载器等领域[5-7]。栅格图下，传统的路径搜索方式主要有4邻域4方向搜索方式和8邻域8方向搜索方式。徐菱等[8]提出一种24邻域16方向的搜索方式，使路径搜索具有更广的搜索范围和更多的方向选择。但是有限方向有限邻域使机器人每次只能在相邻栅格间转移，增大了搜索次数和步数。曾明如等[9]提出了一种搜索范围不局限于相邻栅格的多步长栅格图法，能搜索出一条转移步数更少的路径,该方法在面临较大规模地图时计算量巨大。文献[10-11]提出直接将信息素存放于栅格中而不是存放于路径上，这种信息素存储方式可以降低算法的复杂度，但是由于失去了方向性，在大规模栅格路径规划中易发生闭锁和折回的现象。

路径规划算法主要有局部避障算法、基于几何模型算法和智能搜索算法。局部避障算法包括人工势场法[12]和动态窗口法[13]。人工势场法通过模拟障碍物产生的斥力场和终点产生的引力场，推动机器人避障并向终点移动。动态窗口法是在速度空间中采样多组数据，并模拟移动机器人以这些速度在下一时间段内的轨迹并对轨迹进行评价，选取最优轨迹对应的速度来驱动机器人运动。基于几何模型算法主要有Dijkstra算法[14]和A*算法[15]，Dijkstra算法计算起始点到其他所有点的最短路径长度，是广度优先搜索，具有较高的空间复杂度和时间复杂度，而A*算法是一种启发式算法，是一种深度优先的算法。智能搜索算法有蚁群算法[16-19]、遗传算法[20]、粒子群算法[21]、人工蜂群算法[22]等，是利用群体智能的快速收敛特性寻找最优解。路径规划属于NP-hard问题,因此很多学者采用启发式群智能算法进行求解。蚁群算法模拟自然界蚂蚁寻找最短觅食路径，每只蚂蚁在觅食时都会在路径上留信息素，并且路径越短，信息素浓度越高。蚂蚁更倾向于沿着信息素浓度较高的路径行走，并继续在路径上留下新的信息素。通过上述正反馈效应，最终蚁群路线收敛到信息素浓度最高的最短路径上。蚁群算法具有鲁棒性好、全局搜索能力强、环境约束表达方便等优势，被广泛应用于路径规划问题中。传统的蚁群算法存在迭代次数多、搜索效率低等缺点。为了解决这些问题，LEE[16]提出了一种基于异构蚁群的路径规划方法，该方法改进了蚁群的转移概率函数和信息素更新规则，在不需要后续平滑处理的情况下可以直接找到节点数较少的最优路径；ZHANG等[17]提出了一种智能蚁群路径规划算法，该方法通过消除蚁群算法中禁忌表的约束，引入临时权值矩阵，避免了小权值路径的重复选择，提高了算法的效率；LEE等[18]改变了蚁群算法生成初始种群的方式，缩短了寻找最优解的时间，加快了算法的收敛速度；SAIDI-MEHRABAD等[19]将蚁群算法分为两个阶段进行路径搜索，有效缩短了路径规划的完成时间。刘可等[23]采用参数迁移的方法对蚁群算法进行参数优化，利用先验知识有效解决蚁群算法路径规划时的参数选择问题。张强等[24]在蚁群算法中构建负反馈通道，使全局信息素和局部信息素的更新速率跟随收敛次数的变化自适应调节，使收敛速度与全局搜索精度协调统一。

本文在栅格地图中提出有效拐点，使路径规划能够以任何方向、任何距离的栅格作为下一步的目标栅格的方法，以提高搜索效率并降低转弯频率。提出最短最小路径并给出计算方法，将最短最小距离作为蚁群算法的启发值，作为阈值来指导信息素更新，以期提高引导效率和算法前期的收敛速度，并提高信息素更新的质量。

1 基于拐点的栅格图

栅格图将地图切割成相同尺寸且相互连接的栅格，每个栅格对应相应位置信息。3种典型栅格图搜索方式如图1所示。

本文提出一种能够以任何方向、任何距离的栅格作为下一步目标栅格的搜索方式，大大提高了搜索效率并降低转弯频率。如图2所示，在某一无障碍的环境中，采用4种搜索方式搜索机器人运动轨迹，考虑到地图设定简单，采用常规蚁群算法[8]进行路径搜索，蚁群算法关键参数有：迭代次数K=10，蚂蚁数量m=20，信息素启因子α=2；启发函数因子β=3，信息素蒸发系数ρ=0.3。由图2可以看出，4邻域4方向搜索方式只能走直线拐直角，从起点到终点最短路径长度为14，步数为14；8邻域8方向搜索方式可以走45°，从起点到终点的最短路径长度为9.1，步数为7；24邻域16方向搜索方式从起点到终点的最短路径为8.7，步数为5；本文的搜索方式可以取捷径直达终点，路径长度为8.6，步数为1。

邻域数量的增多，意味着单步搜索空间增大，为了降低单步搜索的计算量，本文提出栅格拐点。考虑最短路径一定会绕过障碍栅格，因此搜索过程中仅需考虑障碍物的邻域栅格，即拐点一定是障碍物的邻域栅格。采用滑动窗口的方法寻找拐点，设定2×2滑动窗，遍历整个地图，当窗内仅有1个障碍物栅格时，将窗内其他3个栅格均设定为拐点；当窗内有2个障碍物栅格，且位置处于对角，则将另外一对对角的2个栅格设定为拐点。几种典型拐点如图3所示，其中黑色表示障碍物栅格，白色表示可通行栅格，红色表示拐点。路径搜索时，只需要搜索拐点。通过设定拐点，可以大大减少单步搜索的工作量。

2 最短最小路径

能够快速、准确地估计各搜索节点到终点的距离对于全局的路径规划具有重要意义。如在A*算法中，当前节点i的代价函数为f(i)=g(i)+h(i)，式中g(i)是移动机器人从起点到当前节点i走过的实际距离，h(i)是从当前节点i到终点的估计值。g(i)是准确值，而h(i)是估计值，正确选择h(i)函数可以提高A*算法中搜索和选择的科学性。传统方法采用欧氏距离[3]表示h(i)。

启发式算法中，需要用搜索节点的启发值计算选择概率，而启发值由搜索节点到终点的距离估计值决定。例如在蚁群算法中，选择概率由信息素浓度和启发值共同决定，在迭代初期，路径信息素浓度差别不大，主要依靠启发信息选择节点，因此准确的启发值有利于快速收敛。常见的蚁群算法[11，25]、蜂群算法[26]也多采用欧氏距离函数表示搜索节点到终点的距离估计值。

采用欧氏距离，即认为搜索节点可取捷径到达终点，使得距离终点直线距离更近的点更容易被选择，但是当捷径路线上存在障碍物时，这种选择倾向可能是错误的。如图4所示，起点为S，终点为E,考虑A、B两点，点A距离终点E的直线距离明显小于点B距离终点E的直线距离，但是由于AE之间存在障碍物，无法通行，因此更近的路径是S-B-E。如果能够在搜索节点到终点的距离估计中，发现B到E的距离比A到E的距离更近，可大大提高节点搜索和选择的科学性。

本文提出最短最小路径，并用最短最小距离代替欧氏距离，用于算法前期搜索节点的启发值。当起点、终点和拐点确定后，根据栅格点之间是否可直达，构造从起点到终点的贯通树。具体操作为：

增枝操作步骤如下：①将终点E置于最底层L0。②将所有与上一层Ln-1可通的点置于当前层Ln。③判断起点S是否在当前层，如果S∈Ln，则算法结束，否则转步骤②。

增枝操作得到贯通树T1。增枝操作依据各点到达终点的步数，对有效栅格进行分层。最底层为终点栅格；第2层为所有与终点栅格可通的点；第3层为所有与第2层任一点可通的点；以此类推，最上层为起点栅格和所有与起点栅格处于同一层的点。

剪枝操作步骤如下：①最上层仅保留起点栅格，其它栅格从最上层中删除。②保留当前层Ln中与上一层Ln+1可通的点，其它点从当前层删除。③如果检索到L0，则算法结束，否则转步骤②。

剪枝操作得到贯通树T2。

设从起点到终点的某条路径Rout=[a1(S),a2,a3,…,a(E)],令ci表示点ai所在的层数，如果Rout为最短路径，必满足ci≥ci+1,即下一个点必须在当前点所在层或距离终点更近的层，不可能是远离终点的一层。基于这一条规律，在启发式路径搜索中，只需要搜索与当前节点处在同一层的点和当前节点的下一层点，而不需要搜索所有与当前点可直达的拐点，可以大大减小搜索压力。

设从起点到终点的某条路径Rout=[a1(S),a2,a3,…,a(E)]，当对于任意i，均满足ci>ci+1时，Rout为最小步数路径。所有最小步数路径中的最短路径称为最短最小路径。本文用最短最小路径的长度作为蚁群算法前期的启发值。

3 蚁群算法求解最短路径

为了配合前文的拐点栅格和最短最小路径，本节对蚁群算法进行特定的设计和改进。蚁群算法路径规划流程见图5。

3.1 有效拐点和最短最小路径

首先删减地图中的无效拐点，并计算有效拐点到终点的最短最小距离，步骤如下：

(1)构造栅格地图，并用两种滑动窗循扫整幅地图，找到所有拐点。

(2)采用增枝操作，得到贯通起点到终点的贯通树T1，采用剪枝操作，得到贯通树T2，保留贯通树T1最上层的拐点和贯通树T2中所有的拐点为有效拐点，其余拐点均视为无效拐点。

(3)初始化信息素矩阵，如果节点i、j满足：Li≥Lj或栅格点i与栅格点j不可直达，则将从节点i到节点j的路径上的信息素强制置零。

(4)计算所有有效拐点到终点的最短最小距离，存放于距离期望矩阵中。

3.2 转移概率

蚂蚁从当前栅格i到下一处栅格j的转移概率为

(1)

(2)

式中α——信息素启发因子

β——启发函数因子

allowed——可选择的栅格点集合

τij——点i到点j的信息素浓度

ηij——蚂蚁从点i到点j的启发信息

τis——点i到点s的信息素浓度

ηis——蚂蚁从点i到点s的启发信息

dij——点i到点j的距离

dj→end——点j到终点的距离期望

3.3 距离期望

初始时，用点j到终点的最短最小转弯路径长度作为距离期望。迭代过程中，实时更新距离期望矩阵，当蚂蚁搜索到一条从起点到终点的可行路径Rout=[a1(S),a2,a3,…,a(E)]，比较中间节点ai沿该条可行路径到终点E的实际距离与节点ai到终点的当前距离期望，如果实际距离小于距离期望，则用该距离代替距离期望。

3.4 信息素更新

算法每次迭代中,让所有蚂蚁各自完成一次路径搜索,并在每只到达终点或出现死锁时停止搜索，每次迭代结束后,根据各蚂蚁搜索到的路径，各栅格的信息素浓度为

(3)

式中m——蚁群数量

此处改进在于，由于已经有了最短最小转弯路径作为参考，本文认为只有蚂蚁成功搜索到终点，且长度小于等于最短最小转弯路径的长度才算对群体有贡献，因此信息素浓度增量取

(4)

式中Q——常数

dk——蚂蚁k从起点到终点走过路径的距离

dm——起点到终点的最短最小距离

4 仿真实验

为了验证本文算法的有效性和可行性,通过仿真实验对算法的相关性能进行验证，并与文献[8]中提出的方法进行对比。仿真实验运行环境:操作系统Windows 7(64位),处理器Inter(R) Core(TM) i5-4590U, CPU3.30 GHz,内存8 GB,仿真平台Matlab R2016a。

4.1 最短最小距离和欧氏距离统计实验

为了验证本文提出的用最短最小距离作为启发值的方法的科学性，进行最短最小距离和欧氏距离统计实验。随机生成100幅规模为30×30、障碍比例为0.2～0.4的栅格地图并从中随机选取起点和终点(每幅地图可取多组起点和终点)，求取起点和终点间的最短最小路径和欧氏距离，同时用本文的蚁群算法计算起点到终点的最近路径，蚁群算法关键参数：迭代次数K=50，蚂蚁数量m=50，信息素启因子α=3；启发函数因子β=6，信息素蒸发系数ρ=0.3。路径距离见表1，其中R表示最短最小距离(欧氏距离)与用本文蚁群算法求得的最短距离的比值。

表1 路径距离Tab.1 Path distance

由表1可以看出，即使拐点层数达到12，最短最小距离和最短距离的比值仍小于1.08，说明最短最小距离可以很大程度上体现起点到终点的距离；而欧氏距离与最短距离的比值随着层数的增多，比值减小到0.354，说明二者差距逐渐加大。由此可以看出，用最短最小距离作为搜索节点的启发值更准确可靠。

4.2 有效拐点数量和单步搜索空间统计实验

蚂蚁在选择下一步节点时,长远的视野范围可以帮助蚂蚁更好地规划路径，但是也造成了单步搜索空间巨大而不利于快速收敛。为解决这个问题，本文基于最短路径和障碍栅格的关系，提出拐点栅格，并通过增枝操作进一步删减掉无效拐点；同时，基于增枝贯通树中栅格点的层级关系，进一步减小了蚂蚁单步移动需要搜索的栅格数量。

为了便于直观地理解增枝操作在减少有效拐点数量和减小单步搜索空间方面的作用，仿真算例如图6所示。图6a为原始栅格地图，白色表示可通行，黑色表示障碍物，左上角为起点，右下角为终点。图6b为拐点地图，红色栅格为拐点。图6c为经过增枝操作生成的分层地图，图中紫色栅格为L0层的点，也就是终点，绿色栅格为L1层的点，也就是所有与L0层的点可直达的点，同理深蓝色为L3层的点，浅蓝色为L4层的点，起点位于L4层中，而图6c中的红色点即为淘汰的无效拐点。可以看出，通过增枝操作减小了有效拐点的数量。由于在最短路径中，下一步到达的点必须是当前点所在层的点或距离终点更近的层中的点，而不可能是远离终点的一层中的点，由此可以明显减少单步搜索空间，以起点为例，当前单步搜索只需要搜索L4层的点(浅蓝色)和L3层的点(深蓝色)，而不需要搜索其他的有效拐点。同时通过节点间是否可直达的限制，进一步删减一部分待搜索的拐点，可以明显减少单步搜索的压力。

为了进一步验证本文方法在减少有效拐点数量和减小单步搜索空间方面的作用，设定地图规模为15×15、30×30、60×60，障碍栅格比例为0.2、0.3、0.4、0.5，共计12种地图下，重复实验20次，统计有效拐点数量和单步搜索空间的平均值。平均有效拐点数量见图7，平均单步搜索空间见图8。

由图7、8可以看出，虽然本文采取了无限邻域的搜索方式，但是由于有效拐点概念的提出删减了大量无效栅格点，使得每幅地图的平均有效拐点数和平均单步搜索空间都在可接受的范围内。对比常规的有限邻域有限方向搜索方式，可通行栅格数和平均单步搜索空间见表2，本文搜索方式的有效拐点数量远远小于常规搜索方式的可通行栅格数，平均单步搜索空间略高于常规搜索方式的平均单步搜索空间。

表2 常规搜索方式可通行栅格数和平均单步搜索空间Tab.2 Number of passable grids and average single step search domain of conventional search methods

4.3 对比实验

文献[8]采用16方向24邻域的蚂蚁搜索方式,并结合向量夹角的思想设计2种启发信息的计算方法，并在转移选择时采用δ-贪婪策略。首先采用文献中的地图进行对比实验。对比方法和本文方法搜索到最优路径如图9所示。

文献[8]方法和本文方法搜索到最优路径的长度和步数比较见表3。经人工分析，图9a、9b、9d、9e中的路径都是相应搜索规则下的最短路径，可以看出，本文方法得到的最短路径，在路径长度和步数上均优于文献[8]方法的最优路径。

为了进一步验证本文算法的优越性，设定地图规模为15×15、30×30、60×60，障碍栅格比例0.2、0.4，随机生成6幅地图。为了便于读者复现和验证，采用rand(‘state’,0)锁定随机地图。如生成规模为15×15、障碍比例为0.2的地图，代码为

表3 最优路径比较Tab.3 Comparison of optimal path

rand(‘state’,0);

G=rand(15);

Map=double(G<0.2)；

分别用本文算法和文献[8]方法求解每幅地图的最短路径，每幅地图重复实验10次。蚁群算法关键参数：迭代次数K=50，蚂蚁数量m=50，信息素启因子α=3；启发函数因子β=6，信息素蒸发系数ρ=0.3，文献[8]算法采用method 1作为启发信息计算方式，贪婪选择概率δ=0.8。本文算法和文献[8]算法最优路径对比见表4。

可以看出，本文方法在路径长度、步数、迭代次数方面均优于文献[8]方法。由于本文提出的搜索方式不受距离限制，随着地图规模增大，所需步数的增加速度较慢，而对比算法的步数随地图规模的增大快速增多,因此随着地图规模增大，本文算法相对于对比算法，步数这一指标的提升愈加明显，更短的步数意味着更少的出错概率和更高的可靠性，利于快速收敛。文献[8]算法在贪婪选择中增加了参数δ，有一定概率随机选择栅格，有利于跳出局部最优解但减缓了收敛速度。因此本文算法比文献[8]算法需要更少的迭代次数。本文方法求得的路径距离更短的原因有：①由于搜索方式的改进，对于远距离的可直达栅格点，机器人可以直接取捷径通过，避免不必要的弯折。②本文方法步数少而带来的低错误率和高收敛精度优势。

表4 本文方法和文献[8]方法最优路径对比Tab.4 Comparison of optimal path of proposed method and Literature[8] method

5 结论

(1)针对栅格图环境下的路径规划问题，提出了一种基于有效拐点和最短最小路径的蚁群路径规划方法。在栅格地图中采取无限邻域的搜索方式，使机器人可取捷径直达任何可直通的栅格点，同时为了减小搜索量，提出有效拐点的概念，大大减小了搜索空间。提出最短最小路径的概念，并用其取代欧氏距离作为启发值，提高了启发值的准确度和可靠性，同时用起点到终点的最短最小距离，指导信息素更新，提高了蚁群算法迭代的质量。

(2)不同规模和复杂度环境的仿真实验表明,本文方法与常规栅格搜索方式下的蚁群路径规划方法相比有较大的提升，有效减少了路径长度和步数,加快了算法的迭代收敛速度。