基于Voronoi圖最近鄰協商的多機協同追捕方法

張云赫， 蘇立晨， 董云帆， 劉瑜， 李宇萌

(1.北京航空航天大學 電子信息工程學院， 北京 100191； 2.北京航空航天大學 自動化科學與電氣工程學院， 北京 100191；3.北京電子工程總體研究所， 北京 100854；4.清華大學 信息科學技術學院， 北京 100084)

隨著我國低空空域持續開放，無人機“黑飛”事件頻發，對公共安全、國防安全帶來巨大挑戰。近年來，以協同追捕為代表的柔性反制技術為復雜低空安全管控提供了新的思路。協同追捕通過控制多個裝備捕獲裝置的追捕無人機，對“黑飛”無人機進行協同追蹤并將其網捕，可更有效地消除“黑飛”無人機帶來的安全隱患，具有重要理論研究意義與實際工程應用價值。

協同追捕問題的本質是一組追捕者依據協同策略與逃逸者連續交互、互相對抗、動態博弈的過程[1-3]，已受到國內外學者高度關注。對于協同追捕問題的求解，是Isaacs[4-6]提出的微分博弈方法，他從狀態交互的角度建立了微分博弈方程組，實現了對雙方動態對抗關系的建模與刻畫。后續工作在此基礎上建立了線性、非線性微分追逃博弈模型[7-15]，分別討論并解決了在不同運動規律下的協同追捕問題。然而此類方法在求解過程中涉及的變量多、維度高，求解速度遲緩。針對這一不足，Parsons[16-17]將圖論概念引入協同追捕問題，提出了離散微分博弈方法，通過在圖上的離散化建模，只求解在離散時刻點上的追捕策略，時刻點間的策略通過平滑近似獲取。此類方法雖然顯著提高了求解速度，但考慮協同追捕問題固有的連續性，離散化表征和平滑近似必然導致精度上的損失，追捕策略在連續時間域上的整體性能難以保證。

此后，基于圖決策理論的方法也被用于解決多智能體協同追捕問題，其中較為經典的是Voronoi圖。由Tsiotras[18]通過Voronoi圖將連續的動作空間轉化為離散的圖單元，極大地縮小了動作搜索空間，降低了計算復雜度，提升了計算效率。同時動態Voronoi圖劃分的時變特性又保證了可行解的連續性，一定程度上平衡了求解速度和計算精度，實現了對移動目標的高效追捕，然而該工作是在逃逸者的控制策略已知的前提下設計協同追捕策略，適應性較差。針對這一問題，張偉等[19-20]基于Voronoi圖提出了一種分布式多對一追捕策略，并驗證了在逃逸者控制策略未知情況下，該追捕策略依然能實現對逃逸者的追捕，然而以上工作均只適用于理想環境下的多對一的協同追捕問題，無法應用于存在多個逃逸者的協同追捕場景。

在多無人機協同追捕問題中，Voronoi圖法通過將有界環境劃分，將連續的動作空間離散化，一方面極大地減小了動作搜索空間，提高了計算效率，適合無人機進行實時決策；另一方面將各架無人機分隔開，保證了一定的安全性。由于實際城市低空環境地形地貌復雜，追捕無人機可能受到障礙物遮擋導致通信受限，然而現有工作中大多設定為無人機均可獲取完備信息，無法適用于存在障礙物且機間通信受限的場景中。

因此，本文重點開展多對多協同追捕問題研究，在信息非完備和多障礙物的環境約束下建立了通信約束與可行域受限下的協同追捕模型，基于Voronoi圖的劃分對環境進行表征，提出了基于最近鄰協商面積最小化的追捕策略求解方法，有效提升了多機協同追捕的可靠性與魯棒性。

1 問題描述與建模

(1)

(2)

追捕者的目標是在有限時間內抓住所有逃逸者，對于第i個逃逸者來說，即至少有一個追捕者離該逃逸者的距離小于抓取半徑rc：

(3)

(4)

(5)

式中tΔ表示時間步。

2 基于Voronoi圖的協同追捕方法

2.1 Voronoi圖的基本性質

本文以Voronoi圖為基本框架，將各架無人機用質點表示，以該質點為生成元構成Voronoi圖，對二維有界環境進行劃分(如圖1所示)，并基于Voronoi圖的以下幾個基本性質來定義協同追捕問題模型：

圖1 Voronoi圖劃分場景示意Fig.1 Schematic diagram of Voronoi partition

