不確定環境下多無人機協同搜索算法研究

張瑩瑩， 周德云， 夏 歡

(西北工業大學，西安 710129)

0 引言

隨著航空技術的發展，無人機(UAV)在軍事和民用兩個方面都發揮著重要的作用，而區域搜索是UAV的常見任務之一。通常UAV在執行搜索任務之前，對搜索區域的信息知之甚少，甚至一無所知，因此，無人機是在一個不確定甚至是未知的環境下執行搜索任務的。在這種情況下，相對于單架無人機來說，多架UAV協同對區域進行搜索，能夠更全面徹底地搜索任務區域、更好地發現目標和獲取情報信息。因此，本文對不確定環境下多UAV協同搜索問題進行了研究。針對不確定環境下的多UAV協同搜索問題，文獻［1］將模型預測控制(MPC)和遺傳算法結合起來，采用遺傳算法進行路徑規劃。但是，一般的遺傳算法只考慮了種群內部的競爭，而協同進化遺傳算法不僅考慮單個種群之間的競爭，還考慮到多個種群，以及生物與環境的競爭、合作與共生的關系。因此，本文研究基于協同進化遺傳算法的多UAV協同搜索算法，進一步提高搜索效能。

論文采用搜索概率圖來描述搜索環境的不確定性，搜索概率圖中包含了UAV對搜索環境的先驗信息，減小了搜索的盲目性。采用協同進化遺傳算法進行多UAV協同搜索路徑規劃，可在線滾動生成局部最優路徑，滿足實時性要求。

1 多機協同區域搜索問題建模

1.1 環境模型

假設搜索區域為一平面矩形區域，其中分布著NT個目標，NV架UAV進入任務區域后對目標進行搜索。本文將搜索區域劃分為Lx×Ly的離散單元，稱所有單元的集合 E={(m，n)|m=1，2，…，Lx，n=1，2，…，Ly}為搜索環境，(m，n)表示位于第m行第n列的單元。單元格(m，n)中目標的真實狀態為 Smn∈{0，1}，Smn=1表示存在目標。

為了便于研究，本文做出以下假設:1)每個單元格最多存在一個目標，該目標可以以Pikill的概率摧毀進入該單元的UAV;2)UAV具有自主避障的能力，因此不考慮環境中的障礙物;3)各架UAV之間可以互相通信，且不考慮通信延遲，即UAV可以即時得到其他UAV的信息。

1.2 UAV的狀態模型

k時刻，UAVi的位置為(mi(k)，ni(k));存活狀態為 δi(k)∈{0，1}(δi(k)=1 表示未被摧毀);航向為Oi(k)∈{0，1，2，3，4，5，6，7}(各數字代表航向如圖 1所示)。假設UAV在一個時刻內只移動一步，即從當前單元移動到相鄰的某個單元。受轉彎特性的限制，UAV在k+1時刻的航向只能是在k時刻航向的基礎上向左轉 45°、直行或向右轉 45°，即 Oi(k+1)∈{(Oi(k) －1)mod 8，Oi(k)，(Oi(k)+1)mod 8}，如圖1所示，其中空心箭頭為k時刻航向，實心箭頭表示k+1時刻航向。

圖1 無人機航向示意圖Fig.1 Sketch map of the orientation of UAV

1.3 搜索概率圖模型

為每個單元(m，n)定義一個目標存在概率Pmn(k)∈［0，1］和不確定度 χmn(k)∈［0，1］。Pmn(k)描述了 k時刻單元格(m，n)存在目標的可能性，Pmn(k)=1表示存在目標的概率最大;χmn(k)描述了UAV對單元格(m，n)處信息的不確定性程度，χmn(k)=1表示UAV對該處的目標信息一無所知。

搜索過程中，UAV根據機載傳感器的探測信息對概率圖進行實時更新。若UAV在k時刻訪問單元格(m，n)，則傳感器獲得探測信息 bk∈{0，1}(bk=1表示UAV在單元格(m，n)探測到目標)，則k+1時刻當bk=1時，單元格(m，n)的目標存在概率更新如式(1)所示，bk=0時如式(2)所示。

其中Pd∈［0，1］為傳感器的探測概率(即單元格(m，n)中存在目標，并被傳感器檢測到的概率)，Pf∈［0，1］為虛警率。

不確定度的更新如式(3)所示。

定義閾值 θ，當單元格(m，n)的目標存在概率Pmn(k)≥θ時，認為該單元格中存在目標。

2 協同搜索路徑規劃算法

2.1 協同進化遺傳算法

協同進化［2］是指生物與生物、生物與環境之間在進化過程中的某種依存關系。也就是說協同進化算法不僅考慮單個種群之間的競爭，而且考慮多個種群，以及生物與環境的競爭、合作與共生的關系，多個物種通過相互間的作用，促使多個種群同時向前進化。協同進化算法主要分為兩大類:競爭型協同進化算法和合作型協同進化算法。對于多UAV協同區域搜索這樣一個既有競爭，更注重合作的博弈格局，合作型協同進化算法是一種適宜的選擇。合作型協同進化按照多UAV之間的合作與約束關系，通過對群體間有利于合作的個體進行適應度加強，促使群體向著有利于產生相互合作和共同適應行為的方向進化。因此本文采用合作型協同進化算法進行多UAV協同區域搜索的路徑規劃。

