一種基于目標聲信息改進概率圖的多UUV 協同搜索方法

楊惠珍 ,周卓彧 ,李 源

(1.西北工業大學 航海學院,陜西 西安,710072;2.水下信息與控制全國重點實驗室,陜西 西安,710072)

0 引言

多無人水下航行器(unmanned undersea vehicle,UUV)目標搜索是指多艘裝配有聲吶傳感器的UUV 進入已知范圍的海域環境中對若干個未知目標進行搜索,要求UUV 合理分配搜索資源,在線決策出最優的搜索軌跡,盡快搜索到全部目標。多UUV 目標搜索能夠擴展單體UUV 的感知范圍,通過共享感知信息并利用系統內UUV 資源的冗余性,提高搜索效率,增強系統魯棒性,在水下資源勘探和目標偵查等領域有著廣闊的應用前景,是多UUV 系統的重點研究內容之一。

多UUV 協同目標搜索是一個多目標多約束的優化問題,其研究內容主要包括環境建模和搜索算法設計兩方面。

目前,主流搜索環境建模方法基于離散化搜索區域,使用占用圖[1]、不確定圖[2]及概率圖[3]等建立對動態環境的信息描述。文獻[4]使用占用圖來描述目標的分布情況,根據先驗信息對未來時刻目標的位置進行預測,設計占用圖更新規則。文獻[5]為離散地圖中每個柵格賦予一個不確定度值,以描述無人機對該柵格中目標分布的不確定性。文獻[6]使用搜索環境中不同區域的權重信息設計動態不確定圖,提高了多UUV 對島礁重點區域的目標搜索效率。文獻[7]使用六邊形網格離散任務區域并建立概率圖,使無人機以相同的代價向不同的相鄰單元移動,并基于概率圖模型定義了搜索信息增益,有效提高了協同搜索的資源利用率。文獻[8]使用目標初始概率分布和目標轉移概率對目標位置進行預測,使UUV 編隊以較高的成功概率和較短的平均搜索時間實現對馬爾可夫運動目標的應召搜索。總得來說,上述環境建模方法將無人機和UUV 等智能體對環境和目標的認知映射到二維離散地圖中,隨著搜索過程中的感知信息不斷更新,如何提高離散地圖的信息量和信息可靠性是提高目標搜索效率的重要手段。

在搜索算法設計方面,群智能優化算法被廣泛應用于搜索問題[9]。文獻[10]提出反信息素改進蟻群優化(ant colony optimization,ACO)算法,并結合參數調節機制提高未知環境目標搜索效率。文獻[11]為了解決UUV 在局部極值點附近無法前進的問題,提出了基于ACO 和人工勢場法的目標搜索算法,具有較好的快速性。文獻[12]提出將機器人系統的協作規則應用到勢場函數中,并作為粒子群優化(particle swarm optimization,PSO)的適應度函數應用于未知環境中機器人協作搜索。文獻[13]為了克服機器人工作空間的局限性,提出一種基于PSO 的分布式算法,在全局機制下實現整體最優。文獻[14]將PSO 結合差分進化(differential evolution,DE)算法提出PSO-DE 算法解決比例積分微分神經網絡中權重參數易陷入局部最優的問題。文獻[15]結合模擬退火法實現三維環境中最優航跡點的選取。文獻[16]結合遺傳算法(genetic algorithm,GA)提出PSO-GA 算法實現無人機部署位置的優化。文獻[17]針對馬爾可夫運動目標的搜索問題,提出一種基于突變遺傳算子和突變交叉算子的改進GA 算法,提高了算法的穩定性和UUV 的搜索效率。文獻[18]提出一種自適應突變GA 算法,通過最大化探測概率實現UUV 對移動目標的搜索。文獻[19]針對城市環境下無人機編隊的搜索和跟蹤問題,提出改進灰狼算法規劃航跡,平衡搜索效率和跟蹤的準度。文獻[20]提出改進的麻雀算法進行模型求解,提升了多機協同目標搜索的準確率。智能優化算法在求解過程中陷入局部最優解,導致UUV 等智能體聚集在某一區域搜索,降低協同目標搜索準確率,這一現象時有發生,因此,研究和尋找合適的智能優化算法,減少局部最優是研究目標搜索問題的主要方向之一。