1)每個Voronoi元胞內有一個生成元(追捕者或逃逸者所在位置)；

2)每個Voronoi元胞內的點到該生成元距離小于到其他生成元的距離；

3)Voronoi元胞邊界上的點到生成此邊界的生成元距離相等；

4)有共同邊界的2個Voronoi元胞互為相鄰元胞。

圖中每架無人機根據所生成的Voronoi元胞及相鄰元胞的相關信息進行決策，這極大地減小了其動作搜索空間，提高了生成決策的計算效率。

2.2 基于面積最小化的協同追捕策略

對于追捕者而言，逃逸者的具體控制策略不可獲知，但逃逸者僅會在其安全到達集內運動[21]。安全到達集是指逃逸者能快于其他追捕者直線到達的點的集合，逃逸者可到達該集合區域內的任何一點，從而避免被追捕者抓取。當追捕者和逃逸者擁有相同的最大速度和動力學方程時，安全到達集也就轉化為了有界環境下的Voronoi圖劃分，即逃逸者的Voronoi元胞表示為：

?j∈{1,2,3,…，N}}

(6)

式中q表示Voronoi元胞內的點。

由于逃逸者只能移向自己安全到達集內的點，追捕者期望通過最小化逃逸者的安全到達集的大小，也就是最小化逃逸者所生成的Voronoi圖劃分區域的面積來逐漸縮小逃逸者的可行動作空間，從而最終完成對逃逸者的抓取，把這個策略稱為“面積最小化”策略，該策略將會把追捕者引導至追捕者和逃逸者共同Voronoi劃分邊界的中點。

假設逃逸者所生成的Voronoi劃分區域為Ve，其面積大小為Ae，則面積的大小可以表示為：

(7)

式中q表示逃逸者生成Voronoi區域Ve內的點，則Ae的導數為：

(8)

希望通過追捕者采取策略來持續地減小Ae，可以把上面公式的右邊第2項分解為單個的減小量，如果最大化Ae的減小速度，則每個追捕者的速度為：

(9)

由此，依據面積最小化策略的思想，可以得到追捕者的控制速度。各追捕者采取這樣的速度選擇，Ae可以沿負梯度方向，即以最快的速度減小。

2.3 追捕策略可行性證明

本文將依據5個結論來簡要證明在該策略下，追捕者可以在有限時間內完成對單個逃逸者的抓取。

(10)

結論證明：對于式(5)中定義的Ae，通過萊布尼茨積分公式，可得Ae的導數簡化為：

(11)

(12)

應用結論1，將式(10)代入式(9)，可得追捕者的速度簡化為：

(13)

(14)

式中Cb為追捕者xp和逃逸者xe的Voronoi圖的共同邊界的重心。

結論證明：對于單個追捕者和單個逃逸者的場景，Ae的導數簡化為：

(15)

將追捕者速度，式(13)代入式(15)，可得：

(16)

從而得到Ae≤0，且當Ae=0時，可以得到：

(17)

根據結論2可以得到，對于逃逸者來說，能夠保持其安全到達集大小的唯一策略就是移向Voronoi共同邊界的重心Cb。定義d為追捕者和逃逸者之間的距離，則：

d=‖xp-xe‖2=(xp-xe)T(xp-xe)

(18)

(19)

結論證明：距離d的導數為

(20)

(21)

由于Cb在相鄰2個Voronoi元胞的公共邊界上，根據2.1節Voronoi圖的性質(3)，可得‖Cb-xp‖=‖Cb-xe‖，因此式(21)簡化為：

(22)

(23)

(24)

移項后得到：

(25)

放縮合并，得到：

(26)

(27)

E=kAe+d

(28)

結論5對于系統函數(28)，在采取策略，式(13)的情況下，如果在t0時刻前沒有完成抓取，則：

E(t)

(29)

結論證明：根據結論4，得到以下的2個條件：

(30)

(31)

則系統函數的導數為：

(32)

(33)

(34)

經過一系列的推導證明，可得到追捕者的速度簡化為：

(35)

由此可以看到，該追捕策略將引導追捕者移向和逃逸者共同Voronoi邊界的重心，在二維環境中，也就是移向共同邊界的中點。

通過以上推導，給出了多無人機的協同追捕策略，證明了在有界凸環境內，無論逃逸者采取何種控制策略，追捕者均可確保在有限時間內完成對其的抓取，在這一前提下，通過設定逃逸者以“move-to-centroid”策略[22]盡可能保持其安全到達集的大小以及所覆蓋區域的均勻劃分：

