基于通行性分析的分层越野路径规划方法

闫星宇，杜伟伟，石 昊

（北方自动控制技术研究所，太原 030006）

0 引言

在战场环境下，机动部队在避险行进、野外行进、隐蔽行进等机动任务中，需要完成野外环境下几十乃至上百公里的大范围地域越野路径规划。相对于传统的有路网路径规划，越野路径规划需要处理大量环境信息，如坡度限制、地表覆盖及地面起伏程度等，在面临大范围地域的野外路径规划问题时，会面临数据量激增，计算量过大的挑战。因此，研究大范围地域越野条件下机动车辆的路径规划方法，对战场环境下的部队执行机动任务具有重要意义。

由于越野路径规划计算量较大，为了解决实时性问题，常使用缩小搜索空间的启发式算法进行规划。A*算法属于启发式搜索算法的优化算法，其算法建立在Dijkstra和BFS算法基础上，是一种广泛使用的路径规划算法。范林林等设计了以通行速度为估价函数的A*算法，多维考虑了地貌因素对车辆越野行车速度的影响，但环境建模时选取的栅格较大，无法准确衡量栅格的通行性能。吴天羿等设计了考虑坡度和粗糙度约束的A*路径优化算法；王坤等设计了基于禁忌表的越野路径规划算法，充分考虑了野外地理环境对车辆通行能力的影响，但存在处理数据过多，时效性下降的问题。

尽管目前越野路径规划方法和传统道路路径规划方法相比较，能够考虑环境因素对机动车辆机动能力的影响，但详尽的环境数据分析使路径规划数据量过大，在处理大范围地域的部队野外机动业务时，会因为处理数据过多、计算量过大而无法保持时效性。同时，如果为了减少计算量而降低路径栅格分辨率，又会导致规划结果不可靠。

1 分层越野路径规划方法

1.1 大范围地域的越野路径规划问题

越野环境下的路径规划需要在无路网条件下规划车辆的行进路线，使得车辆在该路径行驶时，时间及油料等综合耗费最少，该问题可以建模为：

其中，Z 为路径总耗费；S 为任务区域；（x，y）为路径点；f（x，y）为该路径点的通行耗费。由于在越野机动时，车辆受到环境的影响比起道路行驶时更大，为了保证机动任务顺利进行，f（x，y）需要综合考虑地表覆盖种类和地形起伏程度对车辆通行能力的影响。

1.2 分层越野路径规划方法

越野环境下的路径规划为了更加准确地描述环境，需要将（x，y）代表的栅格大小适配车辆长宽，导致数据量和计算量过大，极大地影响了路径规划的时效性。因此，需要一种路径规划方法，在合理量化环境影响数据的前提下，提高大范围地域越野路径规划时的实效性和准确性，本文使用分层规划方法解决这一问题。

如图1 所示，分层越野路径规划方法是指将野外路径规划过程分层，在两个不同分辨率下对野外区域环境进行分层建模，并在低分辨率模型规划结果的基础上进行高分辨率路径规划。

图1 分层越野路径规划方法示意图

整体方法流程如图2 所示。

图2 分层越野路径规划方法流程图

1）根据任务区域裁切地图数据、确定高低分辨率比例，并以两种不同分辨率分层构建栅格模型。

2）使用针对通行速度优化的A*算法对低分辨率栅格模型进行路径规划，并输出规划结果。

3）使用考虑避障的A*算法在高分辨率层，依次处理低分辨率规划结果所经过的每个区域。

4）将所有高分辨率层的路径规划结果合并输出。

2 分层环境建模及通行性分析

2.1 分层环境建模

越野路径规划由于没有路网拓扑辅助，首先需要进行野外环境建模，即对地理环境进行描述，主要是对需要的区域环境信息进行特征提取和表达。常用的环境模型有可视图法、Voronoi 图法、拓扑图法和栅格图法等。其中，栅格化建模能够清晰地描述环境信息，并且建模简单、维护方便、易于构建高效的数据索引，是大多数路径规划方法的首选。栅格大小的选取直接影响着路径规划算法的性能，想要更准确的环境描述，栅格就要尽可能地小，但是存储数据量会急剧增大，使得计算量大幅增加，系统实时性降低；与之相对的，栅格选取较大、数据量变小能够有效提高路径规划速度，但会导致对环境障碍敏感度降低，无法规划出有效路径。为此，本文采取分层环境建模的方式解决栅格大小选取的矛盾问题。

