一种适用于非连通交通网络的军事轮式平台机动路径规划方法研究

柳 玉 张莉丽 赵志军

(中国人民解放军91976部队教研部 广东 广州 510430)

0 引 言

军事轮式作战平台由海上路以后,机动是构成作战基本过程的一种典型作战行动。合适的机动路径规划是保证军事轮式作战平台各项任务顺利执行的前提。军事轮式作战平台机动路径规划问题是指在给定起点和终点条件下,寻求一条通过交通路网机动时间最短的路径。在当前的战术训练模拟系统或仿真实验系统中,军事轮式作战平台从搭载的两栖舰船抵滩上路以后,机动到目的地有两种路径规划方式:一是人在回路时,由操作员手工实时指定机动关键点,关键点不一定在交通路网上,可以在军事轮式作战平台可行进的任一地理点,由系统自动采用插值算法将若干个首尾相接的直线段拟合成机动路线。此种方式能快速规划好路径,但是以能机动而不是最优为主要目的,很难兼顾到不同地形地貌对机动速度的影响,缺乏合理性。二是作战实验时,系统考虑地形地貌的影响,参考机动终点方向采用A*算法搜索计算中间机动点,最后给出完整机动路径,经常出现耗时过长、结果路径无法产生的问题[1]。

国内外专家学者对于路径规划算法进行了探索并取得了较多成果,常用的最优路径算法主要包括Dijkstra算法[2]、Bellman-Ford算法[3]、Floyd-Warshall算法[4]、动态规划算法[5]、SPFA算法[6]、A*[7]等,其中:Dijkstra算法与A*算法在计算时只需获取当前点的后继即可,理论上支持的机动交通路网图可以无限大,适用性较好。其他四种算法针对连通图可以计算当前点与其他所有点之间的最优路径,尤其是Floyd-Warshall算法可以提前计算所有点之间的最优路径,实现“一劳永逸”的效果。但当起点或终点不在交通路网图上,即交通路网图的数学模型是不连通的二分图或者多分图时,上述除A*算法以外全部失效。A*算法作为启发式算法,可适用于连通或非连通的交通路网图,但当交通路网区域过大时,搜索路径会变长,导致大量无用节点产生,算法效率会急剧下降,容易陷入局部最优的凸顶错误[8-9]。

军事轮式作战平台的工作环境决定了其上路点、机动目的地不可能直接处于交通路网附近,且敌纵深梯次配置的防御工事会生成出一个较大地理区域的交通网络图。针对上述需求,探索研究一种适用于非连通交通网络的军事轮式平台机动路径规划方法不仅有助于提高战术训练模拟或仿真实验系统的准确性、合理性及效率,还能为军事轮式平台选择机动路线提供优选方案。近年来基于Geohash[10-12]算法快速寻找最优附近点为解决这一问题开辟了一条切实可行的道路。在考虑作战环境对军事轮式平台机动性能影响情况下,可实现将非连通的起点或终点按照耗时最少的路径连接到原有连通的交通路网,从而将非连通交通网络中的机动路径规划问题转换为求单起点、单终点的有向无环图中的最优路径问题。

1 路径规划问题分析与数学描述

1.1 问题分析

登陆场地域的坡度、地质、植被、水系、障碍等会对军事轮式平台机动性能产生影响。军事轮式平台通过某个区域除必须付出一定的时间代价外,还要面临来自敌火力打击的危险,因此,机动路线的选择一般原则是从抵滩上路点能够快速机动到目的地[13]。由于抵滩上路点和作为机动目的地的敌工事目标或指挥节点一般远离交通路网,所以路径规划首先要使军事轮式平台能够快速从抵滩点机动到交通路网,汇入交通路网的点称之为上路点;其次,当军事轮式平台从上路点进入交通路网之后,按耗时最少的路径行进;最后选择在能最快到达目的地的位置点驶下道路,直接机动到目的地,驶下道路的点称之为下路点。因此,通过寻找起点到上路点,终点到下路点的最短路径,可以将起点和终点连接至已有交通路网,从而将非连通的路径规划问题转化为单起点、单终点的连通路网的最短路径问题。

1.2 交通路网图的最优路径

