嚴浙平,何靚文,李 娟

(哈爾濱工程大學 自動化學院,黑龍江 哈爾濱,150001)

多域限界內(nèi)多AUV巡邏航路規(guī)劃方法

嚴浙平,何靚文,李 娟

(哈爾濱工程大學 自動化學院,黑龍江 哈爾濱,150001)

傳統(tǒng)粒子群優(yōu)化算法在應用于復雜環(huán)境自主式水下航行器(AUV)協(xié)同航路規(guī)劃時,由于粒子群更新過程中缺少約束性,極易產(chǎn)生不可行路徑。針對該問題,文中提出了一種適用于復雜環(huán)境的多AUV協(xié)同航路規(guī)劃優(yōu)化算法。該方法將預測控制與粒子群算法相結(jié)合,將兩步預測植入粒子更新過程,對更新的粒子進行檢測,避免了不可行粒子的生成。文中基于柵格法對環(huán)境進行建模,將環(huán)境的覆蓋信息、不確定度等存入矢量柵格中。將文中改進的算法以島礁監(jiān)視為應用背景進行了仿真驗證,結(jié)果表明,該算法實現(xiàn)了在復雜環(huán)境中的多AUV巡邏航路規(guī)劃,且對于不同性質(zhì)區(qū)域具有不同的巡邏頻率,具有較好的巡邏效能,更符合實際的應用環(huán)境。

多AUV; 協(xié)同路徑規(guī)劃; 預測控制; 粒子群算法

0 引言

近年來,隨著國內(nèi)外局勢持續(xù)升溫,海防體系建設(shè)更需完善。自主水下航行器(autonomous undersea vehicle,AUV)作為一種新型的武器裝備,具備自主航行和獨立執(zhí)行任務的能力。但隨著水下作業(yè)任務類別的與日俱增以及作業(yè)力度需求的逐漸增加,單個AUV自帶能源有限、觀察范圍較小、通信帶寬較窄等缺陷也逐漸顯現(xiàn)。對于海況更加復雜、偵查海域更大的區(qū)域來說,依靠單個AUV已不能滿足作業(yè)需求。而多AUV協(xié)同偵查方式由于其高度的并行性、魯棒性和高效的協(xié)作性,能有效彌補單 AUV執(zhí)行任務時的性能缺陷,大大提高執(zhí)行任務的效能。

目前,國內(nèi)外在空中無人機的區(qū)域覆蓋、區(qū)域搜索等方面已經(jīng)有了很多研究成果。Alfredo Garcia[1]等以狼群通過氣味實現(xiàn)競爭合作進行捕食為靈感,提出一種以掠奪者-食物為模型的仿生學協(xié)同搜索算法。目前,在協(xié)同決策機制方面運用較廣的是數(shù)字信息素法,文獻[2]對傳統(tǒng)的數(shù)字信息更新機理進行改進,提出了基于滾動時域控制的協(xié)同搜索策略。隨著預測控制[3]在各個領(lǐng)域的應用范圍拓寬,又為學者們打開了新的思路。彭輝[4]等提出了一種搜索效率較高的分布式模型預測控制方法,對動態(tài)目標有更好的搜索效果。文獻[5]也提出了一種基于預測控制思想的集散式分區(qū)搜索策略。粒子群算法作為一種啟發(fā)式算法在這方面也得到了廣泛的應用,但因為其具有易陷入局部最優(yōu)解的缺點,Masoud Dadgar[6]等對傳統(tǒng)粒子群算法進行改進,解決了易陷入局部最優(yōu)的問題,同時規(guī)劃出實時避障的安全路徑。在此基礎(chǔ)上,一種分數(shù)階機器達爾文粒子群算法[7]在未知環(huán)境探測上也得到了應用。

