基于二次A*算法的复杂环境下车辆导航路径规划方法

2020-04-25钱燮晖何秀凤郭俊文

甘肃科学学报 2020年2期

钱燮晖,何秀凤,郭俊文,王砾

(1.河海大学地球科学与工程学院,江苏南京 211100; 2.北方信息控制研究院集团有限公司,江苏南京 211100)

车辆在野外环境的路径规划是部队作战和演习的关键问题,一直受到广泛关注。车辆路径规划指的是从起始位置(起始点)到终止位置(目标点)的空间内,根据研究人员对其所设定的某种具有可选择最优路径规划法则,来输出一条能够精确到达目标的最优或次优的安全无碰撞路径[1]。由于受野外环境复杂且信息量大、障碍物多等因素的影响,路径规划问题已被确定为非确定性多项式困难问题[2]。

目前有很多智能算法应用于路径规划问题中,各有其优缺点。遗传算法具有较强的鲁棒性,能自适应地调整搜索方向,但在求解过程中常常伴随着大量的冗余迭代,降低了搜索效率;蚁群算法具有良好地正反馈和自适应能力,适合全局搜索,但其收敛性对初始化参数较为敏感,需要较长的搜索时间,易出现停滞现象;模拟退火算法的计算过程简单,鲁棒性强,适用于并行处理,但其收敛速度慢,收敛时间长,算法性能受初始值和有关参数的影响很大[3];A*算法适合全局最优路径规划,有较强的实时性,但随着搜索空间和存储数据量的增大,导致计算量增大和搜索时间变长,其实时性无法获得保证[4]。

考虑到车辆在野外的路径规划对实时性有较高的要求,选择实时性更高的A*算法进行路径规划。许多研究学者针对A*算法在相应场景下做了很多研究,如文献[5]中通过改进障碍搜索方式和启发函数,在牺牲了路径长度的情况下,提高了算法的性能和路径的安全性,但这是建立在室内仿真环境下,没有考虑复杂的野外环境以及遭遇未知障碍物的情况;文献[6]中通过采用优先子节点的生成策略来避免生成穿过障碍物栅格节点的路径,但仅仅通过一个简单的仿真实验并不足以验证该算法在实际环境下的可靠性;文献[7]中提出了一种双向时效A*算法,并采用多近邻栅格距离计算方案,在提高算法搜索效率的同时平滑路径,但不适合大尺寸复杂地图。总的来说,虽然A*算法有所改进,但仍有些问题没有得到很好的解决:没有考虑在复杂的野外环境下算法的可靠性;仅仅考虑优化搜索效率,却忽略了算法对车辆机动性的提高。

为了考虑在实际的野外环境,给车辆规划出一条快速到达目的地的最优路径,研究借鉴文献[6]中提出的优先子节点生成策略,结合真实的野外背景,计算得到了问题的解决方案。通过改进传统A*算法的搜索策略,提升车辆在野外环境下的机动性,同时提出了一种加入预处理的二次A*算法使车辆能够实时避障。首先,对目标区域进行预处理,得到不同地物的环境信息并加以区分;然后,为验证改正后算法的可靠性将其与A*算法进行实验对比。当车辆沿着规划好的全局最优路径行进中遇到未知障碍物时,实时更新环境信息,确定局部规划区域。再次,应用A*算法进行局部路径规划,将全局路径规划和局部路径规划相结合,从而规划出一条安全无碰撞的最优路径。

1 基于二次A*算法的路径规划

1.1 A*算法原理

A*算法综合分析BFS算法和Dijkstra算法各自的特点,取长补短,通过选择合适的估价函数来引导搜索方向,减小搜索范围,在保证搜索效率的情况下找到最优路径,是一种典型的启发式搜索算法[8-10]。由于A*算法在搜索过程中都是选择代价最低的节点,因此最终得到的路径也是代价最低的。在A*算法中最关键的就是估价函数[11],其公式为

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

(1)

其中:f(n)表示从起始节点经由任意节点n到目标点的估价函数;g(n)表示从起始节点到任意节点n的实际代价;h(n)表示从节点n到目标点的启发式评估代价。启发式函数h(n)表示任意节点n到目标节点的最小代价评估值。

通过实验发现A*算法在进行复杂环境路径规划时存在一个明显的缺点:无法在动态环境下进行路径规划。从A*算法的原理进行分析:估价函数值f(n)由g(n)和h(n)2个部分组成,而g(n)和h(n)的取值都和环境信息有着密切的关系。因此只有在全局环境信息已知的情况下,A*算法才能规划得到最优路径[12]。如果已知环境中突然出现未知障碍物或不可通行区域,A*算法就不能完成预设定的路径。

