基于Voronoi圖最近鄰協(xié)商的多機(jī)協(xié)同追捕方法

張?jiān)坪眨?蘇立晨， 董云帆， 劉瑜， 李宇萌

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

隨著我國(guó)低空空域持續(xù)開(kāi)放，無(wú)人機(jī)“黑飛”事件頻發(fā)，對(duì)公共安全、國(guó)防安全帶來(lái)巨大挑戰(zhàn)。近年來(lái)，以協(xié)同追捕為代表的柔性反制技術(shù)為復(fù)雜低空安全管控提供了新的思路。協(xié)同追捕通過(guò)控制多個(gè)裝備捕獲裝置的追捕無(wú)人機(jī)，對(duì)“黑飛”無(wú)人機(jī)進(jìn)行協(xié)同追蹤并將其網(wǎng)捕，可更有效地消除“黑飛”無(wú)人機(jī)帶來(lái)的安全隱患，具有重要理論研究意義與實(shí)際工程應(yīng)用價(jià)值。

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

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

在多無(wú)人機(jī)協(xié)同追捕問(wèn)題中，Voronoi圖法通過(guò)將有界環(huán)境劃分，將連續(xù)的動(dòng)作空間離散化，一方面極大地減小了動(dòng)作搜索空間，提高了計(jì)算效率，適合無(wú)人機(jī)進(jìn)行實(shí)時(shí)決策；另一方面將各架無(wú)人機(jī)分隔開(kāi)，保證了一定的安全性。由于實(shí)際城市低空環(huán)境地形地貌復(fù)雜，追捕無(wú)人機(jī)可能受到障礙物遮擋導(dǎo)致通信受限，然而現(xiàn)有工作中大多設(shè)定為無(wú)人機(jī)均可獲取完備信息，無(wú)法適用于存在障礙物且機(jī)間通信受限的場(chǎng)景中。

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

1 問(wèn)題描述與建模

(1)

(2)

追捕者的目標(biāo)是在有限時(shí)間內(nèi)抓住所有逃逸者，對(duì)于第i個(gè)逃逸者來(lái)說(shuō)，即至少有一個(gè)追捕者離該逃逸者的距離小于抓取半徑rc：

(3)

(4)

(5)

式中tΔ表示時(shí)間步。

2 基于Voronoi圖的協(xié)同追捕方法

2.1 Voronoi圖的基本性質(zhì)

本文以Voronoi圖為基本框架，將各架無(wú)人機(jī)用質(zhì)點(diǎn)表示，以該質(zhì)點(diǎn)為生成元構(gòu)成Voronoi圖，對(duì)二維有界環(huán)境進(jìn)行劃分(如圖1所示)，并基于Voronoi圖的以下幾個(gè)基本性質(zhì)來(lái)定義協(xié)同追捕問(wèn)題模型：

圖1 Voronoi圖劃分場(chǎng)景示意Fig.1 Schematic diagram of Voronoi partition

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

2)每個(gè)Voronoi元胞內(nèi)的點(diǎn)到該生成元距離小于到其他生成元的距離；

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

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

圖中每架無(wú)人機(jī)根據(jù)所生成的Voronoi元胞及相鄰元胞的相關(guān)信息進(jìn)行決策，這極大地減小了其動(dòng)作搜索空間，提高了生成決策的計(jì)算效率。

2.2 基于面積最小化的協(xié)同追捕策略

對(duì)于追捕者而言，逃逸者的具體控制策略不可獲知，但逃逸者僅會(huì)在其安全到達(dá)集內(nèi)運(yùn)動(dòng)[21]。安全到達(dá)集是指逃逸者能快于其他追捕者直線到達(dá)的點(diǎn)的集合，逃逸者可到達(dá)該集合區(qū)域內(nèi)的任何一點(diǎn)，從而避免被追捕者抓取。當(dāng)追捕者和逃逸者擁有相同的最大速度和動(dòng)力學(xué)方程時(shí)，安全到達(dá)集也就轉(zhuǎn)化為了有界環(huán)境下的Voronoi圖劃分，即逃逸者的Voronoi元胞表示為：

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

(6)

式中q表示Voronoi元胞內(nèi)的點(diǎn)。

