王寧，李哲，*，梁曉龍，侯岳奇，吳傲

（1.空軍工程大學(xué) 空管領(lǐng)航學(xué)院，西安 710051； 2.陜西省電子信息系統(tǒng)綜合集成重點實驗室，西安 710051）

廣域目標(biāo)搜索是現(xiàn)代作戰(zhàn)中的一項重要技術(shù)，美軍已將無人機（unmanned aerial vehicle，UAV）具備廣域目標(biāo)搜索能力確定為UAV技術(shù)的中長期發(fā)展目標(biāo)［1-4］。UAV集群具有卓越的廣域搜索能力，能夠通過UAV之間的協(xié)同合作，實現(xiàn)整體能力涌現(xiàn)，即系統(tǒng)涌現(xiàn)出的能力遠(yuǎn)超系統(tǒng)內(nèi)單架UAV能力的總和［5-6］。因此，使用多架UAV組成集群執(zhí)行目標(biāo)協(xié)同搜索任務(wù)得到了日益廣泛的關(guān)注［7-8］。其中，搜索區(qū)域處理與協(xié)同搜索策略是UAV集群協(xié)同搜索關(guān)注的2個主要問題［9］。已有諸多學(xué)者對上述問題進(jìn)行了深入的探索并取得了豐碩成果。

在搜索區(qū)域處理方面，提出的主要方法有凸多邊形區(qū)域分割、凹多邊形凸處理、Voronoi圖等，主要是將形狀復(fù)雜的搜索區(qū)域分割為特定形狀的子任務(wù)區(qū)域，進(jìn)而通過UAV集群內(nèi)部的任務(wù)分配提高UAV協(xié)同搜索效率。其中，Pehlivanoglu［10］和Guruprasad等［11］提出了使用Voronoi圖對搜索區(qū)域進(jìn)行分割的方法，受到了廣泛關(guān)注，但該方法分割出來的區(qū)域具有不確定性［9］，且運算量大，具有一定的局限性。謝朋志和魏晨［12］提出了一種任意搜索區(qū)域的等面積單側(cè)區(qū)域分割方法，先將任意多邊形采用格雷厄姆法拓展為凸多邊形，然后進(jìn)行等面積劃分，根據(jù)劃分區(qū)域形狀配置UAV起始位置，提高了UAV協(xié)同搜索效率；于駟男等［13］根據(jù)無人機數(shù)量、初始位置將凸多邊形搜索區(qū)域分割成若干子區(qū)域，以UAV總轉(zhuǎn)彎次數(shù)作為搜索效率評判標(biāo)準(zhǔn)，提出了一種協(xié)同區(qū)域分割的有效方法。但上述成果主要應(yīng)用于靜態(tài)搜索規(guī)劃中，無法有效應(yīng)對搜索過程中UAV故障、火力威脅等突發(fā)情況。

在協(xié)同搜索策略方面，主要包括滾動時域優(yōu)化（receding horizon optimization，RHO）［14-17］、動態(tài)規(guī)劃［18］、協(xié)同進(jìn)化算法［19］等方法。其中，文獻(xiàn)［15，20-21］提出的動態(tài)決策方法較為典型，通過模型預(yù)測控制（model predictive control，MPC）方法，使每架UAV根據(jù)當(dāng)前環(huán)境信息做出最大收益決策，并通過仿真實驗驗證了UAV協(xié)同搜索過程中動態(tài)決策相對預(yù)先規(guī)劃的突出優(yōu)勢。文獻(xiàn)［22］提出的分布式模型預(yù)測控制（distributed model predictive control，DMPC）框架將集中式多UAV在線優(yōu)化決策轉(zhuǎn)化為小規(guī)模分布式優(yōu)化決策，是一種有效降低搜索決策問題求解規(guī)模的算法，得到了廣泛應(yīng)用。但上述研究主要是針對形狀規(guī)則的任務(wù)區(qū)域展開的，仍然存在不足。其中，文獻(xiàn)［20-21］未考慮UAV集群協(xié)同的通信約束和防相撞約束；文獻(xiàn)［7］雖然考慮了集群協(xié)同的防相撞問題，但僅通過配置不同高度實現(xiàn)防相撞，并未考慮高度變化對UAV探測范圍產(chǎn)生的影響；文獻(xiàn)［15，23-24］使用了“粗粒度”的UAV運動模型，降低了決策結(jié)果的精細(xì)程度且未考慮集群協(xié)同搜索時的防相撞及抗毀性問題。