军事地形图采用矢量格式,由按照地图要素分类的一系列图层组成。交通路网图层属于其中的一个,主要由点、线构成。经过抽取公共点,合并重复边,加入起点和终点以及起点到上路点的路径、终点到下路点的路径以后,可建立一个标准的有向无环图G=(V,E,D,W)模型(Directed Acyclic Graph,DAG),其中,V是节点集{v0,v1,v2,…,vn};E是连接节点vi、vj的边集{eij};D是边eij的长度集{dij},n是节点数量。考虑地形地貌及道路的级别对军事轮式平台机动性能影响,给边eij赋权值wij,表示军事轮式平台在两个节点vi,vj之间的机动时间,W是权值wij的集合。针对矢量地形图,此拓扑图构造过程具有速度快、无需预处理、对地域大小不限制等显著特点,且在理论上可证存在一条耗时最少路径。

1.3 机动路径规划问题的数学描述

给定一个连通的交通路网图G、起点S、终点T,一定存在至少一条从S到T耗时最少的路径,设计军事轮式作战平台通过这条路径的最短时间模型:

f*(PST)=min{f(PST)}

式中:PST是指由S到T的一条通路,f(PST)指机动平台在通路PST上耗费的时间。

2 图层预处理与算法设计

交通路网图层主要由表示道路交汇处的点和表示道路的线构成。军事轮式平台从起点到最近道路的路径在数学意义上可抽象为点到线的最短欧氏距离,但在矢量军事地形图中情况复杂,原因在于军事地形图中,道路是以线要素来表示的,而线是用一系列坐标点来表示的,一条道路可以看成是一个有限坐标点的集合。一般来说,道路越平坦,表示该道路的坐标点越少;道路越曲折,表示该道路的坐标点越多。因此,寻找军事轮式平台从起点到最近道路的最短路径可定义为寻找一点到数个有限点集中距离最近的点的过程。寻找下路点过程相同,不另作论述。

军事轮式平台从抵滩位置S到纵深要害目标T的最优路径PST可以分解为:

(1) 寻找S到道路耗时最短的上路点u。

(2) 机动目的地T到道路的耗时最短的下路点v。

(3) 交通路网G中从上路点u到下路点v耗时最短的路径。

通过以上分析可将前两个子问题归并为一类问题。

2.1 通路网图层预处理

矢量军事地形图采用特定投影方式进行显示,点用二维坐标表示。在点集中搜寻到某一点耗时最少的点本质上是一个对二维空间搜索的过程,在算法实现上需要计算点集中各个元素到该点的距离,然后在考虑地形地貌对军事轮式平台机动性能影响条件下,求出点集中各个元素到该点所耗费的时间,最后比较选出耗时最少的点。由于道路越平坦,表示道路所需的坐标点就越少,所以从平坦道路附近的起点寻找上路点时,会出现图1(a)这样不符合常理的现象。

图1 矢量地形图上寻找上路点预处理过程

为解决这个问题,根据图G上各条边上相邻坐标点之间的地理距离大小,按照某一适当间距进行插值,这样虽表示各条道路坐标点的数量会增加,但却可以较准确地计算出路外一点到道路的距离,见图1(b)。

2.2 最优上路点、下路点算法

由于插值会导致搜索空间呈指数级增长,计算量大大增加,传统算法对范围较大、路网密集的地域,遍历可能会导致系统运行缓慢、效率低下,Geohash是解决此问题的一个比较合适的空间点索引算法[14-15]。Geohash算法可以把二维的经纬度坐标编码成一个字符串,把二维空间的点搜索问题转化为一维的字符串匹配问题,其基本思想是将地球按某种投影方式展开为二维平面,将平面递归分解成更小的子块,每个子块具有相同的编码;当需要查询上路点时,先将起点的经纬度坐标按照Geohash编码转换成一个字符串,然后根据字符串匹配到所在的Geohash网格,然后按需要返回某些网格中的所有点,计算起点到返回的网格中的所有点的机动时间并排序,所需机动时间最小的那个点就是要找的上路点,见图2。

具体步骤是:

Step1确定Geohash编码的前缀长度m,判断准则:m对应Geohash网格的较小边长大于圆心所在地理位置的搜索半径转换成的经纬度跨度,且此时m是所有满足条件的最大值,计算出搜索中心(上路点或下路点)所在的父级网络编码,即Geohash前缀编码。

Step2提取交通图层中所有的线元素,对线元素按合适间隔进行插值。

Step3建立指定编码长度的交通路网图层对应的Geohash网格图模型。

Step4为防止一些在父级空间外且靠近其边界的点被遗漏,进一步计算与父级网格相邻的8个父级网格的Geohash前缀。

Step5对上述9个Geohash前缀网格分别遍历基本Geohash空间,利用字符串前缀模式匹配,找到其对应的最优附近点及距离,按照与上路点或下路点地理距离的升序排列。

