基于粒子群遺傳算法的多無人機協同路徑搜索*

姚 軍，李思捷，羅德林，劉善國，王國耀，吳 軍

（1.解放軍95894 部隊，北京 102211；2.廈門大學，福建 廈門 361102）

0 引言

近年來無人機（Unmanned Air Vehicles，UAV）被廣泛應用于軍事和民用領域。在不確定環境下偵察作戰時，由于單架無人機對搜索區域信息了解有限，為了提高對搜索區域信息的感知能力和目標搜索效率，多架無人機的協同路徑搜索和信息獲取已經成為當前研究重點，美軍已將無人機集群作戰作為未來發展的重要方向。

無人機目標搜索研究一直備受科研學者的關注。文獻［1-2］中提出了一種基于概率圖模型的遺傳算法，搜索不確定環境中的目標，但該算法未對無人機搜索路徑效率進行分析。基于狀態預測的滾動優化搜索決策方法，根據概率可以預測無人機要經過的路徑，有效避開了禁飛區，但會出現重復搜索的路徑，搜索效率較低［3-4］。文獻［5］提出了一種利用合作模型的搜索算法，無人機可以在指定區域內實現協同搜索，但該算法搜索目標的數量依賴搜索區域先驗信息，具有一定局限性，實用性不強。覆蓋式搜索算法可對整個環境區域進行完整搜索，但考慮到無人機油耗有限，在現實狀態下不太可能采用該方式進行大范圍搜索［6-7］。文獻［8］提出了一種對不規則凸多邊形區域進行分割處理，然后分配給指定無人機進行搜索的算法，但該方法沒有考慮地形和高度等環境因素對搜索的影響，同時對凹多邊形也無法使用。

本文針對以上算法不足，提出了基于粒子群遺傳算法的多無人機不確定區域協同路徑搜索方法，其任務背景如下：在指定未知搜索范圍內，已知重點區域、一般區域和禁飛區域，且在重點和一般區域隨機分布一定數量的目標，研究多無人機協同路徑搜索算法，實現最大可能探測未知搜索范圍的信息量。方法基本流程如下：首先建立柵格化概率圖模型，無人機根據目標報酬函數展開搜索任務，減少了搜索過程的隨機性；其次引入協同思想并與粒子群遺傳算法相結合進行航跡規劃，通過加強多無人機合作，提升搜索效率和質量；最后通過仿真計算驗證算法的有效性。

1 問題建模

1.1 搜索區域模型

假定任務派出n 架UAV 從指定機場出發對目標展開搜索，設定整個任務區搜索環境為X×Y，將其劃分為對應大小的子單元格集合，即E={x，y|x=1，2，3，…，X，y=1，2，3，…，Y}為無人機目標搜索區域，其坐標點{x，y}表示在x 行和y 列的搜索單元格。將X×Y 柵格化為單元格集合E，即完成了柵格化環境建模，為后續無人機仿真實驗提供基礎環境。

為了便于后續仿真實驗，算法模型作以下簡化處理：1）無人機之間可以隨時共享信息，不考慮通信延遲問題；2）不考慮無人機在飛行過程中的故障問題，即無人機飛行狀態一直良好；3）無人機在某個子單元格執行偵察任務時，其傳感器可以獲取該單元格所有信息，并隨時將此單元格中環境和搜索狀態信息發送給其他無人機。

1.2 搜索模型初始化

在柵格圖模型中假設UAV 是一個以一定速度飛行的質點，t 時刻UAVi所在單元格坐標為{xi，yi}，表示UAVi正在該單元格偵察環境信息。規定每個單元格最多存在一個目標（Q={0，1}，Q=1 表示目標存在）。由于無人機存在最小轉彎半徑的物理約束，在柵格圖環境中規定UAVi只有8 種航向狀態，即D={0，1，2，3，4，5，6，7}，具體如圖1 所示。同時無人機UAVi在t 時刻的某種狀態下，下一步只有3 種路徑可選，即t+1 時刻的路徑只能是直飛或者左右45°轉彎。

圖1 航向示意圖

1.3 搜索概率圖模型

