某型無人機(jī)群的監(jiān)視覆蓋任務(wù)航路規(guī)劃

來源：《計(jì)算機(jī)科學(xué)與應(yīng)用》?，作者冷雄暉等

關(guān)鍵詞:?無人機(jī)群；監(jiān)視覆蓋航路規(guī)劃；遺傳算法；人工勢場法；UAV Group；?Surveillance Coverage Route Planning；?Genetic Algorithm；?Artificial Potential Field Method
?

摘要:?利用無人機(jī)群執(zhí)行監(jiān)視任務(wù)，在邊界和區(qū)域管控、反恐防爆監(jiān)視以及軍事應(yīng)用中具有很高的效費(fèi)比。無人機(jī)群監(jiān)視覆蓋航路規(guī)劃算法是提升無人機(jī)群監(jiān)視任務(wù)效率和能力的核心算法。傳統(tǒng)覆蓋航路規(guī)劃算法結(jié)果樣式單一、對抗性環(huán)境下靈活性差，區(qū)域劃分方法不便于計(jì)算機(jī)自動(dòng)生成。本文提出了基于人工勢場和遺傳算法的監(jiān)視覆蓋航路規(guī)劃算法，生成樣式多樣、監(jiān)視任務(wù)執(zhí)行中對抗性好的監(jiān)視覆蓋航路。在人工勢場法的基礎(chǔ)上，將激發(fā)勢場的種子編碼為二元組串形式的基因，通過交叉、變異、合并等算子的操作增加種子樣式的多樣性，從而規(guī)劃出轉(zhuǎn)彎少、監(jiān)視時(shí)間間隔短、對抗性好的監(jiān)視覆蓋航路。最后通過算例對算法進(jìn)行了驗(yàn)證，結(jié)果表明算法有效地滿足了監(jiān)視任務(wù)覆蓋航路規(guī)劃的需求。

1. 引言

無人機(jī)航路規(guī)劃是指在特定約束條件下，尋找從起始點(diǎn)到目標(biāo)點(diǎn)并滿足無人機(jī)性能指標(biāo)的最優(yōu)或可行的航路，耗費(fèi)小的路徑不僅節(jié)省了無人機(jī)運(yùn)行的成本，也增大了無人機(jī)完成任務(wù)的成功率，并且安全性高的路徑也能提高無人機(jī)的存活率。覆蓋航路規(guī)劃CPP (Coverage Path Planning)是指要為無人機(jī)規(guī)劃一條能通過所有感興趣的點(diǎn)的路徑，是無人機(jī)監(jiān)視任務(wù)規(guī)劃中需要解決的關(guān)鍵問題之一。

近期，受2019新型冠狀病毒(COVID-19)影響，國外許多國家下達(dá)了行動(dòng)管制令，以色列等多個(gè)國家軍隊(duì)和警察運(yùn)用無人機(jī)對城市內(nèi)的居民進(jìn)行監(jiān)視，以確定居民的動(dòng)向。加拿大一公司開發(fā)出“流行病無人機(jī)”平臺，利用無人機(jī)監(jiān)視體溫，在人群中尋找表現(xiàn)出癥狀的人。在我國，多個(gè)省市都動(dòng)用了人臉辨識相機(jī)系統(tǒng)、監(jiān)視器及監(jiān)控?zé)o人機(jī)來偵測隔離者的動(dòng)向，全方位多角度，高密度監(jiān)控，無人機(jī)群的監(jiān)視覆蓋運(yùn)用目前比較廣泛。

李御馳 [1] 等提出了一種基于遺傳算法的無人機(jī)監(jiān)視覆蓋航路規(guī)劃算法。對監(jiān)視覆蓋航路進(jìn)行建模，將任務(wù)區(qū)域網(wǎng)格化，將勢場種子編碼成二元串組基因后進(jìn)行算子操作，利用遺傳算法生成監(jiān)視覆蓋航路，并在最后進(jìn)行仿真。

李艷慶 [2] 等提出了一種基于遺傳算法的多無人機(jī)航路規(guī)劃方法。通過對無人機(jī)的轉(zhuǎn)彎角進(jìn)行基因編碼，將多無人機(jī)的監(jiān)視面積覆蓋率作為適應(yīng)度函數(shù)，并進(jìn)行相應(yīng)的遺傳操作，依據(jù)實(shí)時(shí)監(jiān)視面積覆蓋率最大原則，對多無人機(jī)協(xié)同區(qū)域監(jiān)視進(jìn)行航路規(guī)劃。