綜合國內(nèi)外研究現(xiàn)狀可以看出，UAV集群具備了一定程度的協(xié)同搜索能力，但存在以下不足：

1）動態(tài)決策搜索方法普遍面向規(guī)則的矩形搜索區(qū)域，對不規(guī)則區(qū)域的研究較少。

2）對集群協(xié)同搜索過程中的通信問題和避撞問題未予以考慮或過于簡化。

3）對UAV集群協(xié)同搜索過程中抗毀性的研究較少。

針對上述問題，本文做了以下工作：

1）建立了針對不規(guī)則搜索區(qū)域的環(huán)境地圖模型。

2）引入了協(xié)同搜索過程中防相撞與通信拓?fù)錀l件對UAV集群的約束。

3）在分布式最優(yōu)決策基礎(chǔ)上，引入了滾動優(yōu)化決策和MPC思想，實現(xiàn)了集群搜索過程中的意圖交互，保證了協(xié)同搜索任務(wù)中UAV集群在未知威脅條件下的可用性。

1 協(xié)同搜索任務(wù)建模

1.1 任務(wù)描述

UAV集群協(xié)同搜索任務(wù)通常分為區(qū)域覆蓋任務(wù)和目標(biāo)搜索任務(wù)［21-22］。前者是在難以獲取任務(wù)區(qū)域先驗信息的條件下，使UAV集群盡快完成最大化覆蓋面積的飛行。后者是在已知任務(wù)區(qū)域內(nèi)目標(biāo)位置、數(shù)量、重要性等先驗信息的條件下，綜合考慮飛行代價和任務(wù)效率，通過UAV集群實現(xiàn)對區(qū)域內(nèi)所有目標(biāo)信息的獲取。本文針對第1類問題展開研究，UAV集群攜帶通信設(shè)備和光學(xué)傳感器對未知任務(wù)區(qū)域展開搜索，如圖1所示。

圖1 UAV集群協(xié)同搜索示意圖Fig.1 Schematic diagram of UAV swarm collaborative search

1.2 任務(wù)區(qū)域建模

圖2為不規(guī)則任務(wù)區(qū)域Ω示意圖。首先，任選4個可行頂點構(gòu)造尺寸為Lx×Ly的外接矩形。然后，將此矩形區(qū)域按照固定間隔Δd柵格化為M×N的環(huán)境地圖。最后，建立笛卡兒坐標(biāo)系，分別用橫向坐標(biāo)x和縱向坐標(biāo)y來描述環(huán)境地圖中的每個柵格：

圖2 任務(wù)區(qū)域柵格化Fig.2 Rasterized task area

式中： 表示向上取整。

該環(huán)境地圖中任意柵格的位置可以表示為

進(jìn)一步定義k時刻環(huán)境地圖中柵格（i，j）的狀態(tài)：

式中：Ωc（k）為k時刻已搜索柵格；Ωnc（k）為k時刻未搜索柵格；I為非任務(wù)區(qū)域。從而可以得到k時刻的環(huán)境地圖矩陣GM×N（k）為

1.3 UAV系統(tǒng)模型

UAV在攜帶光學(xué)傳感器執(zhí)行搜索任務(wù)時，為保證成像尺寸的一致性，一般不進(jìn)行高度調(diào)整，而是通過調(diào)整偏航角完成避障、航線修正等動作。由于只關(guān)注UAV的運動軌跡，為簡化分析，將UAV視為二維空間中勻速運動的質(zhì)點［14-15］，其離散狀態(tài)空間方程為

式中：（xi（k），yi（k））為k時刻集群中UAVi在環(huán)境地圖中的位置；ψi為UAVi的航向角；控制變量ui為偏航角，滿足ui∈［-umax，umax］，umax為受機動性能限制下的最大轉(zhuǎn)彎角；v0為UAV平飛速度；Δt為決策步長。

