基于D?S證據(jù)論的多AUV協(xié)同搜索決策

魏娜 劉明雍 程為彬

摘? 要： 針對多AUV在不確定環(huán)境中的協(xié)同搜索問題，考慮由于傳感器探測精度的不確定性對目標協(xié)同搜索的影響，提出一種基于Dempster?Shafer（D?S）證據(jù)理論的融合傳感器讀數(shù)的協(xié)同搜索目標方法。引入“競爭力”的概念，協(xié)調(diào)多AUV之間的搜索決策行為，建立了以目標確認收益，AUV協(xié)同收益為目標的多AUV協(xié)同搜索效用函數(shù)。通過多AUV之間的相互協(xié)作，最大程度地減少了搜索路徑的重復(fù)，為多AUV的協(xié)同搜索提供了合理的在線決策支持，提高了搜索效率。仿真結(jié)果顯示，所建模型考慮了環(huán)境的不確定性，提出的基于D?S證據(jù)理論的多AUV協(xié)同搜索方法，具有環(huán)境適應(yīng)性和搜索高效性。

關(guān)鍵詞： 水下自主航行器; 協(xié)同搜索; Dempster?Shafer證據(jù)理論; 探測模型; 信息融合; 仿真分析

中圖分類號： TN911.2?34; TP24; TJ67? ? ? ? ? ? ? ? 文獻標識碼： A? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）11?0015?05

Decision of multi?AUV cooperative search based on D?S evidence theory

WEI Na1， 2， LIU Mingyong1， CHENG Weibin3

（1. School of Marine Science and Technology， Northwestern Polytechnical University， Xian 710072， China;

2. Shaanxi Key Laboratory of Logging and Control Technology for Oil and Gas Well， Xian Shiyou University， Xian 710065， China;

3. MOE Key Laboratory of Oil & Gas Resources and Exploration Technology， Yangtze University， Wuhan 430100， China）

Abstract： In order to solve the problem of cooperative search of multiple autonomous underwater vehicles （AUVs） in uncertain environments， a cooperative target search method based on the Dempster?Shafer （D?S） evidence theory is proposed， in which the sensor readings are fused and the influence of sensor detection accuracy uncertainty on cooperative target search is considered. The concept of "competitiveness" is introduced into the method to coordinate the search decision behaviors among multiple AUVs. A cooperative search utility function of multi?AUVs is established， which takes the confirming revenue and AUVs′ cooperative revenue as a goal. With the cooperation among multiple AUVs， the duplication of search paths is reduced to the full extent， and reasonable online decision support is provided for a cooperative search of multiple AUVs， and the search efficiency is improved. The simulation results show that the built model considers the uncertainty of the environment， and the proposed multi?AUVs cooperative search method based on D?S evidence theory has strong environmental adaptability and high search efficiency.

Keywords： autonomous underwater vehicle; cooperative search; D?S evidence theory; exploration model; information fusion; simulation analysis

0? 引? 言

近年來，水下作戰(zhàn)領(lǐng)域發(fā)生了重大的變化，作戰(zhàn)形式向無人化和多機化轉(zhuǎn)變。與單個自治水下機器人（AUV）所能提供的能力相比，多個AUV組成的編隊中，每個AUV都可以根據(jù)各自的空間占位以及作戰(zhàn)資源，在統(tǒng)一的作戰(zhàn)目的指導(dǎo)下，通過各AUV之間的信息互通，有效地完成更加復(fù)雜而艱巨的任務(wù)[1?3]。由于多AUV編隊可以有效避免資源浪費，提高了任務(wù)的執(zhí)行效率和成功率，具有單個AUV無法比擬的優(yōu)勢，因此，多AUV協(xié)同執(zhí)行任務(wù)已經(jīng)成為當今水下協(xié)同作戰(zhàn)的趨勢，也是當今水下機器人在水下作戰(zhàn)研究中的一個重要方向。本文就多AUV協(xié)同作戰(zhàn)中的協(xié)同搜索問題展開研究和討論。

