基于改进A*蚁群融合算法的路径规划研究

王 锋，李凯璇，朱子文,2*，朱 磊，王海迪,2

（1.中北大学机电工程学院，太原 030051；2.中北大学智能武器研究院，太原 030051；3.西北工业集团有限公司，西安 710043；4.北方自动控制技术研究所，太原 030006）

0 引言

无人车是一种可以自主执行预设程序的无人平台，其功能包括但不限于环境感知、路径规划、运动控制、动态决策等。无人车应用广泛，在工业、农业等民用领域具有重要作用，在未来无人化战场等军事领域同样也发挥着重要作用。路径规划技术在无人车运动中占据着很大比重，是无人车完成自主导航的核心技术。

A*算法是一种利用启发信息寻找最优路径的启发式算法。A*算法需要在地图中搜索节点，并以适合的启发函数进行指导，通过评价各个节点的代价值，选取下一个代价值最小的节点作为拓展的最佳节点，反复迭代到达最终目标位置［1］。A*算法对环境反应迅速，搜索路径方法直接，但实时性差，每一节点计算量大、运算时间长，而且节点数越多，算法搜索效率越低［1］，路径越长，平滑度越低。近年来，多位学者以及研究人员在改进A*算法的研究中取得了一些进展，高民东等提出了一种双向时效A*算法规划路径，采用多近邻栅格距离计算方案，达到提高效率、平滑路径的效果，但得到的路径较长［2］。孔继利等提出了一种引入双向搜索机制的改进A*算法，但得到的路径与障碍物距离过近，易发生碰撞［3］。以上研究虽对A*算法进行了改进，但仍未能解决A*算法效率不高，路径不够平滑等问题，因此，部分学者利用其他算法改进A*算法。陈继清等提出了基于人工势场的A*算法的移动机器人路径规划，减小传统A*算法规划路径的缺点，但带来了人工势场的局部震荡问题［4］。杨明亮等提出了改进A*算法和动态窗口法相结合的混合算法，解决了使用A*算法扩展节点多、容易陷入局部最优的问题，但规划时间较长［5］。

本文提出一种改进A*算法，结合蚁群算法的迭代特性，通过路径距离及平滑程度等评价指标对路径进行优化改进，提高无人车的路径规划能力。

1 环境模型建立与标准A*算法

1.1 环境模型建立

环境建模是利用相关的数学函数工具对环境信息进行数学建模，建立无人车的可通行区域与禁止通行区域。本文采用HOWDEN W E 在1968 年提出的环境建模方法［6-8］。以栅格为单位表示环境信息，通过编码表示栅格。障碍物区域使用黑色栅格表示，编码为1，即禁止通行栅格；非障碍物区域使用白色栅格表示，编码为0，即可通行栅格。栅格地图模型示意图和对应的编码环境矩阵分别如图1和式（1）所示。

图1 栅格地图模型示意图Fig.1 Schematic diagram of grid map model

为了兼顾路径规划的效率以及路径规划的准确性，选择无人车的最小运动面积作为栅格尺寸的大小。假设无人车所处的环境地图为x、y的矩形区域，将其以m×n的标准进行划分，从而构成栅格地图。m表示行数，n表示列数。一般情况下，无人车的最小运动面积是以无人车的质心为中心进行原地旋转所占用的面积［9］，栅格的长度可表示为：

式中，p为栅格的长度；l为无人车质心至其最远点的距离。

1.2 标准A＊算法

A*算法是一种已知障碍物地图下的最短路径规划算法，也是目前无人车路径规划方面使用最多的启发式搜索算法［9］。A*算法的核心公式为：

式中，f(n)为无人车从起始位置到达目标位置的估价函数；g(n)为无人车起始位置到当前节点f(n)的实际代价函数;h(n)为当前节点n到路径目标的估计函数。

代价函数g(n)用欧氏距离表示为：

启发函数有多种表示形式，最常用的表示方式为曼哈顿距离，如式（5）：

式中，（xn、yn）表示无人车当前节点n的位置；（xE、yE）为无人车的目标节点位置；n为常系数，一般定义为栅格间距。

2 改进A*蚁群融合算法

2.1 路径转弯机制改进

在标准A*算法路径规划过程中，由于其代价函数的计算特点，往往会出现与相邻的障碍物方格接触的情形，此情形对应现实的无人车会发生碰撞的事故，因此，必须对标准A*算法路径规划的转弯机制进行改进，通常的解决方法一般是给车辆与障碍物之间设置安全距离，但该方法可能会由于安全距离相互冲突将原本可通行的路径封死，因此，本文从逻辑层面对转弯机制进行改进，避免无人车在路径规划过程中发生碰撞，对转弯机制的具体改进如图2和图3所示。

图2 不允许转弯方式
Fig.2 No turning allowed