AUV在這方面的研究相對比較缺乏,因為水下的環(huán)境更復雜,尤其是 AUV在水下的信息交互比較困難,這使區(qū)域協(xié)同覆蓋搜索受到很大限制[8]。此外,大部分現(xiàn)有算法解決的都是在規(guī)則多邊形區(qū)域中的覆蓋和搜索問題[9],缺少對區(qū)域異構(gòu)性的考慮,對于整個區(qū)域進行無差異的覆蓋與搜索,約束條件較少,很難直接應用于水下的協(xié)同巡邏問題。此外,由于復雜環(huán)境的邊界條件較為苛刻,傳統(tǒng)的粒子群算法在粒子進化過程中極易產(chǎn)生不可行解,即規(guī)劃出不可行路徑。

針對上述問題,文章提出一種適用于復雜異構(gòu)環(huán)境的多 AUV協(xié)同巡邏航路規(guī)劃優(yōu)化算法。該方法基于網(wǎng)格劃分和矢量信息進行環(huán)境建模,考慮區(qū)域的異構(gòu)性,將區(qū)域劃分成不同類型,對目標存在概率較大的區(qū)域進行重點偵察,對目標存在概率很小的區(qū)域適當回避; 并且在 AUV安全的前提下,使 AUV盡可能地分散在目標區(qū)域內(nèi)。文中將粒子群算法與預測控制相結(jié)合,克服了傳統(tǒng)粒子群算法在粒子更新過程中易產(chǎn)生不可行路徑的缺點,保證了規(guī)劃路徑的安全性。

1 協(xié)同巡邏問題建模

以島礁附近海域巡邏作業(yè)為背景,并結(jié)合其具有的復雜環(huán)境與作業(yè)特點,建立以島礁為中心的2D環(huán)形仿真海域數(shù)值模型[10]。由于島礁附近海域巡邏任務其應用背景的特殊性,使得對AUV在該復雜環(huán)境下的巡邏航路規(guī)劃,需要充分考慮目標出現(xiàn)概率、活動范圍限制等因素,提高對高概率目標活動區(qū)域的巡邏頻率,避開對無價值區(qū)域作業(yè),進而提高AUV的巡邏效率。文中結(jié)合目標活動高頻區(qū)域與航行限制區(qū)域等實際海域環(huán)境限制因素,且為達到提高多 AUV的協(xié)同搜索工作效率、快速獲取任務區(qū)域所含目標信息以及快速完成對整個區(qū)域的覆蓋搜索等要求,將任務海域劃分為一般關(guān)注區(qū)、重點關(guān)注區(qū)、禁航區(qū)等區(qū)域。巡邏規(guī)劃將以全局覆蓋巡邏為基礎(chǔ),對目標高概率活動區(qū)域進行重點偵察,限制對禁航區(qū)域的偵查作業(yè)。

1.1 任務區(qū)域模型

采用N個AUV同時在任務區(qū)域進行巡邏搜索,將被執(zhí)行巡邏任務的海域模型近似為以島嶼為中心的環(huán)形區(qū)域M如圖1所示,其中包含重點區(qū)域、普通區(qū)域和禁航區(qū)域(島礁)。將巡邏任務區(qū)域離散成網(wǎng)格單元,每個單元格Mij在某一時刻k的取值為一個矢量信息結(jié)構(gòu),其表達式為

圖1 任務區(qū)域模型圖Fig. 1 Model of task area

式中,Vij為區(qū)域權(quán)重信息,其值對應任務區(qū)域出現(xiàn)目標的概率大小,若網(wǎng)格單元權(quán)重大,則需要較強的巡邏力度,反之則無需進行頻繁巡邏,進而提高巡邏效率,其取值如下

式中:n為在k時刻于Mij執(zhí)行巡邏任務的 AUV數(shù)量。但在實際巡邏過程中,為了保證AUV的安全,必須考慮避碰問題,即同一時刻內(nèi)同一單元格不能由多個 AUV同時巡邏,這將在后文中詳細敘述。為不確定度,表示在k時刻AUV對網(wǎng)格Mij的信息不確定程度,其值為1時表示 AUV完全掌握網(wǎng)格Mij處的目標存在信息,其值為0時表示AUV對網(wǎng)格Mij處的目標信息一無所知。目標信息主要是指該處是否存在目標。取值隨時間k變化而變化,具體如下