由于水下機器人作業(yè)環(huán)境的特殊性，與陸地和天空機器人相比，水下機器人起步較晚，發(fā)展也較為緩慢[4]。因為其具有相關(guān)性，可以將陸地和天空機器人的目標搜索算法借鑒到水下目標搜索的研究中。針對無人機和水下自主航行器的協(xié)同搜索問題，文獻[5]提出了周期性協(xié)調(diào)、最短路徑協(xié)調(diào)和基于概率協(xié)調(diào)的三種協(xié)同搜索策略，并分析了在無人機速度和數(shù)據(jù)影響下三種協(xié)同搜索策略的任務(wù)執(zhí)行時間和使用范圍。文獻[6]利用基于響應(yīng)閾值模型的概率決策機制，考慮環(huán)境的不確定性，實現(xiàn)了快速靈活的無人機協(xié)同搜索和任務(wù)分配。文獻[7]采用基于概率的環(huán)境建模方法，研究了多無人機的協(xié)同搜索問題，并利用遺傳算法求解。遺傳算法雖然具有易與其他算法結(jié)合的優(yōu)點，但是運算效率不高。文獻[8]提出了一種基于量子行為粒子群優(yōu)化的混合差分進化算法，為海上無人機在不同威脅環(huán)境下進行目標搜索提供了安全可靠的路徑?；谛畔⑺氐南伻簝?yōu)化方法[9]對存儲空間的需求會隨著機器人數(shù)量的增多而大大增加，并不適用于數(shù)量規(guī)模較大的搜索任務(wù)。人工神經(jīng)網(wǎng)絡(luò)算法[10]以其智能性較高的特點得到越來越多的關(guān)注。文獻[11?12]將生物啟發(fā)神經(jīng)網(wǎng)絡(luò)算法引入水下環(huán)境中，提出了一種基于自組織神經(jīng)網(wǎng)絡(luò)的多AUV目標搜索算法。根據(jù)神經(jīng)網(wǎng)絡(luò)中神經(jīng)元的活性輸出值分布情況，確定AUV實際的搜索航行方向。

本文針對多AUV在不確定環(huán)境中的協(xié)同搜索問題，考慮了機載聲吶傳感器探測精度對AUV協(xié)同搜索策略選擇的影響，提出了一種基于D?S證據(jù)論的融合傳感器信息讀數(shù)的協(xié)同搜索目標決策方法，以解決多AUV協(xié)同搜索中融合傳感器探測讀數(shù)的環(huán)境信息更新問題。同時，針對多AUV之間的協(xié)同問題，本文引入了“競爭力”的概念，通過計算分析AUV之間的競爭力，避免AUV之間選擇相同的目標搜索路徑，增加AUV之間的協(xié)作性，提高編隊整體的目標搜索效率。

1? 協(xié)同搜索問題描述

1.1? AUV的簡化運動模型

將待搜索區(qū)域抽象成有限的柵格形式，并進行單位為1的柵格劃分。假設(shè)每個柵格最多只能有一個目標，記柵格存在目標的狀態(tài)為[ETx，y]，若柵格存在目標，則[ETx，y=1]，若柵格不存在威脅目標，則[ETx，y=0]。

假設(shè)AUV編隊由[m]艘同構(gòu)的AUV組成，采用分布式搜索方式，同時出發(fā)對搜索區(qū)域進行目標搜索。為了便于分析，假設(shè)AUV之間無通信約束，航行器和目標均不考慮形狀，視為質(zhì)點。AUV在進行目標搜索時，每行進一步都是從一個柵格的中心點前進到相鄰柵格的另一個中心點。建立簡化的AUV運動學方程為：

[xt+1=xt+v0Δtcosθ+Δθyt+1=yt+v0Δtsinθ+Δθ] （1）

式中：[xt，yt]表示[t]時刻AUV的位置坐標;[v0]表示[t]時刻AUV的速度;[Δt]為采樣時間;[θ]為AUV當前時刻的航向角;[Δθ]為下一個采樣時刻航向角的增量。由于AUV受自身機動性能的限制，因此，航向角增量需滿足[Δθ∈[-θa，θa]]的約束，其中，[θa]為航向角的最大增量。在本文中，假設(shè)每個仿真步長的[Δθ]為一固定常量，且與AUV的運動速度無關(guān)。