記k時刻UAVi的狀態(tài)變量pi（k）為

則k+1時刻UAVi的狀態(tài)變量為

式中：f（·）為狀態(tài)轉(zhuǎn)移函數(shù)，由式（5）確定；ui（k）為該UAV在k時刻的控制變量。

進(jìn)而有UAVi在k+j時刻的狀態(tài)變量預(yù)測量為

式中：NUAV為UAV集群規(guī)模；T為預(yù)測周期。

在給定T步預(yù)測輸入后，可以根據(jù)式（7）預(yù)測出未來T步以內(nèi)的UAV航路，如圖3所示。

圖3 UAV i航路預(yù)測圖Fig.3 UAV i route forecast chart

2 環(huán)境地圖更新與融合

2.1 UAV探測矩陣

考慮到CCD、CMOS等光學(xué)傳感器的成像范圍一般為矩形，先將UAV傳感器探測模型簡化為以UAV質(zhì)點為中心的W×H矩形區(qū)域。然后，將該矩形區(qū)域柵格化為P×Q個柵格，如圖4所示。

圖4 UAV探測區(qū)域柵格化Fig.4 Rasterized UAV detection area

進(jìn)而可以確定UAV探測矩陣ΓP×Q的行數(shù)P和列數(shù)Q為

式中：W和H分別為傳感器有效探測區(qū)域的寬度和長度；Δd為環(huán)境地圖中柵格的尺寸大??；為向下取整函數(shù)。

結(jié)合式（3）定義ΓP×Q中的值全為-1，得到最終的UAV探測矩陣為

2.2 環(huán)境地圖更新算子

借鑒文獻(xiàn)［21］中使用Hadamard積進(jìn)行環(huán)境地圖矩陣更新的思想，定義UAV探測矩陣與環(huán)境子矩陣之間的信息更新算子“?”：

其物理含義為：當(dāng)UAV探測未知柵格后，該算子可將環(huán)境地圖矩陣中該柵格狀態(tài)由-1變?yōu)?1，即由未知轉(zhuǎn)變?yōu)橐阎?；?dāng)UAV探測非任務(wù)區(qū)域時，環(huán)境信息矩陣中相應(yīng)柵格的狀態(tài)仍為0，即環(huán)境地圖不進(jìn)行更新；當(dāng)UAV探測已探測柵格后，環(huán)境地圖矩陣中仍將該柵格狀態(tài)標(biāo)記為+1。

其數(shù)學(xué)運算式為

將UAV探測矩陣與環(huán)境地圖矩陣中的相應(yīng)環(huán)境子矩陣進(jìn)行信息更新運算，即可實現(xiàn)環(huán)境地圖矩陣的更新，如圖5所示。

圖5 環(huán)境地圖矩陣更新流程Fig.5 Update process of environment map matrix

2.3 環(huán)境地圖融合算子

通過定義環(huán)境地圖更新算子，每架UAV在搜索過程中可根據(jù)自身決策量更新環(huán)境地圖。但要獲取集群協(xié)同搜索過程中不斷更新的全局環(huán)境信息，還需對每架UAV更新的環(huán)境地圖進(jìn)行整合。文獻(xiàn)［14］提出了廣播式通信條件下的地圖信息融合方法，通過獲取每架UAV的實時決策量集中更新環(huán)境地圖，實現(xiàn)了集群協(xié)同搜索過程中的環(huán)境地圖融合，但該方法對通信條件要求高且運算量較大。因此，本文提出一種分布式環(huán)境地圖融合方法，每架UAV僅根據(jù)自身狀態(tài)更新環(huán)境地圖矩陣。然后，通過環(huán)境地圖融合算子對其他UAV的環(huán)境地圖矩陣進(jìn)行環(huán)境信息融合，能夠減少每架UAV進(jìn)行環(huán)境地圖更新所需的運算量。

設(shè)k時刻UAV通過自身狀態(tài)更新所獲得的環(huán)境地圖矩陣為Gi（k），此時可接受其他UAV的環(huán)境地圖矩陣為Gj≠i（k），定義環(huán)境地圖矩陣中元素融合運算為

