海上風(fēng)電場區(qū)船舶A*避碰尋路算法

薛雙飛， 謝 磊， 王樹武， 夏文濤， 包 竹

(1.武漢理工大學(xué) 能源與動力工程學(xué)院，武漢 430063； 2.國家水運(yùn)安全工程技術(shù)研究中心，武漢 430063)

受傳輸效率和施工難度影響，目前海上風(fēng)電場的建設(shè)大多集中在近海。然而，風(fēng)電機(jī)組的布置通常需占用大片海域，風(fēng)電場區(qū)及其附近的船舶若不能按照合理的路徑航行，容易與風(fēng)電機(jī)碰撞，造成風(fēng)機(jī)受損、船舶遇險等事故。隨著風(fēng)力發(fā)電技術(shù)逐漸成熟，海上風(fēng)電場的數(shù)量和裝機(jī)規(guī)模將不斷增加，這勢必會影響近海船舶的安全航行。因此，研究在風(fēng)電機(jī)組障礙環(huán)境下的船舶避碰航線設(shè)計具有重要意義。

船舶避碰航線可參考路徑規(guī)劃方法設(shè)計。按照對環(huán)境感知情況的不同，路徑規(guī)劃可分為全局路徑規(guī)劃和局部路徑規(guī)劃2類。全局路徑規(guī)劃即掌握全部環(huán)境信息，該方法適用于只有在靜態(tài)障礙物的環(huán)境中；而局部路徑規(guī)劃中的環(huán)境信息部分未知，該方法適用于動態(tài)路徑規(guī)劃。由于風(fēng)電機(jī)通常安裝在海上固定的位置，其對船舶航行的影響可認(rèn)為是已知的，因此船舶在風(fēng)電場區(qū)的路徑規(guī)劃問題屬于全局路徑規(guī)劃問題。

A*搜索算法是全局路徑規(guī)劃方法的一種，該算法簡單易實現(xiàn)，并能保證全局最優(yōu)解的收斂性。[1]A*尋路算法過程可分為環(huán)境構(gòu)建、路徑點生成和路徑優(yōu)化等3部分。

環(huán)境構(gòu)建就是選擇合適的方法描述障礙物信息，是路徑規(guī)劃和解決避障問題至關(guān)重要的一環(huán)，決定路徑的優(yōu)劣。[2]為方便確定障礙物的位置，現(xiàn)有的A*算法大多采用柵格法將環(huán)境信息分割為小方格，若小方格中包含障礙物，則將該方格標(biāo)記為1(表示不可通過)，否則標(biāo)記為0(表示可通過)。柵格法不僅可用來標(biāo)識實體障礙物占有的空間，還可根據(jù)障礙物影響特征表示其影響范圍，使目標(biāo)不到達(dá)該領(lǐng)域。[3]然而，該方法也存在缺陷，即：格子的存在使得路徑不能向任意方向延伸；同時，柵格的細(xì)化程度嚴(yán)重影響著算法的復(fù)雜度和發(fā)現(xiàn)路徑的能力。郭耕辰等[4]提出的自適應(yīng)分片算法在一定程度上突破了格子的限制，但依舊需采用柵格地圖來描述環(huán)境。

根據(jù)環(huán)境地圖的不同，A*算法生成路徑點的方法也存在差異。一般情況下，A*算法采用4鄰域節(jié)點擴(kuò)展法或8鄰域節(jié)點擴(kuò)展法搜尋下一個最優(yōu)節(jié)點位置。擴(kuò)展節(jié)點的擴(kuò)充能在一定程度上增加路徑的自由度，但會使計算量成倍增加。為提高運(yùn)算速度，一種稀疏A*算法[5]得到廣泛應(yīng)用，該方法通過在搜索中加入約束條件，有效裁剪搜索空間內(nèi)的無效點?；诳梢晥D的A*算法[6]也能提高路徑規(guī)劃速度，將當(dāng)前點、障礙物各頂點和目標(biāo)點組合連接，保證這些直線均不與障礙物相交，從而獲取規(guī)劃路徑。