在真實的不確定環境中往往需要對整個區域進行特征劃分，主要包括重點搜索區域、一般搜索區域和禁飛區域，并對每種區域指定的環境狀態進行數學建模。本文同樣在柵格圖模型中設置了重點搜索區域、普通區域和禁飛區域，并在對應區域的單元格中設置了目標存在概率Pxy（t）。由于缺乏目標具體信息，UAVi某時刻對單元格中目標判斷存在不確定性程度，初始設置對單元格目標信息不確定度Pu=1，表示此時對該處目標信息完全不確定。當UAVi在t+1 時刻對該單元格進行偵察時，通過傳感器獲取目標物存在狀態，此時單元格中目標信息的不確定程度會根據比例因子R 不斷調整，如式（1）所示：

由于傳感器存在誤差，在探測過程中傳感器有探測概率Ps和出錯概率Pm，且Ps+Pm=1。在路徑搜索過程中，會根據當前時刻傳感器探測目標的狀況Qt（Qt∈{0，1}，Qt=1 表示探測到目標）更新下一時刻單元格目標存在的概率。當Qt=1 時，根據式（2）更新單元格目標存在概率：

當Q=0 時采用式（3）更新單元格目標存在概率：

2 協同搜索算法設計

2.1 協同搜索及粒子群算法

協同是一種合作型關系，指群體中的個體之間在執行任務中相互協作，分享彼此的資源，以達到更好完成目標的一種合作方式。本文提出的協同搜索，其核心在于無人機在搜索過程中，實時分享傳感器捕獲的目標信息，包括單元格中目標存在概率和自身已經搜索過的單元格，還有為了避免與其他無人機發生碰撞，隨時提供的當前單元格坐標與航向。在搜索完單元格后根據目標存在狀態，更新搜索概率圖和信息不確定度，并通過共享機制使其他無人機獲取該單元格信息，以盡量避免重復搜索，減少不必要的油耗，提升效率。由于假設不存在通信延遲和故障等問題，在搜索過程中所有無人機共享整個柵格圖信息，實現區域目標高效搜索。

粒子群算法（Particle Swarm Optimization，PSO）是由Eberhart 和Kennedy 根據鳥類覓食行為而提出的一種全局隨機搜索算法。在模擬鳥類覓食過程中，假設環境未知方位存在食物，種群中的鳥類根據自身距離食物的位置進行搜索，并將距離食物最近的個體位置作為搜索的主要方向。粒子群算法基于鳥類覓食思想解決問題時，隨機生成一組粒子集合，其中每一個粒子都有自己的飛行速度與方向，并作為對應問題的一個解；在每一次迭代過程中，通過適應度函數計算出粒子的適應度值，并找到當代所有粒子中適應度值最大的粒子；然后跟歷史最大粒子進行對比，選擇最優粒子來調整所有個體的速度和方向，不斷朝著最優方向進化。PSO 算法根據式（4）和式（5）進行迭代尋優。

2.2 基于協同的粒子群遺傳算法

本文以搜索概率圖為基礎，每個UAV 對應一個粒子群，每個粒子群中生成固定數量的個體（即粒子），采取路徑滾動預測的方法，實現路徑搜索。其中個體是隨機生成的、長度為k 的預測搜索路徑，每個路徑代表無人機接下來可能要搜索的k 個單元格。為了滿足最小轉彎半徑的物理約束條件，在搜索過程中規定無人機只能直飛和左右45 °轉彎。由此粒子群算法可通過預測步長k 和飛行方向進行粒子群個體編碼，在每次搜索過程中隨機生成粒子群大小為N、長度為k、由{-1、0、1}（左轉、直飛、右轉）組成的個體，每個個體代表該無人機一個可行的搜索路徑。UAVi在t 時刻位于某一單元格時，根據粒子群中最優粒子的預測路徑移動一個單元格，然后在此基礎上按照協同搜索的原則更新柵格圖概率和無人機航向，為下一次搜索作準備。