1.2? 多AUV之間的競爭力描述

AUV編隊在威脅區(qū)域進行搜索時，為了避免相近的兩個AUV選擇相同的搜索路徑和目標，每個AUV在進行策略選擇時，需要考慮其他AUV對其產(chǎn)生的影響。本文借用“人工勢場法”的思想，將除自身外的其他航行器都視為“虛擬障礙”，提出了“競爭力”的概念。當兩個執(zhí)行搜索任務(wù)的航行器靠近時，隨著兩者距離的減小，其競爭力隨之增大;反之距離增大，競爭力減小。通過計算航行器之間的“競爭力”，衡量航行器之間的協(xié)同情況，以達到減少搜索航跡重疊，提高AUV編隊協(xié)同搜索效率的目的。

本文采用指數(shù)函數(shù)形式來定量描述競爭力，則[AUVi]和[AUVj]之間的競爭力大小為：

[Fijx，y=λe-dij，? ? d0≤dij≤dmax] （2）

式中：[λ]為競爭力加權(quán)系數(shù);[dij=][xi-xj2+yi-yj2]，表示[AUVi]和[AUVj]之間的距離。從式（2）中可以看出，若距離[dij→0]時，對應(yīng)的競爭力[Fij]為無窮大。但實際中，為了避免兩個AUV相撞，可以設(shè)置一個最小安全距離[d0]，同時，為了保證[AUVj]在[AUVi]的掃描區(qū)域內(nèi)，還需要設(shè)置[AUVi]和[AUVj]之間的最大距離[dmax]為[AUVi]的最大探測半徑。

2? 基于D?S證據(jù)論的目標協(xié)同搜索

AUV在進行目標搜索時，需要根據(jù)自己傳感器接收到的信息讀數(shù)和其他AUV傳感器接收到的信息讀數(shù)進行環(huán)境信息庫的更新。而在實際的目標搜索過程中，傳感器探測讀數(shù)存在一定的誤差，需要考慮由于傳感器探測讀數(shù)不準確造成的不確定性影響，因此環(huán)境信息庫的更新至關(guān)重要。本文基于D?S理論的證據(jù)融合方法，將傳感器探測結(jié)果視為證據(jù)，使用證據(jù)推理技術(shù)融合傳感器信息，提取和共享知識，不斷更新環(huán)境信息庫信息，從而為AUV編隊進行協(xié)同搜索提供保障。

2.1? 傳感器探測模型

設(shè)變量[sx，y]為一傳感器探測二值函數(shù)，用來表示傳感器探測到目標與否的情況。[sx，y=1]表示傳感器探測到點[x，y]處有威脅目標;反之，[sx，y=0]表示傳感器沒有在點[x，y]處探測到目標。定義傳感器探測精度的概率表達式如下：

[Psx，y=1ETx，y=1=pc] （3）

[Psx，y=0ETx，y=1=1-pc] （4）

[Psx，y=1ETx，y=0=pf] （5）

[Psx，y=0ETx，y=0=1-pf] （6）

根據(jù)全概率公式，AUV在進行區(qū)域搜索時，第[i]個傳感器[t]時刻探測到點[x，y]處存在目標的概率為：

[ptix，y=stix，ypcpt-1ix，ypcpt-1ix，y+pf1-pt-1ix，y+1-stix，y1-pcpt-1ix，y1-pf1-pt-1ix，y+1-pcpt-1ix，y] （7）

2.2? 基于D?S證據(jù)論的環(huán)境信息庫的更新

待搜索區(qū)域環(huán)境模型中的每個柵格都有“沒有目標”和“被目標占據(jù)”兩個狀態(tài)，每個柵格都有一個屬性值代表該柵格的狀態(tài)。定義識別框架[Θ=E，O]，[E]表示柵格中無目標，[O]表示柵格中有目標。識別框架[Θ]的冪集為[2Θ]，且[2Θ=Φ，E，O，U]。[U]代表“未表達意見”，對信息既不是信任，也不是不信任，即不確定該柵格中目標的狀態(tài)是有還是沒有。[mx，y（A）]代表柵格[x，y]的狀態(tài)，柵格的狀態(tài)由[2Θ]中每個元素的基本分配概率做如下描述：