一般而言，利用A*尋路算法得到的路徑是連接一系列散點生成的，在實際中若嚴(yán)格遵循該規(guī)劃路徑，需頻繁改變方向，這樣就造成方案的靈活性不足。為使A*算法規(guī)劃出的路徑有更強(qiáng)的實用性，單偉等[7]以位置、曲率和斜率作為路徑平滑的標(biāo)準(zhǔn)，引入極多項式曲線生成平滑路徑，使該路徑同時滿足機(jī)器人幾何學(xué)特性和動力學(xué)特性。該方法可規(guī)劃出平滑路徑，但該路徑不能保證遠(yuǎn)離障礙物。與之相比，基于A*路徑規(guī)劃的關(guān)鍵點優(yōu)化法能在保證路徑安全的同時實現(xiàn)路徑平滑。[8]

針對現(xiàn)有A*算法中0-1地圖不能準(zhǔn)確描述船舶避碰過程的問題，首先在各風(fēng)機(jī)位置已知的情況下，根據(jù)船舶避碰要求建立風(fēng)電場區(qū)航行危險度地圖；然后利用改進(jìn)的A*算法，采取8領(lǐng)域節(jié)點擴(kuò)展法生成路徑點，初步規(guī)劃風(fēng)電場區(qū)船舶安全航行路徑；最后提取路徑拐點，并進(jìn)行通視性檢驗，剔除非關(guān)鍵點，進(jìn)一步使所得路徑符合實際情況。

1 風(fēng)電場區(qū)威脅勢場建模

風(fēng)電機(jī)組在海面上作為固定障礙物影響著附近船舶的安全航行，船舶需實時評估其所在位置的碰撞風(fēng)險并及時對航線進(jìn)行調(diào)整，以避免事故發(fā)生。風(fēng)電場區(qū)的船舶碰撞風(fēng)險可通過建立障礙物威脅勢場來描述，決定威脅勢場大小的因素主要有船舶與風(fēng)機(jī)之間的距離和由于風(fēng)機(jī)遮擋造成的船舶附近雷達(dá)陰影區(qū)面積2個。

1.1 風(fēng)機(jī)威脅勢場

船舶距離障礙物越近，與障礙物發(fā)生碰撞的概率就越大，這種關(guān)系可用人工勢場理論來描述。傳統(tǒng)人工勢場法中存在斥力場和引力場，目標(biāo)點對船舶有引力，而障礙物生成斥力。船舶在合力作用下移動，就能不斷靠近指定位置。[9]

在對風(fēng)機(jī)勢場建模時，只考慮障礙物產(chǎn)生的勢力場，按傳統(tǒng)人工勢場法可得斥力函數(shù)為

(1)

式(1)中:kb為斥力增益系數(shù)；d為船舶與障礙物之間的距離；d0為障礙物斥力場的作用距離。

對應(yīng)的斥力為斥力函數(shù)的負(fù)梯度，其表達(dá)式為

(2)

式(2)中：X為船舶當(dāng)前的位置向量。

上述方法中斥力為矢量，這就可能導(dǎo)致在多障礙物環(huán)境下，船舶所受斥力隨著與障礙物間距離的減小而減小(見圖1)。

顯然，這種情況違背了船舶距離障礙物越近，碰撞危險越大(即障礙物威脅勢場值越大)的要求。因此，為建立符合障礙物威脅勢場性質(zhì)的模型，需對傳統(tǒng)人工勢場進(jìn)行改進(jìn)。這里簡單地用標(biāo)量表示人工勢場中的障礙物斥力，各點的威脅值是多障礙物在此處威脅值的疊加。于是單個障礙物產(chǎn)生的斥力表示為

(3)

由此可得多障礙物下的斥力大小見圖2。

1.2 他船威脅勢場

