多域限界內多AUV巡邏航路規劃方法

嚴浙平,何靚文,李 娟

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

多域限界內多AUV巡邏航路規劃方法

嚴浙平,何靚文,李 娟

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

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

多AUV; 協同路徑規劃; 預測控制; 粒子群算法

0 引言

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

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

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

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

1 協同巡邏問題建模

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

1.1 任務區域模型

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

圖1 任務區域模型圖Fig. 1 Model of task area

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

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

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

1.2 狀態空間模型

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

1.3 協同巡邏任務目標函數

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

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

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

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

則巡邏效能函數為

2 基于預測控制的協同航路規劃算法

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

2.1 基于PSO的規劃路徑求解

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

圖3 粒子編碼結構示意圖Fig. 3 Schematic of particle code structure

2.2 基于預測控制的規避策略

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

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

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

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

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

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

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

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

2.3 多AUV協同巡邏航路規劃算法流程

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

3 仿真結果與分析

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

圖7 路徑規劃流程圖Fig.7 Flow chart of path planning

圖8 文中方法航路規劃結果Fig. 8 Path planning result of the proposed method

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

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

圖9 隨機法航路規劃結果Fig. 9 Result of randomized path planning

圖10 貪婪法航路規劃結果Fig. 10 Result of greedy path planning

圖11 數據分析對比圖Fig. 11 Comparison of data analysis

4 結束語

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

[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 的多無人機協同廣域目標搜索滾動時域決策[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] 席裕庚,李德偉,林姝. 模型預測控制——現狀與挑戰[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協同區域搜索[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] 吳青坡,周紹磊,劉偉,等. 基于集散式模型預測控制的多無人機協同分區搜索[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] 李曄,姜言清,張國成,等. 一種基于電子海圖的欠驅動AUV區域搜索方案[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

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

10.11993/j.issn.2096-3920.2017.03.004

2017-03-31;

2017-04-26.

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

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

(責任編輯: 陳 曦)