式中：“⊙”為環(huán)境信息融合算子，運算結(jié)果如表1所示。

表1 環(huán)境地圖融合算子運算規(guī)則Table 1 Environmental map fusion operator operation rules

與文獻(xiàn)［14，21］提出的環(huán)境信息融合方法相比，通過環(huán)境地圖融合算子進(jìn)行環(huán)境融合時，不需要根據(jù)其他UAV預(yù)測控制量更新環(huán)境地圖，只需根據(jù)自身預(yù)測控制量更新環(huán)境地圖矩陣。然后，通過環(huán)境地圖融合算子與獲得的其他UAV環(huán)境地圖矩陣進(jìn)行融合計算，即可得到實時環(huán)境地圖矩陣。

此外，在文獻(xiàn)［14-15］中，當(dāng)k時刻某架UAV通信中斷，后續(xù)決策就會一直缺失k時刻該UAV的決策信息。而通過意圖交互方法決策時，每架UAV始終獲取其他UAV的最新環(huán)境信息矩陣，即使某架UAV通信中斷一定時間，一旦通信恢復(fù)就能夠恢復(fù)該UAV歷史決策信息，使后續(xù)決策不受通信中斷的影響。

3 搜索回報函數(shù)與意圖交互策略

3.1 搜索回報函數(shù)

通過搜索回報函數(shù)實現(xiàn)UAV搜索過程中的路徑?jīng)Q策是UAV集群協(xié)同搜索的關(guān)鍵［7］。針對無先驗條件下的協(xié)同搜索問題，主要考慮了以下約束條件：

1）集群中每架UAV飛行時傾向于選擇覆蓋率增量最高的方向。首先，計算k時刻區(qū)域覆蓋率為

式中：1gij（k）為隨機變量，當(dāng)gij（k）＞0時其值為1，反之為0。

則k～k+1時刻的覆蓋率增量為

2）定義集群中每架UAV之間的安全距離為ds，記第i架UAV與集群中第j架UAV之間的距離為dij（k）：

約束條件有

則集群防相撞的約束函數(shù)為

3）為使協(xié)同搜索過程中UAV盡可能多地獲取其他UAV的搜索意圖，增加通信約束條件：

式中：dc為UAV的機間通信距離。

4）作為UAV的主要控制變量，偏航角的調(diào)整往往會帶來較大的能量與時間損耗。因此，增加偏航角調(diào)整約束條件，偏航角調(diào)整的約束函數(shù)為

5）受任務(wù)區(qū)域邊界限制，需要在UAV選擇路徑時增加強約束條件，使其不能越出任務(wù)區(qū)域邊界。文獻(xiàn)［21］所采用的勢函數(shù)方法會使所有UAV傾向于飛向任務(wù)區(qū)域中心，最終影響搜索效率并帶來相撞風(fēng)險。借鑒文獻(xiàn)［25］中地理圍欄的思想，設(shè)計了約束函數(shù)式（21），UAV搜索視野中無效區(qū)域一旦超過三分之一，回報函數(shù)會迅速下降。因此，k時刻UAV邊界約束條件為

綜上所述，可以進(jìn)一步定義搜索過程中每架UAV選擇路徑時的回報函數(shù)為

式中：ωt為平衡每個約束條件的取值。

3.2 基于MPC和PSO的意圖交互決策

在UAV集群協(xié)同搜索過程中，本文引入了滾動時域控制中的滾動優(yōu)化決策思想（rolling horizon optimization decision，RHOD）。首先，在柵格化搜索區(qū)域和確立搜索回報函數(shù)的基礎(chǔ)上，集群中每架UAV依次采用MPC方法［21］進(jìn)行最優(yōu)控制輸入預(yù)測，并根據(jù)輸入預(yù)測更新環(huán)境地圖。此時每架UAV所做出的決策都是建立在得知前一架UAV決策基礎(chǔ)上進(jìn)行的，從而實現(xiàn)了UAV協(xié)同搜索過程中的意圖交互決策。