在評價風(fēng)電場區(qū)船舶航行的安全性問題時，除了考慮船舶與風(fēng)機(jī)的碰撞風(fēng)險以外，還要考慮他船與本船的碰撞風(fēng)險。風(fēng)機(jī)的遮擋使得雷達(dá)不能探測到其陰影區(qū)內(nèi)的船舶，因而雷達(dá)陰影區(qū)隨時可能有船舶駛出，威脅本船的航行安全。考慮到風(fēng)機(jī)對雷達(dá)電磁波的散射中有80%來自于風(fēng)機(jī)塔身，每個風(fēng)機(jī)葉對電磁波的散射量僅占散射量的5%，且出現(xiàn)在觀測雷達(dá)位于風(fēng)機(jī)正面或背面的情況下，因此在計算風(fēng)機(jī)遮擋時，可只考慮風(fēng)機(jī)塔身對雷達(dá)電磁波的遮擋。

陰影區(qū)對船舶航行安全的度量可用遮擋角表示。由于雷達(dá)波可認(rèn)為沿直線傳播，在分析遮擋角時，連接船舶與風(fēng)機(jī)兩側(cè)所得夾角即為遮擋角α。雷達(dá)遮擋角示意見圖3。

圖3中：O為雷達(dá)位置；M為風(fēng)機(jī)中心；r為風(fēng)機(jī)半徑；A和B為兩處臨界目標(biāo)位置；d為船舶與風(fēng)機(jī)間的距離。由此，遮擋角α的計算式為

α=2arcsin(r/d)

(4)

將船舶與風(fēng)機(jī)間的距離和遮擋角大小一一對應(yīng)，可評估各位置不可見目標(biāo)造成的碰撞威脅Fship為

Fship=kα

(5)

式(5)中：k為比例系數(shù)，實現(xiàn)從遮擋角到碰撞威脅的轉(zhuǎn)換。到風(fēng)機(jī)的距離與風(fēng)機(jī)遮擋角之間的關(guān)系見圖4。

2 基于威脅勢場的A*算法

搜索地圖是影響采用A*算法設(shè)計避碰航線效果的重要因素，若能在地圖中將約束條件詳細(xì)地描述出來，便可設(shè)計出符合需求的最優(yōu)路線。由于采用柵格化地圖便于確定障礙物和規(guī)劃對象的位置，因此該方法被廣泛應(yīng)用。

2.1 他船威脅勢場

傳統(tǒng)柵格化地圖中的小方格只存在被標(biāo)記為障礙物和可行區(qū)2種狀態(tài)，其弊端是得到的航線可能沿著障礙物邊緣或擴(kuò)展的障礙物邊緣。本文綜合考慮風(fēng)機(jī)威脅勢場和船舶威脅勢場，使航船與障礙物保持安全距離。

以包含34座風(fēng)機(jī)的上海東海大橋海上風(fēng)電場一期工程為研究對象(取左上角坐標(biāo)為(121.95°W，30.82°N)、右下角坐標(biāo)為(122.04°W，30.72°N)的矩形區(qū))。在該區(qū)域航行的船舶多數(shù)為長約100 m的小型船舶，因此用100 m×100 m的方塊將該區(qū)域柵格化。根據(jù)小方格相對于風(fēng)機(jī)的位置和遮擋角即可量化該碰撞威脅。任意小方格的總威脅Ftotal是風(fēng)機(jī)威脅Ffan與他船威脅Fship的和，可表示為

(6)

式(6)中：m和n為在影響范圍內(nèi)的風(fēng)機(jī)數(shù)。

無論是與風(fēng)機(jī)避碰還是與他船避碰，船舶與障礙物都應(yīng)保持安全距離。當(dāng)船舶與障礙物的距離小于安全距離時，船舶將主動遠(yuǎn)離障礙物，即此時障礙物威脅勢場發(fā)揮作用。本文中該安全距離參考船舶安全領(lǐng)域要求取值，風(fēng)機(jī)影響范圍取半徑為7倍船長的圓形區(qū)域，被風(fēng)機(jī)遮擋的他船影響范圍取半徑為14倍船長的圓形區(qū)域。[10]

