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

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

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

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

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

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

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

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

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

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

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

1.1 風機威脅勢場

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

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

(1)

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

對應的斥力為斥力函數(shù)的負梯度，其表達式為

(2)

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

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

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

(3)

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

1.2 他船威脅勢場

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

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

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

α=2arcsin(r/d)

(4)

將船舶與風機間的距離和遮擋角大小一一對應，可評估各位置不可見目標造成的碰撞威脅Fship為

Fship=kα

(5)

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

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

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

2.1 他船威脅勢場

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

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

(6)

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

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

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

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

2.2 避碰路徑點生成

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

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

(7)

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

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

(8)

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

(9)

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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

[5] 陳實, 劉純武, 黃芝平,等. 基于稀疏A*算法的AUV全局路徑規(guī)劃[J]. 魚雷技術, 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] 單偉, 孟正大. 基于改進A*算法的平滑路徑設計[J]. 東南大學學報(自然科學版), 2010(S1):155-161.

[8] 王紅衛(wèi), 馬勇, 謝勇,等. 基于平滑A*算法的移動機器人路徑規(guī)劃[J]. 同濟大學學報(自然科學版), 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.