中国指挥与控制学会会刊 
在陆战场各种作战行动中,机动是构成作战基本过程的一种典型作战行动[1]。因此,构建合理的机动路径规划仿真模型,是作战仿真实验系统建设的基础。
在仿真实验系统中,现有的路径规划模型,通常只指定机动所经过的地点,然后用若干个首尾相接的直线段所构成的折线表示机动路线。当遇到湖泊、河流、雷场等障碍因素时,通常采取两种处理方式:强行通过或停止机动,显然缺乏合理性。在实际行动中,机动单元会根据实际情况,灵活选择机动路线(曲线)绕开障碍因素。
针对该问题,结合路径规划相关技术与方法,探索适应陆战场环境下机动单元路径规划仿真模型的研究就显得极为迫切,不仅有助于提高作战仿真实验系统中机动模型的有效性和合理性,还能为机动单元选择机动路线提供优选方案。
1 机动路径规划与最优路径问题
在陆战场,坡度、土质、植被、障碍(包括雷场、铁丝网等)都会对机动产生影响,机动单元要通过某个区域必须要付出一定的时间代价。因此,选择机动路线的一般原则是从出发点到目标点进行机动所用的时间最少。
按步长对作战行动的推进以及按格网对战场环境的划分,分别从时间和空间角度为仿真单元机动的离散化模拟提供了基础,并统一了不同环境因素影响下的时间计算方式,进而可以利用图论中的最优路径算法对机动路径规划问题进行分析解决。机动单元路径的规划先于机动行动实施,本文在路径规划中采用地图格网单元的大小作为途径点的探索步长,以避免仿真步长的大小对规划算法准确性的影响。
2 最优路径算法分析
对最优路径问题的研究已经有多年历史,形成的最优路径算法也层出不穷,且已应用到各个领域。每种算法具有不同的特点,并没有哪一种算法能够在任何情况下都保持优势[7]。因此,针对陆战场机动单元的路径规划问题,首先要对陆战场机动的网络特性进行分析,并结合常见最优路径算法的特点,对其进行筛选分析,最后对这些算法进行实验对比,确定最优算法。
2.1 最优路径问题的网络特性
最优路径问题根据不同的网络特性可以进行不同的分类[8],如图2 所示。
首先,战场态势是瞬息万变的,机动单元受战场环境和态势的影响,其机动性能也将随之变化,因此,作战机动的路径规划属于动态最优路径问题。
其次,整个机动任务看作由相邻点构成的多次机动子任务。因此,作战机动的路径规划属于单源单目标最优路径问题。
再次,战场环境的空间数据模型、战场态势、作战单元机动性能以及机动速度的计算模型一旦确定,就可以通过最优路径算法求得机动路径规划的最优方案。因此,陆战场机动单元的路径规划属于确定型最优路径问题。
最后,在格网化的战场环境空间数据中,仿真实体在任意格网点的机动,只可能与其相邻八个方向的格网点具有邻接关系,如图3 所示。因此,作战机动的路径规划属于稀疏型最优路径问题。
2.2 常用最优路径算法分析
本文从图的角度对常用最优路径算法进行分析,如表1 所示。其中V代表图的顶点数,E代表图的边数。
表1 常用最优路径算法 |
| 算法 | 类型 | 适用负权边 | 时间复杂度 |
|---|---|---|---|
| Dijkstra | 单源多目标 | 否 | 依赖于最小优先队列 的具体实现 |
| Bellman-Ford | 单源多目标 | 是 | O(VE) |
| Floyd-Warshall | 多源多目标 | 是 | O(V3) |
| SPFA | 单源多目标 | 是 | 依赖于有向图的结构 |
| Johnson | 单源多目标 | 是 | O(V2lg V+VE) |
| A* | 单源单目标 | 是 | 依赖于启发因子 |
| 动态规划 | 单源多目标 | 是 | O(V+E) |
其中,动态规划算法具有阶段划分及无后效性的适用条件,决定了其不适用于具有回路的格网图;Johnson算法在于使Dijkstra算法支持负权边,但对于陆战场格网图,本身就不存在负权边。
因此,理论上适用于陆战场格网图的最优路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法、SPFA算法以及A*算法。其中,Dijkstra算法与A*算法在计算时只需获取当前点的后继即可,理论上支持的陆战场格网图可以无限大;其他三种算法可以计算当前点与其他所有点之间的最优路径,尤其是Floyd-Warshall算法可以提前计算所有点之间的最优路径,实现“一劳永逸”的效果。除此之外,要将算法应用到机动单元的路径规划模型中,还要对陆战场各种环境因素对机动的影响、寻路的区域与方向等进行分析。
3 陆战场机动路径规划分析
3.1 机动速度
虽然机动过程会带来一定的油耗和损伤代价,但机动速度依然是量化作战单位机动时最主要的效率指标[1]。机动速度取决于机动单元的机动性能与环境因素,其中机动性能决定了机动单元的标准速度(或平均速度),环境因素对机动速度的影响通常都采用速度修正系数 来体现。环境因素越不利于机动,则D的值越小,反之则越大。因此,机动速度为多种环境因素综合影响下的修正速度:
$v=v_{s} \prod_{i \in \text { 环境因索 }} D_{i}+v_{r}$
其中 为当前机动单元下的标准速度, 为修正系数, 为随机因子。
3.2 环境因素
影响机动的环境因素错综复杂,要面面俱到显然是不现实的,必须要结合陆战场环境模型对现实世界的抽象模型与结构化的描述方式,才能使路径规划模型具有实现的可行性。本文以军内“**战场地理环境模型标准”为基础,对机动影响因素的分类如表2 所示。
表2 机动影响因素 |
| 影响因素 | 要素分类 |
|---|---|
| 居民地 | 独立房屋、普通街区、窑洞…… |
| 道路 | 国道、省道、大车路、标准轨单线铁路…… |
| 水系 | 常年河、时令河、水库、常年湖…… |
| 植被 | 疏、密 |
| 桥梁 | 人行桥、公路桥、铁路桥、立交桥…… |
| 障碍 | 滑坡、陡崖、防步兵雷场、防坦克壕…… |
| 工事 | 堑壕、交通壕、坑道、坦克掩体…… |
| 地质 | 沼泽、沙、泥土、岩石、稻田…… |
| 地貌 | 高山、丘陵、平原、高原、盆地…… |
| 高程 | (数值型) |
| 坡度 | (数值型) |
各种环境因素对速度的影响,同样通过修正系数进行调整,以徒步机动为例,坡度对速度的修正系数如表3 所示。
表3 坡度对徒步机动的速度修正系数 |
| 坡度(单位:度) | 速度修正系数 |
|---|---|
| [0,5) | 1.0 |
| [5,15) | 0.8 |
| [15,25) | 0.6 |
| [25,32) | 0.5 |
| [32,45) | 0.4 |
| [45,60) | 0.3 |
| [60,90) | 0.2 |
3.3 区域限制
陆战场作战单元的行动区域是有限的,因此,机动路径规划分析必须限制在一定区域,即根据出发点和目标点限定最优路径的寻路范围。区域限制的目的在于:1)是可以避免对不必要的区域进行寻路,减少可能路径数目急剧增加甚至出现指数级爆炸增长带来的影响,进而节约时间提高效率;2)是避免出现理论上可行而无现实意义的绕行方案,例如当部队遇到无法通过的河流时,可以通过寻路制定绕路方案,当绕路距离太大导致机动时间超出通过工程部队架设浮桥通行的代价时,该绕路方案便偏离了最初目的,或者绕路太远超出了作战区域也便失去意义。
在作战实验仿真系统中,通常采用三种方式对机动路径规划的区域进行限制:1)是数据限制,即当仿真系统只载入了当前作战行动的数字地图数据时,以数据的图幅范围进行限制即可;2)是自动限制,即根据出发点和目标点的坐标范围,系统自动计算并确定具有一定缓冲距离的外接矩形作为限制区域;3)是人工限制,即用户根据具体的行动需求,通过人机交互指定一定的区域范围进行限制,指定方式包括圆形、矩形和多边形区域等。
需要强调的是,区域限制的方式要根据实际情况进行选择,其中人工限制的方式只是提供一种区域限制的灵活处理方式,对于大范围道路稀疏区,人工限制可能会导致算法失效,此时,可采用降低战场环境模型格网分辨率的方式(即增大格网大小)的方式进行解决。
3.4 寻路方向
陆战场格网数据模型决定了机动单元路径规划,可采用四方向和八方向两种方式进行寻路。虽然,根据下一个途径点结合行进速度和仿真步长,可以准确计算出一个步长后机动单元所抵达的位置,但无论这个步长多小,总会存在一个步长跨越多个格网的可能性,因此,会造成机动路线跨越河流等障碍因素的不合理现象。同时,客观而言,机动单元不应该从当前点跳过相邻点进行机动。这也是本文采用格网单元大小作为探索步长的原因。因此,对寻路方向研究的目的在于提高模型的准确性、合理性。
直观而言,采用八方向寻路更加符合实际情况,可避免四方向寻路出现的锯齿线问题。但这种情况并不是绝对的,例如当采用八方向寻路时同样可能出现跨河机动的不合理现象:陆战场格网数据主要是由矢量数据转换而成的,河流作为线状要素,主要通过线的栅格化转换为格网数据,常用的直线段栅格化算法包括DDA法和Bresenham法[14],这些算法一个共同的特点是转换后的栅格是八向连通的,如图4 所示。
此时,当从A出发点机动到B目标点时,如果采用八方向寻路就会跨过河流,而采用四方向寻路则不会出现此问题;同理,当图中直线代表桥梁时,如果采用四方向寻路又会出现无法通行的问题,必须要采用八方向寻路。因此,采用何种寻路方式,要根据具体的战场环境数据模型并结合不同要素对机动的影响特性综合确定。此外,如果将矢量数据的直线段栅格化算法进行改进,使其具有四向连通性,则可以采用八方向寻路,如图5 所示。
本文对Bresenham算法进行了改进,实现了图5 中矢量数据栅格化时具有四向连通性。即在递推步进过程中,当斜率大于0小于1时,若当前点为 ,直线与 的交点为 ,则下一个推进点不是选择距离最近的单个像素点,而是根据Δy选择单个或两个像素点:当Δy<1时,推进点为 ,当前点更新为该推进点;当Δy≥1,推进点为 和 ,当前点更新为 。与Bresenham算法相同,当斜率大于1时将纵坐标作为推进方向,小于0时,进行对称变换。
4 实验与分析
为了验证常用最优路径算法对陆战场格网数据的适用情况,本文使用某地区1∶50 000地图数据进行了路径规划实验,并开发了相应的测试工具。
4.1 实验环境
硬件环境为2.6 GHz Intel Core i7-5600U处理器,16 G内存,500 G硬盘;软件环境为Win7 64位操作系统、军内某GIS平台及Visual Studio 2010集成开发环境;开发编成语言使用C++和C#。
4.2 实验方案
首先,利用面向对象的方法设计和开发常用的最优路径算法库,如图6 所示。其中,SPFA算法采用BFS(Breadth First Search,广度优先搜索)方式及其三种优化策略[15]:SLF(CSP-SPFA-SLF)、LLL(CSP-SPFA-LLL)及SLF与LLL的结合(CSP-SPFA-S-L)。
其次,根据陆战场环境因素对机动的影响,设计并开发机动速度修正系数编辑工具,如图7 所示。其中,机动方式取决于机动单元的机动平台,可以根据实际情况进行扩展。
最后,为了对比常用最优路径算法在陆战场格网空间数据中的适用情况,本文开发了陆战场机动单元路径规划测试工具,如图8 所示为采用A*算法进行寻路的截图,为了便于展示效果,工具将格网化后的道路信息和河流信息在数字地图背景下,作为单独的图层进行了突出显示。其中,粉红色格网点为道路,浅蓝色为河流, A为出发点,D为目标点,B、C为途径点,黑色即为路径规划的机动路线结果。
实验抽取数字地图数据中某方形区域作为限制区域,并在限制区域内均匀选择多个点相互作为出发地和目标点;然后,应用常用最优路径算法对出发点和目标点进行路径规划计算,并进行统计分析。
4.3 实验结果与分析
本文首先对多源多目标算法Floyd-Warshall算法进行了验证,其计算效率如表4 所示(结果取3次平均值)。其中限制区域宽指的是方形区域每行每列的格网数,时间T为所有节点间最优路径的计算时间。
表4 Floyd-Warshall算法时间统计 |
| 限制 区域宽 | 节点数V | 时间T/ms | T/V3 |
|---|---|---|---|
| 30 | 900 | 754.00 | 1.03429E-06 |
| 31 | 961 | 936.00 | 1.05464E-06 |
| 32 | 1024 | 1086.33 | 1.01173E-06 |
| 33 | 1089 | 1305.00 | 1.01048E-06 |
| 34 | 1156 | 1586.33 | 1.02688E-06 |
| 35 | 1225 | 1851.33 | 1.00711E-06 |
| 36 | 1296 | 2200.00 | 1.01067E-06 |
| 37 | 1369 | 2605.33 | 1.01544E-06 |
| 38 | 1444 | 3057.67 | 1.01552E-06 |
| 39 | 1521 | 3463.67 | 9.84348E-07 |
可以看到,Floyd-Warshall算法的时间复杂度基本符合O(V3),根据实验数据,可推算出将限制区域扩大到一幅1∶50 000地图的计算时间:若以50米为格网宽度进行划分,一幅1∶50000地图的范围约27公里*18公里,则节点数V约为540*360=194 400个,根据时间复杂度得出Floyd-Warshall算法的计算时间约为88天!可以得出Floyd-Warshall算法不具有可行性的结论。
接下来,继续扩大限制区域对其他算法进行实验,随着区域宽度的增加,单对出发点和目标点的计算时间变化如图9 所示。
可以看出,Bellman-Ford算法的效率远低于其他算法,且其他算法的效率在小区域范围难以分出伯仲。最后,本文将限制区域宽度扩大到900,对Dijkstra算法、SPFA及其优化算法、A*算法进行了效率对比实验,结果如图10 所示。需要强调的是,A*算法的关键在于启发式函数[16],本文为了保证算法的一致性要求,将启发式函数——机动时间代价估计设为
其中dis(n,target)为当前寻路节点n与目标点的距离,四方向寻路为曼哈顿距离,八方向寻路为欧氏距离;vs为机动单元在不受任何环境因素影响下的标准速度。
从图中可以直观地得出算法效率由高到低为:A*> SPFA-SLF> SPFA> SPFA-LLL ≈ SPFA-S-L> Dijkstra。
最后,通过以上实验可以得出:陆战场机动单元路径规划,在作战区域内,当出发点已知,在机动命令下达前,可以采用SPFA的SLF优化算法对机动路径进行预规划,机动命令下达后可实时获取最优机动路线;当机动单元已在机动过程中,随着战场态势的变化,遇到突发情况(密集火力打击、遭遇布设雷区等)需要临机调整路线时,可采用A*算法对机动路径进行重新规划。
5 结束语
陆战场机动单元路径规划模型,是陆军作战实验仿真系统中的基础模型。本文针对现有机动模型以直线作为机动路径带来的不合理问题,基于格网空间数据模型,从网络特性和图论角度,分析了通过最优路径规划算法解决该问题的可行性。从机动速度、环境因素、区域限制和寻路方向四个方面,分析了陆战场机动路径规划需重点把握的关键环节。最后,本文开发了算法库和测试工具,通过实验,分析了常用最优路径规划算法对陆战场格网空间数据模型的适用情况,并进行了效率对比,得出陆战场机动单元路径规划仿真模型最宜采用的两种算法:SPFA-SLF算法与A*算法,及二者具体的应用场景。