綜上所述,現有的目標搜索方法在無人機、UUV 等智能體上的應用具有通用性,在傳感器全向視域(field of view,FOV)、目標或環境信息部分已知的條件下取得了較好的搜索效果。然而在未知水下環境中,還需要考慮以下限制條件: UUV 探測聲吶不是FOV,而是有限視域(扇面);目標先驗信息少,甚至沒有,且水下目標感知有限,獲取的目標信息亦有限。因此,針對水下未知環境中多UUV 目標搜索問題,有必要充分利用目標感知信息,提高離散地圖的信息量和可靠性,同時尋找智能優化算法,減少局部最優現象。

針對此,文中提出了一種新的含目標聲學探測信息的概率圖模型及其更新方法,有利于UUV 充分利用聲吶探測的目標信息規劃搜索路徑,解決因為感知信息利用不足導致的目標遺漏問題;同時,文中將線性種群規模減小算法(linear population size reduction,LPSR)與基于成功歷史的自適應微分進化(success-history based adaptive differential evolution,SHADE)和廣泛學習機制(comprehensive learning mechanism,CLM)相結合 的LPSRSHADE-CLM 算法的突變策略引入PSO 算法,提出了一種具有學習機制和自適應參數調節機制的PSO-LPSR-SHADE-CLM 優化算法。通過生成自適應調整參數的突變粒子,增加粒子多樣性,在多UUV 目標搜索應用中,減少了局部最優,提高搜索效率。

1 多UUV 協同目標搜索問題建模

假設在未知無障礙的有界區域中,處于固定深度的N艘同構UUV 對處于同一水平面的若干個非合作目標執行搜索任務。每艘UUV 安裝有主動聲吶感知目標信息,根據感知的目標信息在線規劃搜索路徑,在規定的任務時間內以最優效能搜索到更多的目標。該問題可以描述成一個目標優化問題,涉及的關鍵要素包括: 搜索區域、UUV運動學及UUV 探測能力等。

首先使用柵格化模型描述搜索區域的環境模型。將任務區域 ?均勻劃分為rrows×ccols柵格,每個柵格使用Mmn唯一表示,則離散區域的集合表示為

UUV 水平面運動如圖1 所示。t時刻第i個UUVi的質心在水平面中的坐標為μi(t)=[xi(t),yi(t)]T,UUVi的航向角為ψi(t),航向角增量為ri(t),航行速度為v,通常v的大小不變,僅改變方向。

圖1 UUV 水平面運動坐標系Fig.1 Motion coordinate system of UUV

離散狀態空間中UUV 運動學模型為

式中,ri(t)為t時刻 UUVi的航向角增量,是 UUVi的控制輸入,須滿足UUV 的航向角變化有限的運動學特性約束,即ri(t)∈[-rmax,rmax]。

UUV 聲學探測通常包括主動探測和被動探測,其探測性能主要由探測扇面 (R,ε)來描述,其中R為聲吶作用距離,ε為扇面角。假設目標的坐標為(xT,yT),目標與 UUVi之間的距離為Rv,角度為α,則目標落在UUV 探測扇面內的數學描述為

因此,UUV 目標搜索問題可以用集合{UUVs,Map,J,U}表示。其中: UUVs為UUV 群體集合;Map為搜索環境;J為系統的效能函數;U為系統控制輸入量集合。目標搜索問題可以描述成如下優化問題

即在UUV 運動約束條件下,尋找使性能指標最優的UUV 航向角控制輸入序列。

2 基于目標聲場信息的概率圖模型

