蚁群算法在移动机器人全局路径规划的应用中，具有搜索时间长、过程易停滞、错失全局最优解等方面的问题.针对蚁群算法在应用过程中出现的这些问题，许多研究者提出了相应的改进方法.文献^[1]提出HACO算法，确保算法规划的路径为最短路径；文献^[2]采用两个搜索阶段解决算法效率与优化结果之间的平衡问题；文献^[3]针对特定环境地图进行了相应的路径规划研究，规划结果令人满意.

综上，当前的蚁群优化算法^{[4, 5, 6]}在应用于某些特定环境地图时均取得了很好的规划成果.经研究发现，上述的蚁群算法在应用过程中不具备通用性，即对于随机给出的环境地图，规划结果并不总是令人满意，规划算法对环境地图有很强的依赖性^{[7, 8, 9]}.为此，本文通过改进蚁群算法，并将几何优化思想融入到蚁群全局规划算法中，使得改进后的全局路径规划算法在地面移动机器人的全局路径规划中具有普遍适用性.

栅格法建立的环境地图简单明了，便于数据处理.在本文的研究中，蚁群算法应用环境是平面二维栅格环境地图，栅格地图以地面移动机器人的几何尺寸为依据，建立具有二值(0或1)环境空间.在环境地图-栅格地图的转换过程中，需要注意以下几个方面.

1) 当障碍物占用不满一个栅格，同时扩充该障碍物以及周围其他障碍物后，障碍栅格之间仍有至少一个自由栅格时，可以将障碍物进行扩充，占满栅格，如图 1a所示.

图 1(Figure 1)

Fig. 1

图 1 栅格地图的建立 Fig. 1 The establishment of grid map (a)—障碍物之间距离很远； (b)—障碍物之间距离一般； (c)—障碍物之间距离很近； (d)—环境地图； (e)—栅格地图.

2) 当障碍物占用不满一个栅格，同时扩充该障碍物以及周围其他障碍物后，障碍栅格之间没有自由栅格时，处理过程如下：对于图 1b所示情况，障碍物之间的最短距离d大于一个栅格长度时，根据尽可能少地改变环境信息的原则，以及障碍物A与B对周围环境的影响，将障碍物A的占用栅格进行缩减，对障碍物B的占用栅格进行扩充，这样可以方便后续的障碍物栅格化；而对于图 1c所示的障碍物之间最短距离d小于一个栅格长度，由于在实际环境中机器人不可能通过如此狭窄的空间，则直接将障碍物A与B所占用的栅格扩充成障碍栅格即可.

3) 由于移动机器人的越障能力受限，对于环境地图中的某些特殊地形(针对研究应用的移动机器人提出的，不同的移动机器人越障性能不同，该部分的转换要求亦不同)，亦需要转换成障碍物栅格.本文应用的移动机器人越壕宽为15.2cm，垂直越障高度为10cm.结合上述性能，对于环境地图中宽度大于15.2cm的沟以及垂直高度大于10cm的台阶，都需要进行栅格障碍化.图 1d和图 1e展示了路边人行道以及道路中坑的栅格化过程.

以上即为结合移动机器人几何尺寸与越障性能的栅格地图创建规则.

针对蚁群算法搜索时间过长这一问题进行了详细的研究，发现造成该问题的原因之一是初始时刻蚂蚁开始寻找路径时的方向不确定性.为了改善问题，加快搜索速度，使蚁群在初始搜索时具有一定的明确运动方向，本文设计了一种随距离递减的信息素初始化方式.

数学模型如下：

蚁群算法中的信息素挥发系数ρ的大小直接影响算法的全局搜索能力及其收敛速度.ρ过大时，信息素挥发过快,环境信息素对蚂蚁方向的选择影响度减少,搜索时间增加；ρ过小时，路径上的环境信息素会滞留过多，同样影响蚂蚁对路径方向的选择，不利于蚂蚁对优秀路径方向的发现.因此，合理地选择挥发系数ρ，亦成为算法运行速度快慢的关键问题之一.

