一種適用于非連通交通網(wǎng)絡(luò)的軍事輪式平臺(tái)機(jī)動(dòng)路徑規(guī)劃方法研究

柳 玉 張莉麗 趙志軍

(中國(guó)人民解放軍91976部隊(duì)教研部 廣東 廣州 510430)

0 引 言

軍事輪式作戰(zhàn)平臺(tái)由海上路以后,機(jī)動(dòng)是構(gòu)成作戰(zhàn)基本過(guò)程的一種典型作戰(zhàn)行動(dòng)。合適的機(jī)動(dòng)路徑規(guī)劃是保證軍事輪式作戰(zhàn)平臺(tái)各項(xiàng)任務(wù)順利執(zhí)行的前提。軍事輪式作戰(zhàn)平臺(tái)機(jī)動(dòng)路徑規(guī)劃問(wèn)題是指在給定起點(diǎn)和終點(diǎn)條件下,尋求一條通過(guò)交通路網(wǎng)機(jī)動(dòng)時(shí)間最短的路徑。在當(dāng)前的戰(zhàn)術(shù)訓(xùn)練模擬系統(tǒng)或仿真實(shí)驗(yàn)系統(tǒng)中,軍事輪式作戰(zhàn)平臺(tái)從搭載的兩棲艦船抵灘上路以后,機(jī)動(dòng)到目的地有兩種路徑規(guī)劃方式:一是人在回路時(shí),由操作員手工實(shí)時(shí)指定機(jī)動(dòng)關(guān)鍵點(diǎn),關(guān)鍵點(diǎn)不一定在交通路網(wǎng)上,可以在軍事輪式作戰(zhàn)平臺(tái)可行進(jìn)的任一地理點(diǎn),由系統(tǒng)自動(dòng)采用插值算法將若干個(gè)首尾相接的直線段擬合成機(jī)動(dòng)路線。此種方式能快速規(guī)劃好路徑,但是以能機(jī)動(dòng)而不是最優(yōu)為主要目的,很難兼顧到不同地形地貌對(duì)機(jī)動(dòng)速度的影響,缺乏合理性。二是作戰(zhàn)實(shí)驗(yàn)時(shí),系統(tǒng)考慮地形地貌的影響,參考機(jī)動(dòng)終點(diǎn)方向采用A*算法搜索計(jì)算中間機(jī)動(dòng)點(diǎn),最后給出完整機(jī)動(dòng)路徑,經(jīng)常出現(xiàn)耗時(shí)過(guò)長(zhǎng)、結(jié)果路徑無(wú)法產(chǎn)生的問(wèn)題[1]。

國(guó)內(nèi)外專家學(xué)者對(duì)于路徑規(guī)劃算法進(jìn)行了探索并取得了較多成果,常用的最優(yōu)路徑算法主要包括Dijkstra算法[2]、Bellman-Ford算法[3]、Floyd-Warshall算法[4]、動(dòng)態(tài)規(guī)劃算法[5]、SPFA算法[6]、A*[7]等,其中:Dijkstra算法與A*算法在計(jì)算時(shí)只需獲取當(dāng)前點(diǎn)的后繼即可,理論上支持的機(jī)動(dòng)交通路網(wǎng)圖可以無(wú)限大,適用性較好。其他四種算法針對(duì)連通圖可以計(jì)算當(dāng)前點(diǎn)與其他所有點(diǎn)之間的最優(yōu)路徑,尤其是Floyd-Warshall算法可以提前計(jì)算所有點(diǎn)之間的最優(yōu)路徑,實(shí)現(xiàn)“一勞永逸”的效果。但當(dāng)起點(diǎn)或終點(diǎn)不在交通路網(wǎng)圖上,即交通路網(wǎng)圖的數(shù)學(xué)模型是不連通的二分圖或者多分圖時(shí),上述除A*算法以外全部失效。A*算法作為啟發(fā)式算法,可適用于連通或非連通的交通路網(wǎng)圖,但當(dāng)交通路網(wǎng)區(qū)域過(guò)大時(shí),搜索路徑會(huì)變長(zhǎng),導(dǎo)致大量無(wú)用節(jié)點(diǎn)產(chǎn)生,算法效率會(huì)急劇下降,容易陷入局部最優(yōu)的凸頂錯(cuò)誤[8-9]。

