多因素A*蚁群算法的机器人路径规划*

徐劲力，柳 佳，司马立萱

(武汉理工大学机电工程学院，武汉 430070)

0 引言

移动机器人的路径规划技术是决定其智能与否的关键技术，其目的是在障碍物已知的环境中搜索到一条符合预定要求的路径[1]。目前路径规划算法种类众多，然而这些路径规划算法往往只将路程距离作为考量因素，这会导致机器人在实际应用中产生一些问题。因为在一些特定的环境中，所得到的路径最优结果可能伴随着较多的转弯次数，或者出现频繁上下坡等情况，机器人在这样的道路上行进不仅会耗费更多的时间，还会对机器人的性能和寿命产生影响。所以，未来机器人的路径规划应该结合工作环境和作业需求，寻找一条综合性能最优的路径。

蚁群算法具有鲁棒性强，容易用计算机语言表达，且能很好地应用于路径规划问题等优点[2]，但同时存在容易陷入局部最优解、迭代次数过多、路径转弯次数多等问题[3]。针对以上蚁群算法的缺陷，学者们通过不断地研究提出了一系列的方法进行改进。XIONG等[4]将节点之间的采样信息加入蚁群算法的启发函数，并划分机器人信息采集区域，提高算法计算效率。李二超等[5]将初始信息素按照与起点和终点连线的距离进行非均匀分布，加快蚂蚁前期搜索速度，同时引入B样条曲线，对蚂蚁路径做平滑处理。马小陆等[6]通过结合跳点搜索法，减少势场蚁群算法对无用点的评估，提高了搜索效率，所得的路径更优。姜伟楠等[7]采用改进人工势场法，缩小地图搜索范围，减少蚁群算法迭代次数。WANG等[8]通过遗传算法得到初始路径，减少蚁群算法前期搜索盲目性，提高算法运算速度。任红格等[9]用目标点信息提高蚁群整体搜索效率，同时引入动态信息素挥发系数公式，减少劣质解的影响。

前人的研究在一定程度上对蚁群算法的缺点做了优化，但仍无法同时满足机器人在实际工作中对搜索效率与综合最优路径的需求。为此，本文提出多因素A*蚁群算法。该算法利用改进A*算法得到的路径差异化地图信息素初始值，避免蚁群算法前期搜索的盲目性；在启发式函数和信息素更新公式中加入转弯次数、颠簸程度作为考量因素，并优化距离因素，增加目标点信息，同时在启发信息中引入动态调节因子，实现前期路径搜索依靠启发信息，后期依靠信息素；为防止信息素积累过快而陷入局部最优解，在引入动态调节信息素挥发系数的同时，设置信息素浓度的取值范围。

1 环境建模

1.1 环境地图

图1 栅格地图

栅格法地图建模是指将机器人的工作环境划分为大小相等的若干个正方形栅格，由于栅格法比较直观且易于实现，故本文地图使用栅格法进行实现，具体如图1所示。栅格法地图由只包含0和1矩阵G定义，矩阵中0代表可行栅格，机器人可以通行，在地图中用白色填充，1代表障碍栅格，机器人无法通过，在地图中用黑色填充。为了让地图产生坡度变化，采用与地图大小相同的峰谷随机函数存储每一个栅格的高度，同时用灰色渲染，颜色越深的栅格的高度更高。表示栅格地图的矩阵G中的行数i与列数j与地图栅格的中心点坐标x、y的对应关系表达式：

(1)

式中，R表示栅格地图的G的行数。

1.2 规定行进方式

图2 相邻栅格标号

为了保证移动机器人行进路线的安全性，不会与栅格地图中的障碍物发生碰撞。规定即使是障碍物的顶点，也不能触碰，即在栅格地图中，当机器人想要斜着走时，与前行路线相交的3个栅格都是可行栅格时，机器人才能行进。以图2为例，如果机器人在栅格i处，下一步想要前往栅格3处，只有栅格2、3、4均为可行栅格，机器人才能行进。为了实现该行进方式，本文通过引入一个900×8的距离矩阵D，用于存储栅格地图中900个栅格到其相邻8个栅格的距离，再引入判断条件如式(2)所示，计算相邻栅格间的距离。

(2)

式中，D(i,k)表示矩阵D的第i行第k列的值，同时也表示栅格i到其相邻的第k个栅格的距离，栅格i与相邻栅格序号k的关系如图2所示；mod为求余函数，用于区分直行与斜行；jk表示与栅格i相邻的第k个栅格的栅格号。

2 A*蚁群算法

