無人機群目標搜索的主動感知方法

樓傳煒，葛泉波，劉華平，袁小虎

（1. 上海海事大學 物流工程學院，上海 201306; 2. 同濟大學 電子與信息工程學院，上海 201804; 3. 清華大學 計算機科學與技術系，北京 100084; 4. 清華大學 自動化系，北京 100084）

隨著無人機技術的不斷發展，無人機(unmanned aerial vehicle，UAV)在軍事、商業和農業等各個領域中屢見不鮮，且多無人機系統較單架無人機具有更好的容錯性和魯棒性，在目標搜索以及路徑規劃方面有著廣泛應用[1-6]，其中無人機路徑規劃問題常用蟻群算法優化解決，已有學者在環境已知的基礎上研究了二維平面[7-8]以及三維空間[9-11]上的路徑規劃方法，文獻[12]在TSP問題中利用負信息素實現搜索的多樣化，有效減少了遍歷城市的時間。文獻[13]提出一種求解凸優化子問題的定制內點法來提高多無人機協同軌跡規劃效率。文獻[14]基于蟻群協調方式，提出了基于仿生集群算法的無人機集群分布式目標搜索模型。在此類問題研究中，搜索目標的位置是已知的，而無人機群搜索任務主要是對不確定的或動態的目標的搜索[15]，因此上述蟻群算法不能解決目標位置未知的問題[16]。

為了解決未知目標問題，文獻[16]利用基于信息素的修正蟻群算法完成了對未知目標的搜索，然而由于此算法存在禁忌表，在規模較大的環境中只有一定感知能力的螞蟻很難完全地根據步長遍歷環境，因此局限于規模較小的環境，且啟發函數在柵格環境下并不適用。文獻[17]根據同構無人機的數目對矩形搜索區域分割，將多UAV搜索轉化為單個UAV的區域遍歷搜索，以此實現地圖的全覆蓋搜索。在實際搜索中，UAV與目標到達同一區域時難免有時差，也會給搜索任務帶來挑戰，對此，文獻[18]用概率函數來描述目標模型，對每個柵格進行目標概率的更新，概率越高則表示目標存在幾率越高，有效實現了復雜環境中無人機群對未知目標的搜索。

主動感知是無人機在搜索目標時通過選擇其運動方式，增加在外部環境中通過傳感器獲得的信息。在主動感知的概念中，行動與知覺密不可分，良好的知覺對無人機的搜索任務至關重要，因此在現實世界中實時操作時，可通過行動來幫助它們感知，以獲取更為完善的環境信息[19]。

為了優化蟻群搜索算法，使之適用于規模較大的柵格環境，本文基于主動感知，結合UAV運動與柵格對應關系以及目標概率函數提出無人機群目標搜索的主動感知方法。新方法的搜索機制保留了信息素對UAV的引導作用，本文提出了具有探索偏好的未搜索概率，優化了狀態轉移概率計算方法，使無人機偏向未搜索的區域，減少自鎖出現的幾率，并通過改變目標概率函數中的參數實現了搜索環境的信息更替。

本文首先描述了研究問題，包括環境、無人機、目標以及研究動機，然后結合主動感知框架，對無人機的運動進行了設定，以此提出了具有探索偏好的刺激概率，構建了無人機運動方式選擇機制，設計了環境信息的更替方式，最后進行了仿真驗證。

1 問題描述

本文設定n架無人機在環境I下協同搜索未知動態目標，每架UAV獨立感知環境并將信息存入環境柵格中與其他UAV交互，將存儲的目標信息整合并更新，獲取系統更新后的信息，通過運動方式選擇機制決策下一步的動向，從而有效地搜索目標。為有效開展搜索工作，UAV只對高濃度信息素區域的和未搜索區域感興趣。

1.1 環境描述

本文用Ix×Iy的柵格來表征環境I，如圖1所示。

圖1 搜索環境Fig.1 Search environment

每架UAV占據一個柵格，其單步可行域是與自身所在柵格的相鄰8個柵格，運動步長為1格，且都裝載了可以探測到目標的傳感器，設其感知范圍為r，考慮到無人機的物理結構限制，設其最大偏航角θ為90°。