軍事輪式作戰(zhàn)平臺(tái)的工作環(huán)境決定了其上路點(diǎn)、機(jī)動(dòng)目的地不可能直接處于交通路網(wǎng)附近,且敵縱深梯次配置的防御工事會(huì)生成出一個(gè)較大地理區(qū)域的交通網(wǎng)絡(luò)圖。針對(duì)上述需求,探索研究一種適用于非連通交通網(wǎng)絡(luò)的軍事輪式平臺(tái)機(jī)動(dòng)路徑規(guī)劃方法不僅有助于提高戰(zhàn)術(shù)訓(xùn)練模擬或仿真實(shí)驗(yàn)系統(tǒng)的準(zhǔn)確性、合理性及效率,還能為軍事輪式平臺(tái)選擇機(jī)動(dòng)路線提供優(yōu)選方案。近年來(lái)基于Geohash[10-12]算法快速尋找最優(yōu)附近點(diǎn)為解決這一問(wèn)題開(kāi)辟了一條切實(shí)可行的道路。在考慮作戰(zhàn)環(huán)境對(duì)軍事輪式平臺(tái)機(jī)動(dòng)性能影響情況下,可實(shí)現(xiàn)將非連通的起點(diǎn)或終點(diǎn)按照耗時(shí)最少的路徑連接到原有連通的交通路網(wǎng),從而將非連通交通網(wǎng)絡(luò)中的機(jī)動(dòng)路徑規(guī)劃問(wèn)題轉(zhuǎn)換為求單起點(diǎn)、單終點(diǎn)的有向無(wú)環(huán)圖中的最優(yōu)路徑問(wèn)題。

1 路徑規(guī)劃問(wèn)題分析與數(shù)學(xué)描述

1.1 問(wèn)題分析

登陸場(chǎng)地域的坡度、地質(zhì)、植被、水系、障礙等會(huì)對(duì)軍事輪式平臺(tái)機(jī)動(dòng)性能產(chǎn)生影響。軍事輪式平臺(tái)通過(guò)某個(gè)區(qū)域除必須付出一定的時(shí)間代價(jià)外,還要面臨來(lái)自敵火力打擊的危險(xiǎn),因此,機(jī)動(dòng)路線的選擇一般原則是從抵灘上路點(diǎn)能夠快速機(jī)動(dòng)到目的地[13]。由于抵灘上路點(diǎn)和作為機(jī)動(dòng)目的地的敵工事目標(biāo)或指揮節(jié)點(diǎn)一般遠(yuǎn)離交通路網(wǎng),所以路徑規(guī)劃首先要使軍事輪式平臺(tái)能夠快速?gòu)牡譃c(diǎn)機(jī)動(dòng)到交通路網(wǎng),匯入交通路網(wǎng)的點(diǎn)稱之為上路點(diǎn);其次,當(dāng)軍事輪式平臺(tái)從上路點(diǎn)進(jìn)入交通路網(wǎng)之后,按耗時(shí)最少的路徑行進(jìn);最后選擇在能最快到達(dá)目的地的位置點(diǎn)駛下道路,直接機(jī)動(dòng)到目的地,駛下道路的點(diǎn)稱之為下路點(diǎn)。因此,通過(guò)尋找起點(diǎn)到上路點(diǎn),終點(diǎn)到下路點(diǎn)的最短路徑,可以將起點(diǎn)和終點(diǎn)連接至已有交通路網(wǎng),從而將非連通的路徑規(guī)劃問(wèn)題轉(zhuǎn)化為單起點(diǎn)、單終點(diǎn)的連通路網(wǎng)的最短路徑問(wèn)題。

1.2 交通路網(wǎng)圖的最優(yōu)路徑