本文提出了一种自适应调整挥发系数ρ的解决策略.其调整策略如下:

蚁群算法中的每一只蚂蚁在移动过程中都具有路径记录功能，设置路径记录的长度是为了更好地利用优秀的路径信息，淘汰无利用价值的路径信息.路径长度len_d的定义如下：

为了加快蚁群算法的收敛速度，增加算法对最优路径的敏感度，算法设计的信息素更新原则如下：蚂蚁散播的信息素在总量相同的情况下，根据蚂蚁找到路径的优劣程度，最终确定其路径上

信息素的数量.如果找到的路径是最短路径，则增加信息素的投放量.

信息素投放公式如下：

通常蚁群算法在路径规划应用过程中的结束标志是蚂蚁到达目标点的数量达到一定要求，这种设置方法易受蚁群大小的影响，具有一定的局限性.本文设计如下判断依据作为算法结束与否的标志，该依据可以根据需要自动调整算法结束时间.

当L_k－Lmin< Lmin/12时，food_min++；

当food_min>MAX_ANT/2时，算法结束.

由于蚂蚁受到“视野”、运动方向的保持以及运动步长等方面的限制，根据上述改进的蚁群算法规划出的全局路径经常会带有回转，如图 2所示.回转路径既增加了路径长度，又不利于移动机器人按照规划路径行进的运动控制，因此必须对其进行修正处理.修正的目的一方面减少规划路径的长度，另一方面减少规划路径的转折次数，平滑规划路径.

图 2(Figure 2)

Fig. 2

图 2 路径修正示意图 Fig. 2 v

假设已知蚁群算法规划出的路径可以表示为l={H,a,b,c,d,e,F}，其中路径转折点分别为a，b，c，d，e等.

路径修正流程如下：

首先，分别求出等矢量的方向.

其次，以矢量为起点，通过确定相间(中间间隔一个矢量)矢量的方向，判断该段路径是否需要修正，判别公式如下：

最后，根据下述路径修正规则进行修正.

如图 2所示，以H为起点，矢量与矢量方向相反，则该段路径无需修正.否则，需要判断矢量与矢量之间有无障碍物，若没有障碍物，则需进行路径修正，修正后的路径变为l={H,a,f,d,e,F}.

确定新路径的拐点以及各矢量的方向，按照上述修正流程对新路径重新进行修正处理，直至遍历整条路径.完成路径修正任务之后，算法将转向路径交叉优化模块.

路径交叉优化的目的是为了加快算法收敛速度，确保规划出最优路径.在本文中，最优路径不是指当前蚂蚁走过的最短路径,而是通过路径交叉优化后的最短(或转向最少)路径(如图 3所示)，即路径优化是对蚁群算法全局路径规划结果的有益补充.

图 3(Figure 3)

Fig. 3

图 3 路径交叉优化示意图 Fig. 3 Cross-path optimization schematic

图 3中，假设算法当前规划的最短路径为lmin={H,a,b,c,d,e,f,F}，与lmin不相交的次短路径为l′min，蚂蚁当前找到的路径为l={H,m,d,e,f,F}.

蚂蚁交叉优化准则如下.

当两个相交节点简单路径长度不一致时，以保留最短路径段的原则对最优路径进行修正.当两个相交节点的路径长度一致时，以转向次数最少的路径段作为对最优路径的修正.如图 3所示，路径段{H,a,b,c,d,e}与路径段{H,m,d,e}两者的路径长度相同，前者转向次数为4，后者转向次数为1，因此，规划的最优路径为后者.

蚁群几何优化算法基于C语言开发实现，其算法步骤如下：