UAVs的位置坐標可認為是所在柵格的中心節點坐標，根據柵格序號與坐標轉換公式，計算其準確的坐標(x,y)：

式中：a為單個柵格邊長；MM=Ix=Iy，表示橫(縱)坐標的最大柵格數；j表示柵格序號；mod(·)和ceil(·)分別為取余運算和舍余取整運算。

假設1 任意兩架無人機相差一定的飛行高度且各無人機飛行高度固定，在同一柵格出現時不會發生碰撞。

假設2 無人機不受人為操控，僅通過算法進行控制。

1.2 目標描述

本文設定3個運動軌跡不同的目標，假設目標各有其運動規律且相互獨立。目標不具備探索UAV的能力，若目標在沖出搜索區域前未被探測到，則視為搜索失敗。

根據文獻[18]的方法，用柵格對環境劃分后，當未知環境下的多無人機協同搜索目標時，目標狀態的不確定性使搜索過程被簡化為一個概率問題，每一個柵格都用概率密度f(x,y,σ)表示目標存在的可能性，公式為

式中：x和y的坐標相互獨立且均相對于一個柵格而言，以柵格中心為原點建立橫縱坐標，坐標范圍均為[?0.5a,0.5a]；σ為標準差，如圖2所示。

圖2 目標分布Fig.2 Target distribution

1.3 研究動機

為提升蟻群搜索算法對規模較大的柵格環境的適應力，本文結合主動感知里運動與感知相結合的特性，提出基于蟻群算法的主動感知搜索框架，使無人機實現根據環境信息選擇運動方向的功能。在搜索過程中，由于啟發函數只與相鄰節點間距離有關，文獻[16]中蟻群的決策機制并不能隨著周圍環境的變化而提高引導性能。本文在決策機制的基礎上融入了柵格訪問值，提出具有探索偏好的未搜索概率，使得無人機探索的興趣隨柵格訪問值的增大而提高，將刺激概率與表征目標熱點的信息素相結合，得到無人機運動方式選擇機制。在這種機制下，無人機會綜合考慮目標高概率出現區域和未探索區域，與僅通過信息素來搜索的這種機制相比更具目標針對性和環境的探索性。此外，為了將無人機搜索結果與信息素更新有機結合，本文將目標存在概率作為信息素更新的量的尺度，通過改變標準差調節尺度大小，實現了環境信息的更替。

2 主動感知搜索框架

本文基于蟻群搜索算法提出了UAVs主動感知搜索框架，如圖3所示。

圖3中H(t－1) 和H(t) 分別代表相鄰時刻的歷史環境信息，此信息由目標出現概率和螞蟻的信息素表示，目標出現概率的更新與信息素的釋放和揮發表示環境信息的變化；A(t) 為無人機基于歷史環境信息選擇的運動方式；X(t－1) 和X(t)表示無人機相鄰時刻的運動狀態，根據螞蟻覓食的仿生機理選擇不同的運動方式，運動狀態表達式為

圖3 主動感知搜索框架Fig.3 Active perception search framework

X(t)=[x(t),y(t),v(t),c]

式中：x、y表示無人機坐標；v表示無人機的速度；c表示無人機是否捕獲到目標，c=1時表示捕獲到目標，反之表示沒有捕獲到目標。無人機感知域信息S(t) 由運動方式和運動狀態決定，感知域信息表達式為

S(t)=[τ(t),T(t),s(t)]

式中：T為所有無人機已搜索過的柵格序號集合；s為無人機可選的運動方式集合；τ為信息素。無人機通過綜合考慮信息素濃度、柵格訪問情況和可選的運動方式進行搜索，得到新的環境信息。

無人機飛行高度一定的條件下，飛機通過調整偏航、俯仰和滾轉姿態，固定翼產生的合力會對飛機產生左前進、前進、右前進、左后退、右后退、后退、左移和右移這8個方向的運動，如圖4所示。

圖4 無人機運動方式Fig.4 UAV motion mode