Step6逐个分析每个最优附近点所在网格地理环境,利用表1算出机动时间,取机动时间最小的点作为上路点或下路点。

表1 地形地貌对速度的影响

2.3 改进的最短路径算法

DAG图每个弧段eij的时间权值wij与距离和速度有关系,而速度与该弧段的地形地貌道路等级有关,等级越高,军事轮式平台机动性越佳。作战环境地形地貌对机动平台的影响参考军内标准,以军事轮式车辆在乡级公路上的行驶速度30 km/h为基准,用α表示道路地形地貌特征对速度的影响因子,两者之间关系见表1。

设sij=α×30表示边eij上军事轮式平台的机动速度,则权值函数wij可表示为:

wij=dij/sij

通过对交通路网图层进行DAG建模(见图3)、计算权值函数wij、修正Dijkstra算法,得到改进的最优路径算法,具体描述如下:

图3 交通路网图层DAG建模结果

Step1初始化:T(u)=0,μ(y,x)=0;R={u};S=Φ。

Step2在集合R中选取具有最小T标号的点y,则:

(1)S=S∪{y},R=R-{y};

(2) 如果e(y,x)∈E且x∉S,则R=R∪{x}。

Step3若e(y,x)∈E,则:

条件1:若T(y)+w(y,x)

条件2:若T(y)+w(y,x)=T(x),则μ(y,x)=1。

Step4若所有点都进入集合S,算法停止,从图G(V,E)中删去所有μ(y,x)=0的边,生成最短路径图G*,则从G*中源点u到终点v的任一条路径都是最短路径,T(v)是对应的距离值,也是从源点u到v的权值;否则转入Step2。

时间复杂度:算法的运行时间表示为边数和顶点数的函数,当采用链表或者数组来存储所有顶点的集合时,算法的运行时间是O(n2)。

3 路径规划问题分析与数学描述

3.1 问题分析

采用某省辖市路网数据,实验平台为C++和MGIS的二次开发,实验硬件环境为CPU Intel(R) i7-3770 CPU 3.40 GHz,内存8 GB。考虑到信息安全敏感因素,从地图数据中隐去一些相关的目标信息,为验证算法可行性,分别设定起点、终点都在交通路网上、起点不在交通路网上、终点不在交通路网上、起点、终点均不在交通路网上四种情况,涵盖连通与非连通两种类,结果见图4。

图4 最优路径搜索算法实验结果

可以看出,本文综合Geohash及Dijkstra算法,给出的改进的最优路径算法,通过计算非连通交通网络的最优路径图,有效解决了起点、终点不在交通路网上的非连通网络机动路径寻优问题,适用性广,可直接应用于采用矢量军事地形图的战术训练模拟系统或仿真实验系统中对轮式平台的机动路径进行规划决策。

3.2 性能分析

为证明改进后算法的优越性,与经典Dijkstra算法、标准A*算法进行搜索结果对比,矢量图仍采用上述某省辖市路网图,地形涉及疏林、密林、稻田、沼泽,共14 304条弧,8 730个顶点。为应用Geohash算法,对图层中线元素以100米为单位进行打散、重构,区分起点、终点与路网连通特性4种情况,每种情况试验若干次,统计最优路径、搜索时间以及搜索结束后已标记顶点和已扫描顶点总数,结果见表2。图5是其中一次应用本文所提算法获得的一条最短路径结果。

表2 最短路径搜索算法性能比较

图5 应用改进的最优路径算法的结果

从实验结果可以看出,情况①三种算法均能给出最短路径搜索结果。标准A*算法由于采用栅格遍历+启发搜索方法,对于地理区域较大的网络图性能较差;经典Dijkstra算法与本文算法性能相当,但由于采用图层预算处理技术;本文算法访问顶点总数更少。

4 结 语

军事轮式平台机动路径规划是研制战术训练模拟系统、建设作战仿真实验系统的基础。本文针对现有人在回路及作战实验计算生成机动路径存在的问题,提出了一种基于Geohash及Dijkstra算法的改进的最优路径算法,从起点、终点连通特性和图论角度,分析了通过最优路径规划算法解决该问题的可行性及性能,实验结果表明本文算法相比标准A*算法提高了搜索效率、降低了访问顶点数目,且区域地理面积越大,优势越突出。下一步将重点研究机动平台在穿越交通道路网时,当道路出现不连续、不相交时,所提算法会出现失效的情况,从而提升算法柔性和解决问题范围。