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

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

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

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

A*搜索算法是全局路徑規(guī)劃方法的一種，該算法簡(jiǎn)單易實(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í)實(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ò)充能在一定程度上增加路徑的自由度，但會(huì)使計(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é)特性和動(dòng)力學(xué)特性。該方法可規(guī)劃出平滑路徑，但該路徑不能保證遠(yuǎn)離障礙物。與之相比，基于A*路徑規(guī)劃的關(guān)鍵點(diǎn)優(yōu)化法能在保證路徑安全的同時(shí)實(shí)現(xiàn)路徑平滑。[8]

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

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

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

1.1 風(fēng)機(jī)威脅勢(shì)場(chǎng)

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

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

(1)

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

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

(2)

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

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

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

(3)

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

1.2 他船威脅勢(shì)場(chǎng)

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

陰影區(qū)對(duì)船舶航行安全的度量可用遮擋角表示。由于雷達(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ī)間的距離和遮擋角大小一一對(duì)應(yīng)，可評(píng)估各位置不可見目標(biāo)造成的碰撞威脅Fship為

Fship=kα

(5)

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

2 基于威脅勢(shì)場(chǎng)的A*算法

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

2.1 他船威脅勢(shì)場(chǎng)

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

以包含34座風(fēng)機(jī)的上海東海大橋海上風(fēng)電場(chǎng)一期工程為研究對(duì)象(取左上角坐標(biāo)為(121.95°W，30.82°N)、右下角坐標(biāo)為(122.04°W，30.72°N)的矩形區(qū))。在該區(qū)域航行的船舶多數(shù)為長(zhǎng)約100 m的小型船舶，因此用100 m×100 m的方塊將該區(qū)域柵格化。根據(jù)小方格相對(duì)于風(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í)，船舶將主動(dòng)遠(yuǎn)離障礙物，即此時(shí)障礙物威脅勢(shì)場(chǎng)發(fā)揮作用。本文中該安全距離參考船舶安全領(lǐng)域要求取值，風(fēng)機(jī)影響范圍取半徑為7倍船長(zhǎng)的圓形區(qū)域，被風(fēng)機(jī)遮擋的他船影響范圍取半徑為14倍船長(zhǎng)的圓形區(qū)域。[10]

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

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

2.2 避碰路徑點(diǎn)生成

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)移動(dòng)到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*算法對(duì)長(zhǎng)為100 m的船舶進(jìn)行尋路，最終結(jié)果見圖6。由圖6可知，船舶從起始點(diǎn)出發(fā)，能在障礙物威脅勢(shì)場(chǎng)的影響下遠(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)，還需對(duì)該路徑進(jìn)行優(yōu)化，使其更適合船舶在風(fēng)電場(chǎng)區(qū)航行。

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

對(duì)采用A*算法規(guī)劃得到的路徑進(jìn)行通視性檢查，不僅可減少路徑拐點(diǎn)數(shù)量，還能縮短路徑長(zhǎng)度。[12]為減少運(yùn)算量，這里只對(duì)路徑點(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ù)量明顯減少。

4 結(jié)束語

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

本文提出的方法可為船舶在風(fēng)電場(chǎng)區(qū)航行提供參考，但在威脅地圖建模中未考慮風(fēng)、浪、流等對(duì)船舶安全航行的影響。此外，基于通視性檢查的關(guān)鍵點(diǎn)優(yōu)化雖然能在一定程度上縮短路徑長(zhǎng)度，但各點(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*算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2010, 38(11):1647-1650.

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

[10] 明力, 劉敬賢, 王先鋒. 超大型船舶安全縱向間距計(jì)算模型[J]. 中國(guó)航海, 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.