概率圖是UUV 自身所維護的一種內部數據結構,反映了UUV 對當前不確定環境的認知程度。傳統概率圖(traditional probability map,TPM)由目標存在概率和環境確定度組成[3],即

式中:pmn(t)是在t時刻柵格Mmn對應的目標存在概率,描述了柵格Mmn中存在目標的可能性;qmn(t)是t時刻柵格Mmn的環境確定度,描述了UUV 對柵格Mmn處環境信息的掌握程度。

由文獻[3]中對TPM 的定義可知,pmn(t)∈[0,1],pmn(t)=0表示UUV 認為在t時刻柵格Mmn不會出現目標,pmn(t)=1表示該時刻UUV 認為柵格Mmn中存在目標。qmn(t)∈[0,1],qmn(t)=0表示UUV 對柵格Mmn處信息一無所知,qmn(t)=1表示該時刻UUV 完全掌握了柵格Mmn的信息。

文中在TPM 的基礎上引入占用信息和目標聲信息,提出改進概率圖模型(improved probability map,IPM),即

式中:omn(t)是UUV 的占用信息,用來描述柵格Mmn被UUV 的占用情況;Wmn(t)是柵格Mmn處的目標聲信息,用來反映UUV-目標幾何距離的遠近。

借鑒文獻[1]中關于占用圖的定義,使用UUV當前的視域范圍對占用信息omn(t)進行定義。假設UUV 視域范圍內柵格均視為完全占用,則omn(t)∈{0,1},omn(t)=0 表示柵格Mmn不屬于任一UUV 的FOV 范圍,omn(t)=1表示柵格Mmn正在被FOV 占據。為了利用有限的聲吶感知信息,使用主動聲吶方程結合聲波的傳播特性對目標聲信息Wmn(t)進行定義。為了消除量綱的影響,解決IPM 各元素之間的可比性問題,對Wmn(t)進行歸一化處理,處理后得Wmn(t)∈[0,1],Wmn(t)=0表示聲吶未接收到目標回波信息,或傳播損失過大導致回波強度低于聲吶的檢測閾值,Wmn(t)=1表示聲吶接收到強度大且明確的目標回波信息。

基于上述定義,為IPM 中各元素建立初始化及更新規則。

2.1 目標存在概率

UUVs對任務區域的目標信息事先完全未知時,柵格Mmn處存在目標與不存在目標的可能性相等,此時初始化pmn(0)為

UUVs在搜索過程共享和維護pmn(t),反映了UUV 群體對目標分布信息的認知情況。由于pmn(t)跟隨聲吶探測信息進行動態更新,考慮UUVs聲吶探測的不確定性建立更新規則。

首先,使用檢測概率PD和虛警概率PF描述聲吶性能,有

式中:pmn(t)表示t時刻柵格Mmn處目標存在的先驗概率;Xmn表示事件“柵格Mmn中存在目標”;PD表示事件“柵格Mmn中存在目標的條件下,U UVs的聲吶檢測到Mmn中存在目標”的發生概率,即聲吶的檢測概率;Zmn表示事件“聲吶檢測到柵格Mmn中存在目標”;PF表示事件“柵格Mmn中不存在目標,但UUVs的傳感器卻檢測到Mmn中存在目標”的發生概率,即聲吶的虛警概率。

目標存在概率的更新機理[21]為: 已知t時刻柵格Mmn處目標存在概率pmn(t),由t+1時刻聲吶探測結果Zmn確定后驗概率pmn(t+1)。令t時刻的UUVs傳感器視場范圍內柵格的動態集合為FOV′,YFOV′表示事件“ UUVs在 FOV′內發現目標”,由Bayes 理論可得更新公式(11)和(12),同時綜合式(8)～式(12)和全概率公式,IPM 的目標存在概率更新公式如式(13)所示

2.2 目標聲場信息

由于UUV 系統對目標分布情況預先未知,初始化目標聲場信息

