張瑩瑩， 周德云， 夏 歡

(西北工業(yè)大學(xué)，西安 710129)

0 引言

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

論文采用搜索概率圖來(lái)描述搜索環(huán)境的不確定性，搜索概率圖中包含了UAV對(duì)搜索環(huán)境的先驗(yàn)信息，減小了搜索的盲目性。采用協(xié)同進(jìn)化遺傳算法進(jìn)行多UAV協(xié)同搜索路徑規(guī)劃，可在線滾動(dòng)生成局部最優(yōu)路徑，滿足實(shí)時(shí)性要求。

1 多機(jī)協(xié)同區(qū)域搜索問(wèn)題建模

1.1 環(huán)境模型

假設(shè)搜索區(qū)域?yàn)橐黄矫婢匦螀^(qū)域，其中分布著NT個(gè)目標(biāo)，NV架UAV進(jìn)入任務(wù)區(qū)域后對(duì)目標(biāo)進(jìn)行搜索。本文將搜索區(qū)域劃分為L(zhǎng)x×Ly的離散單元，稱(chēng)所有單元的集合 E={(m，n)|m=1，2，…，Lx，n=1，2，…，Ly}為搜索環(huán)境，(m，n)表示位于第m行第n列的單元。單元格(m，n)中目標(biāo)的真實(shí)狀態(tài)為 Smn∈{0，1}，Smn=1表示存在目標(biāo)。

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

1.2 UAV的狀態(tài)模型

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

圖1 無(wú)人機(jī)航向示意圖Fig.1 Sketch map of the orientation of UAV

1.3 搜索概率圖模型

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

搜索過(guò)程中，UAV根據(jù)機(jī)載傳感器的探測(cè)信息對(duì)概率圖進(jìn)行實(shí)時(shí)更新。若UAV在k時(shí)刻訪問(wèn)單元格(m，n)，則傳感器獲得探測(cè)信息 bk∈{0，1}(bk=1表示UAV在單元格(m，n)探測(cè)到目標(biāo))，則k+1時(shí)刻當(dāng)bk=1時(shí)，單元格(m，n)的目標(biāo)存在概率更新如式(1)所示，bk=0時(shí)如式(2)所示。

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

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

定義閾值 θ，當(dāng)單元格(m，n)的目標(biāo)存在概率Pmn(k)≥θ時(shí)，認(rèn)為該單元格中存在目標(biāo)。

2 協(xié)同搜索路徑規(guī)劃算法

2.1 協(xié)同進(jìn)化遺傳算法

協(xié)同進(jìn)化［2］是指生物與生物、生物與環(huán)境之間在進(jìn)化過(guò)程中的某種依存關(guān)系。也就是說(shuō)協(xié)同進(jìn)化算法不僅考慮單個(gè)種群之間的競(jìng)爭(zhēng)，而且考慮多個(gè)種群，以及生物與環(huán)境的競(jìng)爭(zhēng)、合作與共生的關(guān)系，多個(gè)物種通過(guò)相互間的作用，促使多個(gè)種群同時(shí)向前進(jìn)化。協(xié)同進(jìn)化算法主要分為兩大類(lèi):競(jìng)爭(zhēng)型協(xié)同進(jìn)化算法和合作型協(xié)同進(jìn)化算法。對(duì)于多UAV協(xié)同區(qū)域搜索這樣一個(gè)既有競(jìng)爭(zhēng)，更注重合作的博弈格局，合作型協(xié)同進(jìn)化算法是一種適宜的選擇。合作型協(xié)同進(jìn)化按照多UAV之間的合作與約束關(guān)系，通過(guò)對(duì)群體間有利于合作的個(gè)體進(jìn)行適應(yīng)度加強(qiáng)，促使群體向著有利于產(chǎn)生相互合作和共同適應(yīng)行為的方向進(jìn)化。因此本文采用合作型協(xié)同進(jìn)化算法進(jìn)行多UAV協(xié)同區(qū)域搜索的路徑規(guī)劃。

2.2 基于協(xié)同進(jìn)化遺傳的多UAV協(xié)同搜索算法