步骤1 设置参数，并生成随机栅格地图.随机生成环境地图，设置起始点H与目标点F的栅格坐标，设置信息素挥发时间t_min；初始化蚂蚁种群数量MAX_ANT；初始化结束条件的计数器food_min；计算自由栅格与F栅格的距离，设置初始环境信息素；设置信息素挥发系数ρ，以及蚂蚁携带的信息素总量Q.设置road1与road2用以保存最短与次短路径坐标，lenth1与lenth2分别用以记录最短与次短路径长度.

步骤2 初始化蚂蚁.初始化蚂蚁当前位置坐标(x,y)、行走方向ant_dir、行进位置记录ant_tr、路径长度ant_con，以及发现食物标志F_find.

步骤3 蚂蚁移动.判断当前坐标周围是否有F栅格.如果有，直接移动至目标栅格，同时转向步骤6；没有，计算蚂蚁的方向转移概率，确定蚂蚁的行进方向.当两个方向的转移概率相同时，蚂蚁总是具有保持前一时刻方向的特性；同时蚂蚁又以轮盘赌的方式小概率地随机选择方向.记录蚂蚁位置坐标、更新路径长度.

步骤4 判断路径长度是否超过限制.如果蚂蚁当前已走的路径长度超过设置，蚂蚁自然消亡，重新从起点H出发；否则，转向步骤5.

步骤5 判断是否达到信息素挥发时间.时间计数器达到，进行全局信息素挥发更新；否则，转向步骤3.

步骤6 路径修正模块.当蚂蚁到达终点后，提取蚂蚁找到的路径信息，进入路径修正模块，根据修正规则对路径进行优化处理.

步骤7 路径信息素更新.根据信息素散播规则，对相应的路径点散播信息素.

步骤8 路径优化模块.根据路径修正结果，将规划路径与最优路径或者次优路径进行交叉优化，修正最优或者次优路径.

步骤9 根据路径修正结果，将其与最优路径进行对比，确定计数器food_min的状态，如果达到计数器上限，转向步骤10.

步骤10 算法结束，输出最优路径的坐标点及其长度.

本文将从以下4个方面对蚁群几何优化算法的性能进行仿真实验研究：①信息素初始化对比 测试；②信息素挥发系数对比测试；③信息素散播准则对比测试；④路径优化结果测试.

仿真实验初始条件设置如下：

蚁群大小MAX_ANT为30，tmin为0.05 s，ρ=0.1，β=5，α=1，D=1.

随机生成57×23的栅格地图，其中H表示蚂蚁的起始点，F表示规划的目标点.最优路径运 行结果中，X表示应用改进算法获得的最优路径，O表示初始蚁群算法获得的部分规划路径.

选取5张最优路径通过狭窄通道的环境地图(图 4所示)进行测试,表 1中展示了算法完成规划任务的时间与规划成功率统计结果.对同一环境地图，分别应用两种不同算法进行20次规划仿真测试，取实验结果的平均值.由测试结果可以看出，在环境地图中递归设置初始信息素，有利于加快蚁群算法的收敛速度，提高最优路径质量.

图 4(Figure 4)

Fig. 4

图 4 信息素初始化对比测试 Fig. 4 Comparison test on initial pheromone

表 1

Table 1

表 1(Table 1)

表 1 信息素初始化对全局路径规划结果的影响 Table 1 Effect of pheromone initialization on the global path planning 参数 改进算法 原始算法 ① ② ③ ④ ⑤ ① ② ③ ④ ⑤ 规划时间/s 8.32 10.61 6.87 9.03 7.84 10.64 11.8 8.44 9.87 8.53 最优解/步 62 83 47 72 56 71.2 95 68 84 67 规划成功率/% 100 100 100 100 100 30 30 40 35 25

表 1 信息素初始化对全局路径规划结果的影响 Table 1 Effect of pheromone initialization on the global path planning