陳海等 [3] 證明了從能量角度來看無人機(jī)轉(zhuǎn)彎過程比直線飛行過程效率低，定義了凸多邊形任務(wù)區(qū)域的長度和寬度，并將凸多邊形區(qū)域中的最短飛行路程問題轉(zhuǎn)化為求凸多邊形的最小跨度問題。他們按照“點(diǎn)邊式”寬度算法，提出凸多邊形寬度出現(xiàn)時(shí)，支撐平行線必與一條邊重合，無人機(jī)沿寬度出現(xiàn)時(shí)支撐平行線的方向飛行才能獲得最少的轉(zhuǎn)彎次數(shù)，也就能夠得到最短的飛行路程。但在地形起伏大的任務(wù)區(qū)域，需要加入地形高程等約束進(jìn)行三維航路規(guī)劃。

覆蓋航路規(guī)劃問題在機(jī)器人領(lǐng)域 [4] [5] [6] 有較多的研究。但是，如果將這些方法應(yīng)用于監(jiān)視飛行器的覆蓋路徑生成，則在一次覆蓋后，其對手可以很容易地掌握這些路徑的規(guī)律性，不能滿足監(jiān)視任務(wù)的不可預(yù)測性和覆蓋任務(wù)目標(biāo)的頻繁性要求。

本文首先在任務(wù)區(qū)域網(wǎng)格化模型的基礎(chǔ)上，提出了區(qū)域劃分的方法，然后建立了基于遺傳算法規(guī)劃無人機(jī)群監(jiān)視覆蓋航路。

2. 區(qū)域劃分方法

對于多無人機(jī)覆蓋航路規(guī)劃，需要對各個(gè)無人機(jī)進(jìn)行任務(wù)分配。假定無人機(jī)群有 架無人機(jī)。一般而言，根據(jù)無人機(jī)的數(shù)量把指定區(qū)域劃分為相互隔離的子區(qū)域，且子區(qū)域的數(shù)量與無人機(jī)的數(shù)量相同。

2.1. 任務(wù)區(qū)域網(wǎng)格化

對于要監(jiān)視的目標(biāo)區(qū)域，必須做到全覆蓋。首先需要對目標(biāo)區(qū)域進(jìn)行網(wǎng)格化處理，使我們可以通過訪問網(wǎng)格節(jié)點(diǎn)的方式實(shí)現(xiàn)對目標(biāo)區(qū)域的覆蓋，這里我們采用正方形的網(wǎng)格進(jìn)行網(wǎng)格化。網(wǎng)格化處理時(shí)需要讓無人機(jī)能夠無縫隙的覆蓋目標(biāo)區(qū)域的各個(gè)網(wǎng)格，假設(shè)無人機(jī)的探測范圍在地面的投影是以自身為圓心、以r為半徑的圓形區(qū)域，則網(wǎng)格的大小需要根據(jù)無人機(jī)的探測半徑r來決定。因此，我們可以將覆蓋問題轉(zhuǎn)化為網(wǎng)格掃描問題，任務(wù)區(qū)域就可以使用網(wǎng)格的集合來表示，設(shè)為A。網(wǎng)格要小于這個(gè)投影區(qū)域的大小，但又要盡可能的大。如圖1所示，則網(wǎng)格的邊長 最大可以為：

c=2–√rc=2r

?

?

Figure 1. Grid unit distance

圖1. 網(wǎng)格單位距離

2.2. 矩形任務(wù)區(qū)域劃分

對于矩形任務(wù)目標(biāo)區(qū)域，我們采取簡單的平均分配的方式。對于無人機(jī)編隊(duì)，有n架無人機(jī)，將矩形任務(wù)區(qū)域進(jìn)行n等分。為便于無人機(jī)的部署，采用沿著矩形的X軸方向進(jìn)行等分的方式，如圖2所示。一般而言，定義長邊所在為X軸。

2.3. 不規(guī)則任務(wù)區(qū)域劃分

實(shí)際情況中，更多的任務(wù)目標(biāo)區(qū)域往往是不規(guī)則的形狀。

人工勢場法 [4] 是由Khatib提出的一種虛擬力法。它的基本思想是將移動(dòng)機(jī)器人在周圍環(huán)境中的運(yùn)動(dòng)，設(shè)計(jì)成一種抽象的人造引力場中的運(yùn)動(dòng)，目標(biāo)點(diǎn)對移動(dòng)機(jī)器人產(chǎn)生“引力”，障礙物對其產(chǎn)生“斥力”，最后通過求合力來控制移動(dòng)機(jī)器人的運(yùn)動(dòng)。我們引入勢場的概念對目標(biāo)區(qū)域進(jìn)行劃分，將目標(biāo)區(qū)域均分給 個(gè)無人機(jī)，也即劃分責(zé)任區(qū)。不規(guī)則圖形的最小外接矩形如圖3所示。