图3 允许转弯方式
Fig.3 Turning allowed

当规划路径为斜向路径时，只有当前所在位置栅格与下一位置栅格的两侧栅格均不为障碍物栅格时，此规划路径才成立。根据上述改进方法，可构建转移矩阵dij，如式（6）所示。

式中，为直向栅格标号；为斜向栅格标号；i'和i"分别为与斜向连线垂直的两个直向栅格标号；∞为无法前进或出界的情况，mod(j,2)用于判断j的奇偶性，并判断下一步为直行或斜行。

2.2 基于改进A＊蚁群的融合算法

蚁群算法是由意大利学者DORIGO等于1991年提出的一种模拟蚂蚁觅食行为的模拟优化算法，具有迭代特性，可以通过迭代优化其他算法［9］。

2.2.1 信息素初始化与栅格选择方式改进

将标准A*算法得到的路径记为R，并将路径R上的信息素初始化为：

式中，N为大于1 的常数，其余区域的信息素初始化为常数C。

为了让蚂蚁更容易地选择最佳的下一个栅格，对蚂蚁选择栅格的方式进行改进。常规蚁群算法的栅格选择方式与标准A*算法的栅格选择方式一致，对转弯机制进行改进后，标准A*算法的路径长度会有增加，在此基础上利用常规蚁群算法对标准A*算法的路径进行迭代优化，可能会没有明显的效果，因此，本文将常规蚁群算法的栅格选择方式进行改进，如图4所示。

图4 蚁群算法栅格选择方式改进Fig.4 Improvement of grid selection method in ant colony algorithm

图4中，蓝色栅格为蚁群算法常规的选择方式，以此为基础另外添加8 个栅格，即图4 中的绿色栅格，二者共同构成蚁群算法新的栅格选择方式。

2.2.2 启发函数改进

在新的栅格选择方式的基础上进行栅格选择，下一个栅格必须是可通行栅格，并且有多个出口指向目标。这个概率取决于栅格周围禁止通行栅格的数量。栅格周围的禁止通行栅格越少，概率越大，栅格就越有吸引力，这里引入刺激概率Kij。某栅格j周围禁止通行栅格所有可能分布情况的个数可以计算为：

其中，Nobs为栅格j周围的禁止通行栅格个数。

栅格j的出口分布情况个数可以计算为：

刺激概率Kij计算如下：

新的启发函数定义如下：

其中，djs为下一节点j与终点E之间的距离，增加了栅格j与目标位置的距离对启发函数的影响，同时增加了目标位置对路径的吸引力。Kij增加了禁止通行栅格个数对节点选择的影响，节点j周围的禁止通行栅格越多，Kij越小，启发函数就越小，选择该节点的概率就越小。

2.2.3 信息素更新方式改进以及信息素挥发因子调整

传统蚁群算法信息素更新规则如下：

式中，ρ为信息素挥发因子，ρ∈[0,1)；(t,t+n)表示经过n次步骤后蚂蚁完成一次遍历；Δτij(t,t+n)表示节点i、j之间在完成一次遍历后的信息素增量；Δ(t,t+n)表示蚂蚁k在一次遍历后，其通过路径的信息素增量。Δ(t,t+n)按照式（14）进行更新。

为使蚁群能更快地搜索到最优路径，本文将信息素更新规则修改如下：

若当前路径Lk长度小于上次路径Lk-1，则取＞1，以增加Lk的信息素含量；若当前路径Lk长度大于上次路径Lk-1，则取＜1，以减少Lk的信息素含量。

信息素挥发因子ρ通常为常数，在全局搜索时ρ若为常数会降低搜索效率，现将ρ改进为：

其中，GDmT、GDmT-1分别为第T次迭代与第T-1次迭代中平滑度参数平均值。将无人车路径中的锐角、直角、钝角分别赋予值3、2、1，路径平滑度参数值即所有角度值之和。

引入平滑度参数来影响信息素的挥发，当GDmT小于GDmT-1时，路径更平滑，此时减小ρ值，加快算法收敛速度，当GDmT大于GDmT-1时，增加ρ值，加强算法全局搜索能力。

2.3 基于改进A＊蚁群融合算法的路径规划

改进A*蚁群融合算法的路径规划步骤如下：

1）利用标准A*算法得到原始路径，进行信息素初始化；

2）初始化蚁群算法参数；

3）将蚁群放置在起始位置；

4）通过转移概率，选择蚁群的下一栅格；

5）其中一只蚂蚁到达目标位置后，更新信息素，重复步骤4），直到所有蚂蚁到达目标位置；

6）判断是否达到迭代次数，若达到迭代次数，则输出最优路径；若没有，继续返回步骤3）。

3 仿真实验

3.1 仿真条件

本实验建立的环境模型为30×30 的栅格地图，如图5所示。

图5 栅格地图Fig.5 Grid map

