張美燕,蔡文郁(.浙江水利水電學(xué)院電氣工程系,浙江 杭州,3008;2.杭州電子科技大學(xué)電子信息學(xué)院,浙江 杭州,3008)
AUV(自主式水下航行器,Autonomous Underwater Vehicle)作為新一代的智能化水下機(jī)器人,具有自主搜尋、高精度探索和簡(jiǎn)單作業(yè)的能力,在軍用和民用領(lǐng)域都具有廣泛的應(yīng)用前景[1]。AUV擺脫了人工有纜遙控,在水下作戰(zhàn)和作業(yè)等方面都更加靈活機(jī)動(dòng),因此在軍事偵察與監(jiān)視、反潛與巡邏、海洋測(cè)繪、海洋資源勘探、潛水支援等領(lǐng)域都發(fā)揮著重要作用。由于采用AUV的作業(yè)任務(wù)往往面臨復(fù)雜的水下環(huán)境,單個(gè)AUV的可靠性和時(shí)效性難以保證,并且在一些軍事領(lǐng)域中,比如反水雷探測(cè)系統(tǒng)等,必須使用大量的AUV集群協(xié)同執(zhí)行危險(xiǎn)任務(wù)。因此在水下大范圍三維區(qū)域內(nèi)執(zhí)行多個(gè)目標(biāo)探測(cè)時(shí),一般都會(huì)有多個(gè)AUV一起執(zhí)行作業(yè)任務(wù),由此必須考慮AUV集群內(nèi)部的任務(wù)分配與協(xié)同作業(yè)問題。任務(wù)分配是組織和協(xié)調(diào)多AUV協(xié)同工作的重要內(nèi)容,可為保證大范圍作業(yè)任務(wù)的高效完成提供技術(shù)支撐。
本文以多AUV集群內(nèi)的協(xié)作任務(wù)分配與路徑規(guī)劃為技術(shù)背景,重點(diǎn)研究水下三維區(qū)間內(nèi)多AUV多目標(biāo)節(jié)點(diǎn)的優(yōu)化探測(cè)路徑規(guī)劃機(jī)制。除了以每個(gè)AUV能量耗費(fèi)小于初始能量為約束條件,本文另外添加了多AUV能耗均衡(即AUV訪問目標(biāo)數(shù)上限值)的約束條件,構(gòu)建了水下三維空間中的多旅行商MTSP(Multiple Traveling Salesman Problem)問題模型。由于MTSP問題屬于組合優(yōu)化問題,具有NP-Complete計(jì)算復(fù)雜度,無法在多項(xiàng)式時(shí)間內(nèi)解決,本文利用遺傳算法GA(Genetic Algorithm)對(duì)該問題進(jìn)行啟發(fā)式求解。為了兼顧多AUV的能量消耗優(yōu)化與均衡問題,在遺傳算法迭代求解中引入多AUV能量均衡的適應(yīng)度函數(shù),避免了多AUV巡航任務(wù)中某些AUV因能量消耗過多而失效的問題,從而提高了整體多AUV集群的探測(cè)作業(yè)效率。
目前已有一些關(guān)于多機(jī)器人協(xié)作任務(wù)分配的研究[2-3],其中智能機(jī)器人的路徑規(guī)劃問題屬于目前的研究熱點(diǎn)[4-5]——通過研究單個(gè)或多個(gè)機(jī)器人執(zhí)行任務(wù)時(shí)的路徑規(guī)劃問題,求取優(yōu)化解決方案。由于水下環(huán)境中存在巡航區(qū)域范圍大、海流運(yùn)動(dòng)無規(guī)則、AUV運(yùn)動(dòng)能量受限等特殊性,路徑規(guī)劃問題對(duì)于AUV而言更加重要。而且,單獨(dú)一個(gè)AUV對(duì)于多目標(biāo)探測(cè)任務(wù)往往無法及時(shí)完成,而要求多個(gè)AUV協(xié)同作業(yè),因此有必要深入研究多AUV間的任務(wù)分配與協(xié)同作業(yè)優(yōu)化問題。
目前在水下三維空間內(nèi)多AUV移動(dòng)路徑規(guī)劃的研究成果較少,主要方法有人工勢(shì)場(chǎng)法、模板匹配法、地圖構(gòu)建法和人工智能路徑規(guī)劃法等。近年來,隨著人工智能技術(shù)的迅速發(fā)展,以人工智能為技術(shù)手段的多AUV路徑規(guī)劃方法為主要研究方向。文獻(xiàn)[6]提出了一種用于多AUV路徑規(guī)劃的進(jìn)化算法,將多AUV在各個(gè)時(shí)刻的航向值和速度值進(jìn)行編碼,然后將這些編碼用進(jìn)化算法優(yōu)化以達(dá)到協(xié)調(diào)規(guī)劃的目的;文獻(xiàn)[7]提出了一種用于多AUV路徑規(guī)劃的高效算法,根據(jù)各AUV的起點(diǎn)和終點(diǎn)位置以及剩余能源的多少來確定一個(gè)橢圓,落在橢圓以內(nèi)的路徑點(diǎn)將由該AUV負(fù)責(zé)探測(cè)。文獻(xiàn)[8]將自組織神經(jīng)網(wǎng)絡(luò)(SOM)應(yīng)用于移動(dòng)機(jī)器人系統(tǒng)的任務(wù)分配與路徑規(guī)劃中,提出的算法在保證多機(jī)器人系統(tǒng)以最少的總耗費(fèi)遍歷所有目標(biāo)的前提下,每個(gè)移動(dòng)機(jī)器人都能沿著最短路徑到達(dá)目標(biāo);在此基礎(chǔ)上,文獻(xiàn)[9]考慮了AUV的水下作業(yè)特點(diǎn),將SOM算法應(yīng)用到了水下多AUV多目標(biāo)探測(cè)問題中;文獻(xiàn)[10]在三維柵格地圖的基礎(chǔ)上,給出一種基于生物啟發(fā)模型的三維路徑規(guī)劃和安全避障算法;文獻(xiàn)[11]基于稀疏A*算法,提出了一種用于構(gòu)造搜索空間的隨機(jī)布點(diǎn)方法;文獻(xiàn)[12]利用遺傳算法求解路徑規(guī)劃問題,而且考慮了水下強(qiáng)洋流的作用與影響;文獻(xiàn)[13]對(duì)目前多AUV目標(biāo)探測(cè)與協(xié)同作業(yè)技術(shù)的研究現(xiàn)狀做了簡(jiǎn)單綜述,發(fā)現(xiàn)目前很少有文獻(xiàn)從多AUV的能量均衡方面進(jìn)行研究。我們前期提出了一種基于AUV協(xié)作的水下傳感器網(wǎng)絡(luò)定位技術(shù)[14],但是也沒有對(duì)AUV的巡航路徑規(guī)劃進(jìn)行深入優(yōu)化。
以上各種算法應(yīng)用了各種優(yōu)化方法和搜索算法,為水下多AUV協(xié)同目標(biāo)探測(cè)問題提供了一些解決辦法,但是都沒有綜合考慮到AUV集群內(nèi)的能量約束與能耗均衡問題。有鑒于此,本文提出了一種考慮多AUV能量約束和能耗均衡的水下多目標(biāo)探測(cè)路徑規(guī)劃機(jī)制,并設(shè)計(jì)了一種特殊約束的遺傳算法進(jìn)行優(yōu)化求解。
圖1 水下多目標(biāo)探測(cè)示意
圖2 多AUV與多目標(biāo)節(jié)點(diǎn)隨機(jī)部署示意
如圖1所示,假設(shè)水下立方體區(qū)域內(nèi)包含個(gè)移動(dòng)AUV:和個(gè)靜止目標(biāo)節(jié)點(diǎn):{T1,T2,…,TNtarget},水下目標(biāo)節(jié)點(diǎn)通過在水底錨定的方式固定,因此其三維坐標(biāo)為確定值。由于AUV具有較大范圍的運(yùn)動(dòng)能力,同時(shí)單臺(tái)AUV的成本較高,難以大規(guī)模地使用,可假設(shè)水下AUV和目標(biāo)數(shù)滿足如下條件:。如果,那么問題會(huì)更加簡(jiǎn)單,每個(gè)AUV可以按最短路徑直接到達(dá)離它最近的目標(biāo)節(jié)點(diǎn)即可。如圖2所示,10個(gè)AUV隨機(jī)地部署在長寬高為100×100×100的三維水下空間內(nèi)。每個(gè)AUV通過巡航方式逐個(gè)訪問目標(biāo)節(jié)點(diǎn)以完成整個(gè)目標(biāo)節(jié)點(diǎn)群的探測(cè)任務(wù),AUV到達(dá)目標(biāo)節(jié)點(diǎn)后停航一段時(shí)間進(jìn)行目標(biāo)探測(cè)與數(shù)據(jù)采集,然后再往下一個(gè)目標(biāo)節(jié)點(diǎn)行駛。
(1)
(2)
假設(shè)水下空間內(nèi)每個(gè)目標(biāo)節(jié)點(diǎn)都被唯一的AUV節(jié)點(diǎn)所探測(cè),所以滿足式(3):
(3)
本文假設(shè)每個(gè)AUV以相同的初始位置出發(fā),向水下三維區(qū)間內(nèi)的其他目標(biāo)節(jié)點(diǎn)移動(dòng),最終回到初始位置。每個(gè)AUV都按照旅行商問題TSP(Traveling Salesman Problem)求解得到的路徑進(jìn)行巡航探測(cè),因此可以求得最短路徑。為了簡(jiǎn)單起見,假設(shè)AUV自主移動(dòng)所消耗的能量與所移動(dòng)的歐氏距離度量相對(duì)應(yīng),所有AUV的總能耗如式(4)所示:
i=
(4)
(5)
該問題的優(yōu)化目標(biāo)是最小化多AUV集群巡航耗費(fèi)的總能量,如式(6)所示:
mini
(6)
i (7) (8) 通過上述分析,可以發(fā)現(xiàn)上述問題其實(shí)就是帶多約束條件的改進(jìn)多旅行商MTSP(Multiple Traveling Salesman Problem)問題,由于標(biāo)準(zhǔn)MTSP問題具有NP-Complete計(jì)算難度,本文所提出的問題求解也具有NP-Complete難度。目前大多數(shù)研究都集中在啟發(fā)式求解方法,本文采用一種特殊設(shè)計(jì)的遺傳算法GA(Genetic Algorithm)進(jìn)行多目標(biāo)多AUV探測(cè)問題的求解。在一般的水下多目標(biāo)探測(cè)作業(yè)過程中多個(gè)AUV往往是同類型甚至是同型號(hào)的,因此本文假設(shè)多AUV具有相同的初始能量及能耗模型。為了使多個(gè)AUV承擔(dān)目標(biāo)探測(cè)的任務(wù)量盡量一致,巡航過程消耗能量盡量平等,因此本文提出了多AUV均衡探測(cè)路徑規(guī)劃算法,能量均衡度量采用均方根表示,如式(9)所示: (9) 因此,本文提出的多AUV均衡探測(cè)路徑規(guī)劃算法,通過遺傳算法求解過程中適應(yīng)度函數(shù)和終止條件的設(shè)置,兼顧考慮能量?jī)?yōu)化和能耗均衡兩個(gè)方面,以避免巡航過程中某些AUV因?yàn)槟芰肯倪^多而失效,影響整體多AUV集群的作業(yè)效能。 遺傳算法是通過模擬達(dá)爾文自然進(jìn)化過程的搜尋最優(yōu)解計(jì)算方法[15],由于采用了啟發(fā)式搜索策略,在處理帶約束的復(fù)雜組合優(yōu)化問題方面表現(xiàn)出了良好的性能。本文采用遺傳算法求解多AUV多目標(biāo)協(xié)同探測(cè)問題,通過設(shè)計(jì)考慮AUV巡航路徑長度的適應(yīng)度函數(shù)與多AUV間能耗均衡的終止條件,使得多個(gè)AUV較為均衡地承擔(dān)多目標(biāo)探測(cè)任務(wù)。具體求解過程由以下幾個(gè)步驟組成: ①初始化產(chǎn)生初始種群,根據(jù)MTSP問題對(duì)解實(shí)施編碼操作。在多AUV多目標(biāo)MTSP問題[16]中,采用基因編碼表示遍歷的目標(biāo)點(diǎn)順序及對(duì)應(yīng)的AUV編號(hào),以染色體表示AUV停留狀態(tài)指示變量。 ②依據(jù)目標(biāo)函數(shù),計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值。在多AUV多目標(biāo)MTSP問題中,適應(yīng)度函數(shù)采用了路徑長度i和巡航目標(biāo)數(shù)Ni乘積的倒數(shù),如式(10)所示,其中路徑長度采用三維空間內(nèi)多個(gè)目標(biāo)點(diǎn)間的歐氏距離和來表示。AUV巡航的總路徑越短,AUV巡航過的目標(biāo)數(shù)越少,適應(yīng)度值越大。 (10) ③根據(jù)適應(yīng)度值和AUV巡航目標(biāo)數(shù),判斷是否滿足終止條件,如式(11)所示,當(dāng)單個(gè)AUV巡航目標(biāo)數(shù)達(dá)到時(shí)?Ntarget/Nauv」則終止該AUV的路徑計(jì)算過程;當(dāng)所有AUV計(jì)算完畢后,即可獲得適應(yīng)度值最大的染色體。除此之外,程序中還設(shè)置了最大迭代次數(shù),如果超過最大迭代次數(shù)則自動(dòng)終止遺傳算法。 (11) ④依據(jù)概率選遺傳算子,進(jìn)行交叉和變異操作,產(chǎn)生新的解群,轉(zhuǎn)到第②步。對(duì)于交叉操作,隨機(jī)選擇兩個(gè)個(gè)體,在對(duì)應(yīng)位置交換若干個(gè)基因片段,防止進(jìn)入局部收斂。對(duì)于變異操作,隨機(jī)選取個(gè)體,同時(shí)隨機(jī)選取個(gè)體的兩個(gè)基因進(jìn)行交換以實(shí)現(xiàn)變異操作。 綜上所述,本文提出的遺傳算法迭代求解MTSP問題的具體流程如圖3所示。 圖3 遺傳算法迭代求解方法 (12) 根據(jù)傳統(tǒng)的AUV運(yùn)動(dòng)學(xué)模型[17],可以通過歐拉角φ,θ,ψ變換矩陣T(φ,θ,ψ)轉(zhuǎn)換為本地坐標(biāo)系的俯仰角、滾轉(zhuǎn)角、偏航角(u,v,w),如式(13)和(14)所示。 圖4 AUV運(yùn)動(dòng)坐標(biāo)模型 (13) T-1(φ,θ,ψ)= (14) 實(shí)際AUV運(yùn)動(dòng)控制模型中,一般都以本地坐標(biāo)系的俯仰角、滾轉(zhuǎn)角、偏航角為基本變量研究AUV的運(yùn)動(dòng)速度與路徑。雖然可以通過式(15)轉(zhuǎn)換到三維全局坐標(biāo)系的速度和路徑,但是歐拉變換計(jì)算量較大,因此本文直接以三維全局坐標(biāo)系的AUV位置與軌跡為研究對(duì)象,不考慮AUV因?yàn)檗D(zhuǎn)向、橫滾、俯仰等姿態(tài)調(diào)整而額外耗費(fèi)的能量,而簡(jiǎn)化為AUV消耗能量只與其巡航路徑長度成正比。 (15) 本文采用 MATLAB R2014a仿真平臺(tái)對(duì)所提出的機(jī)制進(jìn)行驗(yàn)證。仿真環(huán)境的主要參數(shù)為:Ntarget個(gè)目標(biāo)節(jié)點(diǎn)和NAUV個(gè)AUV隨機(jī)分布在區(qū)域半徑為10×10×10的三維水下區(qū)域內(nèi),仿真采用的AUV能量模型簡(jiǎn)化為距離模型,AUV消耗能量與其所巡航的距離成正比,為了簡(jiǎn)單起見本文做了歸一化處理,即每個(gè)AUV的能量初始值都定義為1 000單位(Unit),巡航1單位的路徑所需消耗的能量為1單位(Unit)。在本文仿真中,AUV數(shù)量固定為NAUV=5,改變目標(biāo)節(jié)點(diǎn)的數(shù)量Ntarget=10~50,步進(jìn)值為5。通常情況下,比較大的種群規(guī)模并不能優(yōu)化遺傳算法的結(jié)果,因此本文仿真中GA算法的種群數(shù)設(shè)置為較小值80,最大迭代次數(shù)設(shè)置為5000次,變異率為5%。數(shù)據(jù)結(jié)果采用多次仿真取均值的方式獲取,本文仿真中對(duì)單AUV(TSP)探測(cè)路徑規(guī)劃算法、多AUV(MTSP Algorithm)探測(cè)算法、多AUV均衡探測(cè)路徑規(guī)劃算法(MTSP Balanced Algorithm)進(jìn)行了總能量耗費(fèi)、能耗均衡性、巡航速度和巡航生命周期等指標(biāo)的比較。 圖5所示為50個(gè)目標(biāo)節(jié)點(diǎn)時(shí),單AUV(TSP)多目標(biāo)探測(cè)移動(dòng)軌跡及迭代次數(shù)。單AUV(TSP)多目標(biāo)探測(cè)由于約束條件少,因此獲取最優(yōu)解的概率較大。圖6所示為5個(gè)AUV和20個(gè)目標(biāo)場(chǎng)景下多AUV(MTSP)探測(cè)路徑規(guī)劃算法和多AUV均衡探測(cè)路徑規(guī)劃算法的不同目標(biāo)分配與移動(dòng)軌跡情況,圖7所示為5個(gè)AUV和40個(gè)目標(biāo)場(chǎng)景下多AUV(MTSP)探測(cè)路徑規(guī)劃算法和多AUV均衡探測(cè)路徑規(guī)劃算法的不同目標(biāo)分配與移動(dòng)軌跡情況,圖6(b)和圖7(b)相比較于圖6(a)和圖7(a),多個(gè)AUV所探測(cè)的目標(biāo)數(shù)明顯趨于一致。從圖6和圖7可以明顯發(fā)現(xiàn),多AUV均衡探測(cè)路徑規(guī)劃算法相比多AUV(MTSP)探測(cè)路徑規(guī)劃算法,可以避免AUV巡航路線中訪問節(jié)點(diǎn)數(shù)量不均衡的情況,進(jìn)而可以提高多AUV間的能耗均衡性。 圖5 單AUV(TSP)多目標(biāo)探測(cè)移動(dòng)軌跡(Ntarget=50) 圖7 多AUV多目標(biāo)探測(cè)移動(dòng)軌跡(Nauv=5,Ntarget=40) 單AUV(TSP)探測(cè)路徑規(guī)劃算法、多AUV(MTSP)探測(cè)路徑規(guī)劃算法、多AUV均衡探測(cè)路徑規(guī)劃算法等3種算法所消耗的總能量(以巡航距離表示)如圖8所示。多AUV(MTSP)探測(cè)路徑規(guī)劃算法、多AUV均衡探測(cè)路徑規(guī)劃算法等兩種算法的能量消耗均衡、巡航速度和巡航生命周期對(duì)比分別如圖9~圖11所示。 圖8 3種算法能量總消耗對(duì)比 圖9 多AUV探測(cè)算法消耗能量均方根值對(duì)比 圖10 3種算法巡航速度對(duì)比 圖11 3種算法巡航生命周期對(duì)比 圖8表明,由于額外的約束條件造成求解空間的限制,采用遺傳算法進(jìn)行全局最優(yōu)解搜索時(shí),多AUV均衡探測(cè)路徑規(guī)劃算法最終獲取的只是次優(yōu)解,相比較于單AUV(TSP)探測(cè)路徑規(guī)劃算法,會(huì)消耗一部分額外的能量。但是水下多目標(biāo)探測(cè)任務(wù)中,僅靠單個(gè)AUV無法完成大范圍目標(biāo)群的巡航任務(wù),單AUV(TSP)探測(cè)路徑規(guī)劃算法無法保證滿足式(7)約束條件,因此必須采用多AUV集群協(xié)同作業(yè)的方式。 從圖9~圖11可以發(fā)現(xiàn),多AUV均衡探測(cè)路徑規(guī)劃算法相比單AUV(TSP)探測(cè)路徑規(guī)劃算法和多AUV(MTSP)探測(cè)路徑規(guī)劃算法犧牲了小部分能量最優(yōu)性(能量總消耗增加小于20%),但多AUV均衡探測(cè)路徑規(guī)劃算法可以提高多AUV協(xié)同作業(yè)的能耗均衡性,避免某些AUV耗能過多而提前失效。多AUV能耗均衡性采用多AUV消耗能量的均方根值RMS(如式(9)所示)來表示,由于假設(shè)AUV能耗與巡航路徑成正比,因此RMS計(jì)算公式中的能量消耗也可用巡航距離代替計(jì)算。 單AUV(TSP)探測(cè)路徑規(guī)劃算法、多AUV(MTSP)探測(cè)路徑規(guī)劃算法、多AUV均衡探測(cè)路徑規(guī)劃算法等3種算法所對(duì)應(yīng)的能耗均方根值對(duì)比如圖9所示。圖9表明,當(dāng)水下空間中存在5個(gè)AUV和20個(gè)目標(biāo)時(shí),采用多AUV(MTSP)探測(cè)路徑規(guī)劃算法和多AUV均衡探測(cè)路徑規(guī)劃算法所得的消耗能量均方根值分別為18.565 8和17.237 5,多AUV均衡探測(cè)路徑規(guī)劃算法的能耗均衡性有所提高。5個(gè) AUV和50個(gè)目標(biāo)時(shí),采用多AUV(MTSP)探測(cè)路徑規(guī)劃算法和多AUV均衡探測(cè)路徑規(guī)劃算法所消耗能量的均方根值分別為36.578 2和32.613 7,在目標(biāo)數(shù)較多時(shí)(Ntarget=50),雖然消耗的總能量并無增長(Total Distance=140),但是多AUV均衡探測(cè)路徑規(guī)劃算法的能耗均衡性明顯提高。 單AUV(TSP)探測(cè)路徑規(guī)劃算法、多AUV(MTSP)探測(cè)路徑規(guī)劃算法、多AUV均衡探測(cè)路徑規(guī)劃算法等3種算法所對(duì)應(yīng)的巡航速度對(duì)比如圖10所示。巡航速度定義為最后一個(gè)AUV完成所有目標(biāo)巡航所持續(xù)的時(shí)間,本文假設(shè)多AUV都按同樣的速度勻速運(yùn)動(dòng),因此巡航速度也可以用其最長巡航距離(Maximal Distance)來表示。圖10表明,5個(gè)AUV和50個(gè)目標(biāo)時(shí),多AUV均衡探測(cè)路徑規(guī)劃算法相比單AUV(TSP)探測(cè)路徑規(guī)劃算法和多AUV(MTSP)探測(cè)路徑規(guī)劃算法,巡航速度分別提高了200%和93%。 單AUV(TSP)探測(cè)路徑規(guī)劃算法、多AUV(MTSP)探測(cè)路徑規(guī)劃算法、多AUV均衡探測(cè)路徑規(guī)劃算法等3種算法所對(duì)應(yīng)的巡航生命周期對(duì)比如圖11所示。巡航生命周期定義為AUV集群能夠完成的所有目標(biāo)巡航的輪數(shù)(Round),如果有至少一個(gè)AUV因?yàn)槟芰亢馁M(fèi)而無法承擔(dān)水下多目標(biāo)巡航任務(wù)時(shí),即認(rèn)為已經(jīng)到了巡航生命周期。圖11表明,5個(gè)AUV和50個(gè)目標(biāo)時(shí),多AUV均衡探測(cè)路徑規(guī)劃算法相比單AUV(TSP)探測(cè)路徑規(guī)劃算法和多AUV(MTSP)探測(cè)路徑規(guī)劃算法,巡航生命周期提高了60%。 本文對(duì)三維水下空間內(nèi)多AUV多目標(biāo)優(yōu)化探測(cè)問題進(jìn)行了深入研究,提出了一種均衡多AUV能量消耗的多旅行商問題求解方法,并利用遺傳算法尋求優(yōu)化解。仿真結(jié)果表明本文提出的算法可以提高多個(gè)AUV之間的能耗均衡性,以及整體多目標(biāo)探測(cè)問題的巡航速度和巡航生命周期,避免了多AUV協(xié)同作業(yè)時(shí)某些AUV耗費(fèi)能量過多而提前失效的情況。后續(xù)工作將考慮水下存在障礙物時(shí)如何規(guī)劃路徑,使得AUV在目標(biāo)探測(cè)時(shí)也可以智能地避開障礙物。2.2 遺傳算法迭代求解
2.3 AUV運(yùn)動(dòng)模型分析
3 仿真結(jié)果
4 結(jié)語