適用于海軍平臺的自動路徑規(guī)劃算法

沈燕霞

【摘要】本文介紹了一種適用于海軍平臺的自動路徑規(guī)劃算法，自動路徑規(guī)劃算法從電子海圖提取地理數(shù)據(jù)，然后根據(jù)這些數(shù)據(jù)產(chǎn)生從開始點到目標點的航路點序列，該算法能應(yīng)用于任意海軍平臺的路徑規(guī)劃。這種算法可適用于海軍的各種領(lǐng)域，如魚雷發(fā)射航路的計算，水面艦艇和潛艇的導航等。

【關(guān)鍵詞】海軍平臺;自動路徑;規(guī)劃算法

1.引言

開發(fā)適用于海軍平臺的自動路徑規(guī)劃算法的目的是尋找通過給定區(qū)域并能避開所有障礙物的一條最佳路徑。路徑中的航路點序列來自之前掃描發(fā)現(xiàn)的點集。目前算法是針對二維航路點規(guī)劃設(shè)計的，同時也考慮了海區(qū)的深度。

算法的邊界條件定義如下：在開始計算時先獲取自身和所有已知目標的真實位置，假定計算過程中這些目標的位置保持不變。因為整過計算過程僅幾秒鐘，這樣做是可行的。在這短短的計算時間內(nèi)，位置的變化量可以忽略。本文研究的算法的一個約束是最大計算時間不能超過20 s。其目的是為了適應(yīng)多種水下作戰(zhàn)系統(tǒng)。

2.算法實現(xiàn)

算法分為兩大重要部分，它們是程序內(nèi)獨立的兩個模塊，這樣保證了程序的可重用性和可維護性。

第一個模塊為海軍平臺生成一個圖，該圖含有平臺周圍區(qū)域的地理數(shù)據(jù)和區(qū)域內(nèi)障礙物的數(shù)據(jù)。這地理數(shù)據(jù)是從國際標準電子海圖（ECDIS圖型）提取的，并處理成數(shù)字地形模型。該過程是由剖面評算用電子海圖分析器ESCAPE完成的。該程序從海圖中獲取給定區(qū)域的深度數(shù)據(jù)后生成光柵格式的地形圖，如圖1所示。光柵中的每一點表示一個深度值，因此整個區(qū)域都由深度值來描述。

圖1 海圖區(qū)域（左）轉(zhuǎn)換為地形模型后的效果圖（右）

這樣的地形模型是生成圖的基礎(chǔ)。這些光柵點表示圖的節(jié)點和邊。節(jié)點為圖的接合點，一條邊連接兩個接合點。邊可以賦予權(quán)重以表示從起始節(jié)點到目標節(jié)點之間的距離，如圖2所示。

節(jié)點 ? ? ? ? ? ? ? 邊 ? ? ? ? ? ? 權(quán)重邊

圖2 描述節(jié)點和邊的符號

圖3 用圖表說明地形模型

圖4 對角線邊

當?shù)匦文Ｐ娃D(zhuǎn)為圖后，一個光柵點就對應(yīng)一個節(jié)點，光柵點的深度值就表示從該點到相應(yīng)節(jié)點的邊的加權(quán)值，如圖3所示。

圖3上除了按沿直角運動外，還可以沿對角線運動。依照不同的角度（由兩節(jié)點之間x和y的差值來決定），路徑長度不同，因此邊的權(quán)重也不同。當角度為45度時，目標節(jié)點的深1度值需要乘上，如圖4所示。

為了尋找一條能避開島嶼等障礙物的路徑，程序必須能確定是否達到了某一最小深度值。因此圖上所有深度值都與最小深度比較。如果某一節(jié)點的深度比最小深度還深，該深度值將被定義為一個給定的值，比如1000，否則設(shè)置為1。這種區(qū)別對于路徑規(guī)劃算法來說是必要的。

除了（船或飛機）殘骸等地理障礙物以外，石油平臺和其他船只也需要一起考慮。因此在每個障礙物的周圍定義一個危險區(qū)域。危險區(qū)域內(nèi)的節(jié)點深度值都設(shè)置為1000。如果程序用于計算魚雷射擊諸元，目標船的探測范圍也必須認為是障礙物。這種區(qū)域的深度值是可變的以便將探測距離定義為“可穿越”的障礙物。

圖生成后就可以開始尋找從起點到目標點的最優(yōu)路徑，這個功能由第二個程序模塊完成。根據(jù)給定的地理起始節(jié)點和目標節(jié)點位置以及地形模型的地理坐標，就可以用A*算法[2]計算最優(yōu)路徑。該算法來源于導航和機器人領(lǐng)域，在圖格式中應(yīng)用得很好。

算法原理如下：

算法首先建立“Open_List”和“Close_List”兩張空列表。Open_List存儲所有進入考慮視野但尚未處理的節(jié)點，一開始它只存儲了起始節(jié)點。兩個列表中的節(jié)點有三個數(shù)據(jù)域，其中d表示當前節(jié)點與起始點的距離，g表示與目標節(jié)點的估算距離，k表示其前驅(qū)節(jié)點的序號。對于起始節(jié)點s，定義d[s]=0和g[s]=0;對于其他節(jié)點，d和g的初始值為無窮大。所有節(jié)點的前驅(qū)節(jié)點為空。Close_List初始化為空列表。

