基于多AUV間任務協作的水下多目標探測路徑規劃*

張美燕,蔡文郁(.浙江水利水電學院電氣工程系,浙江 杭州,3008;2.杭州電子科技大學電子信息學院,浙江 杭州,3008)

AUV(自主式水下航行器,Autonomous Underwater Vehicle)作為新一代的智能化水下機器人,具有自主搜尋、高精度探索和簡單作業的能力,在軍用和民用領域都具有廣泛的應用前景[1]。AUV擺脫了人工有纜遙控,在水下作戰和作業等方面都更加靈活機動,因此在軍事偵察與監視、反潛與巡邏、海洋測繪、海洋資源勘探、潛水支援等領域都發揮著重要作用。由于采用AUV的作業任務往往面臨復雜的水下環境,單個AUV的可靠性和時效性難以保證,并且在一些軍事領域中,比如反水雷探測系統等,必須使用大量的AUV集群協同執行危險任務。因此在水下大范圍三維區域內執行多個目標探測時,一般都會有多個AUV一起執行作業任務,由此必須考慮AUV集群內部的任務分配與協同作業問題。任務分配是組織和協調多AUV協同工作的重要內容,可為保證大范圍作業任務的高效完成提供技術支撐。

本文以多AUV集群內的協作任務分配與路徑規劃為技術背景,重點研究水下三維區間內多AUV多目標節點的優化探測路徑規劃機制。除了以每個AUV能量耗費小于初始能量為約束條件,本文另外添加了多AUV能耗均衡(即AUV訪問目標數上限值)的約束條件,構建了水下三維空間中的多旅行商MTSP(Multiple Traveling Salesman Problem)問題模型。由于MTSP問題屬于組合優化問題,具有NP-Complete計算復雜度,無法在多項式時間內解決,本文利用遺傳算法GA(Genetic Algorithm)對該問題進行啟發式求解。為了兼顧多AUV的能量消耗優化與均衡問題,在遺傳算法迭代求解中引入多AUV能量均衡的適應度函數,避免了多AUV巡航任務中某些AUV因能量消耗過多而失效的問題,從而提高了整體多AUV集群的探測作業效率。

1 相關文獻

目前已有一些關于多機器人協作任務分配的研究[2-3],其中智能機器人的路徑規劃問題屬于目前的研究熱點[4-5]——通過研究單個或多個機器人執行任務時的路徑規劃問題,求取優化解決方案。由于水下環境中存在巡航區域范圍大、海流運動無規則、AUV運動能量受限等特殊性,路徑規劃問題對于AUV而言更加重要。而且,單獨一個AUV對于多目標探測任務往往無法及時完成,而要求多個AUV協同作業,因此有必要深入研究多AUV間的任務分配與協同作業優化問題。

目前在水下三維空間內多AUV移動路徑規劃的研究成果較少,主要方法有人工勢場法、模板匹配法、地圖構建法和人工智能路徑規劃法等。近年來,隨著人工智能技術的迅速發展,以人工智能為技術手段的多AUV路徑規劃方法為主要研究方向。文獻[6]提出了一種用于多AUV路徑規劃的進化算法,將多AUV在各個時刻的航向值和速度值進行編碼,然后將這些編碼用進化算法優化以達到協調規劃的目的;文獻[7]提出了一種用于多AUV路徑規劃的高效算法,根據各AUV的起點和終點位置以及剩余能源的多少來確定一個橢圓,落在橢圓以內的路徑點將由該AUV負責探測。文獻[8]將自組織神經網絡(SOM)應用于移動機器人系統的任務分配與路徑規劃中,提出的算法在保證多機器人系統以最少的總耗費遍歷所有目標的前提下,每個移動機器人都能沿著最短路徑到達目標;在此基礎上,文獻[9]考慮了AUV的水下作業特點,將SOM算法應用到了水下多AUV多目標探測問題中;文獻[10]在三維柵格地圖的基礎上,給出一種基于生物啟發模型的三維路徑規劃和安全避障算法;文獻[11]基于稀疏A*算法,提出了一種用于構造搜索空間的隨機布點方法;文獻[12]利用遺傳算法求解路徑規劃問題,而且考慮了水下強洋流的作用與影響;文獻[13]對目前多AUV目標探測與協同作業技術的研究現狀做了簡單綜述,發現目前很少有文獻從多AUV的能量均衡方面進行研究。我們前期提出了一種基于AUV協作的水下傳感器網絡定位技術[14],但是也沒有對AUV的巡航路徑規劃進行深入優化。

