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

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

來源：《計算機科學與應用》?，作者冷雄暉等

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

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

1. 引言

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

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

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

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

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

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

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

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

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

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

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

c=2–√rc=2r

?

?

Figure 1. Grid unit distance

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

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

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

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

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

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

?

?

Figure 2. Rectangle target area partition

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

?

?

Figure 3. Irregular target region

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

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

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

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

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

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

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

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

步驟五：n個種子點衍生出來的區(qū)域則為n架無人機的責任區(qū)。

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

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

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

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

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

Figure 4. Irregular division
?

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

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

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

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

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

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

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

1) 轉彎角度總值最小

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

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

z1=∑i=1nqi

其中，?qiqi?為航路上第i個轉彎的角度，?z1z1?越小，效率越高。

2) 最大轉彎角度

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

?

其中?θθ?角是無人機行駛過程中的最大轉彎角度。

3) 網(wǎng)格上的勢的總值及標準差最小化

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

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

?

4) 航路的可預測性要小

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

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

Z5=T?1Z5=T?1

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

4.1. 基因編碼

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

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

1) 交叉算子

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

2) 變異算子

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

3) 合并算子

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

?

?

Figure 5. Merge operation

圖5. 合并操作

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

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

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

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

步驟3：當生成的覆蓋航路滿足要求的時候，停止計算。

5. 仿真實驗

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

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

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

初始勢場采用點型種子生成，四架無人機的初始勢場如圖6所示。

?

?

Figure 6. Initial potential field

圖6. 初始勢場

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

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

6. 小結

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

審核編輯：符乾江