分层环境建模的基本思想是使用高程数据和地表覆盖数据，对规划区域分层构建栅格模型。首先对大范围区域内的野外环境进行低分辨率栅格化，每个栅格都保存有地表覆盖类型和栅格区域粗糙度数据，然后再次对野外环境进行高分辨率栅格化，每个栅格都保存有坡度数据。通常高分辨率栅格可以采用5 m 分辨率，而低分辨率栅格需要结合实际任务区域计算得到，一般保持两个分辨率的路径规划层单次处理数据量相近，可以通过如下方式得到：

设整个区域边长为R，低分辨率栅格长度为r，则

将r 值取整百即可作为低分辨率栅格边长。

2.2 地表通行性分析

在低分辨率栅格模型中，地形量化主要考虑地表覆盖类型和地形起伏对车辆机动能力的影响。在栅格中，将地表覆盖类型的影响量化为地表覆盖通行度，越难以通行的地表覆盖类型，设置其通行度越低；将地形起伏的影响量化为地表粗糙度，通过计算区域内各高程点到拟合平面距离的方差得到。

根据全球30 m 地表覆盖（GlobeLand30）数据集，将地表覆盖类型分为农田、森林、草地、灌丛、湿地、水体、苔原和不透水层、裸地和冰雪。根据不同地表对车辆通行能力的影响，分别设置地表覆盖通行度如表1 所示。

表1 地表属性通行度表

假设栅格区域内有m 个地表覆盖数据点，任意一个点的通行度为r，则区域地表覆盖通行度可由如下公式获取：

在高分辨率情况下，地形量化主要考虑因坡度形成的障碍对车辆行进的影响。在量化时，将坡度大于车辆最大爬坡度的栅格设置为不可通行。高分辨率地形的高程数据来源于5 m 分辨率的栅格，设每个栅格高程值为H。

本文引入窗口移动法，计算当前栅格于其相邻8 个栅格的坡度大小。窗口移动法采用3×3 窗口，如下页图3 所示。

图3 栅格的邻接八坡度示意图

以逆时针方向顺序，以此计算相邻栅格相对于中心点（i，j）的坡度大小S，其中，1≤k≤8。具体公式如下：

当arctan（S）小于车辆最大爬坡度时，该相邻栅格可通行。

3 分层越野路径规划算法

3.1 改进A＊算法

启发式A* 算法是路径规划中使用最多的算法。传统意义上的A*算法是以周围地形信息一致的前提下进行的，即假设同距离下消耗相同，而在研究战场环境下的最短路径问题时，需要考虑地形因素对车辆机动的影响。在研究低分辨率模型的路径规划时，将地表覆盖通行度和地表粗糙度作为消耗系数，对实际通行距离进行放缩来描述栅格之间的实际消耗；在研究高分辨率模型的路径规划时，使用当前地格到目标地格的距离来描述栅格之间的实际消耗。

A*算法的运作需要维护Open、Closed、PassCost 3 个表，Open 表负责存储待检查的栅格，初始化时将起始栅格放入Open 表中。Closed 表用来存储所有不需要再次考察的栅格，从而避免重复搜索已通行的栅格，初始化时将所有不可通行的栅格加入到Closed 表中。PassCost 表用来检查当前栅格的邻域栅格的可通行性。

3.2 栅格距离模型

由于模型采用正方形栅格的方式建模两点之间的距离估算可以按照图4 建模，因此，模型中任意两点之间的距离D 可以表示为：

图4 起终点之间的距离估算

3.3 估价函数优化

启发式A*算法中估价函数定义为f（i，j）=g（i，j）+h（i，j），f（i，j）为算法在当前节点对应的启发函数，它由两部分组成，第1 部分g（i，j）是起始节点到当前节点实际的通行代价，第2 部分h（i，j）是当前节点到终点的通行代价的估计值。

在低分辨率层进行规划时，实际消耗g（i，j）通过实际距离、栅格地表覆盖通行度和栅格地表粗糙度计算得出的通行时间衡量，其公式为：