軍事地形圖采用矢量格式,由按照地圖要素分類的一系列圖層組成。交通路網(wǎng)圖層屬于其中的一個(gè),主要由點(diǎn)、線構(gòu)成。經(jīng)過(guò)抽取公共點(diǎn),合并重復(fù)邊,加入起點(diǎn)和終點(diǎn)以及起點(diǎn)到上路點(diǎn)的路徑、終點(diǎn)到下路點(diǎn)的路徑以后,可建立一個(gè)標(biāo)準(zhǔn)的有向無(wú)環(huán)圖G=(V,E,D,W)模型(Directed Acyclic Graph,DAG),其中,V是節(jié)點(diǎn)集{v0,v1,v2,…,vn};E是連接節(jié)點(diǎn)vi、vj的邊集{eij};D是邊eij的長(zhǎng)度集{dij},n是節(jié)點(diǎn)數(shù)量。考慮地形地貌及道路的級(jí)別對(duì)軍事輪式平臺(tái)機(jī)動(dòng)性能影響,給邊eij賦權(quán)值wij,表示軍事輪式平臺(tái)在兩個(gè)節(jié)點(diǎn)vi,vj之間的機(jī)動(dòng)時(shí)間,W是權(quán)值wij的集合。針對(duì)矢量地形圖,此拓?fù)鋱D構(gòu)造過(guò)程具有速度快、無(wú)需預(yù)處理、對(duì)地域大小不限制等顯著特點(diǎn),且在理論上可證存在一條耗時(shí)最少路徑。

1.3 機(jī)動(dòng)路徑規(guī)劃問(wèn)題的數(shù)學(xué)描述

給定一個(gè)連通的交通路網(wǎng)圖G、起點(diǎn)S、終點(diǎn)T,一定存在至少一條從S到T耗時(shí)最少的路徑,設(shè)計(jì)軍事輪式作戰(zhàn)平臺(tái)通過(guò)這條路徑的最短時(shí)間模型:

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

式中:PST是指由S到T的一條通路,f(PST)指機(jī)動(dòng)平臺(tái)在通路PST上耗費(fèi)的時(shí)間。

2 圖層預(yù)處理與算法設(shè)計(jì)

交通路網(wǎng)圖層主要由表示道路交匯處的點(diǎn)和表示道路的線構(gòu)成。軍事輪式平臺(tái)從起點(diǎn)到最近道路的路徑在數(shù)學(xué)意義上可抽象為點(diǎn)到線的最短歐氏距離,但在矢量軍事地形圖中情況復(fù)雜,原因在于軍事地形圖中,道路是以線要素來(lái)表示的,而線是用一系列坐標(biāo)點(diǎn)來(lái)表示的,一條道路可以看成是一個(gè)有限坐標(biāo)點(diǎn)的集合。一般來(lái)說(shuō),道路越平坦,表示該道路的坐標(biāo)點(diǎn)越少;道路越曲折,表示該道路的坐標(biāo)點(diǎn)越多。因此,尋找軍事輪式平臺(tái)從起點(diǎn)到最近道路的最短路徑可定義為尋找一點(diǎn)到數(shù)個(gè)有限點(diǎn)集中距離最近的點(diǎn)的過(guò)程。尋找下路點(diǎn)過(guò)程相同,不另作論述。

軍事輪式平臺(tái)從抵灘位置S到縱深要害目標(biāo)T的最優(yōu)路徑PST可以分解為:

(1) 尋找S到道路耗時(shí)最短的上路點(diǎn)u。

(2) 機(jī)動(dòng)目的地T到道路的耗時(shí)最短的下路點(diǎn)v。

(3) 交通路網(wǎng)G中從上路點(diǎn)u到下路點(diǎn)v耗時(shí)最短的路徑。

通過(guò)以上分析可將前兩個(gè)子問(wèn)題歸并為一類問(wèn)題。

2.1 通路網(wǎng)圖層預(yù)處理