雖然粒子群算法優點十分顯著，收斂速度快、內涵并行特性、搜索效率高，可以根據個體極值和全局粒子極值指導粒子進行搜索，但也存在明顯的缺點，如算法容易早熟收斂、陷入局部最優解、對不連續問題處理性能不佳。遺傳算法（Genetic Algorithm，GA）憑借其極大的種群規模以及內部選擇、交叉、變異的3 種機制，可以有效求解全局最優解，正好彌補粒子群算法的不足。在粒子群算法更新完個體后，采用遺傳算法對個體進行選擇、交叉、變異和精英保護，形成新的個體再進行粒子搜索，實現兩種算法的完美融合。最后再將這兩種算法和協同搜索結合，形成新的協同粒子群遺傳算法（Collaborative PSO and GA，CPSOGA）用于解決無人機協同區域搜索問題，實現更優路徑搜索，并提升無人機搜索信息的效率和針對性。圖2 給出了UAVi在出發點A0航向為0 時生成規模為N 長度為k 的粒子群集合。

圖2 粒子群集合

UAVi根據圖2 的粒子群集合在柵格圖中生成對應的預測路徑如下頁圖3 所示，然后根據適應度函數計算搜索報酬，從所有路徑中選擇一條最合適的搜索航跡。

圖3 無人機搜索路徑

圖4 用來說明無人機對禁飛區域的回避情況。無人機根據粒子群集合規劃出預測路徑的單元格節點，雖然從A0出發進入第1 個單元格m1不會影響飛機安全，但進入第2 個單元格可能會駛入禁飛區，所以不論是選擇單元格集合{m1，n2，q2}還是{m1，m2，k3}的個體搜索路徑都會進入禁飛區域，只有選擇單元格集合{m1，n2，q1}和{m1，m2，k2}才可以確保安全，因此，面對禁飛區，要提前作好回避決策。

選取47例2017年3月—2018年3月期間本院收治的肺部孤立性肺結節患者納入本次研究，經CT常規檢查結果顯示，47例患者肺部均存在孤立性結節，且無明顯肺門轉移現象，也不存在淋巴腫大等現象。47例患者中男31例，女16例；年齡35～75歲，平均年齡（57.24±9.09）歲；癥狀表現：存在明顯胸部疼痛者9例，出現發熱者7例，咳嗽、咳痰癥狀明顯者10例，無明顯癥狀表現者21例。

圖4 無人機禁飛區回避示意圖

2.3 適應度函數

為了保證UAVi的安全性以及協同搜索的效果，需要防止發生碰撞，并盡可能避免重復路徑搜索，同時確保在規定油耗內能夠完成搜索任務。在UAVi搜索路徑時，如果預測的路徑是之前搜索確定的路徑點，則對應個體的適應度值V=0，如果不是，則按式（6）計算個體的適應度值。

其中，l_ij表示t 時刻無人機UAVi和UAVj分別預測個體路徑位置{xi，yi}與{xj，yj}之間的實際距離，式（7）是其計算公式：

當l_ij＞1.414 時，表示UAVi與UAVj不會發生碰撞，采用式（6）計算個體預測路徑的適應度值；當l_ij=0 時，表示UAVi與UAVj發生碰撞，個體適應度為零；當0＜l_ij≤1.414時，UAVi與UAVj可能發生碰撞，此時適應度需減去一個代價項。

式（6）中，k 表示個體的路徑長度，n 表示無人機的架數，m1是權重因子，m2是代價因子。lt，t+1表示個體預測路徑中相鄰兩個時刻UAVi的飛行預測距離，Pt表示發現目標的回報函數，其計算公式分別如式（8）和式（9）所示；Pf表示不確定度的減少報酬函數，表示隨著搜索的進行，UAVi對搜索區域的信息掌握越來越多，其計算式如式（10）所示。

2.4 算法步驟

本文提出的多無人機協同路徑搜索算法步驟如下：

Step 1 設定柵格圖環境，初始化粒子群和遺傳算法中的參數，確定粒子群大小和預測路徑長度，設置無人機數量和對應的搜索起點、航向等初始狀態；

Step 3 根據粒子群算法和適應度值選擇全局最優粒子，并優化所有個體粒子的速度和位置；