本文采用滾動(dòng)優(yōu)化思想，即在k時(shí)刻，限定各UAV向前規(guī)劃q步(q＞1為規(guī)劃路徑步數(shù))路徑，UAV只執(zhí)行規(guī)劃路徑的第一步，k+1時(shí)刻，基于新的系統(tǒng)狀態(tài)和環(huán)境信息重新規(guī)劃路徑。文中使用NV個(gè)子種群分別進(jìn)化NV架UAV的搜索路徑，若在k時(shí)刻，UAVi位于單元格(m，n)內(nèi)，則k時(shí)刻路徑規(guī)劃的結(jié)果為以(m，n)為起點(diǎn)的長(zhǎng)度為q的路徑。

2.2.1 編碼

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

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

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

2.2.2 適應(yīng)度

求子種群的適應(yīng)度時(shí)，待評(píng)價(jià)個(gè)體必須和其他種群的個(gè)體結(jié)合，組成完整的解。其中，選擇的其他種群的個(gè)體稱(chēng)為代表個(gè)體，論文中選擇其他子種群的最優(yōu)個(gè)體作為代表個(gè)體。對(duì)于初始子種群，選擇沿著個(gè)體代表的路徑進(jìn)行搜索獲得報(bào)酬ρ最大的個(gè)體作為代表個(gè)體。ρ的計(jì)算公式如式(4)所示。由于不考慮通信延遲，各子種群可以即時(shí)獲得其他子種群的代表個(gè)體，并與待評(píng)價(jià)個(gè)體結(jié)合，計(jì)算待評(píng)價(jià)個(gè)體的適應(yīng)度。

待評(píng)價(jià)個(gè)體的適應(yīng)度定義為在不與其他UAV發(fā)生碰撞的前提下(即UAV按待評(píng)價(jià)個(gè)體所示路徑移動(dòng)，在下一時(shí)刻所處的單元格與其他UAV按其代表個(gè)體所示路徑移動(dòng)，在下一時(shí)刻所處的單元格不相同)，沿著該個(gè)體代表的路徑進(jìn)行搜索所能獲得的報(bào)酬。如果沿著該路徑飛行會(huì)與其他UAV發(fā)生碰撞，該路徑就不可行，應(yīng)在其適應(yīng)度函數(shù)中增加懲罰項(xiàng)。

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

式中:ω1，ω2，ω3為加權(quán)系數(shù)，且 ω1+ ω2+ ω3=1，ω 為懲罰因子。Rc－1，c為沿規(guī)劃路徑，UAV在相鄰兩步之間移動(dòng)的距離。ρf為發(fā)現(xiàn)目標(biāo)報(bào)酬，計(jì)算式為

ρu為不確定度降低報(bào)酬，計(jì)算式為

2.2.3 進(jìn)化算子

子種群的進(jìn)化操作選取如下:采用輪盤(pán)賭方法進(jìn)行選擇操作;交叉操作中，對(duì)任意兩個(gè)父代染色體，當(dāng)產(chǎn)生的隨機(jī)數(shù)小于交叉概率Pc時(shí)，隨機(jī)選擇交叉點(diǎn)，進(jìn)行單點(diǎn)交叉;變異操作中，當(dāng)產(chǎn)生的隨機(jī)數(shù)小于變異概率Pm時(shí)，隨機(jī)選擇一點(diǎn)進(jìn)行變異。

2.2.4 算法步驟

本文提出的用于多UAV協(xié)同區(qū)域搜索路徑規(guī)劃的協(xié)同進(jìn)化遺傳算法的步驟如下所述。

Step 1 確定算法的控制參數(shù)，包括進(jìn)化子種群的規(guī)模Psize，基因的交叉概率Pc，變異概率Pm，協(xié)同進(jìn)化的代數(shù)T，算法的終止條件Tstop。

Step 2 令k=0，對(duì)UAVi，產(chǎn)生k時(shí)刻的q步最優(yōu)路徑。

1)令t=0，隨機(jī)生成Psize個(gè)染色體長(zhǎng)度為q的個(gè)體。

2)利用其他進(jìn)化子種群的代表個(gè)體，根據(jù)式(4)～式(5)計(jì)算每個(gè)待評(píng)價(jià)個(gè)體的適應(yīng)值，并進(jìn)行選擇、交叉和變異操作。