(36)

式中CV表示逃逸者生成Voronoi劃分區域的形心。由此可知，該策略將逃逸者引向生成Voronoi劃分區域的形心。

2.4 通信受限下的協同追捕策略

由于低空運行環境復雜、約束多元，通信鏈路可能受到地形遮擋，導致追捕無人機不能實時地和較遠處的無人機進行協商，從而共享目標。

因此，本節針對通信受限條件，提出了一種基于最近鄰協商面積最小化的追捕策略，該策略假設每個追捕者和相鄰的追捕者及逃逸者可進行通信，以獲取相鄰Voronoi元胞的相關信息，通過依次協同最小化相鄰逃逸者的Voronoi元胞面積，實現對逃逸者的追捕。由此，每個追捕者鎖定距離最近的相鄰逃逸者為目標，速度則指向與該逃逸者的Voronoi元胞公共邊的中點，如果追捕者相鄰元胞沒有逃逸者，速度則指向距離最近的逃逸者，對于逃逸者而言，為了盡可能保證各自安全到達集的大小，其速度指向各自生成Voronoi單元的形心。相比面積最小化策略，具有以下優勢：

1)每個追捕者只需要通過和相鄰追捕者，逃逸者進行通信，獲取相鄰Voronoi元胞的相關信息，可適用于信息不完備條件；

2)追捕者在過程中可以更換目標，不需要與其他追捕者進行協商共同目標，可適用于通信受限條件。

(37)

對于逃逸者，其控制策略為移向Voronoi元胞的形心：

(38)

式中：Vi是第i個逃逸者根據所有無人機位置所生成的Voronoi元胞；CVi為該Voronoi元胞的形心。

2.5 可行域受限下的追捕策略

本節針對存在多元障礙物的場景，在基于最近鄰協商的面積最小化策略的基礎上，加入了緊急避障機制，提出了可行域受限下的協同追捕策略，具體如下：

1)計算有界環境Voronoi圖劃分過程中，需要把障礙物中心當作靜態智能體處理，參與Voronoi圖構建，同時在更新Voronoi元胞信息時，需要給障礙物生成的Voronoi元胞進行特殊標記，追捕者可以根據該特殊標記識別障礙物元胞；

2)為了防止追捕者與障礙物相撞，追捕者實時地記錄離附近障礙物的距離，當該距離即將小于設定的安全半徑時，追捕者立即采取緊急避障機制，即上述“move-to-centroid”策略，當距離大于安全距離后，恢復到之前的控制策略。

2.6 算法仿真流程

算法流程主要分為場景定義，循環控制兩個部分。場景定義主要包括追捕者和逃逸者的數量，速度大小，位置，存活狀態，時間步長，邊界大小以及抓取半徑等參數的初始化。

算法流程圖如圖2所示，循環控制主要包含計算各智能體有界環境下的Voronoi圖劃分，計算追捕者和逃逸者的速度方向，追捕者逃逸者的位置更新以及計算是否觸發抓取條件等幾個部分。

圖2 算法流程Fig.2 Algorithm flowchart

3 仿真實現與結果分析

根據前文提出的追捕逃逸策略進行場景仿真，場景為100 m×100 m的二維有界凸環境(本節以下仿真效果圖中1個單位表示100 m)，無障礙物，有4個追捕者和8個逃逸者，場景示意圖如圖3所示。

圖3 仿真場景示意Fig.3 Schematic diagram of simulation scenarios

圖中“o”為追捕者，“*”為逃逸者,不存在障礙物。

3.1 通信受限下的多對多追捕仿真結果

場景為100 m×100 m的二維有界凸環境，存在障礙物，有4個追捕者和8個逃逸者。其中追捕者，逃逸者和障礙物的初始位置均為隨機生成，時間步長設置為1 s，抓取半徑設置為5 m，仿真效果如圖4所示。

圖4 協同追捕效果Fig.4 Schematic diagram of cooperative pursuit

由圖4可以看到，隨著時間的演化，4個追捕者最終完成了對所有逃逸者的追捕。在圖4(a)中，由于追捕者之間的通信受限，每個追捕者只能獲取相鄰Voronoi元胞的信息，比如追捕者X1僅能根據X4、X8、X12的信息進行決策，其目標為相鄰最近的逃逸者，在圖4(b)中，4個追捕者開始逐漸包圍在角落里“無處可走”的逃逸者X8、X11，最終，如圖4(d)所示，多個追捕者最終依次完成了對多個逃逸者的協同追捕。