針對大規(guī)模的UAV集群，本文提出了基于DMPC的分布式意圖交互決策。首先，集群中每架UAV根據(jù)當(dāng)前環(huán)境信息同時做出預(yù)測決策，并根據(jù)預(yù)測決策量更新環(huán)境地圖矩陣，生成預(yù)測環(huán)境地圖矩陣。然后，將該預(yù)測環(huán)境地圖矩陣向集群中其他UAV廣播，每架UAV將從集群其他成員處獲取的預(yù)測環(huán)境地圖矩陣融合成決策環(huán)境信息矩陣（見圖6），并在此基礎(chǔ)上做出自身決策，從而實現(xiàn)UAV集群規(guī)模較大時的協(xié)同搜索決策。

圖6 決策環(huán)境信息矩陣產(chǎn)生流程Fig.6 Decision environment information matrix generation process

對于集群UAVi，其搜索過程中的MPC決策流程如圖7所示。

圖7 UAV集群環(huán)境地圖矩陣更新流程Fig.7 UAV swarm enviornment map update process

綜上所述，可將集群搜索意圖交互決策流程分為3步：

步驟1 意圖產(chǎn)生。

UAVi基于自身環(huán)境地圖矩陣Gi（k）和自身狀態(tài)pi（k）對累積搜索回報函數(shù)進(jìn)行優(yōu)化求解，此時不考慮其他UAV的運動情況。其H步累積回報函數(shù)下的分布式模型預(yù)測控制結(jié)構(gòu)可以表示為

步驟2 意圖交互與融合。

對于小規(guī)模UAV集群的區(qū)域協(xié)同搜索，采用基于RHO的集中式意圖交互策略，如圖8所示。其實質(zhì)是一種順序決策，中央節(jié)點先根據(jù)初始環(huán)境地圖矩陣和UAV1初始位置，通過搜索回報函數(shù)求出決策控制量u1（0），并在此基礎(chǔ)上更新中央環(huán)境地圖矩陣G（0）。集群其他成員在中央環(huán)境地圖矩陣的基礎(chǔ)上，依次在前一架UAV決策意圖上進(jìn)行決策，直至所有UAV完成一輪決策。在協(xié)同搜索過程中，這種決策方式要求中央節(jié)點始終能與所有UAV保持通信，是一種“星形”通信拓?fù)浣Y(jié)構(gòu)，且運算量會隨著集群規(guī)模的增加迅速增長［22］，因此，僅適用于小規(guī)模UAV集群。

圖8 集中式意圖交互Fig.8 Centralized intention interaction

圖9 分布式意圖交互Fig.9 Distributed intention interaction

步驟3 集群分布式?jīng)Q策。

式中：“*”為計算出的最優(yōu)控制決策；u為無人機可以采取的決策量；u*為無人機的最優(yōu)決策量。

意圖交互決策算法偽代碼如下：

4 仿真分析

為驗證本文算法的有效性，分別對無人機集群搜索進(jìn)行分布式?jīng)Q策仿真和意圖交互決策仿真。仿真條件為i5-9300H，主頻2.40 GHz，16 GB內(nèi)存，仿真中所用算法參數(shù)如表2所示。

表2 算法參數(shù)Table 2 Algorithm parameters

4.1 小規(guī)模集群協(xié)同搜索仿真

設(shè)定任務(wù)區(qū)域為不規(guī)則多連通域，如圖10所示。任務(wù)區(qū)域外接矩形邊界為800 m×600 m。在外接矩形中，用黑色表示任務(wù)區(qū)域，用灰色表示非任務(wù)區(qū)域。其中，非任務(wù)區(qū)域可根據(jù)任務(wù)區(qū)域邊界、敵方火力范圍和外部障礙物位置等信息進(jìn)行設(shè)置。設(shè)定UAV飛行高度為8 m，光學(xué)傳感器成像范圍為20 m×16 m，4架UAV從任務(wù)區(qū)域不同位置進(jìn)入，進(jìn)入點坐標(biāo)分別為（100，0）、（300，0）、（500，0）、（700，0），單位均為米/m。UAV均以10 m/s速度勻速飛行，最大轉(zhuǎn)彎角為90°，仿真步長Δt=1 s，預(yù)測步長為1 s，仿真時間為600 s。

圖10 三種搜索算法仿真結(jié)果Fig.10 Simulation results of three search algorithms