?

?

Figure 2. Rectangle target area partition

圖2. 矩形目標(biāo)區(qū)域劃分

?

?

Figure 3. Irregular target region

圖3. 不規(guī)則目標(biāo)區(qū)域

我們在不規(guī)則的區(qū)域平面內(nèi)均勻分布隨機(jī)生成的點(diǎn)，點(diǎn)與點(diǎn)的距離?c=2–√rc=2r，每個(gè)點(diǎn)的勢值為0。點(diǎn)的集合為S。

利用勢值的概念對任務(wù)區(qū)域進(jìn)行劃分的步驟如下：

步驟一：任務(wù)區(qū)域的點(diǎn)集合S中分散地生成n個(gè)種子點(diǎn)，分別命名為?Z1,Z2,?,ZnZ1,Z2,?,Zn，并設(shè)其網(wǎng)格的勢值均為1，其他網(wǎng)格的勢值為0。

為了避免種子點(diǎn)過于緊密，對于任意兩種子點(diǎn)的距離?|xmxn||xmxn|?( 其中?m

步驟二：并行地更新勢值為0的網(wǎng)格的勢值，從與種子點(diǎn)距離為1的鄰居網(wǎng)格中按照一定的規(guī)則，這些規(guī)則可能是順時(shí)針第一個(gè)、逆時(shí)針第一個(gè)、上、下、左、右、隨機(jī)等，選擇勢值為零的網(wǎng)格作為激發(fā)格，并設(shè)當(dāng)前網(wǎng)格的勢值為激發(fā)格勢值 + 1。

步驟三：依次將距離 + 1，持續(xù)激發(fā)新的網(wǎng)格；當(dāng)某一鄰居網(wǎng)格的勢值不為零時(shí)，跳過該網(wǎng)格的擴(kuò)展。

步驟四：重復(fù)運(yùn)行步驟二、三直到所有的網(wǎng)格勢值均為非零，轉(zhuǎn)步驟五。

步驟五：n個(gè)種子點(diǎn)衍生出來的區(qū)域則為n架無人機(jī)的責(zé)任區(qū)。

由于是并行操作，最后得出的n個(gè)責(zé)任區(qū)大小會(huì)盡可能的相等。

利用該方法劃分不規(guī)則區(qū)域如圖4所示。

3. 監(jiān)視覆蓋航路規(guī)劃問題建模

3.1. 人工勢場法生成覆蓋航路

人工勢場法生成覆蓋航路規(guī)劃算法是指從一個(gè)起始的網(wǎng)格出發(fā)，按照一定的規(guī)則沿著勢場運(yùn)動(dòng)，最終會(huì)形成一個(gè)覆蓋航路。覆蓋航路的生成樣式和勢場值的設(shè)置以及運(yùn)動(dòng)規(guī)則密切相關(guān)，不同的勢場值設(shè)置方法以及規(guī)則，生成的覆蓋航路不同。

Figure 4. Irregular division
?

圖4. 不規(guī)則區(qū)域劃分

傳統(tǒng)的基于人工勢場的覆蓋航路生成方法是在兩個(gè)點(diǎn)之間，按照勢值遞增的趨勢生成勢場，然后依據(jù)勢場生成航路，算法在避障以及覆蓋效率方面有不錯(cuò)的效果，但是生成的樣式比較單一。

我們根據(jù)區(qū)域劃分生成的人工勢場應(yīng)用人工勢場的發(fā)現(xiàn)進(jìn)行覆蓋航路規(guī)劃；包括兩個(gè)步驟：

步驟1：無人機(jī)從起始網(wǎng)格出發(fā)，移動(dòng)向勢值最小的鄰居網(wǎng)格，并將起始網(wǎng)格標(biāo)記為已覆蓋。

步驟2：無人機(jī)不停地向勢值最小的未覆蓋的鄰居網(wǎng)格移動(dòng)。

3.2. 監(jiān)視覆蓋航路的目標(biāo)函數(shù)

根據(jù)無人機(jī)監(jiān)視任務(wù)的性質(zhì)，監(jiān)視覆蓋航路的優(yōu)劣主要取決于覆蓋航路實(shí)際執(zhí)行的效率和效果，也就是要更快、更頻繁、更不可預(yù)測地完成對任務(wù)區(qū)域的覆蓋監(jiān)視，這就要求航路的轉(zhuǎn)彎的次數(shù)和角度要少、對單個(gè)網(wǎng)格的監(jiān)視間隔要小、航路變換多樣。因此，監(jiān)視覆蓋航路規(guī)劃的目標(biāo)函數(shù)主要有以下幾個(gè)：

1) 轉(zhuǎn)彎角度總值最小