由于逃逸者只能移向自己安全到達(dá)集內(nèi)的點(diǎn)，追捕者期望通過(guò)最小化逃逸者的安全到達(dá)集的大小，也就是最小化逃逸者所生成的Voronoi圖劃分區(qū)域的面積來(lái)逐漸縮小逃逸者的可行動(dòng)作空間，從而最終完成對(duì)逃逸者的抓取，把這個(gè)策略稱(chēng)為“面積最小化”策略，該策略將會(huì)把追捕者引導(dǎo)至追捕者和逃逸者共同Voronoi劃分邊界的中點(diǎn)。

假設(shè)逃逸者所生成的Voronoi劃分區(qū)域?yàn)閂e，其面積大小為Ae，則面積的大小可以表示為：

(7)

式中q表示逃逸者生成Voronoi區(qū)域Ve內(nèi)的點(diǎn)，則Ae的導(dǎo)數(shù)為：

(8)

希望通過(guò)追捕者采取策略來(lái)持續(xù)地減小Ae，可以把上面公式的右邊第2項(xiàng)分解為單個(gè)的減小量，如果最大化Ae的減小速度，則每個(gè)追捕者的速度為：

(9)

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

2.3 追捕策略可行性證明

本文將依據(jù)5個(gè)結(jié)論來(lái)簡(jiǎn)要證明在該策略下，追捕者可以在有限時(shí)間內(nèi)完成對(duì)單個(gè)逃逸者的抓取。

(10)

結(jié)論證明：對(duì)于式(5)中定義的Ae，通過(guò)萊布尼茨積分公式，可得Ae的導(dǎo)數(shù)簡(jiǎn)化為：

(11)

(12)

應(yīng)用結(jié)論1，將式(10)代入式(9)，可得追捕者的速度簡(jiǎn)化為：

(13)

(14)

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

結(jié)論證明：對(duì)于單個(gè)追捕者和單個(gè)逃逸者的場(chǎng)景，Ae的導(dǎo)數(shù)簡(jiǎn)化為：

(15)

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

(16)

從而得到Ae≤0，且當(dāng)Ae=0時(shí)，可以得到：

(17)

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

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

(18)

(19)

結(jié)論證明：距離d的導(dǎo)數(shù)為

(20)

(21)

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

(22)

(23)

(24)

移項(xiàng)后得到：

(25)

放縮合并，得到：

(26)

(27)

E=kAe+d

(28)

結(jié)論5對(duì)于系統(tǒng)函數(shù)(28)，在采取策略，式(13)的情況下，如果在t0時(shí)刻前沒(méi)有完成抓取，則：

E(t)

(29)

結(jié)論證明：根據(jù)結(jié)論4，得到以下的2個(gè)條件：

(30)

(31)

則系統(tǒng)函數(shù)的導(dǎo)數(shù)為：

(32)

(33)

(34)

經(jīng)過(guò)一系列的推導(dǎo)證明，可得到追捕者的速度簡(jiǎn)化為：

(35)

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

通過(guò)以上推導(dǎo)，給出了多無(wú)人機(jī)的協(xié)同追捕策略，證明了在有界凸環(huán)境內(nèi)，無(wú)論逃逸者采取何種控制策略，追捕者均可確保在有限時(shí)間內(nèi)完成對(duì)其的抓取，在這一前提下，通過(guò)設(shè)定逃逸者以“move-to-centroid”策略[22]盡可能保持其安全到達(dá)集的大小以及所覆蓋區(qū)域的均勻劃分：

(36)

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

2.4 通信受限下的協(xié)同追捕策略

由于低空運(yùn)行環(huán)境復(fù)雜、約束多元，通信鏈路可能受到地形遮擋，導(dǎo)致追捕無(wú)人機(jī)不能實(shí)時(shí)地和較遠(yuǎn)處的無(wú)人機(jī)進(jìn)行協(xié)商，從而共享目標(biāo)。

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

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

2)追捕者在過(guò)程中可以更換目標(biāo)，不需要與其他追捕者進(jìn)行協(xié)商共同目標(biāo)，可適用于通信受限條件。

(37)

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

(38)

式中：Vi是第i個(gè)逃逸者根據(jù)所有無(wú)人機(jī)位置所生成的Voronoi元胞；CVi為該Voronoi元胞的形心。

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

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

1)計(jì)算有界環(huán)境Voronoi圖劃分過(guò)程中，需要把障礙物中心當(dāng)作靜態(tài)智能體處理，參與Voronoi圖構(gòu)建，同時(shí)在更新Voronoi元胞信息時(shí)，需要給障礙物生成的Voronoi元胞進(jìn)行特殊標(biāo)記，追捕者可以根據(jù)該特殊標(biāo)記識(shí)別障礙物元胞；

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

