某型無人機群的監視覆蓋任務航路規劃

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

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

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

1. 引言

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

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

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

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

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

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

本文首先在任務區域網格化模型的基礎上，提出了區域劃分的方法，然后建立了基于遺傳算法規劃無人機群監視覆蓋航路。

2. 區域劃分方法

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

2.1. 任務區域網格化

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

c=2–√rc=2r

?

?

Figure 1. Grid unit distance

圖1. 網格單位距離

2.2. 矩形任務區域劃分

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

2.3. 不規則任務區域劃分

實際情況中，更多的任務目標區域往往是不規則的形狀。

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

?

?

Figure 2. Rectangle target area partition

圖2. 矩形目標區域劃分

?

?

Figure 3. Irregular target region

圖3. 不規則目標區域

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

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

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

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

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

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

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

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

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

利用該方法劃分不規則區域如圖4所示。

3. 監視覆蓋航路規劃問題建模

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

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

Figure 4. Irregular division
?

圖4. 不規則區域劃分

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

我們根據區域劃分生成的人工勢場應用人工勢場的發現進行覆蓋航路規劃；包括兩個步驟：

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

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

3.2. 監視覆蓋航路的目標函數

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

1) 轉彎角度總值最小

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

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

z1=∑i=1nqi

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

2) 最大轉彎角度

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

?

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

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

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

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

?

4) 航路的可預測性要小

對于監視任務，為使無人機的路線不被預測，應當不具有規律性，不可預測性越高航路越優越。

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

Z5=T?1Z5=T?1

4. 基于遺傳算法的監視覆蓋航路規劃算法

4.1. 基因編碼

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

4.2. 交叉、變異產生新的基因

1) 交叉算子

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

2) 變異算子

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

3) 合并算子

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

?

?

Figure 5. Merge operation

圖5. 合并操作

4.3. 監視覆蓋航路生成

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

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

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

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

5. 仿真實驗

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

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

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

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

?

?

Figure 6. Initial potential field

圖6. 初始勢場

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

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

6. 小結

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

審核編輯：符乾江