功耗受轉(zhuǎn)彎總數(shù)影響。在整個(gè)飛行任務(wù)中需要轉(zhuǎn)多少彎是一個(gè)主要問題。根據(jù)前文我們可以得知，無人機(jī)在飛行過程中，拐彎的次數(shù)越少，消耗的能量和時(shí)間等資源就越少，航路的優(yōu)越性越好。

對此，我們使用航路中所有拐彎角度總和?z1z1?來度量航路的這一個(gè)性能，并將這個(gè)總和稱為拐彎角度總值。

z1=∑i=1nqi

其中，?qiqi?為航路上第i個(gè)轉(zhuǎn)彎的角度，?z1z1?越小，效率越高。

2) 最大轉(zhuǎn)彎角度

也即是無人機(jī)在航路規(guī)劃中允許的最大轉(zhuǎn)彎角度，對于相鄰的兩點(diǎn)?

?

其中?θθ?角是無人機(jī)行駛過程中的最大轉(zhuǎn)彎角度。

3) 網(wǎng)格上的勢的總值及標(biāo)準(zhǔn)差最小化

為了反映對網(wǎng)格監(jiān)視間隔的大小，我們提出了一種勢值動(dòng)態(tài)增加的機(jī)制，也就是在計(jì)算推進(jìn)的過程中，所有網(wǎng)格的勢值也在同步增加，但是剛剛覆蓋過的網(wǎng)格的勢值清零，這樣，在計(jì)算過程中，網(wǎng)格的勢值就與監(jiān)視間隔的大小成正比，如果網(wǎng)格監(jiān)視間隔時(shí)間大，則網(wǎng)格勢值的增加就多。這樣，就可以用網(wǎng)格的動(dòng)態(tài)勢值來評價(jià)對網(wǎng)格監(jiān)視間隔。因此我們利用任務(wù)區(qū)域網(wǎng)格勢值的總值、標(biāo)準(zhǔn)差來評價(jià)監(jiān)視覆蓋的效率。

我們可以利用任務(wù)區(qū)域的總勢場值這項(xiàng)指標(biāo)來判斷覆蓋航路的效率，

?

4) 航路的可預(yù)測性要小

對于監(jiān)視任務(wù)，為使無人機(jī)的路線不被預(yù)測，應(yīng)當(dāng)不具有規(guī)律性，不可預(yù)測性越高航路越優(yōu)越。

對此，我們選擇使用遺傳算法中的種子更新時(shí)間T來度量航路的不可預(yù)測性

Z5=T?1Z5=T?1

4. 基于遺傳算法的監(jiān)視覆蓋航路規(guī)劃算法

4.1. 基因編碼

最常用的基因編碼方式是二進(jìn)制編碼 [7]，也即是01字符串。但是在航路規(guī)劃中，若使用二進(jìn)制編碼，在進(jìn)行遺傳算法的變異、交叉、合并等算子時(shí)，會(huì)容易產(chǎn)生不可行的個(gè)體，大大降低了算法的效率和可行性。為了讓產(chǎn)生的新的航路位置節(jié)點(diǎn)可行，我們使用二維坐標(biāo)組作為基因編碼。

4.2. 交叉、變異產(chǎn)生新的基因

1) 交叉算子

交叉 [8] [9] 是指通過就是兩個(gè)個(gè)體把一部分或者多部分的基因相互交換從而產(chǎn)生新的個(gè)體。

2) 變異算子

基因發(fā)生突變就叫變異，會(huì)產(chǎn)生一定概率的不可預(yù)測性性波動(dòng)，進(jìn)而增加種群進(jìn)化的多樣性。通過變異可以增加航路規(guī)劃的隨機(jī)性，使航路的可選擇性更加豐富多樣。

3) 合并算子

在本問題中，提出一種合并算子，也即將兩個(gè)基因進(jìn)行合并操作而生成新的基因。如圖5。

?

?

Figure 5. Merge operation

圖5. 合并操作

4.3. 監(jiān)視覆蓋航路生成

基于遺傳算法 [10] 的監(jiān)視覆蓋航路生成算法的步驟如下所示：

步驟1：初步驟1：初始化種群，生成種子，并確定種群的更新周期T，在任務(wù)區(qū)域網(wǎng)格中生成勢場，無人機(jī)從起始位置?(x0,y0)(x0,y0)?出發(fā)，此時(shí)時(shí)間?t=0t=0，移動(dòng)向勢值最小的鄰居網(wǎng)格，并將起始網(wǎng)格標(biāo)記為已覆蓋。