算法依次考慮Open_List列表中d+g為最小的點。在第一步，該最小點就是起始點本身。首先把起始節(jié)點從Open_List列表刪除后添加到Close_List列表。然后把起始節(jié)點的所有相鄰節(jié)點加入到Open_List列表，對每一個節(jié)點計算到距離d和對應(yīng)邊權(quán)重值之和，然后在不考慮邊權(quán)重的情況下估算到目標點的距離g。新得出來的值與鄰節(jié)點對應(yīng)值相比較，如果新值小，那么將用新的d和g代替原來的對應(yīng)值，并把當前節(jié)點存儲為鄰節(jié)點的前驅(qū)節(jié)點。

當目標節(jié)點被添加到Close_List列表，算法結(jié)束。這時最佳的路徑就可以從目標節(jié)點根據(jù)前驅(qū)節(jié)點從目標節(jié)點回溯到起始節(jié)點。

當最佳路徑?jīng)Q定后，需要將其簡化為航路點列表，因此對于最佳路徑上的每一個節(jié)點，如果節(jié)點改變了路徑方向就將其加入到航路點序列，這樣就將所有節(jié)點轉(zhuǎn)換為實際的地理位置。

若想定復(fù)雜，計算最佳路徑的時間可能超過20秒。計算機系統(tǒng)的性能也會影響計算時間。為了滿足時間約束，A*算法能加速，不足的是會降低規(guī)劃路徑的質(zhì)量。在距離估算項乘以一個常數(shù)因子，計算速度就會增加，因子越大，計算速度越快。

3.測試結(jié)果

開發(fā)的算法進行了一系列測試。針對不同的想定，在德國Bight平臺上已經(jīng)完成功能等測試。目的是規(guī)劃出魚雷從我方船只到目標船只（用深灰色的圓做標記）的航行軌跡。圖5提供了其中兩種想定。黑色區(qū)域代表深度值在最小深度之下，被定義為威脅區(qū)域?；疑珔^(qū)域表示深度在我船深度之下，需要魚雷改變航行深度。白色區(qū)域表示水深合適。圓的深灰色地區(qū)表示目標船的探測范圍，紅色線是計算得出的路徑。

圖5 German Bight試驗結(jié)果

除了幾個一般功能測試外，也對一些極端情形進行了測試。圖6顯示了從迷宮左下角出發(fā)到迷宮中心的路徑，在這個測試中沒有考慮時間限制。

圖6 極端情況下的試驗結(jié)果

此外還分析了A*算法的加速效果，在評估中用了幾個不同的因子，如圖7和圖8所示。從圖中可以明顯看出，隨著因子的增大，路徑質(zhì)量不斷下降。因子從1.0增加到30時計算時間從14.9s減少到0.4s。經(jīng)過幾個系列測試分析后，選擇1.5作為算法的加速因子，這一因子在不明顯影響計算路徑的質(zhì)量的前提下大大縮短了計算時間。若計算時間超過給定值，程序會自動增加因子的大小。

圖7 因子從1.0到1.5的加速測試

圖8 因子從2.0到3.0的加速測試

4.結(jié)束語

程序的實現(xiàn)和測試都取得成功，它能計算出兩個地理位置之間的最佳路徑并能避開所有障礙物。

在絕大多數(shù)的實際想定中，計算最佳路徑和相應(yīng)的航路點列表的時間小于3s。就是對于軍事應(yīng)用，這一時間也是很理想了，因為手工計算要慢得多。在一些特例中，最佳路徑的質(zhì)量有所差別。加速因子取值為1.5時，A*算法在計算的時間和路徑質(zhì)量方面達到較好的平衡。但是因子依賴不同想定和圖，在有些想定和圖中，算法會擴展很多不必要的節(jié)點。因子取值越大，路徑的質(zhì)量差別越明顯，如圖7和圖8所示。

在所有測試中，給定的20s時間約束存在2%的誤差，若不存在路徑，就將20.2s作為最大計算時間。這是A*算法中止執(zhí)行的標準，如果計算時間超過這個值就認為不存在路徑。A*算法操作的時間限制為20s，過了這個值就可以中止執(zhí)行算法操作了。依賴于計算機系統(tǒng)性能的時間認為與A*算法沒有關(guān)系。

程序在應(yīng)用于海軍平臺前，還需要做一些修改，如對程序進行擴展以改進與海圖的接口。根據(jù)路徑質(zhì)量要求，可以增加相應(yīng)的曲線平滑算法，以盡量減少確定的路徑與最優(yōu)路徑的差異。

參考文獻

[1]ESCAPE V4（2005）;Wolter，Nils;ATLAS ELEKTRONIK GmbH.

[2]Graphentheoretische Konzepte und Algorithmen（2005）;Krumke.S.O.，Noltemeier，H.;Teubner Verlag.