基于改进AWA*算法的智能车辆全局路径规划研究

吴麟麟，杨俊辉

(江苏大学 汽车工程研究院， 江苏 镇江 212013)

智能车辆的路径规划是指根据某一性能指标搜索一条从起始点到目标点的最优或近似最优的无碰路径[1]。路径规划的传统方法主要分为两类[2]：分析法、图形法。而图形法又分为路图法、栅格法等。在搜索算法方面，蚁群算法(GA)[3]、粒子群算法[4]、遗传算法[5]及其混合算法等众多主流算法均被运用在路径规划中。蚁群算法收敛速度慢，在障碍物包围情况下易陷入局部最优问题；粒子群算法计算效率偏低且抗噪能力较差；遗传算法实现比较复杂，同时参数的选择不够精确。上述算法均存在计算效率低、编程复杂等实际问题，而A*算法作为启发式搜索算法的一种，在保留了Dijkstra算法[6]精度高的同时减少了扩展节点数目，具有结构简单、搜索精度高等优点。但在规划路径中A*算法[7]存在扩展节点数目较多，Weighted A*算法存在路径精度不佳等问题。随着智能车辆的不断发展，环境地图日益庞大且复杂，现有的启发式算法[8]无法满足搜索耗时及路径精度的综合需求，致使搜索耗时冗长或者路径规划精度不佳。针对上述问题，本文在原有Anytime Weighted A*算法(AWA*算法)的基础上引入动态优化因子，建立一种基于扩展节点耗时的新型动态AWA*算法估价函数，重点对改进的AWA*算法与AWA*算法在路径规划效率及规划路径的影响进行分析[9]。

1 AWA*算法路径规划

全局路径规划主要分为2个步骤：首先是建立障碍物及自由空间区域的环境地图，其次是在环境地图中选择合适的搜索算法。

1.1 环境建模

根据不同的表示形式，环境地图表示方法主要分为度量地图表示法、拓扑地图表示法和混合地图表示法。

本研究主要运用的是度量地图表示法中的空间分解法。假设智能车辆的自由空间为矩形，其内部分布着多个静止障碍物，对任务区域进行栅格化，得到如图1的环境模型，其中：设定起点为红色节点，终点为蓝色节点，障碍物为黑色节点。

图1 环境模型

1.2 AWA*算法的基本原理

AWA*算法是在A*算法的基础上发展起来的。A*算法在它的每个道路节点均设计了一个估价函数：

k(s)=g(s)+h(s)

(1)

而AWA*算法区别于A*算法的是其初次搜索时，在估价函数的基础上引入了权值系数K：

k(s)=g(s)+K·h(s)

(2)

在讨论A*算法及AWA*算法的标准术语中，g(s)表示从初始节点到任意节点s的真实代价消耗，K为启发函数的权值系数，h(s)表示从节点s到目标点的启发式评估代价消耗。g(s)是可知的：

A*算法一定能搜索到最优路径的前提条件：

h(s)≤cost*(s,sgoal)

(4)

考虑到浮点数处理较慢的因素，栅格节点间采用的连接关系是无浮点数计算的四连接。为了保证搜索路径的最优性，采用以当前节点s到目标点goal的曼哈顿距离作为启发式函数：

h(s)=|xs-xgoal|+|ys-ygoal|

(5)

在节点s的扩展子节点中，由于各个子节点g值相同，所以子节点越靠近终点G(goal)，该子节点到终点的曼哈顿距离越小，则 f 值就越小。以此引导搜索的方向，使得智能车辆逐步靠近目标。

AWA*算法用OPEN表与CLOSED表2个集合来管理道路节点。OPEN表存放待扩展的道路子节点，CLOSED表存放扩展过的子节点。所有节点创建时仅已知特性值(X,Y)，其Cost特性值均设为0。

AnytimeWeightedA*算法(算法1)是在WeightedA*算法[10]的基础上，通过改变其终止条件来改善路径精度。算法1的具体框架参考文献[10]。

算法1的核心思想是在限定的搜索时间下，基于WeightedA*算法条件进行搜索，当AWA*算法的OPEN表为空时，那么算法结束，没有搜索到可行路径；当AWA*算法搜索到了不大于最优路径K倍的可行路径 f(inc)时，如果时间仍有剩余，那么算法会将当前的路径长度 f (inc)保存，同时对已经扩展的节点继续搜索，但该搜索满足的条件相对于之前WeightedA*算法做了相应的改变，后续扩展的节点除了要满足k(s)值最小之外，其f(s)值必须要小于f(inc)值，这样，之后得到的路径均对原始可行路径进行了优化。AWA*算法终止条件为：OPEN表为空，或者时间结束，算法终止。

2 优化AWA*算法路径规划

