针对多障碍陆战场路径规划的改进A*算法研究

张明路，沈祺宗，高春艳，李满宏

（河北工业大学机械工程学院，天津 300130）

1 前言

在多障碍陆战场环境中，路径规划[1]即为在存在障碍物的前提下，利用栅格法等方法构造地图，根据搜索算法（A*[2]，D*[3]，遗传算法[4]，蚁群算法[5]等）生成从初始节点到目标节点的最优路径。其中A*算法作为静态启发式算法，更适合处理复杂障碍，并且它在解决静态全局规划问题时还具有参数少、效率高等优点。

文献[6]提出利用微分改进A*算法，有效降低了转折次数，但是涉及了大量计算；文献[7]一种改进的D*LIte算法—Field D*，对栅格进行线性插值使路径点不局限于栅格点中心，搜索方向也不再受限于π4整数倍；文献[8]则将该线性插值法应用于A*中，但是需要对栅格地图进行定义修改。因此提出一种将A*算法与元胞自动机[9]相结合的路径规划算法，改进估价函数使当前点可以直连扩展Moore的第二层邻域任意点，然后在依据通行性判定规则，继续修改估价函数，添加多组限制条件，进行第二通行次可行性邻域判定，从而对路径的可行性提供优化。

该混合方法不但减少了路径长度与转向角度，同时能在复杂环境中满足障碍物回避[10]。

经仿真验证，路径满足陆战场行军灵活性的要求，具有可行性与有效性。

2 A*算法改进

2.1 传统A＊算法

传统A*算法属于全局路径规划，利用从初始状态和当前状态到目标状态估计所需的费用等信息，在选择下一个节点时对当前结点距离终点的距离作出估计。

设计估价函数是A*算法的核心，本实验估价函数参考欧几里得距离估价法，假设起点S的坐标（Hx，Hy），终点G的坐标（Mx，My），中间点N的坐标（Nx，Ny），则欧几里得距离表示为：

A*算法在搜索中设置两个表。Open表收录了已知生成而待遍历的邻域点，Close表中收录了已被遍历的邻域点。

若检查到在Open表中留存重复节点，则依照欧几里得估计函数计算并对照重整Open表中的搜索节点，并录入close表中。最后将保留下来的节点排列出来即为规划所得路径。传统A*算法流程，如图1所示。

图1 传统A*算法流程图Fig.1 Traditional A* Algorithm Flowchart

2.2 改进估价函数

传统A*算法虽然遍历效率高，但是首先由于搜索模式为直线搜索，使得传统A*算法中的最小转角为45°，当存在目标点与某一路径点间的相对角度小于45°时，路径会出现锯齿式的折叠。为了解决这一问题，设计将搜索邻域内的偏转角度继续缩小，因此参考元胞自动机理论，对A*算法的搜索领域进行改进，首先引入扩展Moore型邻域，如图2所示。其次，由于设置扩展Moore型邻域存在两层邻域点，即内层8个与外层16个，为了使路径能够直接连接最外层邻域，需要改进估价函数使其依旧能够遵循最小代价排序原则，如图3所示。

图2 常见3种元胞邻域结构Fig.2 Common 3 Cell Neighborhood Structures

图3 改进前后搜索方式对比Fig.3 Comparison of Search Methods Before and After Improvement

因此需要改进A*的估价函数，已知路径点的选择原则为选择邻域中f（x）最小值点，在图3中，需要使当前点A搜索B，C（或C，D）两点时，B（或D）点的f（x）小于C点的f（x）。则设存在一条直线k（x，y）经过目标点，分别改变目标点的x，y值，使目标点存在水平或垂直方向上的平移。设计该曲线拟合公式为：

式中：xg,yg—位置目标点的坐标，A点为起始点。分别计算B（或D）点与C点的估价值f（B）与f（C）进行对比，根据获取多次曲线拟合图，如图4所示。

图4 系列1（AC）与系列2（AD）曲线拟合Fig.4 Series 1（AC）and Series 2（AD）Curve Fitting

计算f（C）与f（B）曲线值差，如图5所示。

图5 系列1（AC）与系列2（AB）曲线差值Fig.5 Series 1（AC）and Series 2（AB）Curve Difference

由曲线拟合分析可知当遍历点为B或D点时，均存在一个固定值t，该值为B点或D点的x，y坐标与目标点坐标的差x1，y1的比值，即t=x1/y1，该值随B点或D点的选择而变。

由此，采用逼近原则，多次对B/D点选择不同的x1，y1值，计算其f值与t值，则多次计算获得的数值逼近，如表1所示。

表1 数值逼近Tab.1 Numerical Approximation