[mx，yΦ=0] （8）

[A?2Θmx，yA=mx，yE+mx，yO+mx，yU=1] （9）

當傳感器讀數(shù)顯示[t]時刻點[x，y]處探測到有目標時，此時傳感器的讀數(shù)可視為狀態(tài)[O]增加的證據(jù)。但由于傳感器讀數(shù)并不完全準確，所以提供的證據(jù)不能100%確定。根據(jù)D?S證據(jù)理論，任一未被分配給具體子集的“信任”被看成“未表達意見”，因此，傳感器的探測讀數(shù)不能給狀態(tài)[E]提供任何信息，剩下的信度只能分配給狀態(tài)[U]。因此，在傳感器探測到點[x，y]處有目標的情況下，來自傳感器的證據(jù)的mass為：

[msE=0] （10）

[msO=px，y] （11）

[ms（U）=1-ptx，y] （12）

基于傳感器信度的定義，應(yīng)用D?S證據(jù)組合規(guī)則，將傳感器讀數(shù)與環(huán)境信息庫的信息融合，可得點[x，y]處新的基本概率分配函數(shù)。[mx，y]為來自待更新的環(huán)境信息庫的mass，則合成后，點[x，y]的基本概率賦值為：

[mx，y⊕msE=? ? ? ? ?mx，yEmsE+mx，yEmsU+mx，yUmsE1-mx，yOmsE-mx，yEmsO]

（13）

[mx，y⊕msO=? ? ? ? ?mx，yOmsO+mx，yOmsU+mx，yUmsO1-mx，yOmsE-mx，yEmsO]

（14）

[mx，y⊕msU=mx，yUmsU1-mx，yEmsO-mx，yOmsE] （15）

其中：

[mx，yO=pfx，y] （16）

[mx，yU=-ptx，ylog2pt（x，y）-1-ptx，ylog21-ptx，y] （17）

至此，通過D?S證據(jù)理論將傳感器探測信息與原有環(huán)境信息進行融合，實現(xiàn)了待搜索區(qū)域環(huán)境信息庫的更新。

2.3? 多AUV的協(xié)同搜索效益函數(shù)

多AUV執(zhí)行協(xié)同搜索任務(wù)時，每個AUV需要有一個可以評估每條搜索路徑花費的函數(shù)，來選擇收益最大的路徑，完成對目標的有效搜索。

為了能成功完成搜索任務(wù)，AUV需要在執(zhí)行任務(wù)時使確認的目標數(shù)量最大化。設(shè)一個目標的價值為[ctarget]，此時在點[x，y]的預(yù)期目標確認收益為[C1x，y]，則有目標確認收益函數(shù)：

[C1x，y=pc-pfptx，y+pf?ctarget] （18）

同時，在搜索過程中還要考慮AUV之間的協(xié)同性，以提高搜索效率。為了與目標確認收益函數(shù)保持一致，這里將協(xié)同收益函數(shù)定義為競爭力的負數(shù)，則AUV的協(xié)同收益函數(shù)為：

[C2x，y=-i=1mFix，y] （19）

根據(jù)協(xié)同收益函數(shù)計算出來的收益值來調(diào)節(jié)個體AUV參與目標搜索的程度。當兩個AUV距離越近，競爭力越強，收益越低，則參與目標搜索的概率越小，反之參與搜索的概率越大。通過迭代搜索，實現(xiàn)多AUV更合理的目標分配。根據(jù)子目標收益對AUV預(yù)期收益所起作用的不同重要性，分別設(shè)置不同的權(quán)重[ωi（i=1，2）]且[i=12ωi=1]，從而將2個子函數(shù)線性組合成一個目標優(yōu)化函數(shù)來表達AUV的預(yù)期總收益。通過調(diào)整權(quán)重[ωi]的值可以動態(tài)調(diào)整子目標收益對AUV總體預(yù)期收益的影響，可得AUV的協(xié)同搜索效益函數(shù)為：