在聲吶探測過程中,聲波的傳播損失TL作為度量聲源到接收機之間聲強衰減大小的一個物理量,其大小反映了UUV-目標幾何距離的遠近。檢測閾值DT作為可接受傳播損失的指標,其大小反映了聲吶設備的信號處理能力。通過設置合理的DT并與TL比較,UUV 能夠在噪聲環境下對當前UUV-目標相對方向和幾何距離的遠近進行合理判斷。因此,使用檢測閾值DT和傳播損失TL對Wmn(t)進行更新。

檢測閾值DT根據主動聲吶方程(15)進行設定且各UUV 設定相同

式中:S L為目標聲源級;NL為環境噪聲級;DI為發射指向性系數;TS為目標強度;TL為單程傳播損失,隨UUV-目標的距離變化而變化。

對于主動聲吶,聲波的雙程傳播損失為2TL,2TL通過測量聲吶視域范圍內不同方向的回波信號聲強度的衰減進行確定。為更好地區分不同方向的回波信息,令 FOV′內同一回波方向上的柵格具有相同的雙程傳播損失,則t時刻 FOV′內各柵格包含的雙程傳播損失信息記為2TLmn(t)。為了消除量綱的影響,對 2TLmn(t)進行歸一化處理,即

當 2TLmn(t)過大時,表示該方向不存在目標或UUV-目標距離過遠;2TLmn(t)足夠小時表示聲吶接收到強度大且明確的目標回波信息。文中以DT/2、DT作為判斷的分段點,使用歸一化后的雙程傳播損失定義目標聲場信息更新公式為

2.3 UUV 占用信息

由于任務區域中占用信息僅和當前UUV 聲吶視域內的柵格集合有直接關系,因此占用信息的初始化和更新均與其余時刻無關。令 FOVt表示t時刻UUV 的視野范圍,占用信息的初始化和更新公式相同,即

2.4 環境確定度

假設UUV 能完全掌握其視域范圍內柵格的信息,則UUV 系統初始視域范圍內的柵格環境確定度最大,其余柵格信息視為完全未知,環境確定度最小。則初始化環境確定度為

在搜索過程中,UUV 系統完全掌握的環境信息跟隨omn(t) 改變,對omn(t)=1的柵格更新確定度為1,對于未被FOV 所占據的柵格,UUV 丟失了是否存在目標的信息,但考慮到目標以連續軌跡移動,柵格內的聲信息仍具有一定可靠性,為減少目標遺漏和誤判現象,將目標聲信息Wmn(t)引入qmn(t)的更新公式中,越靠近目標的區域,單位時間內確定度下降越慢,從而利于引導UUV 對可能存在目標的區域進行重訪[22]。令動態更新因子λ∈[-1,0],定義更新公式為

3 協同目標搜索算法

3.1 效能函數

為使多UUV 系統在規定任務時間內以最優效能搜索到更多的目標,需要考慮以下效能指標:

1) 優先搜索目標存在概率較高的區域;

2) 優先搜索環境確定度較低的區域(包括未被探測和因為長時間未被探測而需要重訪的區域);

3) 優先搜索聲場強度較大的區域。

將這3 個指標加權求和,得

式中: ω1,ω2,ω3分別為3 種指標所占的權重,滿足約束ω1+ω2+ω3=1;JF為目標發現收益;JE為環境搜索收益;JL為聲場信息收益。

式(21)中的第1 項將UUV 在執行任務過程中發現目標的可能性累加,引導UUV 向概率高的柵格航行;第2 項使用柵格的動態集合和動態更新的確定度,保證對確定度較低柵格的回訪率;第3 項中,使用聲場信息收益表示對于聲場強大的區域應當優先搜索。因此,該目標函數綜合了協同搜索效率和聲吶探測結果,通過優化可以獲得最佳的航向角輸入集合。

3.2 基于PSO-LPSR-SHADE-CLM 的搜索算法