式中,為不確定度更新系數(shù),對于不同權(quán)重的區(qū)域其不確定度增長速度也不同,如此有利于吸引AUV加大對權(quán)重較高區(qū)域的巡邏頻率。

1.2 狀態(tài)空間模型

根據(jù)任務區(qū)域模型,可建立 AUV執(zhí)行任務決策的離散狀態(tài)空間。假定參與執(zhí)行任務的所有AUV航行于同一固定深度進行巡邏任務,由于文中重點考察其作業(yè)狀態(tài)下的路徑規(guī)劃問題,忽略AUV艇體結(jié)構(gòu)對作業(yè)的影響,故將AUV機體簡化成質(zhì)點進行分析。在該狀態(tài)空間內(nèi),第i個AUV的狀態(tài)記為?,其中xpi(k)=表示AUV在k時刻在任務區(qū)域里的坐標,表示AUV當前的艏向角; 而第i個AUV的決策記為其中表示AUV的速度,Δψi(k)表示AUV的艏向角增量。由此,可得AUV的狀態(tài)方程

1.3 協(xié)同巡邏任務目標函數(shù)

采用多 AUV參與協(xié)同巡邏任務的目的是增加巡邏效率,并加大對目標活動高頻區(qū)域的巡邏力度,盡可能多地獲取任務區(qū)域的信息,降低任務區(qū)域信息的不確定性。此外,AUV的空間分布條件應有利于之后執(zhí)行對目標的打擊任務,因此AUV需能盡快抵達任務區(qū)域內(nèi)各網(wǎng)格。結(jié)合以上原則,采用巡邏效能函數(shù)J作為優(yōu)化目標函數(shù),其特點是對多AUV在巡邏過程中的環(huán)境搜索收益和加權(quán)距離J2進行綜合考察分析,具體如下。

1) 環(huán)境搜索效益J1。環(huán)境搜索效益是指在巡邏過程中,隨著 AUV的搜索和傳感器的觀測,AUV對整個任務區(qū)域逐漸了解,對應環(huán)境的未知信息逐漸減少,因此,環(huán)境搜索效益定義為對環(huán)境不確定度消除量的總和,即

骨質(zhì)疏松性椎體壓縮骨折(osteoporotic vertebral vompression fractures,OVCF)是臨床常見、多發(fā)的骨科疾病,經(jīng)皮椎體后凸成形術(shù)(percutaneous kyphoplasty,PKP)已成為目前治療此病的主要方式之一,但術(shù)中球囊擴張部位對療效及預后的影響研究尚少。本文將選取我院于2015年2月-2017年5月期間收治的90例骨質(zhì)疏松性椎體壓縮型骨折患者作為本次研究對象,探討骨質(zhì)疏松性椎體壓縮骨折患者接受椎體后凸成形術(shù)治療過程中不同的球囊擴張部位對其療效及安全性的影響情況,為提高患者治療效果及預后提供切實依據(jù),現(xiàn)總結(jié)如下。

2) 加權(quán)距離J2。AUV的空間分布應有利于之后執(zhí)行對目標的打擊任務。此外,對于不同權(quán)重的區(qū)域,AUV應對權(quán)重高的區(qū)域具有更短的打擊距離。具體定義為

則巡邏效能函數(shù)為

2 基于預測控制的協(xié)同航路規(guī)劃算法

由多 AUV協(xié)同巡邏模型可以看出,對于多AUV的協(xié)同路徑求解實際是一個優(yōu)化求解過程,優(yōu)化目標是使規(guī)劃出的路徑能夠具有最優(yōu)的巡邏效能。通過優(yōu)化性能指標,即可求解出最優(yōu)的多AUV決策序列。

2.1 基于PSO的規(guī)劃路徑求解

圖2 AUV決策輸入Fig. 2 Input of AUV decision

圖3 粒子編碼結(jié)構(gòu)示意圖Fig. 3 Schematic of particle code structure