步驟2：仿真步長向前推進(jìn)?t=t+1t=t+1，勢場中所有網(wǎng)格的勢值增加某個(gè)數(shù)值p，無人機(jī)從當(dāng)前位置移動(dòng)到勢值最大的鄰居網(wǎng)格?(x,y)(x,y)?中，網(wǎng)格?(x,y)(x,y)?的勢值清零。當(dāng)達(dá)到種子更新周期條件的時(shí)候，對種群進(jìn)行交叉變異操作，并選擇一個(gè)基因，重新生成任務(wù)區(qū)域網(wǎng)格的勢場。

步驟3：當(dāng)生成的覆蓋航路滿足要求的時(shí)候，停止計(jì)算。

5. 仿真實(shí)驗(yàn)

為了對算法進(jìn)行測試，我們使用四架無人機(jī)完成對一個(gè)區(qū)域的監(jiān)視任務(wù)。首先對目標(biāo)區(qū)域進(jìn)行劃分，生成四個(gè)子區(qū)域，各無人機(jī)在各自責(zé)任區(qū)內(nèi)基于遺傳算法的航路規(guī)劃。

對于任意一架無人機(jī)，其責(zé)任區(qū)為30*30的任務(wù)區(qū)域網(wǎng)格，我們選用點(diǎn)型、線型兩種典型的人工勢場種子編碼產(chǎn)生遺傳算法的初始種群。設(shè)定仿真每向前推進(jìn)一步，所有點(diǎn)的人工勢場均增加0.001，種群更新的機(jī)制為按照仿真時(shí)間進(jìn)行更新，周期為T，也就是每向前推進(jìn)T時(shí)間，利用算子更新遺傳算法的種群，并從種群中隨機(jī)選擇一個(gè)種子更新當(dāng)前的勢場，繼續(xù)生成航路。

在航路生成的過程中，每完成一次區(qū)域覆蓋就對航路的性能參數(shù)進(jìn)行測試統(tǒng)計(jì)，性能參數(shù)包括無人機(jī)轉(zhuǎn)彎角度總值、區(qū)域網(wǎng)格勢場總值、網(wǎng)格勢場最大值、網(wǎng)格勢場值的標(biāo)準(zhǔn)差等。

初始勢場采用點(diǎn)型種子生成，四架無人機(jī)的初始勢場如圖6所示。

?

?

Figure 6. Initial potential field

圖6. 初始勢場

在多無人機(jī)路徑規(guī)劃時(shí)，為適應(yīng)監(jiān)視任務(wù)性質(zhì)的要求，在任務(wù)過程中要調(diào)整各個(gè)無人機(jī)的責(zé)任區(qū)。以本次仿真為例，使用四架無人機(jī)進(jìn)行監(jiān)視覆蓋任務(wù)，每進(jìn)行5*900個(gè)仿真步長，也即是無人機(jī)分別對各自的責(zé)任區(qū)域進(jìn)行了五次監(jiān)視覆蓋之后，重新分配一次責(zé)任區(qū)；因?yàn)檫z傳算子的變異特性，單無人機(jī)在子區(qū)域內(nèi)的覆蓋路徑已經(jīng)具有不確定性。

從仿真結(jié)果來看，轉(zhuǎn)彎角度總值分布比較平穩(wěn)，勢場總值也比較平穩(wěn)，網(wǎng)格勢場最大值、勢場標(biāo)準(zhǔn)差除初始外趨于平穩(wěn)，無人機(jī)在子區(qū)域內(nèi)能較好的生成預(yù)測性較小的航路。

6. 小結(jié)

本文通過結(jié)合人工勢場法運(yùn)用勢場的概念對目標(biāo)任務(wù)區(qū)域進(jìn)行劃分，并且依據(jù)勢場對各個(gè)無人機(jī)進(jìn)行初步路徑規(guī)劃，在監(jiān)視覆蓋航路的約束條件下，將勢場種子編碼成二元串組基因后進(jìn)行算子操作，產(chǎn)生更多新的種子，增加航路變化的多樣性。通過仿真驗(yàn)證算例的轉(zhuǎn)彎角度總值、勢場總值、網(wǎng)格勢場最大值、勢場標(biāo)準(zhǔn)差等結(jié)果，表明本算法可以滿足監(jiān)視覆蓋航路多樣性和對抗性的需求。最后通過在監(jiān)視過程中定期改變各無人機(jī)責(zé)任區(qū)，增加監(jiān)視路徑的不確定性，以適應(yīng)監(jiān)視覆蓋的要求。

審核編輯：符乾江