若以長為100 m的船舶為研究對象，則風(fēng)機(jī)威脅勢場模型中的d0取值700 m，另取斥力增益kb=10，此時單風(fēng)機(jī)威脅值范圍為0～10；而他船威脅勢場中取比例系數(shù)k=100，此時單風(fēng)機(jī)遮擋影響的他船威脅值范圍為3～10。

根據(jù)以上約束條件，對各小方格進(jìn)行計算之后得到的威脅地圖見圖5，顏色越深表示該處威脅度越大。

2.2 避碰路徑點生成

A*算法的核心在于設(shè)計一個符合特定問題需求的代價函數(shù)[11]，可表示為

f(n)=g(n)+h(n)

(7)

式(7)中：f(n)為從出發(fā)點到終點路徑上的代價值，在符合航行要求的情況下，f(n)越小，得到的路徑越優(yōu)；g(n)為從起點到當(dāng)前點n產(chǎn)生的實際代價，是已有各路徑點的累積和；h(n)為從當(dāng)前點到終點代價的估計，又稱啟發(fā)函數(shù)，作用是引導(dǎo)路徑點不斷地接近最終目標(biāo)。

g(n)=g(n-1)+G+T(n)+Ftotal(n)

(8)

估價函數(shù)h(n)是保證找到最佳路徑的關(guān)鍵影響因素之一。當(dāng)估價值h(n)小于或等于當(dāng)前點到目標(biāo)節(jié)點的距離實際值時，搜索點數(shù)多、 搜索范圍大、效率低，但能得到最優(yōu)解；當(dāng)估價值h(n)大于當(dāng)前點到目標(biāo)節(jié)點的距離實際值時，搜索的點數(shù)少、搜索范圍小、效率高，但不能保證得到最優(yōu)解。為得到最優(yōu)解，用歐幾里得距離作為估價函數(shù)，即

(9)

在選好合適的代價函數(shù)并確定始發(fā)點和終止點之后，便可開始A*尋路過程。在柵格地圖中利用8鄰域節(jié)點擴(kuò)展法的A*算法尋路過程可表述為：

1) 建立open列表和close列表，將起始方格放到open表中，初始化close列表為空。

2) 記當(dāng)前節(jié)點為A，與該點相鄰的8個方格為其子節(jié)點，將這些子節(jié)點放入open表中，同時將A節(jié)點移動到close表中(若A節(jié)點周圍的8個點已在open表中且以A節(jié)點作為這8個點中任意一點的父節(jié)點減小了該點的F值，則更新該點)。

3) 將F值最小的節(jié)點放到close表中，并將該點作為當(dāng)前節(jié)點A。

4) 重復(fù)步驟1)～步驟3)，直到把終點放到open表中。

5) 從當(dāng)前點(終點)開始追溯父節(jié)點即為滿足需求的路線。

根據(jù)以上步驟，采用A*算法對長為100 m的船舶進(jìn)行尋路，最終結(jié)果見圖6。由圖6可知，船舶從起始點出發(fā)，能在障礙物威脅勢場的影響下遠(yuǎn)離風(fēng)機(jī)航行，并能在部分間隔較遠(yuǎn)的風(fēng)機(jī)間穿行，最終到達(dá)目標(biāo)位置。然而，即便在代價函數(shù)中已考慮轉(zhuǎn)彎代價，采用A*算法得到的路徑還是存在拐點較多的問題。這是由于在柵格環(huán)境中，8鄰域搜索法限制路徑只能朝8個方向延伸。為減少拐點，還需對該路徑進(jìn)行優(yōu)化，使其更適合船舶在風(fēng)電場區(qū)航行。

3 基于通視性檢查的路徑優(yōu)化