2.2 基于預測控制的規(guī)避策略

在 AUV巡邏過程中,不僅要限制其在指定的海域范圍內(nèi)進行巡邏任務,而且應避開島礁陸地區(qū)域以保證執(zhí)行任務的安全性。在粒子群算法中,粒子速度和位置更新公式為

式中:w為慣性權(quán)重;t為當前迭代次數(shù);vi為粒子更新速度;c1和c2為加速因子;1r和r2為[0,1]區(qū)間的隨機數(shù);pi為個體極值;pg為群體極值。由式(10)可以看出,粒子群算法在對粒子進行更新時存在隨機性,極易產(chǎn)生超出巡邏任務區(qū)域的不可行解。此外,1.1節(jié)提到需要考慮避碰問題,避免同一時刻內(nèi)同一單元格內(nèi)出現(xiàn)由多個 AUV同時巡邏的情況。

文中提出采用預測控制的策略,對生成的粒子進行檢測,來保證粒子群尋優(yōu)過程中產(chǎn)生的AUV巡邏路徑一定在任務所要求的區(qū)域內(nèi)。如圖4所示,假設(shè)在k時刻對AUV進行接下來的兩步預測,其中0P為當前時刻更新節(jié)點。結(jié)合前文提到,需要考慮 AUV的最大偏轉(zhuǎn)角約束,即 AUV在前行過程中只能直行或者左右偏轉(zhuǎn)一定的角度,再結(jié)合環(huán)境地圖柵格化之后,AUV每次只有前方、左前方以及右前方 3個可選節(jié)點。由此,一步預測產(chǎn)生的節(jié)點集合為,兩步預測產(chǎn)生的節(jié)點集合為則首先需要對當前更新的節(jié)點進行判斷,是否為可行節(jié)點,若不可行則需要重新進行更新。其中,可行指的是該節(jié)點處不屬于禁航區(qū)域,同時在界定范圍內(nèi),且不出現(xiàn)多個AUV同時進入的情況。在接下來預測的兩步中,必須每一步都存在可行節(jié)點才能之后的尋優(yōu)求解。

圖4 兩步預測示意圖Fig. 4 Schematic of two-step prediction

綜上,粒子的更新規(guī)則如圖5所示。

采取兩步預測主要出于以下考慮: 首先,如果僅進行一步預測,則即使當前時刻更新的節(jié)點為可行節(jié)點,但難以保證下一節(jié)點必定可以生成可行節(jié)點。如圖 6所示,很有可能出現(xiàn)該種下一時刻無法避開禁航區(qū)域的情況,導致粒子更新陷入“鎖死”狀態(tài),無法進行下一步更新。其次,若進行三步或更多步的預測,的確更利于保證可行解存在,但會造成運算量的指數(shù)型增加,這很不利于 AUV規(guī)劃決策的實時性。而兩步預測從可行性和實時性兩方面解決了上述問題,由此使AUV能夠自動避開島礁區(qū)域,且不超出任務區(qū)域范圍,并且解決了避碰問題。

圖5 基于預測控制的粒子更新流程圖Fig. 5 Flow chart of particle update based on predictive control

圖6 一步預測示意圖Fig. 6 Schematic of one-step prediction

2.3 多AUV協(xié)同巡邏航路規(guī)劃算法流程

綜合2.1節(jié)基于PSO的規(guī)劃路徑求解和2.2節(jié)基于預測控制的規(guī)避策略,文中提出的多AUV協(xié)同巡邏航路規(guī)劃算法流程如圖7所示。

3 仿真結(jié)果與分析