运动过程中突然出现障碍物情形如图1所示,其中黑色方格表示障碍物,其他白色方格为可通行区域,红色三角形表示起点P,红色圆圈表示目的地Q,虚线为规划的路径。当按照规划好的路径移动,运动到M点时突然遇到障碍物(灰色方格所示),此时就不能继续前进,此次路径规划失败。

图1 运动过程中突然出现障碍物Fig.1 Sudden obstructions during motion

1.2 改进A*算法

考虑到车辆在野地中的行驶速度会比在道路上慢得多,因此将道路设置为最高优先级,即道路凌驾于障碍区之上,在居民区等不可通行区域中假如存在道路,那么车辆依然可以在这些障碍区内的道路中行进。由于传统A*算法在生成8邻域的子节点时,没有优先顺序。研究借鉴文献[6]中的优先级子节点生成策略提出一种改进搜索策略。

节点O的子节点生成策略如图2所示。图2中把与当前节点O的8个方向上的节点(A、B、C、D、P、Q、M、N)分成2组,将水平和垂直方向上的节点(A、B、C、D)设为优先级,将对角线方向上的节点(P、Q、M、N)设为次优先级。在生成子节点的过程中,优先生成节点A、B、C、D,至于剩下的次优先级节点根据如下规则生成:

(1) 当相邻优先节点A、B或B、C或C、D或D、A同是在道路上的节点,则优先生成此方向与其对角线方向的子节点,比如节点A、B都在道路上,则优先生成子节点P,并且路径搜索方向偏向于OA、OB和OP;

图2 节点O的子节点生成策略Fig.2 Node O’s child node generation policy

(2) 当A、B、C、D同时都是道路或野地上的节点,则生成的子节点没有优先顺序;

(3) 当优先节点中包含有野地上的节点,则不生成与其相邻的子节点,比如节点A在野地上,则不生成子节点P、N,也就不会生成路径OA、OP、ON。

此方法优先选取在道路上的节点,从而在搜索路径时优先生成道路的路径。为了区分道路速度和野地速度,通过MapX工具分别计算出所规划路径在道路和野地的长度,计算方法是:首先判断间隔足够小的2个特征点是否同时在道路或野地上,然后通过迭代将每2个点间的距离分别相加得到道路和野地的长度。同时给道路行驶速度和野地行驶速度取一个适当的比例,这里设定车辆在道路的速度为57 km/h,在野地的速度为26 km/h。

1.3 基于二次A*算法的路径规划原理

由上所述,A*算法的估价函数与环境信息有着密切的关系。在环境信息未知的情况下,A*算法规划路径存在很大的不足,且无法动态规划路径。研究提出了一种预处理的算法,在进行路径规划前先将所选区域进行预处理,这样就可以充分掌握该地区的环境信息,进一步我们可以将该区域内的可通行区域和障碍物进行区分。同时,加入预处理算法能够有效弥补A*算法只能静态规划路径的缺陷。在复杂的野外环境下,当车辆由于遭遇极端天气等不可抗力因素导致原先可通行区域变得不可通行,这时就需要实时更新局部环境信息从而实现动态路径规划。

二次A*算法实质上就是已规划好的路径在运动过程中突然出现未知障碍物时,再次采用A*算法进行障碍区的局部规划而不需要重新运用A*算法进行全局规划,局部规划区域明显小于全局规划区域,因而局部规划的时间比全局规划少,提高了车辆运动的实时性。

基于二次A*算法的路径规划步骤如下:

(1) 地图预处理,明确全局环境信息后选取起始点和终点进行全局最优路径规划;

(2) 运动过程中突然出现未知障碍物,那么已规划好的路径就无法到达目的地,此时更新局部环境信息,确定局部规划区域,运用A*算法进行局部路径规划;

(3) 结合全局规划和局部规划得到最优路径。路径规划流程如图3所示。

图3 基于二次A*算法的路径规划流程Fig.3 Path planning flowchart based on the quatratic A* algorithm

1.4 确定局部规划区域

车辆运动过程中突然遇到障碍物时需要进行局部路径规划,当运动的下一步有障碍物时,记下当前点的位置,并检测前进路径中障碍物所占有的格子数,记为n,设s=n+5,当s为奇数,则s=n+6。局部规划区域如图4所示。①当下一步障碍物所占格子(图4中黑色格子)在当前格子(图4(a)中灰色格子)的正上方(或正下方),则局部规划区域为(s+1)×s,如图4(a)中第2行到第8行的方框区域(图4(a)中线条突出区域);②当下一步障碍物所占格子在当前格子的左侧(或右侧),则局部规划区域为s×(s+1),如图4(b)中第2行到第7行的方框区域(图4(b)中线条突出区域);③当下一步障碍物所占格子在当前格子的斜45°方向,则局部规划区域为s×(s+1),如图4(c)中第2行到第9行的方框区域(图4(c)中线条突出区域)。