矢量軍事地形圖采用特定投影方式進(jìn)行顯示,點(diǎn)用二維坐標(biāo)表示。在點(diǎn)集中搜尋到某一點(diǎn)耗時(shí)最少的點(diǎn)本質(zhì)上是一個(gè)對(duì)二維空間搜索的過(guò)程,在算法實(shí)現(xiàn)上需要計(jì)算點(diǎn)集中各個(gè)元素到該點(diǎn)的距離,然后在考慮地形地貌對(duì)軍事輪式平臺(tái)機(jī)動(dòng)性能影響條件下,求出點(diǎn)集中各個(gè)元素到該點(diǎn)所耗費(fèi)的時(shí)間,最后比較選出耗時(shí)最少的點(diǎn)。由于道路越平坦,表示道路所需的坐標(biāo)點(diǎn)就越少,所以從平坦道路附近的起點(diǎn)尋找上路點(diǎn)時(shí),會(huì)出現(xiàn)圖1(a)這樣不符合常理的現(xiàn)象。

圖1 矢量地形圖上尋找上路點(diǎn)預(yù)處理過(guò)程

為解決這個(gè)問(wèn)題,根據(jù)圖G上各條邊上相鄰坐標(biāo)點(diǎn)之間的地理距離大小,按照某一適當(dāng)間距進(jìn)行插值,這樣雖表示各條道路坐標(biāo)點(diǎn)的數(shù)量會(huì)增加,但卻可以較準(zhǔn)確地計(jì)算出路外一點(diǎn)到道路的距離,見(jiàn)圖1(b)。

2.2 最優(yōu)上路點(diǎn)、下路點(diǎn)算法

由于插值會(huì)導(dǎo)致搜索空間呈指數(shù)級(jí)增長(zhǎng),計(jì)算量大大增加,傳統(tǒng)算法對(duì)范圍較大、路網(wǎng)密集的地域,遍歷可能會(huì)導(dǎo)致系統(tǒng)運(yùn)行緩慢、效率低下,Geohash是解決此問(wèn)題的一個(gè)比較合適的空間點(diǎn)索引算法[14-15]。Geohash算法可以把二維的經(jīng)緯度坐標(biāo)編碼成一個(gè)字符串,把二維空間的點(diǎn)搜索問(wèn)題轉(zhuǎn)化為一維的字符串匹配問(wèn)題,其基本思想是將地球按某種投影方式展開(kāi)為二維平面,將平面遞歸分解成更小的子塊,每個(gè)子塊具有相同的編碼;當(dāng)需要查詢上路點(diǎn)時(shí),先將起點(diǎn)的經(jīng)緯度坐標(biāo)按照Geohash編碼轉(zhuǎn)換成一個(gè)字符串,然后根據(jù)字符串匹配到所在的Geohash網(wǎng)格,然后按需要返回某些網(wǎng)格中的所有點(diǎn),計(jì)算起點(diǎn)到返回的網(wǎng)格中的所有點(diǎn)的機(jī)動(dòng)時(shí)間并排序,所需機(jī)動(dòng)時(shí)間最小的那個(gè)點(diǎn)就是要找的上路點(diǎn),見(jiàn)圖2。

具體步驟是:

Step1確定Geohash編碼的前綴長(zhǎng)度m,判斷準(zhǔn)則:m對(duì)應(yīng)Geohash網(wǎng)格的較小邊長(zhǎng)大于圓心所在地理位置的搜索半徑轉(zhuǎn)換成的經(jīng)緯度跨度,且此時(shí)m是所有滿足條件的最大值,計(jì)算出搜索中心(上路點(diǎn)或下路點(diǎn))所在的父級(jí)網(wǎng)絡(luò)編碼,即Geohash前綴編碼。

Step2提取交通圖層中所有的線元素,對(duì)線元素按合適間隔進(jìn)行插值。

Step3建立指定編碼長(zhǎng)度的交通路網(wǎng)圖層對(duì)應(yīng)的Geohash網(wǎng)格圖模型。