3)選擇最優(yōu)個(gè)體作為代表個(gè)體。

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

Step 3 執(zhí)行最優(yōu)路徑的第一項(xiàng)，移動(dòng)UAVi，并更新單元格和UAVi的狀態(tài)。

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

3 仿真分析

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

圖4 目標(biāo)分布圖Fig.4 The distribution of targets

圖5 和圖6分別為使用協(xié)同進(jìn)化算法和使用遺傳算法進(jìn)行路徑規(guī)劃的結(jié)果。當(dāng)目標(biāo)被發(fā)現(xiàn)后，由黑色的小方塊表示，從圖中可以清楚地看出找到了多少目標(biāo)，漏掉了多少目標(biāo)。

圖5 協(xié)同進(jìn)化遺傳算法的路徑規(guī)劃Fig.5 The path planning of CEGA

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

圖7 給出了在相同時(shí)間內(nèi)，分別使用協(xié)同進(jìn)化算法和遺傳算法發(fā)現(xiàn)目標(biāo)的數(shù)量和時(shí)刻。圖8為分別使用兩種算法，在相同時(shí)間內(nèi)，對(duì)環(huán)境不確定度的影響。從圖中可以看出:兩種算法中，無(wú)人機(jī)在進(jìn)入任務(wù)區(qū)域后都是對(duì)目標(biāo)概率較高的區(qū)域優(yōu)先進(jìn)行搜索，避免了對(duì)目標(biāo)概率為0的區(qū)域的無(wú)效搜索。在相同的時(shí)間內(nèi)，由于協(xié)同進(jìn)化算法考慮了協(xié)同因素，使多架UAV之間較好地進(jìn)行協(xié)調(diào)，避免了對(duì)同一區(qū)域的重復(fù)搜索，優(yōu)化了搜索效能。故使用協(xié)同進(jìn)化算法比使用遺傳算法對(duì)環(huán)境不確定度的降低程度稍大一點(diǎn)，并且使用協(xié)同進(jìn)化算法可以發(fā)現(xiàn)更多的目標(biāo)。因此，與遺傳算法相比，協(xié)同進(jìn)化算法具有更好的搜索效能。

圖7 兩種算法發(fā)現(xiàn)目標(biāo)圖Fig.7 Targets finded by two algorithms

圖8 兩種算法對(duì)環(huán)境不確定度的影響Fig.8 Effect of the two algorithms on environmental uncertainty

4 結(jié)束語(yǔ)

本文針對(duì)不確定環(huán)境下的多UAV協(xié)同搜索問(wèn)題，進(jìn)行了分析，建立了環(huán)境模型和搜索概率圖模型，并根據(jù)滾動(dòng)優(yōu)化思想，提出了基于協(xié)同進(jìn)化算法的多UAV協(xié)同搜索的路徑規(guī)劃方法。仿真結(jié)果表明，協(xié)同進(jìn)化算法充分利用了多UAV之間的協(xié)同信息，比遺傳算法具有更高的搜索效能。

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

［2］ 焦李成，劉靜，鐘偉才.協(xié)同進(jìn)化計(jì)算與多智能體系統(tǒng)［M］.北京:科學(xué)出版社，2006.

［3］ 夏歡，周德云，陳龍建.多無(wú)人機(jī)協(xié)同搜索路徑規(guī)劃方法研究［C］//中國(guó)航空學(xué)會(huì)航空武器系統(tǒng)分會(huì)2010年學(xué)術(shù)年會(huì)暨第三屆“中國(guó)航空武器裝備試驗(yàn)與發(fā)展學(xué)術(shù)論壇”論文集，2010:432-436.

［4］ 申曉寧，郭毓，陳慶偉，等.基于多目標(biāo)協(xié)同進(jìn)化算法的多機(jī)器人路徑規(guī)劃［J］.南京航空航天大學(xué)學(xué)報(bào)，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］ 劉國(guó)興，李敏強(qiáng).基于協(xié)同進(jìn)化的多目標(biāo)優(yōu)化算法研究［D］.天津:天津大學(xué)，2008.

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

［12］ 李子文，夏潔.無(wú)人偵察機(jī)路徑規(guī)劃方法研究［J］.系統(tǒng)仿真學(xué)報(bào)，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.