通過水雷障礙群的最短路徑尋徑問題研究*

2011-06-06 10:05:08張年春

艦船電子工程 2011年7期

龍鵬林平張年春

1 引言

已知水域中水雷位置和危險半徑,但是任務緊迫,來不及清掃水雷,或者水雷障礙群為我方所布不能清掃,而且由于水雷障礙群過于龐大或者可能處于水道中無法繞行,此時水面艦艇編隊需掃雷艦緊急引導航渡通過水雷障礙群。為保證水面艦艇編隊安全迅速通過從而及時完成作戰任務或到達指定海域,我們需要在水雷障礙群中尋找一條最短通行路徑以達到快速通過的目的。戰斗部隊面對這一問題時目前基本上都是憑經驗尋徑通過。當水雷障礙群水雷數較多,種類繁雜的時候,我們可以利用計算機運算速度快的特點尋找一種使用計算機快速解算通過水雷障礙群所需最短路徑的方法。利用這種方法得到的路徑可以輔助指揮員參考決策,大大減輕指揮員的負擔,因此具有重大的戰術意義。

2 水雷障礙群的量化建模方法

2.1 柵格量化模型

2.1.1 柵格及柵格連接性的概念

將水雷障礙群如圖1所示劃分成等大小的柵格,再對這些柵格如圖2所示進行預先初始化使其變為柵格節點和具有連接各相鄰節點的具有路長的邊,然后再在此基礎上對其進行最短尋徑計算即可。

水雷障礙群柵格量化模型中的每一個柵格節點只與其鄰近的節點連接,因此必須確定每個節點與鄰近節點的是否連接和連接路徑的路長,如在圖2中黑點所在柵格表示為((8bits)01101111),每1bit表示從此柵格節點出發向相應數字所在方向是否可通過。

2.1.2 柵格的構造方法

1)柵格大小的選取

柵格尺寸大小的選取需折衷考慮算法搜索空間的大小、運算時間的長短以及解算得到最短路徑的精度等問題。一般來說,柵格取的越小,相應的路徑精度及可接受性就越高,但是運算的時間、空間代價也會相應的增加不少,此外還需綜合考慮艦艇導航精度誤差及一般水雷的爆炸威力半徑,因此在這里推薦取1鏈作為柵格長寬的大小。

2)柵格連接性的判斷方法

在圖2中,任意兩個柵格之間是否連通主要從兩個方面來討論:

(1)連線平行或垂直于航線方向上的兩個柵格節點:如圖3中的G、H柵格節點連線(設航線方向為從下至上)垂直于航線方向,在其鄰近區域各取一半柵格作為這兩個柵格的連接區域(如圖中陰影所示),我們可以將這個連接區域看作是無數條與這兩個柵格節點連線垂直的連接線段組成,如果這兩個柵格所構成的連結區域中的任一一條連接線段完全包含于某水雷威脅圓中,則判定這兩個柵格無法連接,如圖3中的C、D柵格在D柵格中有一條連接線段(虛線所示)完全包含于水雷威脅圓Y中,因此我們判斷C、D柵格無法連通;

(2)節點連線與航線斜交的兩個柵格,如果有兩顆相切或者相交的水雷的連線與這兩個柵格節點的連線相交則判斷這兩個柵格之間無法連通;如果這兩個柵格節點都包含在某水雷威脅圓中,也判斷其無法連通。在圖3中的A、B柵格節點,雖然XY兩個水雷威脅圓沒有相交,但是因為這兩個節點被完全包含于Y中,因此也判斷其為無法連接。

水雷威脅圓半徑的取值應該保證兩個威脅圓如果即使相切,水面艦艇亦可在兩個水雷之間通過,因此水雷威脅半徑可取值為

圖3 柵格節點連接判斷

從圖1可以看出柵格量化模型中判斷兩個柵格之間是否連通的精確度的大小,獲得路徑的可行性的高低主要依賴于柵格的大小,柵格越小,則判斷精度越準確,但是相應計算量也將增加。

2.2 包可視圖量化模型

2.2.1 包可視圖的概念

在模仿人類的智能行為中,有一個更加復雜的地方,那就是電腦沒有視覺。人類只要瞟上幾眼,就可以從中獲得豐富的信息,但是對電腦來說就太困難了。針對這種情況我們可以使用包這個簡單而強大的將障礙包圍起來的幾何閉合圖形來對這種行為進行仿真,包占用的內存很小,而且效率很高,此外還具有一定的精確度。包幾乎在RTS游戲引擎中的每一種區域上都可以得到使用,它使得復雜的人工智能行為的創建更容易實現,這是因為它們可以讓開發人員快速的得到一個區域的障礙情況?？梢晥D法是由麻省理工學院的Tomas Lozano.Perez和IBM研究院的MichaelA.Wesley于1979年提出的,如圖4所示,其最大特點是在表達障礙物的多邊形包中探尋出各個包上的包絡點之間的連接情況。圖4左側表示某一個水雷障礙群,右側是構造出的對應于左側水雷障礙群的包可視圖,并繪出了右下角包的包絡點的連接情況。