由于無人機在飛行過程中受物理結構限制，偏航運動能力比俯仰、滾轉運動能力弱,因此在偏航運動中更容易出現執行器飽和[20]。鑒于上述考慮，參考文獻[21]，本文為無人機設定了一個90°的最大偏航角，最大偏航角定義為上一時刻無人機運動方向與此刻運動方向所夾的最大角度。如圖5所示，本文設定無人機的運動步長為柵格地圖的1個柵格長度，在設定下，無人機每次選擇運動方式時，最多考慮5個運動方向(4個角落只有3個運動方向)，且實現掉頭所需的最小轉彎半徑r為0.5格。

圖5 最大偏航角下無人機的運動Fig.5 Motion of UAV under the maximum yaw angle

搜索過程中，無人機根據最大偏航角得到初步的運動方式可選集合，結合T得到最終的可選方式集合，避免出現重復搜索現象。無人機綜合信息素的濃度變化以及環境的探索程度兩個因素，實現互相的配合。在一次迭代中，無人機偏好于探索未搜索的區域，從而達到各無人機分散搜索的效果，且在搜索過程中根據是否捕獲目標來選擇釋放或揮發信息素，以此改變信息素濃度，進而使各區域的信息素濃度產生差異。在下一次迭代中，高濃度的信息素對附近無人機起引導作用，低濃度的信息素起相反效果，從而使得無人機對目標分布可能性高的區域加強搜索。

3 具有探索偏好的未搜索概率

在完成上述運動方向的限制后，根據主動感知框架，算法需要一定的機制來抉擇出無人機最感興趣的區域所對應的運動方式，蟻群算法中作為核心函數之一的啟發函數是螞蟻當前位置與下一位置坐標差歐氏距離的倒數。在柵格地圖環境下，相鄰位置間的距離并不相等，因此所有運動方式下函數值僅有2種值，存在一定的錯誤導向性。文獻[22]采用強化最優解的引導作用、減小最差解路徑上的信息素來加快算法的收斂速度，但是降低了算法的探索能力。基于上述問題，本文借鑒文獻[20]中的避障機制，計算無人機當前狀態下，各可選運動方式的未搜索概率(unsearchable probability，UP)，此概率表示不同運動方式對無人機的吸引程度。UP的計算過程如下：

1) 統計各運動方式下的柵格訪問值

由于無人機運動步長為1格，無人機各運動方式下對應的柵格即為當前柵格的相鄰柵格，因此需要對任意兩柵格之間設定一個訪問權限，以此限定無人機的運動步長。無向圖的鄰接矩陣第i行(或第i列)中的非零元素為第i個柵格的度，剛好對應此柵格的相鄰柵格，因此本文采用無向圖的鄰接矩陣(以下簡稱為鄰接矩陣)建立相鄰柵格的連接。

無人機每到達一個柵格，系統會更改該柵格的訪問狀態，記錄在mark中，無人機當前時刻各運動方式的柵格訪問值統計通過鄰接矩陣鎖定可訪問柵格，并統計對應mark中非零的數量，即為柵格訪問值，統計過程如下：

①按先上后下，先左后右的順序對各運動方式對應的柵格進行排序；

②按順序選擇一個柵格；

③根據此柵格的序號，通過鄰接矩陣鎖定相鄰柵格；

④統計這些相鄰柵格儲存的mark值；

⑤通過累加的方法計算得到該運動方式對應的柵格訪問值。

⑥重復步驟②～⑤，直至完成所有柵格訪問值的統計。

2) 統計各運動方式下的未搜索概率

某一運動方式下的未搜索概率表示無人機對該運動方式的傾向程度，文獻[20]為無人機避障提出了基于排列組合的刺激概率(stimulate probability，SP)引導方法，本文在機器人運動方式的選擇過程中采用并改進了此方法。在排列組合中，具有探索偏好的未搜索概率(unsearchable probability with exploring preferences，UPEP)可看作已經在可選運動方式集合里選擇某一運動方式（此方式對應的柵格未被訪問）的條件下，在包含所有未被訪問柵格對應的運動方式集合中，選擇其中一個運動方式的概率，計算方式為

式中：i表示無人機序號；j為無人機所在柵格序號；markj為柵格j的柵格訪問值；Normalize(·)為歸一化函數，其值為數組元素除以數組中最大值與最小值和的商。圖6為刺激概率SP和UPEP隨柵格訪問值變化的特性曲線對比圖。