WeightedA*算法[10]基于A*算法的扩展特点，引入了权值系数K，通过扩大启发函数使其扩展节点数目减少，加快搜索速度。但由于启发函数的过分增大，最优子节点选取不充分，导致路径精度折损过多。AnytimeWeightedA*算法在WeightedA*算法的基础上加入了终止条件，使AWA*算法可在时间充裕的条件下继续搜索更优路径。但AWA*算法如若初次搜索到最优路径，仍会继续搜索，扩展多余无用节点。综上所述，本文基于WeightedA*算法的估价函数，在AnytimeWeightedA*算法的启发下引入了动态优化因子，提出了一种新型动态估价函数。根据搜索过程中当前耗时T与当前扩展节点数目的线性关系，通过获取当前搜索耗时参数T，时刻更新启发函数的权值系数，保证AWA*算法在初次搜索路径时便可找到较优路径，进而可在限定时间内找到最优路径。

2.1 优化AWA*算法的流程步骤

优化AWA*算法大体分为3个阶段：

开始阶段：将起始节点放入OPEN表中，同时初始化所有变量。

扩展阶段：判断是否找到初始路径，是则继续搜索，但是新增条件为当前搜索的路径 f 值要小于初始路径inc的 f 值；否则选取OPEN表中最小k值节点，放入CLOSED表中。同时扩展该节点，判断其4个子节点是否在OPEN表中，计算这些子节点的k值及 f 值后，放入或更新OPEN表；

动态优化阶段：根据AWA*算法每次扩展子节点后均检查最优子节点的机制，获取当前搜索耗时，更新动态优化因子ε*值。

优化AWA*算法框架如算法2所示，其中：OPEN表示A*算法中存放待扩展的节点集合；CLOSED表示存放扩展过的节点集合。sstart为起始栅格节点；sgoal为目标栅格节点；s′是s的扩展子节点；K为启发函数的权值系数；inc为找到目标点的节点集合；g(s)表示从起始节点sstart到当前节点s的真实代价值；c(s,s′)为节点s到s′节点的距离值；k(s)为本文公式中当前节点s的估价函数值； f(s)是当前节点的估价长度； f(inc)表示第1次找到的从起始节点到目标节点的可行路径长度；h(s′)为当前子节点s′的启发函数值；ε*表示动态优化因子；T1表示限定的搜索时间；P1表示开始时记录的计算机时间截点；P2表示扩展当前子节点后的计算机时间截点；T为当前搜索消耗的时间；α表示触发搜索极限时间比率；B表示搜索极限速度常数。

算法2 优化Anytime Weighted A*算法

2.2 优化AWA*算法的具体思路

本文在AWA*算法的初次搜索中估价函数中引入动态优化因子ε*，根据A*算法循环扩展子节点的特点来不断变化启发函数的权值系数Kε*，以保证初始路径时可快速地选择较优的路径，同时可进一步在限定时间内寻找更优路径。

优化AWA*算法的估价函数如下：

河南省战略性新兴产业发明专利数量不多、质量不高的现实状况，反映出河南省自主创新能力不足。这些问题的形成，既与河南省经济发展、科技创新、人才培养等方面的历史欠账有关，又与新时期河南省知识产权战略实施不彻底、知识产权布局不科学、知识产权潜力挖掘不充分等有关。具体来说，主要有以下几个方面的问题。

k(s)=g(s)+Kε*×h(s)

(6)

本文定义了动态优化因子ε*，其具体计算公式如下：

式中： K为初始权值系数；T1为限定搜索时间(ms)； T为获取的当前搜索耗时(ms)； B为搜索极限速度常数； α为触发搜索极限时间比率。

加入了搜索耗时T1后，ε*值在开始时每次扩展子节点后均会增大，同时优化AWA*算法的估价函数也会相应改变，减少了可选择节点数目，保证了搜索效率。随着搜索耗时T的不断增大，当T大于或等于αT1时，此时距离目标节点较近，通过使ε*变为常数B，来确保搜索路径精度。

又由式(7)可知：

K

(8)

由式(4)(8)可证得：

(9)

推导结果证明了优化AWA*算法初次规划出的路径要小于KB倍的最优路径，以此保证了优化AWA*算法路径的次优性。

3 仿真实验及结果分析

本文针对路径规划搜索耗时问题，对AWA*算法及优化AWA*算法进行了路径规划耗时误差仿真实验，验证了优化AWA*算法在不同单一环境地图下，仿真平台具有一定稳定性，搜索耗时误差具有一定局限性，实验数据具有一定可靠性。同时，本文进行了低百分比障碍物环境地图路径规划普适性仿真实验，对比分析了优化AWA*算法与传统AWA*算法的耗时情况和路径精度。为进一步验证优化AWA*算法的普适性，本文进行了高百分比障碍物的环境地图路径规划普适性仿真实验，并对仿真实验总体上进行了系统性地分析。2种算法均在VitualStudio2013上实现，仿真实验采用的计算机CPU型号为Intel酷睿i5 3230M，主频均为2.6GHz，RAM为4GB。在2种仿真实验中，优化AWA*算法均采用相同的参数，且该参数均由实际需要自行设定，如表1所示。