Step4為防止一些在父級(jí)空間外且靠近其邊界的點(diǎn)被遺漏,進(jìn)一步計(jì)算與父級(jí)網(wǎng)格相鄰的8個(gè)父級(jí)網(wǎng)格的Geohash前綴。

Step5對(duì)上述9個(gè)Geohash前綴網(wǎng)格分別遍歷基本Geohash空間,利用字符串前綴模式匹配,找到其對(duì)應(yīng)的最優(yōu)附近點(diǎn)及距離,按照與上路點(diǎn)或下路點(diǎn)地理距離的升序排列。

Step6逐個(gè)分析每個(gè)最優(yōu)附近點(diǎn)所在網(wǎng)格地理環(huán)境,利用表1算出機(jī)動(dòng)時(shí)間,取機(jī)動(dòng)時(shí)間最小的點(diǎn)作為上路點(diǎn)或下路點(diǎn)。

表1 地形地貌對(duì)速度的影響

2.3 改進(jìn)的最短路徑算法

DAG圖每個(gè)弧段eij的時(shí)間權(quán)值wij與距離和速度有關(guān)系,而速度與該弧段的地形地貌道路等級(jí)有關(guān),等級(jí)越高,軍事輪式平臺(tái)機(jī)動(dòng)性越佳。作戰(zhàn)環(huán)境地形地貌對(duì)機(jī)動(dòng)平臺(tái)的影響參考軍內(nèi)標(biāo)準(zhǔn),以軍事輪式車輛在鄉(xiāng)級(jí)公路上的行駛速度30 km/h為基準(zhǔn),用α表示道路地形地貌特征對(duì)速度的影響因子,兩者之間關(guān)系見(jiàn)表1。

設(shè)sij=α×30表示邊eij上軍事輪式平臺(tái)的機(jī)動(dòng)速度,則權(quán)值函數(shù)wij可表示為:

wij=dij/sij

通過(guò)對(duì)交通路網(wǎng)圖層進(jìn)行DAG建模(見(jiàn)圖3)、計(jì)算權(quán)值函數(shù)wij、修正Dijkstra算法,得到改進(jìn)的最優(yōu)路徑算法,具體描述如下:

圖3 交通路網(wǎng)圖層DAG建模結(jié)果

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

Step2在集合R中選取具有最小T標(biāo)號(hào)的點(diǎn)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若所有點(diǎn)都進(jìn)入集合S,算法停止,從圖G(V,E)中刪去所有μ(y,x)=0的邊,生成最短路徑圖G*,則從G*中源點(diǎn)u到終點(diǎn)v的任一條路徑都是最短路徑,T(v)是對(duì)應(yīng)的距離值,也是從源點(diǎn)u到v的權(quán)值;否則轉(zhuǎn)入Step2。

時(shí)間復(fù)雜度:算法的運(yùn)行時(shí)間表示為邊數(shù)和頂點(diǎn)數(shù)的函數(shù),當(dāng)采用鏈表或者數(shù)組來(lái)存儲(chǔ)所有頂點(diǎn)的集合時(shí),算法的運(yùn)行時(shí)間是O(n2)。

3 路徑規(guī)劃問(wèn)題分析與數(shù)學(xué)描述

3.1 問(wèn)題分析

采用某省轄市路網(wǎng)數(shù)據(jù),實(shí)驗(yàn)平臺(tái)為C++和MGIS的二次開(kāi)發(fā),實(shí)驗(yàn)硬件環(huán)境為CPU Intel(R) i7-3770 CPU 3.40 GHz,內(nèi)存8 GB?？紤]到信息安全敏感因素,從地圖數(shù)據(jù)中隱去一些相關(guān)的目標(biāo)信息,為驗(yàn)證算法可行性,分別設(shè)定起點(diǎn)、終點(diǎn)都在交通路網(wǎng)上、起點(diǎn)不在交通路網(wǎng)上、終點(diǎn)不在交通路網(wǎng)上、起點(diǎn)、終點(diǎn)均不在交通路網(wǎng)上四種情況,涵蓋連通與非連通兩種類,結(jié)果見(jiàn)圖4。