A*算法在蚁群算法中主要起到差异化地图初始信息素的作用，在蚁群开始搜索前，通过A*算法找到一条距离最短的路径，将地图上这条路径的初始信息素的浓度提高，这样既可以提高蚁群算法前期搜索效率，也可以避免蚂蚁过多地走入死路。

2.1 传统A*算法及其改进

A*算法的启发函数同时包含了起点和终点的信息，能够在栅格地图中快速找到一条距离最短的路径，其启发函数为：

f(n)=g(n)+h(n)

(3)

式中，n为当前栅格编号；g(n)为起始栅格到达当前栅格n的已知最短长度；h(n)为当前栅格n达到目标栅格的距离，一般采用欧氏距离表示。

传统A*算法中，会将每个当前栅格的可行未遍历相邻栅格加入待遍历栅格集合中，然后按照待遍历栅格的启发函数的值从小到大逐个遍历这些栅格，产生了大量无效遍历。因此，本文通过引入一个评价函数对当前栅格的相邻栅格进行判断，减少无用栅格加入待遍历集合，提高算法计算速度。评价函数如式(4)所示。

H(n)=h(n)-h(n-1)+μ

(4)

式中，h(n)为相邻栅格到目标栅格的欧式距离；h(n-1)为当前栅格到目标栅格的欧式距离；μ为评价函数调节系数，根据地图环境取值。

如果当前栅格的相邻栅格中有障碍栅格时，为了防止陷入局部陷阱而无法找到目标点，仍然将每个当前栅格的可行未遍历相栅格点加入待遍历栅格集合中；如果当前栅格的相邻栅格中没有障碍栅格，且其评价函数大于0，则将该栅格加入待遍历栅格集合，否则，不加入。

图3 传统A*算法

为了证明本文算法的优越性，建立栅格地图，将传统A*算法、文献[10]算法与本文算法做对照仿真实验，通过反复实验结果分析，取评价函数调节系数μ=0.3。仿真实验结果对比如图3～图5所示。障碍物和边界用黑色栅格表示，已遍历栅格用灰色渲染，起始点为蓝色栅格，目标点为绿色栅格。对每种算法已遍历栅格的数目、最终路径长度进行比较，仿真实验数据如表1所示。

图4 文献[10]算法 图5 本文改进A*算法

表1 仿真结果分析

实验数据表明，在所获得的最短路径相同的基础上，本文改进算法对比文献[10]算法已遍历栅格数减少18.05%，对比传统A*算法已遍历栅格数减少33.82%，极大地提升了A*算法的搜索效率。

2.2 基本蚁群算法

2.2.1 概率选择

蚁群算法的转移概率公式用于指导蚂蚁从当前栅格选择下一步栅格，蚂蚁的状态转移概率公式如式(5)所示。

(5)

式中，allowedi表示蚂蚁在栅格i时的可行相邻栅格的集合；τ表示信息素浓度；η表示启发信息；α表示信息素浓度影响因子；β表示启发信息影响因子；其中，启发信息函数的表达式如式(6)所示。

(6)

式中，dij为当前节点i到下一节点j的欧氏距离。

2.2.2 信息素更新

信息素是模拟自然界蚂蚁在寻找食物时留在路途中用于指导其他蚂蚁前进方向的某种化学物质[11]。在蚁群算法中，每次迭代中所有蚂蚁完成寻路后会对地图的信息素进行一次更新，更新公式如式(7)和式(8)所示。

(7)

(8)

2.3 改进蚁群算法

2.3.1 初始信息素改进

传统蚁群算法将地图所有可行栅格的初始信息素设为一个常数C，蚂蚁在迭代初期主要依靠启发函数，不仅搜索盲目，还容易陷入地图死点。为了解决这个问题，在建立栅格地图后，通过改进A*算法得到的起始点到目标点之间的路径，并将此路径上所有栅格的集合记为R，重新设置地图栅格的初始信息素如式(9)所示。

(9)

式中，n为正数。

2.3.2 启发函数改进

传统蚁群算法的启发函数仅将当前节点i与相邻节点j的欧式距离dij作为决定因素，搜索盲目且求解单一。考虑到移动机器人工作环境的复杂性和自身移动结构的局限性，应综合考虑路径的距离、转弯次数和颠簸程度等因素。同时，为了解决传统蚁群算法迭代次数过多，容易陷入局部最优解的问题，加入动态调节因子，在迭代前期，让启发函数发挥主导作用，对蚁群前期搜索给予方向指引。在迭代后期，让信息素发挥主导作用，避免算法得到局部最优解。优化后的启发函数如式(10)所示。

(10)

在路径的距离因素中，增加相邻节点j与目标点q的欧式距离diq作为考量因素，能更好地引导蚂蚁向目标点进发。由于各可行相邻栅格的dij、djq差别较小，为了体现距离差别，引入距离因素启发函数如式(11)所示。

