沈燕霞

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

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

1.引言

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

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

2.算法實(shí)現(xiàn)

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

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

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

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

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

圖2 描述節(jié)點(diǎn)和邊的符號(hào)

圖3 用圖表說(shuō)明地形模型

圖4 對(duì)角線(xiàn)邊

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

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

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

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

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

算法原理如下：

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

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

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

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

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

3.測(cè)試結(jié)果

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

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

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

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

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

圖7 因子從1.0到1.5的加速測(cè)試

圖8 因子從2.0到3.0的加速測(cè)試

4.結(jié)束語(yǔ)

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

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

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

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

參考文獻(xiàn)

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

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