以上各種算法應用了各種優化方法和搜索算法,為水下多AUV協同目標探測問題提供了一些解決辦法,但是都沒有綜合考慮到AUV集群內的能量約束與能耗均衡問題。有鑒于此,本文提出了一種考慮多AUV能量約束和能耗均衡的水下多目標探測路徑規劃機制,并設計了一種特殊約束的遺傳算法進行優化求解。

圖1 水下多目標探測示意

2 水下多目標探測路徑規劃機制

2.1 最優化理論模型

圖2 多AUV與多目標節點隨機部署示意

如圖1所示,假設水下立方體區域內包含個移動AUV:和個靜止目標節點:{T1,T2,…,TNtarget},水下目標節點通過在水底錨定的方式固定,因此其三維坐標為確定值。由于AUV具有較大范圍的運動能力,同時單臺AUV的成本較高,難以大規模地使用,可假設水下AUV和目標數滿足如下條件:。如果,那么問題會更加簡單,每個AUV可以按最短路徑直接到達離它最近的目標節點即可。如圖2所示,10個AUV隨機地部署在長寬高為100×100×100的三維水下空間內。每個AUV通過巡航方式逐個訪問目標節點以完成整個目標節點群的探測任務,AUV到達目標節點后停航一段時間進行目標探測與數據采集,然后再往下一個目標節點行駛。

(1)

(2)

假設水下空間內每個目標節點都被唯一的AUV節點所探測,所以滿足式(3):

(3)

本文假設每個AUV以相同的初始位置出發,向水下三維區間內的其他目標節點移動,最終回到初始位置。每個AUV都按照旅行商問題TSP(Traveling Salesman Problem)求解得到的路徑進行巡航探測,因此可以求得最短路徑。為了簡單起見,假設AUV自主移動所消耗的能量與所移動的歐氏距離度量相對應,所有AUV的總能耗如式(4)所示:

i=

(4)

(5)

該問題的優化目標是最小化多AUV集群巡航耗費的總能量,如式(6)所示:

mini

(6)

i

(7)

(8)

通過上述分析,可以發現上述問題其實就是帶多約束條件的改進多旅行商MTSP(Multiple Traveling Salesman Problem)問題,由于標準MTSP問題具有NP-Complete計算難度,本文所提出的問題求解也具有NP-Complete難度。目前大多數研究都集中在啟發式求解方法,本文采用一種特殊設計的遺傳算法GA(Genetic Algorithm)進行多目標多AUV探測問題的求解。在一般的水下多目標探測作業過程中多個AUV往往是同類型甚至是同型號的,因此本文假設多AUV具有相同的初始能量及能耗模型。為了使多個AUV承擔目標探測的任務量盡量一致,巡航過程消耗能量盡量平等,因此本文提出了多AUV均衡探測路徑規劃算法,能量均衡度量采用均方根表示,如式(9)所示:

(9)

因此,本文提出的多AUV均衡探測路徑規劃算法,通過遺傳算法求解過程中適應度函數和終止條件的設置,兼顧考慮能量優化和能耗均衡兩個方面,以避免巡航過程中某些AUV因為能量消耗過多而失效,影響整體多AUV集群的作業效能。

2.2 遺傳算法迭代求解

遺傳算法是通過模擬達爾文自然進化過程的搜尋最優解計算方法[15],由于采用了啟發式搜索策略,在處理帶約束的復雜組合優化問題方面表現出了良好的性能。本文采用遺傳算法求解多AUV多目標協同探測問題,通過設計考慮AUV巡航路徑長度的適應度函數與多AUV間能耗均衡的終止條件,使得多個AUV較為均衡地承擔多目標探測任務。具體求解過程由以下幾個步驟組成:

①初始化產生初始種群,根據MTSP問題對解實施編碼操作。在多AUV多目標MTSP問題[16]中,采用基因編碼表示遍歷的目標點順序及對應的AUV編號,以染色體表示AUV停留狀態指示變量。

②依據目標函數,計算種群中每個個體的適應度值。在多AUV多目標MTSP問題中,適應度函數采用了路徑長度i和巡航目標數Ni乘積的倒數,如式(10)所示,其中路徑長度采用三維空間內多個目標點間的歐氏距離和來表示。AUV巡航的總路徑越短,AUV巡航過的目標數越少,適應度值越大。

