基于搜索意圖交互的無人機集群協同搜索算法

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

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

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

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

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

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

1）動態決策搜索方法普遍面向規則的矩形搜索區域，對不規則區域的研究較少。

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

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

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

1）建立了針對不規則搜索區域的環境地圖模型。

2）引入了協同搜索過程中防相撞與通信拓撲條件對UAV集群的約束。

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

1 協同搜索任務建模

1.1 任務描述

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

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

1.2 任務區域建模

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

圖2 任務區域柵格化Fig.2 Rasterized task area

式中： 表示向上取整。

該環境地圖中任意柵格的位置可以表示為

進一步定義k時刻環境地圖中柵格（i，j）的狀態：

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

1.3 UAV系統模型

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

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

記k時刻UAVi的狀態變量pi（k）為

則k+1時刻UAVi的狀態變量為

式中：f（·）為狀態轉移函數，由式（5）確定；ui（k）為該UAV在k時刻的控制變量。

進而有UAVi在k+j時刻的狀態變量預測量為

式中：NUAV為UAV集群規模；T為預測周期。

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

圖3 UAV i航路預測圖Fig.3 UAV i route forecast chart

2 環境地圖更新與融合

2.1 UAV探測矩陣

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

圖4 UAV探測區域柵格化Fig.4 Rasterized UAV detection area

進而可以確定UAV探測矩陣ΓP×Q的行數P和列數Q為

式中：W和H分別為傳感器有效探測區域的寬度和長度；Δd為環境地圖中柵格的尺寸大小；為向下取整函數。

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

2.2 環境地圖更新算子

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

其物理含義為：當UAV探測未知柵格后，該算子可將環境地圖矩陣中該柵格狀態由-1變為+1，即由未知轉變為已知；當UAV探測非任務區域時，環境信息矩陣中相應柵格的狀態仍為0，即環境地圖不進行更新；當UAV探測已探測柵格后，環境地圖矩陣中仍將該柵格狀態標記為+1。

其數學運算式為

將UAV探測矩陣與環境地圖矩陣中的相應環境子矩陣進行信息更新運算，即可實現環境地圖矩陣的更新，如圖5所示。

圖5 環境地圖矩陣更新流程Fig.5 Update process of environment map matrix

2.3 環境地圖融合算子

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

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

式中：“⊙”為環境信息融合算子，運算結果如表1所示。

表1 環境地圖融合算子運算規則Table 1 Environmental map fusion operator operation rules

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

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

3 搜索回報函數與意圖交互策略

3.1 搜索回報函數

通過搜索回報函數實現UAV搜索過程中的路徑決策是UAV集群協同搜索的關鍵［7］。針對無先驗條件下的協同搜索問題，主要考慮了以下約束條件：

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

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

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

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

約束條件有

則集群防相撞的約束函數為

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

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

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

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

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

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

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

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

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

圖6 決策環境信息矩陣產生流程Fig.6 Decision environment information matrix generation process

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

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

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

步驟1 意圖產生。

UAVi基于自身環境地圖矩陣Gi（k）和自身狀態pi（k）對累積搜索回報函數進行優化求解，此時不考慮其他UAV的運動情況。其H步累積回報函數下的分布式模型預測控制結構可以表示為

步驟2 意圖交互與融合。

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

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

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

步驟3 集群分布式決策。

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

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

4 仿真分析

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

表2 算法參數Table 2 Algorithm parameters

4.1 小規模集群協同搜索仿真

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

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

分別運用無意圖交互的個體最優決策、分布式意圖交互決策和集中式意圖交互決策進行對比仿真。仿真結果如圖10所示。

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

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

4.2 大規模集群協同搜索仿真

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

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

圖12 10架UAV集群協同搜索仿真結果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 結 論

1）算法在實驗仿真條件下實現了較高的區域覆蓋率，對比了個體最優決策與協同決策的搜索效率，體現了意圖交互策略在UAV集群搜索任務中的優勢。

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

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

4）以區域覆蓋率為引導，在通信、防相撞等關鍵約束的條件下，通過實驗仿真驗證了算法對大規模集群執行搜索任務時的可行性。

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