在高分辨率层进行规划时，需要建立一个tabu 表，用于标记栅格相对于相邻格网的通行禁忌表，当栅格（i，j）的坡度大于最大爬坡度时，令tabu（i，j）=0。

栅格（i，j）的实际消耗g（i，j）。通过实际距离衡量，其公式为：

3.4 算法流程

在给定起始格元S 和目标格元E 的前提下，战场环境下机动车辆生成最短路径的A* 算法流程，如图5 所示。

图5 A*算法步骤流程

4 实验结果及分析

本文提出的越野路径规划方法在国产麒麟系统平台上实现仿真，采用的数据是某地ALOS PALSAR 12.5 m DEM 数据经过插值计算得到的5 m 高程数据以及清华大学2017 年全球10 m 分辨率地表覆盖数据，空间范围为65 km×75 km，规划区域展示如图6 所示。本实验以国内最多的现役主战坦克96 式坦克在该区域执行越野任务为背景，根据坦克最大爬坡度，将坡度约束设为31°。为了保证坦克行进路线的可行性，规划路线分辨率应以5 m 以上精度为优。

图6 规划区域展示

实验中使用本文提出的分层越野路径规划方法和A*避障算法寻路方法，对不同分辨率条件下的地图数据进行仿真模拟。分别设定A*避障算法规划分辨率为50 m 和20 m，分层越野路径规划方法规划分辨率为20 m 和5 m。

图7 为使用避障A*算法规划在地图数据上进行规划的结果，其中，阴影区域越浓代表坡度越大，粗线为50 m 分辨率规划结果，细线为20 m 分辨率规划结果。

图7 A*坡度避障规划结果（局部）

图8 为分层越野路径规划方法在低分辨率层上的规划结果，左图展示了低分辨率层规划结果在区域高程地图上的情况。右图展示了低分辨率层规划结果在区域地表覆盖地图上的情况，区域内地表覆盖主要为黄色裸地、绿色草地，并伴有少量蓝色水体、白色冰雪、深绿森林等。

图8 低分辨率规划结果

图9 为高分辨率层规划结果在区域坡度地图上的部分展示。其中，阴影区域越浓代表坡度越大，透明区域为低分辨率层规划路径，粗线为20 m 分辨率规划结果，细线为5 m 分辨率规划结果。

图9 高分辨率规划结果（局部）

表2 为A*避障算法规划和分层越野路径规划在不同分辨率条件下进行实验的结果对比。

表2 两种路径规划方法结果对比表

从以上实验结果能够看出：

1）基于通行性分析的分层越野路径规划所选择的通行区域有着更易通行的地表覆盖和更平坦的路面。比起直接使用A*避障算法，基于通行性分析的分层越野路径规划方法产生的规划结果不仅能够避开坡度障碍，还能引导车辆避开通行性较差的复杂地域。

2）基于通行性分析的分层越野路径规划方法能够有效缩减越野路径规划的规划时长，并能够完成高精度的路径规划来保证路线可行性。实验结果表明，未经优化的A*算法在分辨率由50 m 提升至20 m 时，规划时长急剧升高，并且由于单次规划数据量过大，无法顺利完成实验背景下分辨率为5 m的越野路径规划任务；而分层越野路径规划方法在相同分辨率条件下有更好的表现，且规划时长受分辨率影响较小，当分辨率达到5 m 时仍然能够以较短的时间完成越野路径规划，从而及时为坦克部队完成路径规划任务，并保证规划结果的可行性。

5 结论

本文使用分层越野路径规划和改进后的A*算法，对大范围地域的车辆越野路径规划问题进行了研究。通过提出分层规划概念，设计了基于通行性分析的分层越野路径规划方法。在规划算法中，引入了考虑地表覆盖和地形粗糙度的通行性分析，设计了考虑地表覆盖通行度和地表粗糙度约束的改进A*路径规划算法。仿真结果表明，本规划方法相对于传统A*算法，能够降低规划过程计算量，并规划出更加合理的越野区域通行路径。

本文在进行通行性分析时参数仍可以优化，下一步研究工作可以继续在相关方面进行研究，用以完善A*算法的估价函数。