图4 局部规划区域Fig.4 Local planning area

1.5 预处理算法分析

(1) 地图环境构建真实地图栅格化如图5所示。图5(a)表示的是真实地图,其中绿色的部分和白色的部分分别表示障碍物区域和可通行区域。图5(b)表示对真实地图环境加以栅格化,黑色表示障碍区,白色表示可通行区域。在将真实地图栅格化的过程中,把障碍区适当地扩大以达到车辆安全无碰撞通行的目的。

图5 真实地图栅格化Fig.5 Real map rasterization

(2) 地图要素的提取与表示地图要素可以分为障碍要素和可通行要素。障碍要素包括居民区、湖泊、河流等,可通行要素一般是指野外环境下可以通行的道路。各个地图要素的类型和处理方式如表1所列。

由于不可通行的障碍都是有特征的(线状要素或面状要素)而且相对于可通行区域要小的多,为了更方便路径规划,将不可通行区域提取出来,把表示障碍的区域或者曲线用红色绘制出来,表示不可通行区域;同时将可通行的道路用绿色绘制出来,表示可通行的道路。

障碍区域的提取与绘制见图6。图6(a)表示河流、湖泊以及居民区等障碍区域,白色条纹区域表示居民区,浅蓝色线条和区域分别表示河流和湖泊。经过地图要素的提取,将这些障碍区域用红色标出,对比图6(a)和图6(b),可以看出,在绘制障碍区域时,将表示线状要素的障碍区(河流)以及面状要素的障碍区域(居民区和湖泊)的边界适当扩大,来达到使车辆安全通行的目的。

道路及等距线绘制见图7。图7(a)中的黑色线条表示可通行的道路。经过地图要素的提取,将可通行的道路用绿色标出(见图7(b))。围绕在绿色道路周围的蓝色线条则是道路等距线,在进行路径规划时用来分析离道路的距离,从而达到快速接近道路的目的。

表1 地图要素及其处理方式

图6 障碍区域的提取与绘制Fig.6 Extraction and plotting of obstacle areas

图7 道路及等距线绘制Fig.7 Road and equidistant line plotting

2 实验验证

为了验证提出方法的可行性,选择沈阳某地区的dem地图进行实验。实验环境:Windows 10,Visual Studio 2010,MapX 5.0,以C++为实验平台。由于dem地图的区域过大,因此实验时选取其中具有代表性的一块区域进行分析。

研究将所选区域栅格化,具备居民区、湖泊、河流、道路等地图要素,可以满足实验的要求,如图8所示。将所选区域进行地图预处理,明确全局环境信息,结果如图9所示,图9中的栅格表示采样密度为8 000的实际大小。

图8 地图栅格化Fig.8 Map rasterization

图9 地图预处理结果Fig.9 Map preprocessing results

为了提升实验的可靠性,根据不同的地形条件选取4组不同的起点和终点进行对比实验,如图10所示。图10中黄线表示传统A*算法规划的路径,蓝线表示改进A*算法规划的路径,图10(a)～(d)对应的地形条件越来越复杂,相应的实验结果见表2和表3。当遇到未知障碍物时,二次A*算法动态规划的路径结果如图11所示,图11(a)是没有障碍物时的路径规划;图11(b)为突然遇到障碍物,红色网格区域为未知障碍区域;图11(c)为局部规划后,结合全局规划和局部规划得到的运动路径。

实际规划路径长度对比见表2,相应的搜索时间与行驶时间对比见表3。从实验结果可知:①预处理使全局环境信息更加明了,便于之后的路径规划。②改进搜索策略的算法虽然在实际规划的路径长度和搜索时间有所牺牲,但减少了行驶时间,提高了车辆的机动性。从实验结果来看,随着地形条件的不断复杂,行驶时间分别减少了26.6%、29.5%、32.4%和35.2%,说明改进后的算法适用于复杂的环境。③局部规划的区域比全局区域小,减少了总体规划时间,提高了车辆运动的实时性。

3 结论

针对车辆无法在环境信息未知的复杂野外环境下快速到达目的地的问题,提出了一种加入预处理算法的基于二次A*算法的车辆路径规划方法。通过地图预处理明确全局环境信息,提取障碍物信息和可通行区域,通过改进搜索策略的A*算法规划出一条快速到达目的地的路径,当出现未知障碍物时确定局部规划区域,结合全局规划和局部规划,得到最优路径。实验结果表明:改进算法规划的路径虽然牺牲了部分搜索时间和路径长度,但对于车辆的机动性有了极大的提高,有利于车辆在作战或演习中快速到达指定位置,同时地形越复杂,算法的优化程度越明显,适用于复杂环境的路径规划。并且在遇到障碍物时,由于局部规划区域比全局区域小,因而减少了总体的规划时间,提高了车辆的实时性。