对图 5所示的环境地图(即起始点或目标点位于凹型障碍物内部)进行信息素挥发系数对比测试，共选取5张类似环境地图进行全局路径规划测试.表 2中列出了规划算法分别在5张环境地图中的平均规划时间，每张环境地图的测试结果均为20次测试时间的平均值.测试结果表明，加大初始环境信息素的挥发系数，有利于改善如图 5所示环境地图的规划时间对全局路径规划效率的影响，加快规划速度，增强算法的普遍适用性.

图 5(Figure 5)

Fig. 5

图 5 挥发系数测试 Fig. 5 Test on volatile factor

表 2

Table 2

表 2(Table 2)

表 2 不同信息素挥发系数对全局路径规划时间的影响 Table 2 Effects of different pheromone evaporation coefficient on the global path planning s 算法 地图序号 ① ② ③ ④ ⑤ 原始算法 8.93 10.34 15.67 7.64 6.74 改进挥发系数算法 9.02 9.89 11.63 7.78 6.21

表 2 不同信息素挥发系数对全局路径规划时间的影响 Table 2 Effects of different pheromone evaporation coefficient on the global path planning

对图 6所示的环境地图，分别进行三种不同的信息素散播准则对规划时间影响的对比实验：一步散播、规划路径散播以及本文提出的加权散播准则，选取5张类似环境地图进行全局路径规划对比测试.表 3中列出了规划算法分别在5张环境地图中的平均规划时间，每张环境地图的测试结果均为20次测试时间的平均值.由表中实验数据可以看出，以路径的优劣程度确定信息素的散播准则有利于加快算法的规划速度，大大缩短了规划时间，表明该准则的有效性.

图 6(Figure 6)

Fig. 6

图 6 信息素散播准则对比 Fig. 6 Test on pheromone spread standards

表 3

Table 3

表 3(Table 3)

表 3 不同信息素散播准则对全局路径规划时间的影响 Table 3 Effects of different pheromone strewing criteria on the global path planning s 散播准则 地图序号 ① ② ③ ④ ⑤ 一步散播 15.87 20.47 28.56 19.65 23.67 路径散播 12.14 16.83 22.31 18.01 20.13 路径加权散播 11.39 14.32 20.08 17.33 18.07

表 3 不同信息素散播准则对全局路径规划时间的影响 Table 3 Effects of different pheromone strewing criteria on the global path planning

由于全局路径规划结果是为移动机器人自主行进服务的，频繁的航向变换不利于机器人的行进航向控制.因此，移动机器人的全局规划路径应该综合考虑路径长度以及路径转折点个数.路径长度将影响移动机器人行进中的能耗，而路径转折点个数影响的是机器人的运动控制能力.转折点越多，机器人的控制越复杂，不利于机器人完成任务，为此，本文在改进蚁群算法全局路径规划应用的基础上，对获得的路径进一步优化处理，使得规划路径更加满足移动机器人全局路径规划的要求.在如图 7所示的环境地图中，“O”表示的 路径与“X”表示的路径在路径长度上是一致的，但是“O”表示的路径拐点个数为7，而“X”表示的路径拐点个数为3.根据规划任务，最终，“X”路径将作为算法规划的全局最优路径.

图 7(Figure 7)

Fig. 7

图 7 路径优化测试 Fig. 7 Test on path optimization

本文从基本蚁群算法的思想出发，针对移动机器人路径规划的特点，从改进信息素的挥发、散播原则等方面入手，解决蚁群算法在移动机器人全局路径规划应用过程中的局限性，加快算法的运行速度，提高路径解的质量.同时，算法结合工程应用的需要，对已规划路径进行进一步的优化，使规划的路径更能够满足移动机器人路径跟踪控制的要求.仿真结果表明，与基本蚁群算法相比，在移动机器人的全局路径规划应用中，本文提出的全局路径规划算法具有更高的应用价值和普遍适用性，对于随机给定的环境地图，该算法亦可以迅速地规划出1条易于移动机器人运动控制的最优路径.