(10)

③根據適應度值和AUV巡航目標數,判斷是否滿足終止條件,如式(11)所示,當單個AUV巡航目標數達到時?Ntarget/Nauv」則終止該AUV的路徑計算過程;當所有AUV計算完畢后,即可獲得適應度值最大的染色體。除此之外,程序中還設置了最大迭代次數,如果超過最大迭代次數則自動終止遺傳算法。

(11)

④依據概率選遺傳算子,進行交叉和變異操作,產生新的解群,轉到第②步。對于交叉操作,隨機選擇兩個個體,在對應位置交換若干個基因片段,防止進入局部收斂。對于變異操作,隨機選取個體,同時隨機選取個體的兩個基因進行交換以實現變異操作。

綜上所述,本文提出的遺傳算法迭代求解MTSP問題的具體流程如圖3所示。

圖3 遺傳算法迭代求解方法

2.3 AUV運動模型分析

(12)

根據傳統的AUV運動學模型[17],可以通過歐拉角φ,θ,ψ變換矩陣T(φ,θ,ψ)轉換為本地坐標系的俯仰角、滾轉角、偏航角(u,v,w),如式(13)和(14)所示。

圖4 AUV運動坐標模型

(13)

T-1(φ,θ,ψ)=

(14)

實際AUV運動控制模型中,一般都以本地坐標系的俯仰角、滾轉角、偏航角為基本變量研究AUV的運動速度與路徑。雖然可以通過式(15)轉換到三維全局坐標系的速度和路徑,但是歐拉變換計算量較大,因此本文直接以三維全局坐標系的AUV位置與軌跡為研究對象,不考慮AUV因為轉向、橫滾、俯仰等姿態調整而額外耗費的能量,而簡化為AUV消耗能量只與其巡航路徑長度成正比。

(15)

3 仿真結果

本文采用 MATLAB R2014a仿真平臺對所提出的機制進行驗證。仿真環境的主要參數為:Ntarget個目標節點和NAUV個AUV隨機分布在區域半徑為10×10×10的三維水下區域內,仿真采用的AUV能量模型簡化為距離模型,AUV消耗能量與其所巡航的距離成正比,為了簡單起見本文做了歸一化處理,即每個AUV的能量初始值都定義為1 000單位(Unit),巡航1單位的路徑所需消耗的能量為1單位(Unit)。在本文仿真中,AUV數量固定為NAUV=5,改變目標節點的數量Ntarget=10～50,步進值為5。通常情況下,比較大的種群規模并不能優化遺傳算法的結果,因此本文仿真中GA算法的種群數設置為較小值80,最大迭代次數設置為5000次,變異率為5%。數據結果采用多次仿真取均值的方式獲取,本文仿真中對單AUV(TSP)探測路徑規劃算法、多AUV(MTSP Algorithm)探測算法、多AUV均衡探測路徑規劃算法(MTSP Balanced Algorithm)進行了總能量耗費、能耗均衡性、巡航速度和巡航生命周期等指標的比較。

圖5所示為50個目標節點時,單AUV(TSP)多目標探測移動軌跡及迭代次數。單AUV(TSP)多目標探測由于約束條件少,因此獲取最優解的概率較大。圖6所示為5個AUV和20個目標場景下多AUV(MTSP)探測路徑規劃算法和多AUV均衡探測路徑規劃算法的不同目標分配與移動軌跡情況,圖7所示為5個AUV和40個目標場景下多AUV(MTSP)探測路徑規劃算法和多AUV均衡探測路徑規劃算法的不同目標分配與移動軌跡情況,圖6(b)和圖7(b)相比較于圖6(a)和圖7(a),多個AUV所探測的目標數明顯趨于一致。從圖6和圖7可以明顯發現,多AUV均衡探測路徑規劃算法相比多AUV(MTSP)探測路徑規劃算法,可以避免AUV巡航路線中訪問節點數量不均衡的情況,進而可以提高多AUV間的能耗均衡性。

圖5 單AUV(TSP)多目標探測移動軌跡(Ntarget=50)

圖7 多AUV多目標探測移動軌跡(Nauv=5,Ntarget=40)

