基于数字地图和加权A*算法的战术路径规划

苏玉婷 原大川 侯磊

摘要：本文首先对在军事仿真中经常使用到的数字地图进行了详细阐述；其次，对在静态路网中求解最短路径的A*算法进行了介绍，并对静态加权A*算法进行了分析和实现；再次，提出了一种进行战术路径规划的实现方法；最后，运用MATLB仿真平台对某真实岛屿的数字地图和静态加权A*算法进行结合，实现了战术路径规划，证明了该方法的有效性和快速性。

关键词：静态加权A*搜索算法；数字地图；战术路径规划；MATLAB

中图分类号：TP391.41 文献标识码：A 文章编号：1007-9416（2018）08-0112-02

A*算法[1]是一种静态路网中进行路径规划时求解最短路径最有效的直接搜索算法，该算法可针对真实地图，可以使得寻路结果的逼真度和真实性得到体现。

以数字地图为基础，可以建立数字化战场所必需的“战场环境信息系统”。在现代战争中，数字地图是高技术武器的一个重要支撑。[2] 本文首先对数字地图进行了环境建模，建立了二维栅格地图和三维高程模型；其次，运用静态加权A*算法在已知环境下进行战术路径规划。

1 数字地图

1.1 基于栅格数字地图的环境描述

栅格（像素）数字地图是以一系列大小相同、排列有序的栅格像素的灰度值表示的地图，叫栅格（像素）数字地图[3]，它通常由一个图像矩阵G表示，即：

栅格数字地图是采用整数对地形符号进行表示的，其位置与分布表示为符号所在位置的像素的有序集合。

1.2 数字高程模型

数字高程模型是用一组有序数值阵列形式表示地面高程的一种实体地面模型。一般认为，数字地形模型（Digital Terrain Model，DTM）是描述包括高程在内的各种线性和非线性地貌因子组合的空间分布，如坡度、坡向、坡度变化率等等。[4]真实的数字高程模型如图1所示，可在Index of /srtm/version2_1/SRTM3/Africa数据库进行下载，SRTM3表示采样间隔为地球等角坐标系的3角秒（约90米）。

1.3 数字地图的MATLAB实现

MATLAB可用于实现图形化建模，实现数据的可视化。首先建立createFigure（）函数用于创建一个大小为60×60的空图，创建函数initializeField（）将地图进行初始化。然后，读取已经建立好的地图矩陣，将其进行可视化，建立好的二维栅格地图如图2所示。将二维栅格地图添加高程信息，进行数字高程模型的建立。建立函数imread（'DEM.tif'）读入高程矩阵，将其进行可视化。

2 A*搜索算法

2.1 传统的A*算法

A*算法是一种最佳优先搜索算法，它通过搜索在所有可能路径中代价最小的路径来寻找目标。A*算法的代价函数一般表示为：

其中，f（n）是从起点到终点的估计代价函数，g（n）表示从起点到当前点的实际代价值，h（n）表示从当前点到终点的最短路径的估计代价值。数字地图中，横向移动和竖向移动，移动代价是一个节点的距离，斜向移动的移动代价是×节点的距离。采用四向邻域的移动方式将避免开放和小数的计算，也将提高算法的计算效率。因此，在仿真中我们采用的是曼哈顿距离。

2.2 加权A*算法

虽然传统的A*算法能保证在静态网中找到最优解路径，但是它要检查所以具有相同价值的路径以找到最佳路径，搜索速度较慢。加权A*算法/静态加权算法加大了启发函数的权重从而减少了搜索深度，在搜索结果可接受的前提下加快了搜索速度。其公式如下：

研究表明，加权A*算法的速度是传统A*算法的ε倍。[6]

3 战术路径规划

机动是军队战场主动权的体现，在高技术装备的条件下，沿道路机动将是陆地战场的最主要机动方式；而对具体的战斗而言，越野机动占有及其重要的地位。沿道路机动和越野机动都会受到地形的限制和影响。分析地形对机动的影响及其大小，在于选择最为合理的机动路线。综合分析地形对沿道路机动运动的影响或对越野机动的影响，目的在于选择距离最短、最便于机动、隐蔽性最好、危险性最少，要点地形有利且便于控制的机动路线，以便在最短时间内快速到达目的地。[5]地形对机动的影响包括地貌、水系、植被和居民地四个方面。不同地形条件下各级公路的行车速度如表1所示，本表摘自交通部1981年《公路工程技术标准》。

从表1可看出，在丘陵上的行车速度是在平原上行车速度的50%-67%，因此，在丘陵道路上的通行代价大约是在平原道路上通行代价的两倍。

本文在运用MATLAB在真实数字地图上使用加权A*算法进行路径规划时，将地形对通行的影响转换为在不同地形条件下比较合理的通行代价比例，如表2所示。

使用三维地形栅格地图和数字高程模型对环境区域进行建模，从起点开始寻找相邻的可能到达或者可以通过的方格，同时按照不同的地形条件改变通行代价的设置。改进加权A*算法进行战术路径规划的代价函数可表示如下：

其中x（n）表示不同地形的不同通行代价。经过测试，将ε设置为10，即：

运用MATLAB读取坐标是北纬xx度东经yy度的数字高程模型（岛屿模型），大小为408×408，完成设置起点和目标点后，利用改进加权A*算法进行战术路径规划。其结果如图3所示。

4 结果分析

真实可信的行为是军事概念模型行为模型可信度的核心。经过上文的分析，改进加权A*算法在真是数字地图上进行战术路径规划的可行性，逼真有效的模型可使得模拟训练的效率得到很大提高。随着科技的不断发展，路径规划技术所要求的环境将会越来越复杂，寻路算法迅速响应复杂环境变化的能力需要得到不断提高。将好的环境建模技术与优秀的路径规划算法相结合进行优势互补，以期更加适应复杂的作战仿真环境。[7]本文在进行环境建模时运用到了GIS（地理信息系统）的一些技术，提高了仿真环境的逼真度，同时运用改进加权A*算法，实验结果也表明该方法的能够在真实数字地图上进行路径规划的有效性和搜索的快速性。

参考文献

[1]P. E. Hart， N. J. Nilsson， and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs[J].IEEE Trans. Syst. Sci. and Cybernetics，SSC-4（2）：100-107，1968.

[2]汤国安.我国数字高程模型与数字地形分析研究进展[J].地理学报，2014，69（09）：1305-1325.

[3]李兆旺.电子地图的内涵及其优势[J].科技视界，2012，（23）：122+226.

[4]王峥.基于GIS的泾河流域特征信息提取分析和降水径流预测[D].西北农林科技大学，2012.

[5]白多宁.军事地形学训战实用词典[M].北京：国防大学出版社，2010.

[6]Pearl，Judea.Heuristics： Intelligent Search Strategies for Computer Problem Solving[M]. Addison-Wesley Pub.Co，1984.

[7]马仁利，关正西.路径规划技术的现状与发展综述[J].现代机械，2008，（03）：22-24.