圖4 包可視圖概念及應用

2.2.2 包可視圖的構造方法

1)包的構造方法

只給出了水雷障礙群中各個水雷的坐標及威脅半徑,因此首先要在此基礎上構造包。如圖5所示,首先將相切或相交的水雷連線成凝聚水雷群,各個凝聚水雷群將按照各個不同凝聚情況構成相應的包:

(1)單個水雷。依照順航線方向在水雷威脅圓上的前后左右分別定位四個包絡點,將這四個包絡點連接即可構成單個水雷的包;

(2)兩個水雷構成的凝聚水類群。將兩個水雷點的連線分別向兩側平移一個水雷威脅半徑(即與兩個水雷威脅圓相切)可得四個切點,將連線反向延長一個水雷威脅半徑又可得兩個包絡點(即與水雷威脅圓的交點),將這六個包絡點相連即可;

(3)不規則的凝聚水雷群。凝聚水雷群兩端及處于水雷連線夾角外側的包絡點按照(B)的方法定出,再將每一個折角的角平分線向兩側延長一個水雷威脅半徑即可得到相對應的包絡點,將所有包絡點依次相連即可得到不規則凝聚群的包;

(4)構成環的凝聚水雷群。如果凝聚水雷群線連接成環,將每一個折角的角平分線向外側延長一個水雷威脅半徑即可得到相對應的包絡點,再將每連線向外側平移與這兩個水雷威脅圓相切可得相應切點,將這些包絡點依次連接即得到構成環的凝聚水雷群構成的包。

2)邊的構造方法

所有的包構造出來以后,我們已經得到n個包m個包絡點,再將水雷障礙群的進入邊界和駛出邊界虛構成一個開始頂點和一個結束頂點即共m+2個包絡點,運用包可視圖法我們還需要將所有的可用邊構造出來,共分為三種情況:

圖5 包可視可圖與構建方法

(1)包上連接每兩個相鄰包絡點的邊;

(2)如果有兩個不處在同一個包的包絡點的可以無障礙連接,則將連接這兩個包絡點的邊加入可視圖;

(3)如果包上的包絡點與任意一個虛構的包絡點能夠無障礙垂直連接,即將這條連接邊加入可視圖中。

無障礙連接就是指兩個包絡點之間的連線沒有穿過任何一個包,如圖5中右下角包的所有邊,其判斷的方法是:將這兩個包絡點連接的邊與每一個包上不包含這兩個包絡點第(1)類邊進行遍歷計算看是否有相交,如果沒有則這兩個包絡點可以無障礙連接。

3 通過水雷障礙群的最短路徑尋徑改良算法

上面已經對水雷障礙群的量化建模方法進行了描述。在量化建模的基礎上,我們可以利用許多的最短路徑尋徑算法如Dijkstra、Floyd和A*自啟發算法進行最短路徑的求解。由于柵格量化模型類似于迷宮模型,因此我們可以結合Dijkstra算法和A*自啟發算法的優點得到一個更高效的改良算法。對于包可視圖模型來說,利用這三種算法的任意一種都可以很好的運算。

3.1 柵格模型最短路徑尋徑改良算法

因為所尋路徑都是從航線的起始邊界進入到雷區然后從終止邊界駛出雷區,所以將起始邊界和終止邊界虛擬為一個起始節點和終止節點,起始節點和終止節點分別到其相應邊界柵格節點的距離為0,包可視圖法中包上各包絡點到邊界的垂直的邊即可以視為其連接起始節點或終止節點的邊。將一個多個起始節點和多個終止節點的問題轉化為單個起始節點到單個終止節點的最短路徑尋徑問題,這樣運用最短路徑尋徑算法時一次計算即可得出結果,而不必進行多次重復計算出每一對起始節點和終止節點的最短路徑以后再從這些最短路徑里選擇路長值最小的路徑。

Dijkstra算法的精要在于其每次尋找使路徑距離增加最小的柵格加入路徑,A*自啟發算法則主要體現了尋徑的方向性,即優先將向終止節點接近最迅速的節點加入路徑。將兩者結合起來,即是新加入路徑的節點必須滿足三個條件:

1)方向性的要求使得應優先選擇向終止邊界靠近最快的節點,因為算法欲到達的終止節點位于水雷障礙群的終止邊界上;

2)所加入當前路徑節點必須使所有路徑長的和增加最少;

3)新加入的節點必須也只可能是未使用節點,因為從當前節點出發探尋到一個已經標記為使用的節點,那就說明在先前的操作中這個節點因為對總的路徑和最少的貢獻已經加入了路徑,通過別的路徑到達這一節點的肯定已經不是最短路徑到達。