[C=ω1C1+ω2C2] （20）

3? 仿真結(jié)果及分析

仿真環(huán)境中任務(wù)區(qū)域為一個2 000×2 000的固定深度的水平面，一個柵格的長度為1。投放3艘AUV進行協(xié)同搜索，AUV之間為理想通信狀態(tài)，搜索區(qū)域內(nèi)有3個目標。對沒有協(xié)同作用下的多AUV協(xié)同搜索目標情況進行仿真，結(jié)果如圖1所示。

從圖1可以看出，在非協(xié)同搜索模式下，AUV編隊將全部目標找到，完成搜索任務(wù)，共花費時間398.4 s，運行3 984步。多AUV在執(zhí)行搜索任務(wù)過程中，多處搜索路徑有非常明顯的重疊情況，能源浪費嚴重。圖2為AUV之間工作在強協(xié)同的情況下?？梢钥闯觯珹UV很快覆蓋了遠處的目標，搜索路徑基本沒有重疊，搜索任務(wù)完成共花費時間104.9 s，運行1 049步。與多AUV工作在非協(xié)同的搜索情況下相比，強協(xié)同搜索方式下AUV編隊的目標搜索時間大大縮短，搜索效率得到了較大的提升。

為了進一步分析不同環(huán)境信息庫構(gòu)建更新方法對目標協(xié)同搜索能力的影響，本實驗對基于貝葉斯理論更新環(huán)境信息庫和基于D?S證據(jù)論更新環(huán)境信息庫的協(xié)同搜索情況進行了模擬仿真。不失一般性，仿真同時考慮了傳感器分別工作在低保真率和高保真率的情況。本次實驗任務(wù)區(qū)域有8個目標，投放了5艘AUV執(zhí)行搜索任務(wù)。圖3，圖4分別為聲吶傳感器工作在探測精度為低保真率和高保真率的兩種情況下，基于貝葉斯理論構(gòu)建更新環(huán)境信息庫和基于D?S證據(jù)論構(gòu)建更新環(huán)境信息庫的多AUV目標協(xié)同搜索仿真結(jié)果。

（聲吶傳感器的探測保真率為[pc=]0.95）

從仿真結(jié)果可以看出：在相同采樣時間段內(nèi)，當傳感器探測精度不高時，基于D?S證據(jù)理論更新環(huán)境信息庫的協(xié)同搜索方法在1 100時間步長時搜索到了8個目標，完成了搜索任務(wù);而基于貝葉斯理論更新環(huán)境信息庫的協(xié)同搜索方法在1 100時間步長時只搜索到了5個目標，還有3個目標未找到。仿真結(jié)果顯示，基于D?S證據(jù)理論更新環(huán)境信息庫的協(xié)同搜索算法比基于貝葉斯理論的協(xié)同搜索算法在傳感器探測精度不高時，能夠在較短時間內(nèi)發(fā)現(xiàn)更多數(shù)量的目標。而在傳感器探測精度較高的情況下，可以看到這兩種搜索方法在搜索區(qū)域內(nèi)發(fā)現(xiàn)8個目標，完成搜索任務(wù)，花費的時間步長差別不大，搜索性能上基本相當。造成上述結(jié)果的主要原因在于，這兩種方法對關(guān)于“未知狀態(tài)”的初始賦值不同。D?S理論不要求必須對“無知的假設(shè)”和“反駁假設(shè)”賦予信任值。在該理論中，任一違背分配給具體子集的“信任”都被視為“未表達意見”，而不是像貝葉斯理論表示的那樣把這部分分配給“不信任”。由于AUV編隊在進行水下協(xié)同搜索時，水下環(huán)境復(fù)雜，機載傳感器不一定能保證有較高的探測精度，因此，基于D?S證據(jù)理論的協(xié)同搜索方法就顯得更加適用。同時從仿真結(jié)果也可以看出，由于傳感器探測精度的影響，傳感器在探測精度較低的情況下搜索發(fā)現(xiàn)目標所需要的時間也會增加。