2.2 基于協同進化遺傳的多UAV協同搜索算法

本文采用滾動優化思想，即在k時刻，限定各UAV向前規劃q步(q＞1為規劃路徑步數)路徑，UAV只執行規劃路徑的第一步，k+1時刻，基于新的系統狀態和環境信息重新規劃路徑。文中使用NV個子種群分別進化NV架UAV的搜索路徑，若在k時刻，UAVi位于單元格(m，n)內，則k時刻路徑規劃的結果為以(m，n)為起點的長度為q的路徑。

2.2.1 編碼

本文以航向角增量為控制量，如1.2節所述，UAV受轉彎特性限制，k時刻UAV的動作集U={－1，0，1}，其中－1表示左轉、0表示直行、1表示右轉。本文以UAV的動作u∈U為基因進行編碼，染色體長度為路徑規劃步數q，如圖2所示為q=6時的染色體結構。每條染色體均可解碼為可行路徑解空間中的一個解(候選路徑)。k時刻，若UAVi的航向為1，則染色體－1，1，1，0，－1，1 代表的路徑如圖3 所示。

圖2 染色體示意圖Fig.2 Sketch map of chromosome

圖3 路徑示意圖Fig.3 Sketch map of path

2.2.2 適應度

求子種群的適應度時，待評價個體必須和其他種群的個體結合，組成完整的解。其中，選擇的其他種群的個體稱為代表個體，論文中選擇其他子種群的最優個體作為代表個體。對于初始子種群，選擇沿著個體代表的路徑進行搜索獲得報酬ρ最大的個體作為代表個體。ρ的計算公式如式(4)所示。由于不考慮通信延遲，各子種群可以即時獲得其他子種群的代表個體，并與待評價個體結合，計算待評價個體的適應度。

待評價個體的適應度定義為在不與其他UAV發生碰撞的前提下(即UAV按待評價個體所示路徑移動，在下一時刻所處的單元格與其他UAV按其代表個體所示路徑移動，在下一時刻所處的單元格不相同)，沿著該個體代表的路徑進行搜索所能獲得的報酬。如果沿著該路徑飛行會與其他UAV發生碰撞，該路徑就不可行，應在其適應度函數中增加懲罰項。

設UAVi按第i個種群的第l個個體所示路徑移動，到k+1時刻時，位于單元格(mil(k+1)，nil(k+1))內，UAVj按第j個種群的代表個體所示路徑移動，k+1時刻，位于單元格(mj(k+1)，nj(k+1))內，則當時，不會發生碰撞，則適應度函數 Fil為待評價個體代表路徑的報酬ρ，見式(4);當時，UAVi與UAVj在k+1時刻可能發生碰撞，如果存在一個 j(j=1，2，…，Nv，且，使得，則令適應度為零，見式(5)，若，則增加懲罰項，見式(6)。

式中:ω1，ω2，ω3為加權系數，且 ω1+ ω2+ ω3=1，ω 為懲罰因子。Rc－1，c為沿規劃路徑，UAV在相鄰兩步之間移動的距離。ρf為發現目標報酬，計算式為

ρu為不確定度降低報酬，計算式為

2.2.3 進化算子

子種群的進化操作選取如下:采用輪盤賭方法進行選擇操作;交叉操作中，對任意兩個父代染色體，當產生的隨機數小于交叉概率Pc時，隨機選擇交叉點，進行單點交叉;變異操作中，當產生的隨機數小于變異概率Pm時，隨機選擇一點進行變異。

2.2.4 算法步驟

本文提出的用于多UAV協同區域搜索路徑規劃的協同進化遺傳算法的步驟如下所述。

Step 1 確定算法的控制參數，包括進化子種群的規模Psize，基因的交叉概率Pc，變異概率Pm，協同進化的代數T，算法的終止條件Tstop。

Step 2 令k=0，對UAVi，產生k時刻的q步最優路徑。

1)令t=0，隨機生成Psize個染色體長度為q的個體。

2)利用其他進化子種群的代表個體，根據式(4)～式(5)計算每個待評價個體的適應值，并進行選擇、交叉和變異操作。

3)選擇最優個體作為代表個體。

4)判斷是否滿足進化停止條件t=T，若滿足，則停止進化，并輸出優化的q步路徑;否則，令t=t+1，轉Step2中第2)步。

Step 3 執行最優路徑的第一項，移動UAVi，并更新單元格和UAVi的狀態。

Step 4 判斷是否滿足算法終止條件k=Tstop，若滿足，則算法停止;否則，令k=k+1，轉Step2中第1)步。

