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

沈燕霞

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

【關鍵詞】海軍平臺;自動路徑;規劃算法

1.引言

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

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

2.算法實現

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

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

圖1 海圖區域（左）轉換為地形模型后的效果圖（右）

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

節點 ? ? ? ? ? ? ? 邊 ? ? ? ? ? ? 權重邊

圖2 描述節點和邊的符號

圖3 用圖表說明地形模型

圖4 對角線邊

當地形模型轉為圖后，一個光柵點就對應一個節點，光柵點的深度值就表示從該點到相應節點的邊的加權值，如圖3所示。

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

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

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

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

算法原理如下：

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

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

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

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

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

3.測試結果

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

圖5 German Bight試驗結果

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

圖6 極端情況下的試驗結果

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

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

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

4.結束語

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

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

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

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

參考文獻

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

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