文中將LPSR-SHADE-CLM 算法的突變策略[23]引入PSO 算法,通過生成自適應調整參數的突變粒子,增加粒子多樣性,減少局部最優。參數的自適應控制可以從歷史決策中學習成功經驗,完成最優決策的選取。

文獻[23]中突變粒子v的生成公式為

式中:Fw、F為突變因子;pg為群體極值;μpb,g是當前種群中最佳適應度位置;μpr1,g、μpr2,g是從當前種群中隨機選擇的位置。

LPSR-SHADE-CLM 算法中突變因子F、Fw的自適應控制的步驟如下[23]。

1) 初始化當前迭代次數g、當前進化數量n;設置算法相關參數: 最大迭代次數Gmax、最大進化數量nmax、正弦率f1、f2、成功率s1=0.5、s2=0.5。

2) 設置生成突變因子F的函數候選池f1、f2,其中f1為自適應正弦遞減函數,f2為自適應正弦遞增函數,記為

3) 根據當前進化次數n和nmax,在函數候選池中進行選擇。若n≤0.2×nmax,使用隨機數在函數候選池中選擇生成F的函數

4) 若 0.2×nmax≤n<0.5×nmax,令c1和c2分別是使用f1、f2進行參數生成的次數。ki為使用fi進行參數生成時產生更優秀的個體次數。分別更新f1、f2的成功率s1、s2,使用獎勵機制在函數候選池中選擇生成F的函數

5) 若n≥0.5×nmax,令uF為在過去迭代過程中參數F的歷史值中隨機選擇的一個值,使用柯西分布生成

6) 根據突變因子F設計Fw如下

7) 進入下一次迭代,重復步驟3)～6)。

可以看出,通過式(22)中的μpb,g、μpr1,g和 μpr2,g,自適應控制策略在粒子更新公式中使用次優位置、隨機位置,避免了算法的早熟收斂。式(26)～(27)通過對歷史信息中成功樣本的學習,自適應選擇突變因子的生成函數,有利于生成優秀個體。由式(29)可知,在算法運行初期,為了增強算法的全局搜索能力和種群的多樣性,將F設置為一個大值、Fw設置為一個小值。在算法運行后期,為了加快算法的收斂速度,將F設置為一個小值。該方法不受函數約束條件的連續性、可導性限制,避免了過早收斂和參數敏感性高等問題,有利于提高求解效率。

將式(22)引入PSO 算法粒子更新公式,PSOLPSR-SHADE-CLM 融合算法的粒子更新如下

式中:w為慣性權重;c1,c2為常值學習因子;S(?)=[cos(?) sin(?)]T為式(2)UUV 運動學模型中關于三角函數關系的函數。

PSO-LPSR-SHADE-CLM 融合算法的流程框圖如圖2 所示。

圖2 PSO-LSHADE-CLM 算法流程框圖Fig.2 Flow chart of PSO-LSHADE-CLM algorithm

4 仿真與分析

為了驗證文中所提出的基于聲場信息的IPM以及PSO-LPSR-SHADE-CLM 混合算法的有效性,基于Matlab GUI 開發多UUV 協同目標搜索仿真軟件。主要功能為選擇UUV 參數(包含UUV 的初始位置和移動方向)、目標參數(包含目標的初始位置及是否移動)、搜索方法的選擇、顯示搜索軌跡及顯示搜索結果。軟件界面如圖3 所示。

圖3 多UUV 系統目標搜索仿真界面Fig.3 Simulation interface of multi-UUV target search

仿真實驗中,設置矩形搜索區域的大小為20 km×20 km,在該區域中投放4 艘UUV 執行搜索任務,UUV 參數如表1 所示,聲吶參數如表2所示。

表1 UUV 初始狀態及參數表Table 1 Initial states and parameters of UUVs

表2 聲吶參數表Table 2 Parameters of sonar

滾動優化的時間窗T=3,每隔1 0 s進行一次決策。每決策一次作為一個仿真時間節點,限制搜索最大時間為1 000 個時間節點,算法參數如表3所示。