分別運用無意圖交互的個體最優(yōu)決策、分布式意圖交互決策和集中式意圖交互決策進(jìn)行對比仿真。仿真結(jié)果如圖10所示。

從仿真結(jié)果可以看出，UAV集群在對不規(guī)則任務(wù)區(qū)域協(xié)同搜索過程中，有效避開了非任務(wù)區(qū)域。從圖10（a）中可以看出，在滿足通信、防相撞約束的條件下，缺少意圖交互的UAV集群在決策時會產(chǎn)生大量的重復(fù)搜索，導(dǎo)致整體搜索效率下降。圖10（b）中，集群中每架UAV在獲得其他UAV決策意圖后，會做出盡量避免與其他UAV搜索區(qū)域重復(fù)的決策，使集群的整體搜索效率明顯提高。圖10（c）中，每架UAV根據(jù)自身編號在獲取前一架UAV決策的基礎(chǔ)上進(jìn)行決策，從而獲得更接近當(dāng)前全局最優(yōu)解的決策。從圖11中可以看出，相較個體最優(yōu)決策，通過意圖交互能夠有效提高集群的協(xié)同搜索效率。

圖11 三種搜索算法覆蓋率變化曲線Fig.11 Coverage change curves of three search algorithms

4.2 大規(guī)模集群協(xié)同搜索仿真

集中式意圖交互決策雖然能夠得到全局最優(yōu)決策序列，但是其求解過程是在中央節(jié)點上進(jìn)行的，隨著UAV數(shù)量增加，其求解時間會迅速增大，進(jìn)而導(dǎo)致無法在線實時決策［14，22］。而分布式意圖交互決策能夠適用于較大規(guī)模的UAV集群協(xié)同搜索決策，以包含10架UAV的集群為例進(jìn)行仿真，結(jié)果如圖12所示。

設(shè)定不規(guī)則任務(wù)區(qū)域外接矩形邊界為800 m×600 m，集群中10架UAV的初始位置和航向隨機分布，機間安全距離為20 m，仿真時間為360 s。設(shè)定UAV2、UAV3、UAV7、UAV8分別于100 s、120 s、330 s、300 s處被擊毀，仿真結(jié)果如圖12所示，可以看出在4架UAV被擊毀的條件下，UAV集群仍然有效地完成了協(xié)同搜索任務(wù)。從圖13中可以看出，在集群協(xié)同搜索過程中，機間距離始終大于所設(shè)定的機間安全距離20 m，滿足了集群的防相撞要求。從圖14可以看出，在集群中部分UAV被擊毀的時刻，搜索覆蓋率受到一定影響，但仍然能有效增長，最終完成協(xié)同搜索任務(wù)。

圖12 10架UAV集群協(xié)同搜索仿真結(jié)果Fig.12 Collaborative search simulation results for swarm with 10 UAVs

圖13 集群中機間最小距離曲線Fig.13 Curve of minimum distance between UAVs of swarm

圖14 覆蓋率變化曲線Fig.14 Change curve of coverage

5 結(jié) 論

1）算法在實驗仿真條件下實現(xiàn)了較高的區(qū)域覆蓋率，對比了個體最優(yōu)決策與協(xié)同決策的搜索效率，體現(xiàn)了意圖交互策略在UAV集群搜索任務(wù)中的優(yōu)勢。

2）采用了DMPC框架，使無人機決策過程中能夠考慮長期收益并具有較快的決策速度，避免了集中式意圖交互決策中較大的運算量。

3）利用環(huán)境地圖更新算子和環(huán)境地圖融合算子實現(xiàn)了環(huán)境地圖的分布式更新與快速共享。

4）以區(qū)域覆蓋率為引導(dǎo)，在通信、防相撞等關(guān)鍵約束的條件下，通過實驗仿真驗證了算法對大規(guī)模集群執(zhí)行搜索任務(wù)時的可行性。

算法實現(xiàn)了無人機集群在火力威脅場景下的有效覆蓋搜索，但針對集中式協(xié)同搜索和分布式協(xié)同搜索算法復(fù)雜度的對比分析，還有待進(jìn)一步更深入的研究。