计算可得t（AD）约为0.6667，t（AB）约为1.4721。下一步则需要将该t值融入到改进估价函数中。A*算法为启发式算法，具有方向性，其遍历方向一定指向目标点。由图3可知，BFGJ四点均相较于CKLM点发生了x轴方向位移，DEHI相较CKLM发生了y轴方向位移。因此均可适用于t（AB）和t（AD）。

根据曲线拟合结果，f（B）或F（D）与F（C）的值大小对比根据t值的变化而变化。因此在A*算法中添加流程，即每遍历邻域内的各点时，计算该点的t值并于t（AB）或t（AD）进行比较，同时考虑到内层可能存在障碍物，如图3 当C，O，N中存在一点为障碍物时，A点无法直接连接到B或D点。因此设置m（x），计算遍历点与A点直线经过的障碍数，设置n（x），计算遍历点与A点的直线距离。

至此归纳改进后的A*算法估价函数如下：

经过此步改进后，A*算法的搜索邻域将呈现为扩展Moore型，并且当邻域内无障碍时，外层节点的f（x）将小于内层节点，即满足A*规则且实现路径跨层连接。

2.3 添加通过性选择功判定

在复杂陆战场中，部队车辆需要随时临时调整，当通过狭隘路段时，可能出现被狭隘路口阻拦无法通行及掉头的问题。传统的A*算法只负责计算路径，为追求最短路径而可能规划出实际无法通行的路径，而没有考虑通过性问题。本实验考虑在路径搜索过程中添加筛选功能。由图2可见，扩展Moore型邻域具有24个遍历邻域，本实验假设部队车辆能够通过加上本车宽度换算到栅格地图上一共3个像素宽的路口，因此需要该拓展节点放入closel‐ist之前附近8个邻域必须为无障碍，即相邻8个栅格的值都为0。

因此将通行性判定简化为转换为大小为Moore型的车队能够行驶出扩展Moore型的最外层16个元胞的问题。在此归纳代表车队的9个元胞组成的Moore型数学集合为：

式中：Z—整数集合。归纳扩展Moore型外部16元胞数学集合为：

根据问题列出集合1能够从集合2的包围中正常行驶出的路线，即部分cj需要满足元胞值为0，分析可行路径得出cj需要满足如下条件：

归纳上述集合1集合2与通行条件，构造map函数，须同时满足集合1中c1=0与式（6），如式（7）所示。

式中：∑fMoore—以车辆为中心的Moore型邻域；f∑proMoore—扩展Moore 型外部16 个元胞。当式（7）满足式（4）与式（6）时，map（x，y）=0，判定当前区域可以通过。根据数学条件，建立通行模型，如图6所示。

图6 路口通行逻辑模型Fig.6 Intersection Traffic Logic Model

至此，获取符合通过性分析的邻域点，将此点存入closelist，继续循环流程直到完成路径规划。

修改过后的A*算法整体流程图，如图7所示。

图7 添加通过性分析后后的A*流程图Fig.7 A* Flow Chart After Passing Analysis

3 Matlab仿真实验

为验证A*算法改进后的效果，本实验根据战场环境模拟形成栅格地图，利用Matlab2018进行路径规划仿真。

3.1 扩展搜索邻域验证

改进后的A*算法能够实现跨网格的偏转，相较于改进前减少了路径长度与偏转距离，如图8所示。

图8 改进前后路径对比Fig.8 Path Comparison Before and After Improvement

应用于100*100地图上，改进前后A*算法路径规划效果，如图9、图10所示。

图9 改进前Fig.9 Before Improvement

图10 改进后Fig.10 After Improvement

根据上述路径对比，获得数据分析结果，如表2所示。

表2 传统A＊与改进后A＊对比Tab.2 Comparison of Traditional A＊ and Improved A＊

通过对比，经过对搜索邻域进行改进后，路径平滑度提升，同时路径长度缩短了13.16%，累计偏折角度减少26.8%。

可见改进搜索邻域后确实对算法实现优化。

3.2 通过选择性验证

为验证改进通过性选择分析前后效果，均在地图右下角设置一道狭隘路口，如图11、图12所示。

图11 传统A*算法Fig.11 Traditional A* Algorithm

图12 改进A*算法Fig.12 Improved A* Algorithm

可见相对于改进前，改进后的A*可以绕过狭隘路段重新规划路线，表明改进具有可行性。

4 结论

这里提出的改进A*算法搜索邻域、改进估价函数与添加通行条件判定函数，可将搜索邻域个数从单层的8个变为双层的24个，最小转交减小为18.3°，能够有效解决传统A*算法存在的路径非最短及转折角度过大的问题，增加的通过性逻辑判定函数能够有效绕过直径小于3 的狭隘路段，提高行驶的安全性与应变能力，相较于传统A*算法，更加适应实际道路环境。