圖6 SP和UPEP特性曲線對比Fig.6 Comparison of SP and UPEP characteristic curves

由圖6可見，UPEP隨柵格訪問值的升高而升高，柵格訪問值越高，未搜索概率越大，無人機對此柵格就越有興趣探索；文獻[20]的刺激概率SP曲線中在柵格訪問值為2、3、4和5時，其刺激概率均小于柵格訪問值等于1時的刺激概率，在[1,5]區間內，刺激概率并不具有單調遞增性。

4 無人機運動方式選擇機制

無人機選擇運動方式時不能僅對未搜索區域感興趣，在搜索過的區域中極有可能有與目標相關的歷史環境信息，本文基于蟻群算法的狀態轉移概率，將上節的UPEP與信息素相結合，得到各運動方式的評價指標P，計算公式為

式中：i表示無人機序號；j為無人機所在柵格序號；allowedj為第i架無人機的第j種運動方式；s為這些運動方式的序號；α為信息素重要因子；t為時間。式(1)會根據未搜索概率對信息素進行衰減，概率越小，衰減越多，計算所得的狀態轉移概率即為無人機各運動方式選擇概率。

無人機在選擇運動方式時只看概率高低會導致搜索的局部最優，喪失廣泛性，因此本文采用累積和函數cumsum(·)，形成幸運輪盤，圖7為輪盤展開示意圖。

圖7 輪盤展開示意圖Fig.7 Diagram of the roulette’s expansion

由圖8可見，各運動方式根據式(1)計算所得概率越高，在此輪盤中所占面積越大；采用隨機函數rand(·)作為指針并認為此函數產生的偽隨機數足夠接近真正的隨機數。如產生的隨機數為0.52，則無人機選中第3種運動方式。

圖8 Pob曲線Fig.8 Pob curve

5 環境信息的更替

無人機根據歷史環境信息選擇了運動方式并更新了狀態后，需要對其所在柵格以及路徑進行信息更新，形成新的環境信息，因此環境信息分目標出現概率Pob和吸引無人機的信息素τ。Pob表示在一定的搜索后，相應柵格中目標出現的概率，并用熱力圖的形式將其可視化；無人機上一時刻的路徑信息由τ表示，由于對信息素的依賴性，τ值的高低會直接影響無人機運動方式的選擇。

以上2種環境信息皆由當前時刻的無人機目標捕獲狀態c決定，信息增量表達式為

式中：ρ為信息素揮發因子，作為無人機狀態衰減值；d表示無人機與目標的歐氏距離；r為無人機感知域半徑。由式(2)可見，當d>r時，c=0，即無人機捕獲目標失敗， Δσ 設定為衰減值，反之，設定為增長值，且增長值與衰減值之比為30∶1。

5.1 目標發現概率

某一柵格中目標出現概率為對應概率密度函數的雙重定積分，即

根據1.3節的目標描述，在柵格邊長不變的條件下，目標概率密度函數的自變量只有σ，由圖8可知σ與Pob呈反比趨勢。

因此，可以通過改變σ的方式達到調節Pob的目的。σ的更新方式為

σ(t)=σ(t?1)+0.05Δσ

5.2 信息素更新方式

蟻群算法的信息素用于儲存路徑信息，并非存儲在柵格中，因此σ無法與信息素對應。無向圖的鄰接矩陣除了建立柵格聯系，還可以將矩陣內的數值細化表征所建聯系的強弱，本文以此來進行信息素的更新。

信息素更新的目的是使得較優路徑上的信息素增加，同時根據揮發因子ρ(0<ρ<1)的值模擬一種揮發的方式削弱較差路徑上的信息素，避免信息素的無限累積，出現局部解[23]。路徑上的信息素更新為

式中：j為柵格序號；ξj為鄰接矩陣中第j行中的所在列；t為當前時刻。式(3)僅僅更新無人機上一時刻到當前時刻的路徑，σ的正負分別對應信息素的產生和揮發，式(3)的揮發是系統根據無人機的搜索狀況而進行的，實際環境中，信息素作為昆蟲的外激素也會因為溫度等環境因素而自然揮發，為了構建環境的真實性以及避免過度地局部搜索，需要進行全局更新：