圖4 最優(yōu)路徑搜索算法實(shí)驗(yàn)結(jié)果

可以看出,本文綜合Geohash及Dijkstra算法,給出的改進(jìn)的最優(yōu)路徑算法,通過(guò)計(jì)算非連通交通網(wǎng)絡(luò)的最優(yōu)路徑圖,有效解決了起點(diǎn)、終點(diǎn)不在交通路網(wǎng)上的非連通網(wǎng)絡(luò)機(jī)動(dòng)路徑尋優(yōu)問(wèn)題,適用性廣,可直接應(yīng)用于采用矢量軍事地形圖的戰(zhàn)術(shù)訓(xùn)練模擬系統(tǒng)或仿真實(shí)驗(yàn)系統(tǒng)中對(duì)輪式平臺(tái)的機(jī)動(dòng)路徑進(jìn)行規(guī)劃決策。

3.2 性能分析

為證明改進(jìn)后算法的優(yōu)越性,與經(jīng)典Dijkstra算法、標(biāo)準(zhǔn)A*算法進(jìn)行搜索結(jié)果對(duì)比,矢量圖仍采用上述某省轄市路網(wǎng)圖,地形涉及疏林、密林、稻田、沼澤,共14 304條弧,8 730個(gè)頂點(diǎn)。為應(yīng)用Geohash算法,對(duì)圖層中線元素以100米為單位進(jìn)行打散、重構(gòu),區(qū)分起點(diǎn)、終點(diǎn)與路網(wǎng)連通特性4種情況,每種情況試驗(yàn)若干次,統(tǒng)計(jì)最優(yōu)路徑、搜索時(shí)間以及搜索結(jié)束后已標(biāo)記頂點(diǎn)和已掃描頂點(diǎn)總數(shù),結(jié)果見(jiàn)表2。圖5是其中一次應(yīng)用本文所提算法獲得的一條最短路徑結(jié)果。

表2 最短路徑搜索算法性能比較

圖5 應(yīng)用改進(jìn)的最優(yōu)路徑算法的結(jié)果

從實(shí)驗(yàn)結(jié)果可以看出,情況①三種算法均能給出最短路徑搜索結(jié)果。標(biāo)準(zhǔn)A*算法由于采用柵格遍歷+啟發(fā)搜索方法,對(duì)于地理區(qū)域較大的網(wǎng)絡(luò)圖性能較差;經(jīng)典Dijkstra算法與本文算法性能相當(dāng),但由于采用圖層預(yù)算處理技術(shù);本文算法訪問(wèn)頂點(diǎn)總數(shù)更少。

4 結(jié) 語(yǔ)

軍事輪式平臺(tái)機(jī)動(dòng)路徑規(guī)劃是研制戰(zhàn)術(shù)訓(xùn)練模擬系統(tǒng)、建設(shè)作戰(zhàn)仿真實(shí)驗(yàn)系統(tǒng)的基礎(chǔ)。本文針對(duì)現(xiàn)有人在回路及作戰(zhàn)實(shí)驗(yàn)計(jì)算生成機(jī)動(dòng)路徑存在的問(wèn)題,提出了一種基于Geohash及Dijkstra算法的改進(jìn)的最優(yōu)路徑算法,從起點(diǎn)、終點(diǎn)連通特性和圖論角度,分析了通過(guò)最優(yōu)路徑規(guī)劃算法解決該問(wèn)題的可行性及性能,實(shí)驗(yàn)結(jié)果表明本文算法相比標(biāo)準(zhǔn)A*算法提高了搜索效率、降低了訪問(wèn)頂點(diǎn)數(shù)目,且區(qū)域地理面積越大,優(yōu)勢(shì)越突出。下一步將重點(diǎn)研究機(jī)動(dòng)平臺(tái)在穿越交通道路網(wǎng)時(shí),當(dāng)?shù)缆烦霈F(xiàn)不連續(xù)、不相交時(shí),所提算法會(huì)出現(xiàn)失效的情況,從而提升算法柔性和解決問(wèn)題范圍。