對采用A*算法規(guī)劃得到的路徑進(jìn)行通視性檢查，不僅可減少路徑拐點數(shù)量，還能縮短路徑長度。[12]為減少運(yùn)算量，這里只對路徑點中的拐點做通視性檢驗。判斷某點是否為拐點的依據(jù)是看其與相鄰兩點的連線是否共線。具體流程見圖7。

將起始點P1作為當(dāng)前節(jié)點,依次檢查當(dāng)前節(jié)點與拐點序列中的其他節(jié)點的通視性(即兩點連線與障礙物之間的距離是否符合船舶航行安全距離要求)。若能通視,則保留該節(jié)點。最后將得到的拐點序列依次連線便得到優(yōu)化之后的路徑(見圖8)。由圖8可知，優(yōu)化之后的路徑總體走向不變，但拐點數(shù)量明顯減少。

4 結(jié)束語

本文結(jié)合人工勢場理論和A*算法，提出基于障礙物威脅勢場的A*尋路算法。該算法可在保證船舶遠(yuǎn)離風(fēng)機(jī)障礙的同時，以最短路徑到達(dá)目標(biāo)位置。相對于傳統(tǒng)的*算法，采用本文提出的方法得到的路徑不一定最短，但從船舶避障、操作復(fù)雜程度和最終路徑長度等角度綜合考慮是最優(yōu)的。

本文提出的方法可為船舶在風(fēng)電場區(qū)航行提供參考，但在威脅地圖建模中未考慮風(fēng)、浪、流等對船舶安全航行的影響。此外，基于通視性檢查的關(guān)鍵點優(yōu)化雖然能在一定程度上縮短路徑長度，但各點間以線段連接得到的最終路線并不是符合條件的最短路線。

[1] 黃海威,鄧開發(fā). 改進(jìn)的A*算法在游戲地圖尋路中的應(yīng)用[J]. 信息技術(shù),2015(4):188-191.

[2] 方昕, 呂方興. 一種改進(jìn)A*算法的智能機(jī)器人路徑規(guī)劃[J]. 信息技術(shù), 2015(9):40-42.

[3] 吳博, 文元橋, 吳貝,等. 水面無人艇避碰方法回顧與展望[J]. 武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版), 2016, 40(3):456-461.

[4] 郭耕辰, 馮良炳, 鄧亮,等. 基于A*算法與自適應(yīng)分片的大規(guī)模最優(yōu)路徑規(guī)劃[J]. 集成技術(shù), 2014(2):68-77.

[5] 陳實, 劉純武, 黃芝平,等. 基于稀疏A*算法的AUV全局路徑規(guī)劃[J]. 魚雷技術(shù), 2012, 20(4):271-275.

[6] JANET J A, LUO R C, KAY M G. The Essential Visibility Graph: An Approach to Global Motion Planning for Autonomous Mobile Robots[C]// IEEE International Conference on Robotics and Automation, 1995: 1958-1963.

[7] 單偉, 孟正大. 基于改進(jìn)A*算法的平滑路徑設(shè)計[J]. 東南大學(xué)學(xué)報(自然科學(xué)版), 2010(S1):155-161.

[8] 王紅衛(wèi), 馬勇, 謝勇,等. 基于平滑A*算法的移動機(jī)器人路徑規(guī)劃[J]. 同濟(jì)大學(xué)學(xué)報(自然科學(xué)版), 2010, 38(11):1647-1650.

[9] 謝朔, 初秀民, 柳晨光,等. 船舶智能避碰研究綜述及展望[J]. 交通信息與安全, 2016(1):1-9.

[10] 明力, 劉敬賢, 王先鋒. 超大型船舶安全縱向間距計算模型[J]. 中國航海, 2014, 37(4):40-43.

[11] HART P E, NILSSON N J, RAPHAEL B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science & Cybernetics, 1972, 4(37):28-29.

[12] 陳彬, 李靖靖, 宋磊,等. 基于可視圖和A*算法的連續(xù)模型路徑搜索[J]. 交通信息與安全, 2012, 30(3):39-42.