為了驗證文中規(guī)劃方法的有效性與可行性,設(shè)置任務區(qū)域為以島礁為中心,內(nèi)徑為5 km,外徑為25 km的環(huán)形區(qū)域,并利用該方法對任務區(qū)域進行建模。仿真中設(shè)置了 2個重點區(qū)域,權(quán)重為5,剩余的普通區(qū)域權(quán)重為1。用7個AUV從島礁附近區(qū)域出發(fā)開始執(zhí)行巡邏任務。設(shè)定AUV在巡邏狀態(tài)下,每一個時間步長前進一個網(wǎng)格。粒子群優(yōu)化算法的參數(shù)如下: 粒子數(shù)目 Number=30,最大迭代次數(shù)為MaxDT=100,w從0.9至0.5線性變化,c1=c2=2,1r和r2是[0,1]區(qū)間的隨機數(shù)。利用該方法進行路徑規(guī)劃,仿真航路點數(shù)K=70,結(jié)果如圖8所示。所有AUV能很好地避開島礁區(qū)域,并且不超過任務區(qū)域范圍,有效實現(xiàn)了對區(qū)域的巡邏,說明了該方法的有效性和可行性。

圖7 路徑規(guī)劃流程圖Fig.7 Flow chart of path planning

圖8 文中方法航路規(guī)劃結(jié)果Fig. 8 Path planning result of the proposed method

為了說明該方法的優(yōu)越性,通過仿真將文中提出的方法與傳統(tǒng)的隨機法、貪婪法進行比較。其中,隨機方法是一種非協(xié)同的方法,AUV在決策時隨機選擇航行方向。貪婪法每個時刻都選擇當前目標函數(shù)最優(yōu)的路徑點。圖9和圖10分別顯示了一次仿真中這2種方法所規(guī)劃出的7個AUV的70個航路點的巡邏航跡。

結(jié)合圖11的數(shù)據(jù)分析可知,雖然隨機法和貪婪法的平均覆蓋率略高于文中方法,但對整體區(qū)域的巡邏不存在差異性,對重點區(qū)域的巡邏頻率明顯不及文中方法的高。

圖9 隨機法航路規(guī)劃結(jié)果Fig. 9 Result of randomized path planning

圖10 貪婪法航路規(guī)劃結(jié)果Fig. 10 Result of greedy path planning

圖11 數(shù)據(jù)分析對比圖Fig. 11 Comparison of data analysis

4 結(jié)束語

在柵格法進行環(huán)境建模的基礎(chǔ)上,以增強巡邏效能作為優(yōu)化目標,采用預測控制與粒子群算法相結(jié)合的方法,對傳統(tǒng)區(qū)域覆蓋搜索不適于異構(gòu)環(huán)境的缺點進行了改進,提出了一種應用于復雜環(huán)境的多 AUV協(xié)同航路規(guī)劃算法。以島礁監(jiān)視為應用背景進行建模仿真,結(jié)果表明該方法實現(xiàn)了在復雜環(huán)境中的多 AUV巡邏航路規(guī)劃,且對于不同性質(zhì)區(qū)域具有不同的巡邏頻率。文中沒有考慮實際情況下不規(guī)則障礙以及具體的目標對象。下一步工作將結(jié)合實際情況,健全區(qū)域模型,并加入具體目標來優(yōu)化巡邏效果。

[1] Garcia A,Li C Y,Pedraza F. A Bio-Inspired Scheme for Coordinated Online Search[J]. IEEE Transactions on Automatic Control,2010,55(9): 2142-2147.

[2] 沈東,魏瑞軒,祁曉明,等. 基于 MTPM 和 DPM 的多無人機協(xié)同廣域目標搜索滾動時域決策[J]. 自動化學報,2014,40(7): 1391-1403.Shen Dong,Wei Rui-xuan,Qi Xiao-ming,et al. Receding Horizon Decision Method Based on MTPM and DPM for Multi-UAVs Cooperative Large Area Target Search[J].Acta Automatica Sinica,2014,40(7): 1391-1403.

[3] 席裕庚,李德偉,林姝. 模型預測控制——現(xiàn)狀與挑戰(zhàn)[J]. 自動化學報,2013,39(3): 222-236.Xi Yu-geng,Li Wei-de,Lin Shu. Model Predictive Control — Status and Challenges[J]. Acta Automatica Sinica,2013,39(3): 222-236.