單AUV(TSP)探測路徑規劃算法、多AUV(MTSP)探測路徑規劃算法、多AUV均衡探測路徑規劃算法等3種算法所消耗的總能量(以巡航距離表示)如圖8所示。多AUV(MTSP)探測路徑規劃算法、多AUV均衡探測路徑規劃算法等兩種算法的能量消耗均衡、巡航速度和巡航生命周期對比分別如圖9～圖11所示。

圖8 3種算法能量總消耗對比

圖9 多AUV探測算法消耗能量均方根值對比

圖10 3種算法巡航速度對比

圖11 3種算法巡航生命周期對比

圖8表明,由于額外的約束條件造成求解空間的限制,采用遺傳算法進行全局最優解搜索時,多AUV均衡探測路徑規劃算法最終獲取的只是次優解,相比較于單AUV(TSP)探測路徑規劃算法,會消耗一部分額外的能量。但是水下多目標探測任務中,僅靠單個AUV無法完成大范圍目標群的巡航任務,單AUV(TSP)探測路徑規劃算法無法保證滿足式(7)約束條件,因此必須采用多AUV集群協同作業的方式。

從圖9～圖11可以發現,多AUV均衡探測路徑規劃算法相比單AUV(TSP)探測路徑規劃算法和多AUV(MTSP)探測路徑規劃算法犧牲了小部分能量最優性(能量總消耗增加小于20%),但多AUV均衡探測路徑規劃算法可以提高多AUV協同作業的能耗均衡性,避免某些AUV耗能過多而提前失效。多AUV能耗均衡性采用多AUV消耗能量的均方根值RMS(如式(9)所示)來表示,由于假設AUV能耗與巡航路徑成正比,因此RMS計算公式中的能量消耗也可用巡航距離代替計算。

單AUV(TSP)探測路徑規劃算法、多AUV(MTSP)探測路徑規劃算法、多AUV均衡探測路徑規劃算法等3種算法所對應的能耗均方根值對比如圖9所示。圖9表明,當水下空間中存在5個AUV和20個目標時,采用多AUV(MTSP)探測路徑規劃算法和多AUV均衡探測路徑規劃算法所得的消耗能量均方根值分別為18.565 8和17.237 5,多AUV均衡探測路徑規劃算法的能耗均衡性有所提高。5個 AUV和50個目標時,采用多AUV(MTSP)探測路徑規劃算法和多AUV均衡探測路徑規劃算法所消耗能量的均方根值分別為36.578 2和32.613 7,在目標數較多時(Ntarget=50),雖然消耗的總能量并無增長(Total Distance=140),但是多AUV均衡探測路徑規劃算法的能耗均衡性明顯提高。

單AUV(TSP)探測路徑規劃算法、多AUV(MTSP)探測路徑規劃算法、多AUV均衡探測路徑規劃算法等3種算法所對應的巡航速度對比如圖10所示。巡航速度定義為最后一個AUV完成所有目標巡航所持續的時間,本文假設多AUV都按同樣的速度勻速運動,因此巡航速度也可以用其最長巡航距離(Maximal Distance)來表示。圖10表明,5個AUV和50個目標時,多AUV均衡探測路徑規劃算法相比單AUV(TSP)探測路徑規劃算法和多AUV(MTSP)探測路徑規劃算法,巡航速度分別提高了200%和93%。

單AUV(TSP)探測路徑規劃算法、多AUV(MTSP)探測路徑規劃算法、多AUV均衡探測路徑規劃算法等3種算法所對應的巡航生命周期對比如圖11所示。巡航生命周期定義為AUV集群能夠完成的所有目標巡航的輪數(Round),如果有至少一個AUV因為能量耗費而無法承擔水下多目標巡航任務時,即認為已經到了巡航生命周期。圖11表明,5個AUV和50個目標時,多AUV均衡探測路徑規劃算法相比單AUV(TSP)探測路徑規劃算法和多AUV(MTSP)探測路徑規劃算法,巡航生命周期提高了60%。

4 結語

本文對三維水下空間內多AUV多目標優化探測問題進行了深入研究,提出了一種均衡多AUV能量消耗的多旅行商問題求解方法,并利用遺傳算法尋求優化解。仿真結果表明本文提出的算法可以提高多個AUV之間的能耗均衡性,以及整體多目標探測問題的巡航速度和巡航生命周期,避免了多AUV協同作業時某些AUV耗費能量過多而提前失效的情況。后續工作將考慮水下存在障礙物時如何規劃路徑,使得AUV在目標探測時也可以智能地避開障礙物。