(11)

式中，D为所求相邻栅格的dij、djq之和；Dmax、Dmin分别为当前栅格的所有相邻可行栅格的dij、djq之和的最大值和最小值；a、b为距离调整系数，由地图环境决定，0.01用于避免Dmax=Dmin的情况导致无法计算。

在路径的转弯因素中，通过图2所示的相邻栅格标号，用矩阵dir存储每次蚂蚁前进的方向，为了得到转弯次数较少的规划路径，引入转弯因素启发函数如式(12)所示。

(12)

在路径的坡度因素中，采用peaks函数存储地图的坡度，并采用与路径的距离因素类似的方式体现各可行栅格的坡度差别，引入坡度因素启发函数如下：

(13)

式中，H为栅格i的坡度与栅格j的坡度之差的绝对值；Hmax、Hmin分别为当前栅格i与其所有相邻可行栅格的坡度差绝对值的最大值和最小值；c、d为坡度修正系数，根据地图环境取值。

2.3.3 信息素更新方式的改进

(14)

Sk(t)=x2Lk(t)+y2TK(t)+z2Fk(t)

(15)

式中，Sk(t)为第t次迭代中第k只蚂蚁所寻路径的综合性能函数；Tk(t)为第t次迭代中第k只蚂蚁所寻路径的转弯次数；Fk(t)第t次迭代中第k只蚂蚁所寻路径的坡度均方差；x2、y2、z2分别为各因素的影响系数。

(16)

式中，ρ(t+1)为第t+1次迭代时的挥发系数；ρ(t)第t次迭代时的挥发系数，挥发系数会随着迭代次数的增大而减小，直到取到设定的最小挥发系数ρmin为止。

(17)

式中，τmin、τmax分别为地图设定信息素浓度的下极限值与上极限值。

3 仿真分析

本文改进算法流程如图6所示。

图6 改进算法流程图

为了验证本文算法的正确性，建立栅格地图并将传统蚁群算法、文献[12]以及本文的改进算法进行仿真实验对比分析。由于蚁群算法通过轮盘赌选择行进方向，每次得到的实验结果会有所差别，故在同一地图环境中对每个算法进行相同次数的实验，取其综合指标出现频率最高的结果来进行比较分析。

本文的公共参数初始值经大量实验分析后设置如表2所示。

表2 公共参数表

建立较复杂的30×30的栅格地图，将本文改进蚁群算法、文献[12]算法和传统蚁群算法进行对比试验，仿真结果如表3和图7所示。

表3 实验数据表

(a) 路径规划图

(b) 路径转弯次数迭代图 (c)路径长度迭代图

(d) 路径坡度均方差迭代图 (e)路径综合指标迭代图

由表3可知，在路径长度上，虽然三种算法的差距不大，但本文算法所得到的结果还是优于其他两种算法。在路径的转弯次数和坡度均方差上，由于引入了路径转弯因素和路径坡度因素，本文算法和文献[12]算法均明显优于传统蚁群算法，说明本文算法和文献[12]算法对于多因素路径规划的可行性。对比本文算法和文献[12]算法指标，由于融合改进A*算法，优化启发函数和信息素更新公式，本文算法均优于文献[12]算法，不仅在路径长度、坡度均方差、路径转弯次数、综合指标上分别优化了2.5%、9.5%、6.7%、5.0%，在迭代次数上更是减少了57.9%。虽然本文算法程序运行时间略高于文献算法和传统蚁群算法，但迭代稳定估计时间却优于它们。总体来看，本文算法在30×30栅格地图中各方面表现均比较优异，对于考虑多因素机器人路径规划的问题有明显的优势。

4 结束语

本文针对移动机器人实际工作环境需求，提出一种多因素A*算法蚁群算法。通过改进A*算法使得初始信息素不平等分配，降低蚁群算法前期搜索的盲目性，减少迭代次数；在蚁群算法中加入了路程长度、转弯次数和颠簸程度三种因素的影响，弥补了传统蚁群算法以距离作为唯一因素的不足；在启发函数和挥发系数中引入动态调整因子，让蚁群前期扩大搜索范围，后期快速向最优解收敛。

通过栅格法搭建地图环境的仿真实验表明，在同一栅格地图环境下，本文算法的最终路径长度、颠簸程度、转弯次数、迭代稳定次数均要优于传统算法和文献[12]算法，所以本文算法寻路的效率更高。在今后的研究过程中，可以结合机器人的实际工作环境，对本文算法中的启发函数和综合指标中各因素系数的进行更合适的分配。