4? 結(jié)? 語

本文針對不確定環(huán)境下多AUV協(xié)同搜索目標的問題，提出了基于D?S證據(jù)論的融合傳感器讀數(shù)信息的協(xié)同搜索決策方法。該方法充分發(fā)揮了D?S證據(jù)理論能清楚表示“未表達意見”的優(yōu)勢，將傳感器探測到的信息讀數(shù)作為證據(jù)，利用D?S證據(jù)組合規(guī)則融合傳感器讀數(shù)信息，更新環(huán)境信息庫，為協(xié)同搜索的策略選擇提供指導(dǎo)。AUV之間“競爭力”的引入，避免了搜索路徑的重復(fù)，縮短了AUV搜索目標的時間，提高了AUV編隊的任務(wù)執(zhí)行效率。仿真結(jié)果表明，在傳感器探測讀數(shù)精度不高時，基于D?S證據(jù)論的協(xié)同搜索方法可以發(fā)現(xiàn)更多的威脅目標，驗證了所提方法的正確性和有效性，為水下協(xié)同作戰(zhàn)中的目標搜索問題提供了合理的研究思路，具有一定的現(xiàn)實意義。

參考文獻

[1] WEI Na， LIU Mingyong， CHENG Weibin. Decision?making of underwater cooperative confrontation based on MODPSO [J]. Sensors， 2019， 19（9）： 2211.

[2] ALLOTTA B， CAITI A， COSTANZI R， et al. Cooperative navigation of AUVs via acoustic communication networking： field experience with the Typhoon vehicles [J]. Autonomous robots， 2016， 40（7）： 1229?1244.

[3] ZHU D， HUANG H， YANG S X. Dynamic task assignment and path planning of multi?AUV system based on an improved self?organizing map and velocity synthesis method in three?dimensional underwater workspace [J]. IEEE transactions on cybernetics， 2013， 43（2）： 504?514.

[4] ZENG Z， LIAN L， SAMMUT K， et al. A survey on path planning for persistent autonomy of autonomous underwater vehicles [J]. Ocean engineering， 2015， 110： 303?313.

[5] SUJIT P B， SARIPALLI S. An empirical evaluation of co?ordination strategies for an AUV and UAV [J]. Journal of intelligent & robotic systems， 2013， 70（1/4）： 373?384.

[6] KIM M H， BAIK H， LEE S. Response threshold model based UAV search planning and task allocation [J]. Journal of intelligent & robotic systems， 2014， 75（3/4）： 625?640.

[7] SHORAKAEI H， VAHDANI M， IMANI B， et al. Optimal cooperative path planning of unmanned aerial vehicles by a parallel genetic algorithm [J]. Robotica， 2016， 34（4）： 823?836.

[8] FU Yangguang， DING Mingyue， ZHOU Chengping， et al. Route planning for unmanned aerial vehicle （UAV） on the sea using hybrid differential evolution and quantum?behaved particle swarm optimization [J]. IEEE transactions on systems， man， and cybernetics： systems， 2013， 43（6）： 1451?1465.

[9] LEBEDEV D V， STEIL J J， RITTER H J. The dynamic wave expansion neural network model for robot motion planning in time?varying environments [J]. Neural networks， 2005， 18（3）： 267?285.

[10] PASHKEVICH A， KAZHEUNIKAU M， RUANO A E. Neural network approach to collision free path?planning for robotic manipulators [J]. International journal of systems science， 2006， 37（8）： 555?564.

[11] 朱大奇，劉雨，孫兵，等.自治水下機器人的自主啟發(fā)式生物啟發(fā)神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃算法[J].控制理論與應(yīng)用，2019，36（2）：183?191.

[12] 朱大奇，曹翔.多個水下機器人動態(tài)任務(wù)分配和路徑規(guī)劃的信度自組織算法[J].控制理論與應(yīng)用，2015，32（6）：762?769.