3 仿真分析

設定仿真環境為30×30的矩形區域，環境中隨機分布著10個目標，3架UAV對搜索區域進行搜索，初始位置分別為:(1，1)，(6，1)，(11，1)。設 Pd=0.9，Pf=0.1，路徑規劃長度q=5，進化子種群的規模Psize=100，交叉概率Pc=0.7，變異概率Pm=0.05，目標對進入其所在單元格的UAV的摧毀概率Pkill=0.1，仿真時間取為Tstop=100。初始環境如圖4所示。其中黑色三角表示UAV的初始位置，黑色菱形表示真實的目標位置，該位置UAV未知，p為由先驗信息得知的區域單元格目標存在概率。

圖4 目標分布圖Fig.4 The distribution of targets

圖5 和圖6分別為使用協同進化算法和使用遺傳算法進行路徑規劃的結果。當目標被發現后，由黑色的小方塊表示，從圖中可以清楚地看出找到了多少目標，漏掉了多少目標。

圖5 協同進化遺傳算法的路徑規劃Fig.5 The path planning of CEGA

圖6 一般遺傳算法的路徑規劃Fig.6 The path planning of GA

圖7 給出了在相同時間內，分別使用協同進化算法和遺傳算法發現目標的數量和時刻。圖8為分別使用兩種算法，在相同時間內，對環境不確定度的影響。從圖中可以看出:兩種算法中，無人機在進入任務區域后都是對目標概率較高的區域優先進行搜索，避免了對目標概率為0的區域的無效搜索。在相同的時間內，由于協同進化算法考慮了協同因素，使多架UAV之間較好地進行協調，避免了對同一區域的重復搜索，優化了搜索效能。故使用協同進化算法比使用遺傳算法對環境不確定度的降低程度稍大一點，并且使用協同進化算法可以發現更多的目標。因此，與遺傳算法相比，協同進化算法具有更好的搜索效能。

圖7 兩種算法發現目標圖Fig.7 Targets finded by two algorithms

圖8 兩種算法對環境不確定度的影響Fig.8 Effect of the two algorithms on environmental uncertainty

4 結束語

本文針對不確定環境下的多UAV協同搜索問題，進行了分析，建立了環境模型和搜索概率圖模型，并根據滾動優化思想，提出了基于協同進化算法的多UAV協同搜索的路徑規劃方法。仿真結果表明，協同進化算法充分利用了多UAV之間的協同信息，比遺傳算法具有更高的搜索效能。

［1］ 田菁，陳巖，沈林成.不確定環境中多無人機協同搜索算法［J］.電子與信息學，2007，29(10):2325-2328.

［2］ 焦李成，劉靜，鐘偉才.協同進化計算與多智能體系統［M］.北京:科學出版社，2006.

［3］ 夏歡，周德云，陳龍建.多無人機協同搜索路徑規劃方法研究［C］//中國航空學會航空武器系統分會2010年學術年會暨第三屆“中國航空武器裝備試驗與發展學術論壇”論文集，2010:432-436.

［4］ 申曉寧，郭毓，陳慶偉，等.基于多目標協同進化算法的多機器人路徑規劃［J］.南京航空航天大學學報，2008，40(2):245-249.

［5］ FLINT M，POLYCARPOU M，GAUCHERAND E F.Cooperative control for multiple autonomous UAV's searching for targets［C］//Proc.of the 4lst IEEE Conference on Decision and Control，2002(3):2823-2828.

［6］ POLYCARPOU M，YANG Y，PASSINO K.A cooperative search framework for distributed agents［C］//Proceedings of the 2001 IEEE International Symposium on Intelligent Control，2001:1-6.

［7］ YANG Y，HILINAI A A，POLYCARPOU M M.Decentralized cooperative search in UAV's using opportunistic learning［DB/OL］.http://www.ece.uc.edu/aminai/papers/yang gnco2.pdf，2002.

［8］ FLINT M，POLYCARPOU M，GAUCHER F.Cooperative path-planning for autonomous vehicles using dynamic programming［DB/OL］.http://www.nt.ntnu.no/users/skoge/poroleedings/ifac2002/data/content/01694/1694.pdf，2001.

［9］ DECKER D D.Decision factors for cooperative multiple warhead UAV target classifycation and attack with control application［D］.Xi'an:Air Force Institute of Technology，2004.

［10］ 劉國興，李敏強.基于協同進化的多目標優化算法研究［D］.天津:天津大學，2008.

［11］ 沈延航，周洲，祝小平.基于搜索理論的多無人機協同控制方法研究［J］.西北工業大學學報，2006，24(3):367-370.

［12］ 李子文，夏潔.無人偵察機路徑規劃方法研究［J］.系統仿真學報，2008(S1):490-494.

［13］ PENG H，SU F，BU Y L，et al.Cooperative area search for multiple UAVs based on RRT and decentralized receding horizon optimization［C］//Proceedings of the 7th Asian Control Conference，2009:298-303.