[4] 彭輝,沈林成,朱華勇. 基于分布式模型預測控制的多UAV協(xié)同區(qū)域搜索[J]. 航空學報,2010,31(3): 593-601.Peng Hui,Shen Lin-cheng,Zhu Hua-yong. Multiple UAV Cooperative Area Search Based on Distributed Model Predictive Control[J]. Acta Aeronautica et Astronautica Sinica,2010,31(3): 593-601.

[5] 吳青坡,周紹磊,劉偉,等. 基于集散式模型預測控制的多無人機協(xié)同分區(qū)搜索[J]. 控制理論與應用,2015,32(10): 1414-1421.Wu Qing-po,Zhou Shao-lei,Liu Wei,et al. Multi-unmanned Aerial Vehicles Cooperative Search Based on Central-distributed Model Predictive Control[J]. Control Theory and Applications,2015,32(10): 1414-1421.

[6] Masoud Dadgar,Shahram Jafari,Ali Hamzeh. A PSO-based Multi-robot Cooperation Method for Target Searching in Unknown Environments[J]. Neurocomputing,2016,177(C): 62-74.

[7] Wang Dong-shu,Wang Hai-tao,Liu Lei. Unknown Environment Exploration of Multi-robot System with the FORDPSO[J]. Swarm and Evolutionary Computation,2016,26: 157-174.

[8] Yoon Seokhoon,Qiao Chunming. Cooperative Search and Survey Using Autonomous Underwater Vehicles (AUVs)[J]. IEEE Transactions on Parallel and Distributed Systems,2011,22(3): 364-379.

[9] Caiti A,Casalino G,Munafo A,et al. Cooperating AUV Teams: Adaptive Area Coverage with Space-varying Communication Constraints[C]. Bremen: Oceans 2009 Europe,2009: 1-7.

[10] 李曄,姜言清,張國成,等. 一種基于電子海圖的欠驅(qū)動AUV區(qū)域搜索方案[J]. 機器人,2014,36(5): 609-618.Li Ye,Jiang Yan-qing,Zhang Guo-cheng,et al. An Under actuated AUV-oriented Region Search Method Based on Electronic Chart[J]. Robot,2014,36(5): 609-618.

Path Planning Method for Multi-AUVs Patrol in Restricted Multizone Area

YAN Zhe-ping,HE Jing-wen,LI Juan
(College of Automation,Harbin Engineering University,Harbin 150001,China)

Conventional particle swarm optimization(PSO) may generate infeasible path due to lack of constraints during the particle swarm updating process when it is applied to cooperative path planning for autonomous undersea vehicle(AUV) in complex environment. In this paper,a cooperative path planning optimization method for multi-AUVs in complex environments is proposed. This method combines the predictive control with the particle swarm optimization by embedding the two-step prediction into the particle updating process,and the new particles are tested to avoid formation of infeasible particles. Moreover,the environment is modeled based on the grid method,and the coverage information and uncertainty of the environment are stored in the vector grid. Simulation is conducted to verify the improved algorithm in island monitoring scenario. The results show that the proposed algorithm achieves multi-AUV patrol path planning for complex environment,and different patrol frequency for the regions with different nature to increase the patrol efficiency.

multi-AUV; cooperative path planning; predictive control; particle swarm optimization

TP24; U612.1

A

2096-3920(2017)03-0237-06

嚴浙平,何靚文,李娟. 多域限界內(nèi)多AUV巡邏航路規(guī)劃方法[J]. 水下無人系統(tǒng)學報,2017,25(3): 237-242.

10.11993/j.issn.2096-3920.2017.03.004

2017-03-31;

2017-04-26.

國家自然科學基金項目資助(51679057); 黑龍江省杰出青年科學基金項目資助(JC2016007); 中央高?；究蒲袠I(yè)務費專項基金資助(HEUCFM170403).

嚴浙平(1972-),男,工學博士,教授,研究方向為水下無人航行器的總體設(shè)計、智能控制和運動控制.

(責任編輯: 陳 曦)