3.2 可行域受限下的多對多追捕仿真結果

本節采用的場景為100 m×100 m的二維有界凸環境，存在障礙物，有4個追捕者，4個逃逸者和4個障礙物。其中追捕者，逃逸者和障礙物的初始位置均隨機生成，圓形區域表示障礙物，所有追捕者不能進入障礙物區域。仿真的時間步長設置為1 s，抓取半徑和障礙物半徑均設定為5 m，障礙物半徑設定為3 m。一次試驗過程中的幾幀圖像，仿真效果如圖5所示。

圖5 障礙物場景下追捕效果Fig.5 Schematic diagram of cooperative pursuit under obstacle scenarios

由圖5可以看到，隨著時間的演化，4個追捕者在規避障礙物的同時完成了對所有逃逸者的追捕。在圖5(a)中，通過障礙物參與Voronoi圖劃分，將追捕者與障礙物分隔開，使其可以在追捕過程中有效地規避障礙物。

3.3 基線策略對比分析

上述仿真結果表示，提出的策略可以在通信受限和可行域受限的約束下實現對所有逃逸者的協同追捕，本節將和基線策略對比所有逃逸者被抓取的完成時間來分析多無人機協同追捕策略的效率。

首先給出基線策略：對于追捕者，不進行Voronoi圖劃分，追捕者的速度直接指向距離最近的逃逸者；對于逃逸者而言，為了使其在設定的有界環境內運動，其速度指向生成Voronoi元胞的形心。然后在不同追捕者—逃逸者數量比的情況下，分別仿真試驗20次，記錄基線策略和基于Voronoi圖劃分提出的協同追捕策略下的抓取時間，對比分析所提出協同追捕策略的效率。圖6給出了2種策略在不同追捕者—逃逸者數量比的情況下多次仿真試驗中抓取時間的最大值，最小值和平均值。上圖中Am策略是本文提出的基于Voronoi圖最近鄰協商的多對多協同追捕策略。

圖6 不同策略抓取時間對比Fig.6 Comparison of capturing durations under different strategies

如圖6所示，當追捕者的數量多于逃逸者數量時，Am策略抓取時間的平均值比基線策略要短，這說明相比基線策略，Am策略效率更高；當逃逸者數量與追捕者數量持平甚至高于追捕者數量時，Am策略的優勢則逐漸減小，這說明Am策略相比于基線策略不太適用于大量逃逸者的情況。但由于民航空管的管控，在實際的多無人機協同追捕“黑飛”無人機問題中，一般均為多個無人機抓取較少數量的“黑飛”無人機，不會出現大批量的“黑飛現象”，因此本文所提出的策略適用于實際多無人機協同追捕“黑飛”無人機問題。

此外，可以發現，對于不同的追捕者，逃逸者數量比，基線策略的抓取時間均呈現出較大的波動，其最大值和最小值差值較大，這是由于每次試驗中追捕者和逃逸者的初始位置是隨機的，不同的初始位置對基線策略的表現影響很大，這表明基線策略的追捕效率具有一定的不穩定性。相比而言，本文所提出策略相應的抓取時間的波動相比基線策略要小，這表明該策略的穩定性更強。

4 結論

1)采用Voronoi圖對有界環境進行表征，對于多無人機協同追捕問題，提出了一種面積最小化策略，實現了多個追捕者對多個逃逸者的高效協同追捕。

2)證明了所提出的面積最小化策略可以在有限時間內完成對逃逸者的協同追捕。

3)針對城市低空復雜環境下的多元障礙和通信受限約束，提出了基于最近鄰協商的協同追捕策略，仿真結果表明，在環境障礙、信息非完備的約束下，所提出的策略可以實現對多個逃逸者的高效協同追捕。

本文提出的追捕策略具有一定的有效性和魯棒性，為多無人機協同追捕提供了理論與技術支撐。

由于在探討多無人機協同追捕問題中，是把無人機當作質點考慮的，沒有考慮無人機的大小尺寸以及相關動力學約束，另外仿真場景都是基于二維有界環境，一定程度上限制了方法對于實體無人機和實際問題的適用性。因此考慮如何添加動力學約束，在三維場景下完成多無人機的協同追捕任務是未來研究的一個重要方向。

> >