式中ρ為信息素揮發因子。

6 仿真實驗

本文仿真環境為Windows 10系統，電腦配置為i5-8300H/1050Ti，本次仿真在Matlab R2014b版本中進行。仿真場景設置如表1所示。

表1 仿真場景參數設置匯總表Table 1 Summary of simulation scenario parameter setting

文獻[16]中對環境進行節點建模，節點個數為32個，為了對比大環境中本文算法的有效性，實驗設置了1 369個節點的柵格環境。基于上述場景，為了能夠比較算法的優劣性，需要進行多角度、長時間迭代的對比分析，本文仿真對比了基于貪婪思想的搜索方法、隨機搜索方法、文獻[16]的搜索方法和本文的搜索方法。貪婪搜索方法是在運動方向中選擇信息素濃度最高的方向；隨機搜索方法則是沒有任何決策機制，隨機選擇運動方向[24-25]。圖9為本文算法的流程。

圖9 本文算法流程Fig.9 Algorithm flow chart of this paper

圖10所示為基于貪婪、隨機、本文搜索方法以及文獻[16]搜索方法運行結束后的可視化界面。

圖10中的4幅圖均為各自算法最后一次迭代下的熱力圖和無人機群航跡圖。結果表明，主動搜索和隨機搜索與貪婪搜索相比，其目標的捕捉率高，捕捉范圍廣；且主動算法的搜索覆蓋最廣，隨機搜索容易圍繞在出生點附近，所以其捕獲目標的效率很大程度取決于出生點的好壞，貪婪搜索由于貪婪思想，多架無人機均選擇了相同的路徑，容易導致局部最優。本文就無人機群航跡覆蓋率、地圖高亮區域和目標捕獲點的分布規律3個指標對這4種算法進行了比對分析，其中航跡覆蓋率對比如圖11所示。

圖10 4類算法的可視化界面Fig.10 Visual interface of four algorithms

如圖11所示，本文的搜索算法的航跡覆蓋率均值達到80%左右，僅以此結果來看，本文搜索的效果比較可觀，文獻[16]搜索算法的覆蓋率僅有52.3%，以此可以表明本文所提算法相較于文獻[16]更適用于較大的環境。然而動態目標相對于無人機群體具有時間和空間的不確定性，因此實驗中用熱力圖中高亮區域的數量來表征算法中目標被捕獲的效率，設定了亮度>75%為高亮柵格，如圖12所示。

圖11 4類算法航跡覆蓋率對比Fig.11 Comparison of track coverage of four algorithms

圖12 4類算法高亮區域數量對比Fig.12 Comparison of hot spot area of four algorithms

從圖12中可以明顯看出，4種搜索算法隨著迭代次數的增加，其高亮柵格逐漸增多。然而貪婪算法因為局部最優，導致后半段高亮柵格數量不再增長，即目標總在同樣的地方被捕獲。文獻[16]的搜索方法由于受到環境的限制，高亮柵格明顯少于隨機搜索和本文搜索方法。如圖12由于無人機每次迭代均在地圖中心產生，本文搜索方法較隨機搜索效果略好一些。因此本文用目標捕獲點的分布表示算法搜索到的目標分布，結果如圖13所示。4類算法一維數據統計如表2所示。

圖13 4類算法目標捕獲點分布Fig.13 Four types of target capture points distribution

表2 4類算法一維數據統計表Table 2 One-dimensional data statistics of four algorithms

7 結束語

經上述仿真實驗結果可得：本文提出的主動感知框架下的UAVs目標搜索算法適用于未知環境下未知目標的無人機群體目標搜索問題。相比較于文獻[5]的蟻群搜索算法、貪婪搜索和隨機搜索，本文提出的主動搜索方法對環境探索的覆蓋性強，對運動目標的捕獲能力也較強。然而，算法中UAVs僅僅依靠共享的環境信息互相通信，協作搜索能力還有待提升，因此以后可對UAV的通信能力以及無人機協同方式深入研究。