基于上述仿真軟件以及參數,設置2 種任務場景。

場景1: 搜索區域中存在1 個動態目標,該目標以位置坐標 (18 km,4 km)為起點,沿正弦軌跡往返運動。采用PSO-LSHADE-CLM 算法,分別使用TPM 和IPM 模型進行搜索。

對比圖4、圖5 各UUV 的搜索軌跡可知,采用TPM,圖4 中 UUV1、UUV2(見圖中數字標記)軌跡始終沒有導向目標,UUV3在搜索前期同樣出現盲目搜索現象,降低了搜索效率。采用IPM 模型,在相同時間內,圖5 中全部UUV 均導向了目標可能存在的方位,增大了搜索到目標的概率,加快了搜索速度。圖中: 黑色方塊為移動目標;黑色實線為移動目標的運動軌跡;其余4 種顏色的線條分別為4 艘UUV 的搜索軌跡;扇形區域為搭載聲吶的探測范圍;k為當前時間節點。

圖4 TPM 搜索軌跡(第800 步時)Fig.4 Search trajectories of TPM at step 800

圖5 IPM 搜索軌跡(第800 步時)Fig.5 Search trajectories of IPM at step 800

場景2: 搜索區域中存在2 個動態目標,目標1 以位置坐標 (8 km,8 km)為圓心,1.5 km為半徑做勻速圓周運動,目標2 以坐標 (18 km,4 km)為起點,沿正弦軌跡往返運動。采用IPM 模型,分別使用PSO、PSO-LPSR-SHADE-CLM 算法進行搜索。其余設置和場景1 一致。

對比圖6、圖7 各UUV 的搜索軌跡可知,采用PSO 算法,圖6 中出現了很明顯的局部最優現象: UUV2、UUV4對同一區域在短時間內進行了重復搜索,降低了搜索效率。這是由于PSO 算法在算法運行過程中,粒子多樣性迅速消失,在2 艘UUV 同時面對具有高目標函數值的區域時,無法通過引入突變粒子實現新區域的選擇。采用PSOLPSR-SHADE-CLM 算法,圖7 中 UUV3、UUV4較好地避免了對目標2 的重復搜索,UUV3改變航向前往新區域進行搜索,表明引入學習機制和突變粒子的改進算法提高了求解效率。

圖6 PSO 搜索軌跡(第600 步時)Fig.6 Search trajectories of PSO at step 600

圖7 PSO-LPSR-SHADE-CLM 搜索軌跡(第600 步時)Fig.7 Search trajectories of PSO-LPSR-SHADE-CLM at step 600

為進一步驗證改進概率圖IPM、PSO-LSHADECLM 算法的有效性,分別改變移動目標數量及投放的UUV 數量進行搜索,完成蒙特卡洛實驗100 次。表4 對比了IPM+改進算法、IPM+傳統算法及TPM+改進算法3 種組合條件下搜索到的平均目標數目,可以看出,IPM 與PSO-LPSR-SHADECLM 組合算法發現的目標數量最多。

表4 不同組合算法搜索到的目標數量Table 4 Number of searched targets by different combination algorithms

5 結束語

文中對未知環境同構多UUV 系統的目標搜索問題展開研究,針對感知信息利用不足帶來的盲目搜索及局部最優難題,提出了一種基于目標聲信息的IPM 模型,充分利用聲吶探測的目標信息,提高了UUV 對動態環境的認知;提出了一種基于學習機制和自適應參數調節的PSO-LPSRSHADE-CLM 優化算法,增加了粒子多樣性,減少了局部最優,得到了UUV 最優路徑可行解。仿真結果表明,文中所提出的搜索方法在相同搜索周期的約束下發現目標的數量更多、速度更快。后續將對該多UUV 目標搜索系統引入通信距離約束,開展分布式目標搜索方法的研究,以便更好地滿足實際系統的需求。