表1 优化AWA*算法主要参数

3.1 路径规划耗时误差仿真实验

本文为研究每次搜索耗时的误差特性，对2种算法分别进行了单一地图在10%～50%障碍物百分比下的100次重复规划仿真实验，并以20%障碍物下的单一环境地图为例，其结果如图2所示。

仿真实验结果显示：在环境地图障碍物百分比为20%时，AWA*算法每次搜索耗时之间的误差值为32ms，优化AWA*算法搜索耗时误差分别为16ms。同理，在10%、30%、40%、50%障碍物的环境地图中，AWA*算法与优化AWA*算法搜索耗时误差也均保持在32ms以内，说明2种算法在各个环境地图中的耗时误差均具有一定局限性，且重复规划的路径结果均一致，验证了2种算法路径结果重复规划的一致性和仿真平台数据结果的可靠性。

3.2 算法普适性仿真实验分析

3.2.1低百分比障碍物环境地图的普适性仿真实验

为分析优化AWA*算法在特定障碍物百分比但不同环境地图下的各项性能，本文分别在障碍物百分比为10%、20%、30%、40%、50%下，均随机生成100种环境地图。路径规划后的搜索耗时仿真实验结果如图3～7所示。

仿真实验结果显示：优化AWA*算法与AWA*算法相比，在障碍物为10%、20%、30%、40%、50%下的环境地图中搜索耗时分别下降了69.3%、73.5%、49.8%、21.4%、19.9%，扩展节点数目减少了55%、62%、43%、22%、12%，路径平均长度分别减少了0.47%、1.3%、1.2%、1.7%、0。综上可知，在10%～50%障碍物环境地图下，优化AWA*算法的各项指标均优于AWA*算法。此仿真实验验证了优化AWA*算法在保证路径次优性的同时仍具有搜索耗时少的优势。

通过对比图3(c)、图4(c)、图5(c)、图6(c)、图7(c)，发现随着环境地图障碍物百分比逐步增大，优化AWA*算法相比于AWA*算法的搜索耗时优势逐步减少这一现象。为此，本文通过进一步地仿真实验来验证此发现。

3.2.2高百分比障碍物环境地图的普适性仿真实验

由于障碍物百分比为90%时，自由空间不足以生成起点到达终点的可行驶路径，故随机生成路径的障碍物百分比最高设定为80%。本文针对优化AWA*算法相比于AWA*算法，在高百分比障碍物环境地图下的搜索耗时优势减少的问题，设定60%、80%百分比障碍物，分别随机生成100种环境地图，仿真实验结果见图8、9。

仿真实验结果显示：优化AWA*算法与AWA*算法相比，在60%、80%障碍物下的环境地图中，搜索耗时分别下降了3.27%、4.56%，路径精度分别下降了0.1%、0。此仿真实验结果与上述发现的环境地图障碍物百分比逐步增大，优化AWA*算法相比于AWA*算法的搜索耗时优势逐步减少的现象一致。

图2 20%障碍物地图下的路径规划

图3 10%障碍物地图下的路径规划

图4 20%障碍物地图下的路径规划

图5 30%障碍物地图下的路径规划

图6 40%障碍物地图下的路径规划

图7 50%障碍物地图下的路径规划

图8 60%障碍物地图下的路径规划

图9 80%障碍物地图下的路径规划

本文对此现象的原因进行了合理推断：

耗时大小的具体体现是OPEN表中存放的待扩展节点数目。在低百分比障碍物的环境地图中，障碍物数量少，自由空间相对多。在未搜索到初始路径时，由于优化AWA*算法相比于A*算法启发函数值偏大，故在OPEN表中添入可选择的待扩展子节点数目偏少，导致扩展节点过程中计算k值的次数少，规划路径时间更短。

而随着环境地图障碍物逐步增多，自由空间相对逐步减小。在扩展子节点时，AWA*算法OPEN表中添入可选择的待扩展节点被动减少，导致优化AWA*算法相比于AWA*算法扩展数目的差距逐步减小，故优化AWA*算法在搜索耗时方面的优势逐步减少，直至持平。

4 结束语

本文提出了一种基于AWA*算法的新型估价函数。在原有AWA*算法估价函数基础上，引入了动态优化因子ε*，建立了新型的估价函数，根据AWA*算法流程中循环扩展节点的特点不断更新启发函数的权值系数Kε*，加快路径规划最优性收敛，改善智能车辆路径规划在限定时间下路径精度不佳问题。

在全局工况下，优化AWA*算法相比于AWA*算法，在保证路径次优性的同时降低了搜索路径耗时，尤其是在低障碍物百分比地图下，效果更为明显。

当环境地图障碍物百分比逐步增大时，优化AWA*算法相比于AWA*算法的搜索耗时优势逐步减小，最后两者搜索耗时基本一致。