图5（a）是简单地图，障碍物简单分布在栅格地图中，图5（b）是复杂地图，随机生成动态障碍物，随机产生障碍栅格的概率为0.75［10］，障碍物较为复杂的分布在栅格地图中。本文选择的无人车质心至其最远点的距离为0.5 m，每一栅格长度为1 m。

在复杂陆战场中环境是多变的，无人车需要随时临时调整［11］，若最优路径上出现新增障碍物，则需要重新进行路径规划。本文在路径规划时，当各路径长度差d满足式（18）时，将当前所有已知路径存入数据库内，不再进行路径优化。当环境改变后，优先在数据库中搜索可行路径，若无，则重新进行路径规划。本文选择路径长度差为3 m。

蚁群算法初始化参数设置如表1所示。

表1 蚁群算法初始化参数设置Table 1 Initialization parameters setting for ant colony optimization algorithm

其中，迭代次数以50 次为变化量进行迭代次数增加，其余参数不变。

3.2 仿真结果与分析

本实验基于简单地图和复杂地图设计两组实验，设置起点坐标为（0.5，0.5），目标点坐标为（29.5，29.5）。未改进转弯机制情况下，基于标准A*算法的路径规划仿真结果如图6所示。

图6 未改进转弯机制的标准A*算法路径规划仿真结果Fig.6 The simulation results of standard A*algorithm path planning without improved turning mechanism

由图6可以看出，未改进转弯机制情况下，在简单地图环境中，标准A*算法能够成功完成搜索出从起始点到目标点最佳路径的任务，但是在复杂地图环境中发生路径跨越障碍物的情形，该情形在无人车路径规划过程中是不允许的。

因此，本文在标准A*算法的基础上，修正A*算法的转弯机制，并引入蚁群算法。在简单地图和复杂地图两种环境下，分别进行100、400 和800 次迭代，对修正转弯机制的标准A*算法与改进A*蚁群融合算法进行仿真分析并对比，结果如图7～下页图8所示。

图7 简单地图仿真结果Fig.7 The simulation results of a simple map

图8 复杂地图仿真结果Fig.8 The simulation results of a complex map

图7～图8 中蓝色线条为修正转弯机制的标准A*算法，红色线条为改进A*蚁群融合算法。由仿真结果看出，修正转弯机制的标准A*算法与改进A*蚁群融合算法，在复杂地图中均能成功避开障碍物，完成搜索出从起始点到目标点最佳路径的任务。

改进A*蚁群融合算法进行800 次迭代的路径长度如图9～图10所示。

图9 简单地图中迭代800次路径长度Fig.9 The path length after 800 iterations in a simple map

图10 复杂地图中迭代800次路径长度Fig.10 The path length after 800 iterations in a complex map

由图9～图10 可知，在一定的迭代范围内，迭代次数越多，路径长度越短，总转弯角度越小，路径越平滑。但随着迭代次数的增加，节点数量和运行时间也随之增加，且路径的优化效果并不明显。

统计两组实验的路径长度和总转弯角度如下页表2和表3所示。

表2 简单地图仿真数据统计结果Table 2 The statistical results of simulating data in a simple map

表3 复杂地图仿真数据统计结果Table 3 The statistical results of simulating data in a complex map

由以上两组仿真实验数据对比可知，改进A*转弯机制可以避免碰撞障碍物的情况，但带来路径变长、总转弯角度变大的问题。利用改进A*蚁群融合算法进行迭代优化后，路径长度变短、总转弯角度也变小，使得路径更加平滑，在实际应用中，无人车将使用更少的能量，花费更短的时间，完成从起始位置到目标位置的任务。意味着改进后的A*蚁群融合算法在实际应用中更高效。

综合对比仿真结果可知，400 次迭代的效果较好。以400 次迭代优化的仿真数据可知，简单地图中，改进A*蚁群融合算法相较于改进转弯机制后的A*算法路径规划长度减少2.34%，总转弯角度减小5.62%；复杂地图中，改进A*蚁群融合算法相较于改进转弯机制后的A*算法路径规划长度减少2.62%，总转弯角度减小26.3%。

4 结论

本文主要针对标准A*路径规划算法展开研究，利用栅格地图法进行环境建模，针对标准A*算法进行全局路径规划时发生碰撞障碍物的问题，改进其转弯机制，同时又针对其路径较长、路径不够平滑等问题，引入蚁群算法，并引入刺激概率对蚁群算法启发函数进行改进，引入自适应信息素更新方式改进其更新规则，最后通过仿真实验验证改进A*蚁群融合算法的优越性。仿真结果表明，基于改进A*蚁群融合算法的路径规划方法能够避开障碍物，且路径长度和路径平滑度得到改善。该算法能够为未来无人战场上无人车在复杂环境中的自主行驶提供理论依据。