薛雙飛, 謝 磊, 王樹武, 夏文濤, 包 竹
(1.武漢理工大學(xué) 能源與動力工程學(xué)院,武漢 430063; 2.國家水運(yùn)安全工程技術(shù)研究中心,武漢 430063)
受傳輸效率和施工難度影響,目前海上風(fēng)電場的建設(shè)大多集中在近海。然而,風(fēng)電機(jī)組的布置通常需占用大片海域,風(fēng)電場區(qū)及其附近的船舶若不能按照合理的路徑航行,容易與風(fēng)電機(jī)碰撞,造成風(fēng)機(jī)受損、船舶遇險(xiǎn)等事故。隨著風(fēng)力發(fā)電技術(shù)逐漸成熟,海上風(fēng)電場的數(shù)量和裝機(jī)規(guī)模將不斷增加,這勢必會影響近海船舶的安全航行。因此,研究在風(fēng)電機(jī)組障礙環(huán)境下的船舶避碰航線設(shè)計(jì)具有重要意義。
船舶避碰航線可參考路徑規(guī)劃方法設(shè)計(jì)。按照對環(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ī)劃方法的一種,該算法簡單易實(shí)現(xiàn),并能保證全局最優(yōu)解的收斂性。[1]A*尋路算法過程可分為環(huán)境構(gòu)建、路徑點(diǎn)生成和路徑優(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)識實(shí)體障礙物占有的空間,還可根據(jù)障礙物影響特征表示其影響范圍,使目標(biāo)不到達(dá)該領(lǐng)域。[3]然而,該方法也存在缺陷,即:格子的存在使得路徑不能向任意方向延伸;同時(shí),柵格的細(xì)化程度嚴(yán)重影響著算法的復(fù)雜度和發(fā)現(xiàn)路徑的能力。郭耕辰等[4]提出的自適應(yīng)分片算法在一定程度上突破了格子的限制,但依舊需采用柵格地圖來描述環(huán)境。
根據(jù)環(huán)境地圖的不同,A*算法生成路徑點(diǎn)的方法也存在差異。一般情況下,A*算法采用4鄰域節(jié)點(diǎn)擴(kuò)展法或8鄰域節(jié)點(diǎn)擴(kuò)展法搜尋下一個(gè)最優(yōu)節(jié)點(diǎn)位置。擴(kuò)展節(jié)點(diǎn)的擴(kuò)充能在一定程度上增加路徑的自由度,但會使計(jì)算量成倍增加。為提高運(yùn)算速度,一種稀疏A*算法[5]得到廣泛應(yīng)用,該方法通過在搜索中加入約束條件,有效裁剪搜索空間內(nèi)的無效點(diǎn)。基于可視圖的A*算法[6]也能提高路徑規(guī)劃速度,將當(dāng)前點(diǎn)、障礙物各頂點(diǎn)和目標(biāo)點(diǎn)組合連接,保證這些直線均不與障礙物相交,從而獲取規(guī)劃路徑。
一般而言,利用A*尋路算法得到的路徑是連接一系列散點(diǎn)生成的,在實(shí)際中若嚴(yán)格遵循該規(guī)劃路徑,需頻繁改變方向,這樣就造成方案的靈活性不足。為使A*算法規(guī)劃出的路徑有更強(qiáng)的實(shí)用性,單偉等[7]以位置、曲率和斜率作為路徑平滑的標(biāo)準(zhǔn),引入極多項(xiàng)式曲線生成平滑路徑,使該路徑同時(shí)滿足機(jī)器人幾何學(xué)特性和動力學(xué)特性。該方法可規(guī)劃出平滑路徑,但該路徑不能保證遠(yuǎn)離障礙物。與之相比,基于A*路徑規(guī)劃的關(guān)鍵點(diǎn)優(yōu)化法能在保證路徑安全的同時(shí)實(shí)現(xiàn)路徑平滑。[8]
針對現(xiàn)有A*算法中0-1地圖不能準(zhǔn)確描述船舶避碰過程的問題,首先在各風(fēng)機(jī)位置已知的情況下,根據(jù)船舶避碰要求建立風(fēng)電場區(qū)航行危險(xiǎn)度地圖;然后利用改進(jìn)的A*算法,采取8領(lǐng)域節(jié)點(diǎn)擴(kuò)展法生成路徑點(diǎn),初步規(guī)劃風(fēng)電場區(qū)船舶安全航行路徑;最后提取路徑拐點(diǎn),并進(jìn)行通視性檢驗(yàn),剔除非關(guān)鍵點(diǎn),進(jìn)一步使所得路徑符合實(shí)際情況。
風(fēng)電機(jī)組在海面上作為固定障礙物影響著附近船舶的安全航行,船舶需實(shí)時(shí)評估其所在位置的碰撞風(fēng)險(xiǎn)并及時(shí)對航線進(jìn)行調(diào)整,以避免事故發(fā)生。風(fēng)電場區(qū)的船舶碰撞風(fēng)險(xiǎn)可通過建立障礙物威脅勢場來描述,決定威脅勢場大小的因素主要有船舶與風(fēng)機(jī)之間的距離和由于風(fēng)機(jī)遮擋造成的船舶附近雷達(dá)陰影區(qū)面積2個(gè)。
船舶距離障礙物越近,與障礙物發(fā)生碰撞的概率就越大,這種關(guān)系可用人工勢場理論來描述。傳統(tǒng)人工勢場法中存在斥力場和引力場,目標(biāo)點(diǎn)對船舶有引力,而障礙物生成斥力。船舶在合力作用下移動,就能不斷靠近指定位置。[9]
在對風(fēng)機(jī)勢場建模時(shí),只考慮障礙物產(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)。
顯然,這種情況違背了船舶距離障礙物越近,碰撞危險(xiǎn)越大(即障礙物威脅勢場值越大)的要求。因此,為建立符合障礙物威脅勢場性質(zhì)的模型,需對傳統(tǒng)人工勢場進(jìn)行改進(jìn)。這里簡單地用標(biāo)量表示人工勢場中的障礙物斥力,各點(diǎn)的威脅值是多障礙物在此處威脅值的疊加。于是單個(gè)障礙物產(chǎn)生的斥力表示為
(3)
由此可得多障礙物下的斥力大小見圖2。
在評價(jià)風(fēng)電場區(qū)船舶航行的安全性問題時(shí),除了考慮船舶與風(fēng)機(jī)的碰撞風(fēng)險(xiǎn)以外,還要考慮他船與本船的碰撞風(fēng)險(xiǎn)。風(fēng)機(jī)的遮擋使得雷達(dá)不能探測到其陰影區(qū)內(nèi)的船舶,因而雷達(dá)陰影區(qū)隨時(shí)可能有船舶駛出,威脅本船的航行安全。考慮到風(fēng)機(jī)對雷達(dá)電磁波的散射中有80%來自于風(fēng)機(jī)塔身,每個(gè)風(fēng)機(jī)葉對電磁波的散射量僅占散射量的5%,且出現(xiàn)在觀測雷達(dá)位于風(fēng)機(jī)正面或背面的情況下,因此在計(jì)算風(fēng)機(jī)遮擋時(shí),可只考慮風(fēng)機(jī)塔身對雷達(dá)電磁波的遮擋。
陰影區(qū)對船舶航行安全的度量可用遮擋角表示。由于雷達(dá)波可認(rèn)為沿直線傳播,在分析遮擋角時(shí),連接船舶與風(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ī)間的距離。由此,遮擋角α的計(jì)算式為
α=2arcsin(r/d)
(4)
將船舶與風(fēng)機(jī)間的距離和遮擋角大小一一對應(yīng),可評估各位置不可見目標(biāo)造成的碰撞威脅Fship為
Fship=kα
(5)
式(5)中:k為比例系數(shù),實(shí)現(xiàn)從遮擋角到碰撞威脅的轉(zhuǎn)換。到風(fēng)機(jī)的距離與風(fēng)機(jī)遮擋角之間的關(guān)系見圖4。
搜索地圖是影響采用A*算法設(shè)計(jì)避碰航線效果的重要因素,若能在地圖中將約束條件詳細(xì)地描述出來,便可設(shè)計(jì)出符合需求的最優(yōu)路線。由于采用柵格化地圖便于確定障礙物和規(guī)劃對象的位置,因此該方法被廣泛應(yīng)用。
傳統(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)船舶與障礙物的距離小于安全距離時(shí),船舶將主動遠(yuǎn)離障礙物,即此時(shí)障礙物威脅勢場發(fā)揮作用。本文中該安全距離參考船舶安全領(lǐng)域要求取值,風(fēng)機(jī)影響范圍取半徑為7倍船長的圓形區(qū)域,被風(fēng)機(jī)遮擋的他船影響范圍取半徑為14倍船長的圓形區(qū)域。[10]
若以長為100 m的船舶為研究對象,則風(fēng)機(jī)威脅勢場模型中的d0取值700 m,另取斥力增益kb=10,此時(shí)單風(fēng)機(jī)威脅值范圍為0~10;而他船威脅勢場中取比例系數(shù)k=100,此時(shí)單風(fēng)機(jī)遮擋影響的他船威脅值范圍為3~10。
根據(jù)以上約束條件,對各小方格進(jìn)行計(jì)算之后得到的威脅地圖見圖5,顏色越深表示該處威脅度越大。
A*算法的核心在于設(shè)計(jì)一個(gè)符合特定問題需求的代價(jià)函數(shù)[11],可表示為
f(n)=g(n)+h(n)
(7)
式(7)中:f(n)為從出發(fā)點(diǎn)到終點(diǎn)路徑上的代價(jià)值,在符合航行要求的情況下,f(n)越小,得到的路徑越優(yōu);g(n)為從起點(diǎn)到當(dāng)前點(diǎn)n產(chǎn)生的實(shí)際代價(jià),是已有各路徑點(diǎn)的累積和;h(n)為從當(dāng)前點(diǎn)到終點(diǎn)代價(jià)的估計(jì),又稱啟發(fā)函數(shù),作用是引導(dǎo)路徑點(diǎn)不斷地接近最終目標(biāo)。
g(n)=g(n-1)+G+T(n)+Ftotal(n)
(8)
估價(jià)函數(shù)h(n)是保證找到最佳路徑的關(guān)鍵影響因素之一。當(dāng)估價(jià)值h(n)小于或等于當(dāng)前點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值時(shí),搜索點(diǎn)數(shù)多、 搜索范圍大、效率低,但能得到最優(yōu)解;當(dāng)估價(jià)值h(n)大于當(dāng)前點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值時(shí),搜索的點(diǎn)數(shù)少、搜索范圍小、效率高,但不能保證得到最優(yōu)解。為得到最優(yōu)解,用歐幾里得距離作為估價(jià)函數(shù),即
(9)
在選好合適的代價(jià)函數(shù)并確定始發(fā)點(diǎn)和終止點(diǎn)之后,便可開始A*尋路過程。在柵格地圖中利用8鄰域節(jié)點(diǎn)擴(kuò)展法的A*算法尋路過程可表述為:
1) 建立open列表和close列表,將起始方格放到open表中,初始化close列表為空。
2) 記當(dāng)前節(jié)點(diǎn)為A,與該點(diǎn)相鄰的8個(gè)方格為其子節(jié)點(diǎn),將這些子節(jié)點(diǎn)放入open表中,同時(shí)將A節(jié)點(diǎn)移動到close表中(若A節(jié)點(diǎn)周圍的8個(gè)點(diǎn)已在open表中且以A節(jié)點(diǎn)作為這8個(gè)點(diǎn)中任意一點(diǎn)的父節(jié)點(diǎn)減小了該點(diǎn)的F值,則更新該點(diǎn))。
3) 將F值最小的節(jié)點(diǎn)放到close表中,并將該點(diǎn)作為當(dāng)前節(jié)點(diǎn)A。
4) 重復(fù)步驟1)~步驟3),直到把終點(diǎn)放到open表中。
5) 從當(dāng)前點(diǎn)(終點(diǎn))開始追溯父節(jié)點(diǎn)即為滿足需求的路線。
根據(jù)以上步驟,采用A*算法對長為100 m的船舶進(jìn)行尋路,最終結(jié)果見圖6。由圖6可知,船舶從起始點(diǎn)出發(fā),能在障礙物威脅勢場的影響下遠(yuǎn)離風(fēng)機(jī)航行,并能在部分間隔較遠(yuǎn)的風(fēng)機(jī)間穿行,最終到達(dá)目標(biāo)位置。然而,即便在代價(jià)函數(shù)中已考慮轉(zhuǎn)彎代價(jià),采用A*算法得到的路徑還是存在拐點(diǎn)較多的問題。這是由于在柵格環(huán)境中,8鄰域搜索法限制路徑只能朝8個(gè)方向延伸。為減少拐點(diǎn),還需對該路徑進(jìn)行優(yōu)化,使其更適合船舶在風(fēng)電場區(qū)航行。
對采用A*算法規(guī)劃得到的路徑進(jìn)行通視性檢查,不僅可減少路徑拐點(diǎn)數(shù)量,還能縮短路徑長度。[12]為減少運(yùn)算量,這里只對路徑點(diǎn)中的拐點(diǎn)做通視性檢驗(yàn)。判斷某點(diǎn)是否為拐點(diǎn)的依據(jù)是看其與相鄰兩點(diǎn)的連線是否共線。具體流程見圖7。
將起始點(diǎn)P1作為當(dāng)前節(jié)點(diǎn),依次檢查當(dāng)前節(jié)點(diǎn)與拐點(diǎn)序列中的其他節(jié)點(diǎn)的通視性(即兩點(diǎn)連線與障礙物之間的距離是否符合船舶航行安全距離要求)。若能通視,則保留該節(jié)點(diǎn)。最后將得到的拐點(diǎn)序列依次連線便得到優(yōu)化之后的路徑(見圖8)。由圖8可知,優(yōu)化之后的路徑總體走向不變,但拐點(diǎn)數(shù)量明顯減少。
本文結(jié)合人工勢場理論和A*算法,提出基于障礙物威脅勢場的A*尋路算法。該算法可在保證船舶遠(yuǎn)離風(fēng)機(jī)障礙的同時(shí),以最短路徑到達(dá)目標(biāo)位置。相對于傳統(tǒng)的*算法,采用本文提出的方法得到的路徑不一定最短,但從船舶避障、操作復(fù)雜程度和最終路徑長度等角度綜合考慮是最優(yōu)的。
本文提出的方法可為船舶在風(fēng)電場區(qū)航行提供參考,但在威脅地圖建模中未考慮風(fēng)、浪、流等對船舶安全航行的影響。此外,基于通視性檢查的關(guān)鍵點(diǎn)優(yōu)化雖然能在一定程度上縮短路徑長度,但各點(diǎn)間以線段連接得到的最終路線并不是符合條件的最短路線。
[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é)報(bào)(交通科學(xué)與工程版), 2016, 40(3):456-461.
[4] 郭耕辰, 馮良炳, 鄧亮,等. 基于A*算法與自適應(yīng)分片的大規(guī)模最優(yōu)路徑規(guī)劃[J]. 集成技術(shù), 2014(2):68-77.
[5] 陳實(shí), 劉純武, 黃芝平,等. 基于稀疏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ì)[J]. 東南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2010(S1):155-161.
[8] 王紅衛(wèi), 馬勇, 謝勇,等. 基于平滑A*算法的移動機(jī)器人路徑規(guī)劃[J]. 同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2010, 38(11):1647-1650.
[9] 謝朔, 初秀民, 柳晨光,等. 船舶智能避碰研究綜述及展望[J]. 交通信息與安全, 2016(1):1-9.
[10] 明力, 劉敬賢, 王先鋒. 超大型船舶安全縱向間距計(jì)算模型[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.