Step 4 通過遺傳算法的選擇、交叉、變異等方式增強粒子群多樣性，并通過精英保護方式保留Step 3 中最優個體，最后對遺傳算法獲得的粒子群進行適應度值計算，并以此對每個粒子代表的預測路徑排序；

Step 5 對比預測路徑和歷史搜索路徑，同時檢測不同粒子群的預測路徑之間是否同時相遇，剔除重復路徑和危險路徑，然后根據Step 4 中排序，選擇最優粒子路徑，并沿該路徑移動一個單元格，進入下一時刻路徑搜索，最后對航向和概率圖進行更新；

Step 6 判斷搜索是否結束，若完成搜索路徑長度Tend，則輸出對應UAVi的航跡，反之，跳轉至Step2 繼續路徑搜索。

3 算法仿真

為了驗證基于協同的粒子群遺傳算法在多無人機區域路徑搜索的效果，在MATLAB R2014a 環境中編寫仿真程序。如圖5 所示，設置30×30 的矩形柵格圖，設定3 架無人機（圖中3 個三角形）分別以航向0、4、6 從（3，1）（10，30）（30，24）位置起飛，設定2 個禁飛區和2 個重點搜索區，分別為圖中黑色區域和白色方框區域，生成10 個目標（圖中10個菱形）在各個搜索區域隨機分布。設定每架無人機對應粒子群大小N=50，預測路徑長度k=5，搜索路徑長度Tend=80，傳感器探測概率Ps=0.9，出錯概率Pm=0.1，慣性因子ω 為3，加速因子c1和c2均為1.494 45，比例因子R 為0.5，交叉概率為0.7，變異概率為0.05。

圖5 無人機路徑搜索仿真環境

圖6 和圖7 分別為采用CPSOGA 和PSO 方法的無人機路徑搜索仿真圖，可以看到兩幅圖中，無人機都有效避開了禁飛區域，確保了搜索的安全性。在CPSOGA 算法中，設置的10 個目標均被搜索到，PSO 算法中一共31 次搜到9 個不同目標，重復率為3 倍多；在PSO 算法中出現了大量重復搜索的路徑，并且只是集中在重點區域進行搜索，基本忽視了一般區域中的目標，但CPSOGA 算法不僅有效對重點區域進行搜索，而且基本沒有重復無效搜索路徑，同時會嘗試對普通區域目標展開了搜索。

圖6 CPSOGA 仿真圖

圖7 PSO 仿真圖

為了進一步分析算法的仿真效果，對兩種算法分別單獨運行20 次，每一次運行對應3 架飛機共有路徑點240 個，統計并分析重復路徑和重點區域搜索的路徑點數量，其結果如表1 所示。可以發現CPSOGA 的重復路徑明顯低于PSO，說明通過協同粒子群遺傳算法搜索，無人機之間進行了良好的溝通，減少了重復搜索路徑，提高了搜索效率，標準差更小，搜索結果更加穩定；CPSOGA 在重點區域路徑少于PSO，其主要原因是無人機完成對該區域的搜索任務后會自動離開，并嘗試搜索一般區域，由于離開時間取決于當時的環境，是一個不確定的狀態，所以會導致其標準差比PSO 高，這也說明CPSOGA 不是一味地在重點區域搜索，算法更加先進。從仿真數據可以看出，CPSOGA 比PSO 具有更好的路徑搜索效果。

表1 20 次仿真數據分析

4 結論

本文針對多無人機區域搜索問題，提出了一種新的基于粒子群遺傳算法的多無人機協同路徑搜索方法。為了準確描述算法，針對問題進行了建模，并采用數學語言表述，分別構建了搜索區域模型和概率圖模型；為了提高路徑搜索的質量和效率，將粒子群算法和遺傳算法進行融合，采用適應度函數評價預測路徑，形成了一種新的協同粒子群遺傳算法；為了驗證算法的有效性，編寫程序進行了仿真實驗，其結果顯示，無人機的搜索航跡滿足最小轉彎半徑約束，避開了威脅區域，實現對重點區域的強化搜索并降低了重復路徑，有效提升了多無人機協同搜索效率和質量，證明了所提方法具有良好的路徑搜索能力。