2.6 算法仿真流程

算法流程主要分為場(chǎng)景定義，循環(huán)控制兩個(gè)部分。場(chǎng)景定義主要包括追捕者和逃逸者的數(shù)量，速度大小，位置，存活狀態(tài)，時(shí)間步長(zhǎng)，邊界大小以及抓取半徑等參數(shù)的初始化。

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

圖2 算法流程Fig.2 Algorithm flowchart

3 仿真實(shí)現(xiàn)與結(jié)果分析

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

圖3 仿真場(chǎng)景示意Fig.3 Schematic diagram of simulation scenarios

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

3.1 通信受限下的多對(duì)多追捕仿真結(jié)果

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

圖4 協(xié)同追捕效果Fig.4 Schematic diagram of cooperative pursuit

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

3.2 可行域受限下的多對(duì)多追捕仿真結(jié)果

本節(jié)采用的場(chǎng)景為100 m×100 m的二維有界凸環(huán)境，存在障礙物，有4個(gè)追捕者，4個(gè)逃逸者和4個(gè)障礙物。其中追捕者，逃逸者和障礙物的初始位置均隨機(jī)生成，圓形區(qū)域表示障礙物，所有追捕者不能進(jìn)入障礙物區(qū)域。仿真的時(shí)間步長(zhǎng)設(shè)置為1 s，抓取半徑和障礙物半徑均設(shè)定為5 m，障礙物半徑設(shè)定為3 m。一次試驗(yàn)過(guò)程中的幾幀圖像，仿真效果如圖5所示。

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

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

3.3 基線策略對(duì)比分析

上述仿真結(jié)果表示，提出的策略可以在通信受限和可行域受限的約束下實(shí)現(xiàn)對(duì)所有逃逸者的協(xié)同追捕，本節(jié)將和基線策略對(duì)比所有逃逸者被抓取的完成時(shí)間來(lái)分析多無(wú)人機(jī)協(xié)同追捕策略的效率。

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

圖6 不同策略抓取時(shí)間對(duì)比Fig.6 Comparison of capturing durations under different strategies

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

此外，可以發(fā)現(xiàn)，對(duì)于不同的追捕者，逃逸者數(shù)量比，基線策略的抓取時(shí)間均呈現(xiàn)出較大的波動(dòng)，其最大值和最小值差值較大，這是由于每次試驗(yàn)中追捕者和逃逸者的初始位置是隨機(jī)的，不同的初始位置對(duì)基線策略的表現(xiàn)影響很大，這表明基線策略的追捕效率具有一定的不穩(wěn)定性。相比而言，本文所提出策略相應(yīng)的抓取時(shí)間的波動(dòng)相比基線策略要小，這表明該策略的穩(wěn)定性更強(qiáng)。

4 結(jié)論

1)采用Voronoi圖對(duì)有界環(huán)境進(jìn)行表征，對(duì)于多無(wú)人機(jī)協(xié)同追捕問(wèn)題，提出了一種面積最小化策略，實(shí)現(xiàn)了多個(gè)追捕者對(duì)多個(gè)逃逸者的高效協(xié)同追捕。

2)證明了所提出的面積最小化策略可以在有限時(shí)間內(nèi)完成對(duì)逃逸者的協(xié)同追捕。

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

本文提出的追捕策略具有一定的有效性和魯棒性，為多無(wú)人機(jī)協(xié)同追捕提供了理論與技術(shù)支撐。

由于在探討多無(wú)人機(jī)協(xié)同追捕問(wèn)題中，是把無(wú)人機(jī)當(dāng)作質(zhì)點(diǎn)考慮的，沒(méi)有考慮無(wú)人機(jī)的大小尺寸以及相關(guān)動(dòng)力學(xué)約束，另外仿真場(chǎng)景都是基于二維有界環(huán)境，一定程度上限制了方法對(duì)于實(shí)體無(wú)人機(jī)和實(shí)際問(wèn)題的適用性。因此考慮如何添加動(dòng)力學(xué)約束，在三維場(chǎng)景下完成多無(wú)人機(jī)的協(xié)同追捕任務(wù)是未來(lái)研究的一個(gè)重要方向。

> >