摘要：

摘要: 為解決傳統覆蓋航路規劃算法結果樣式單一、對抗性環境下靈活性差的問題，提出了基于遺傳算法的監視覆蓋航路規劃算法，生成樣式多樣、監視任務執行中對抗性好的監視覆蓋航路。在人工勢場法的基礎上，將激發勢場的種子編碼為二元組串形式的基因，通過交叉、變異、合并等算子的操作增加種子樣式的多樣性，從而規劃出轉彎少、監視時間間隔短、對抗性好的監視覆蓋航路。最后通過算例對算法進行了驗證，結果表明算法有效地滿足了監視任務覆蓋航路規劃的需求。

1. 引言

無人機航路規劃是指在特定約束條件下，尋找從起始點到目標點并滿足無人機性能指標的最優或可行的航路。而覆蓋航路規劃的任務是確定一條路徑，該路徑通過感興趣的區域所有點，同時避免障礙。經過查閱文獻，發現由于無人機受到任務區域和性能的約束，關于監視覆蓋航路規劃的研究較少，大多是關于地面機器人覆蓋航路規劃的研究。

A. Zelinsky等 [1] 提出了第一種基于網格的覆蓋路徑規劃方法。他們使用網格表示任務區域，并對網格應用完整的覆蓋路徑規劃算法。該方法設定一個起始單元格和一個目標單元格。算法首先給目標網格賦值0，給它周圍的所有單元格賦值1。然后，所有與標記1相鄰的未標記網格都標記為2。這個過程不斷重復，直到標記面到達開始單元格。經過計算距離轉換，通過從開始單元格開始選擇未訪問的賦值最高的相鄰單元格來找到覆蓋路徑。如果兩個或兩個以上的鄰居單元格為相同的值，則隨機選擇其中一個單元格。

H. Choset等 [2] 提出了一種能夠產生完整覆蓋路徑的簡單精確的網格分解技術。他們將任務區域劃分成每個網格為梯形的工作空間，并且只處理平面的多邊形區域。使用簡單的來回運動來覆蓋每個單元網格，通過查找與分解相關的鄰接網格進行窮舉遍歷來保證完全覆蓋任務區域，詳盡的前進規則決定了訪問單元格的順序，最后生成覆蓋每個單元格的特定“之”字形路徑。

陳海等 [3] 證明了同等能量下無人機轉彎過程比直線飛行過程效率低，定義了凸多邊形任務區域的長度和寬度，并將凸多邊形區域的覆蓋航跡規劃問題轉化為求解凸多邊形寬度的問題。他們按照“點邊式”寬度算法，找到凸多邊形寬度出現時支撐平行線的方向，如果無人機沿該方向利用掃描線對區域進行掃描覆蓋，則可以獲得最少的轉彎次數，也就能夠得到最短的飛行路程。但在地形起伏大的任務區域，需要加入地形高程等約束進行三維航路規劃。

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

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

2.1. 任務區域網格化

規劃監視覆蓋航路時必須考慮到無人機執行任務的區域，簡單易行的任務區域劃分可以極大方便覆蓋航路生成，所以我們把任務區域網格化。網格化就是要將任務區域劃分為規則的網格，網格的大小由無人機監視器視場在地面的投影大小決定。那么任務區域就可以使用網格的集合來表示了，設為A。網格要小于這個投影區域的大小，但又要盡可能的大。若無人機的飛行高度為h，垂直視場角為 αα ，水平視場角為 λλ ，俯視角為 ββ 。假設在地面的視場為梯形ABCD如圖1所示， N,K,FN,K,F 分別為邊 AB,PQ,CDAB,PQ,CD 的中點，OK為 ∠NOF∠NOF 的角平分線。則網格的邊長最大可以為：

PQ=2OKtanλ/2PQ=2OKtanλ/2

Figure 1. UAV surveillance field of view

圖1. 無人機監視視場

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

人工勢場法 [7] 就是為任務區域設定一個虛擬的人工勢場，每個網格上設定一個數字代表網格的勢值。覆蓋航路規劃算法從一個起始的網格出發，按照一定的規則沿著勢場運動，最終會形成一個覆蓋航路。覆蓋航路的生成樣式和勢場值的設置以及運動規則密切相關，不同的勢場值設置方法以及規則，生成的覆蓋航路不同。

傳統的基于人工勢場的覆蓋航路生成方法是在兩個點之間，按照勢值遞增的趨勢生成勢場，然后依據勢場生成航路，算法在避障以及覆蓋效率方面有不錯的效果，但是生成的樣式比較單一。為了豐富勢場的樣式，我們將勢場生成的起始態勢進行了改進，并將這種起始的態勢成為種子。

所謂種子就是在勢場生成算法開始的時候，設定的一個勢值不為0的網格的集合，設為 S?AS?A 。傳統的人工勢場法中，種子S只包含一個網格。基于種子概念的人工勢場法生成覆蓋航路的過程如下：

步驟1：選擇任務區域網格集合的一個子集作為種子S，并設其網格的勢值均為1，其他網格的勢值為0;

步驟2：并行地更新勢值為0的網格的勢值，從其鄰居網格中選擇勢值最大的網格作為激發格，并設當前網格的勢值為激發格勢值 + 1;

步驟3：重復運行步驟2直到所有的網格勢值均為非零，轉步驟4;

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

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

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

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

1) 轉彎角度總值最小

每個轉彎通常意味著無人機在轉彎后再次減速并再次加速的額外成本，所以要減少最小化路徑中的轉彎(次數、角度)來增加監視的效率。這里我們采用統計航路中所有拐彎角度總和的辦法來度量航路的這一個性能，并將這個總和稱為拐彎角度總值

其中， qiqi 為航路上第i個轉彎的角度，拐彎角度總值越小的航路，越有利于增加監視效率。

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

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

其中， wiwi 為網格i的勢值。

3) 航路的可預測性要小

監視任務的性質決定了無人機被發現的概率越小越好，所以覆蓋航路的可預測性至關重要。當覆蓋航路越不容易被預測判斷時，無人機執行任務越不容易被發現，任務的成功率和可靠性越高。若覆蓋航路被預測出時，敵方可根據預測避開無人機或采取措施迷惑無人機，導致任務失敗。

這里我們簡單地利用種子更新的周期來評估可預測性的大小，也就是種子更新越頻繁，覆蓋航路樣式的變換越頻繁，航路就越不容易被預測

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

3.1. 基因編碼

普通的基因編碼 [8] 以01字符串編碼為主，但這種編碼形式不利于種子的直觀表示，并且經過交叉變異等操作后，經常會產生非可行解。因此，我們采用二元組串的形式進行編碼，每個網格可以對應平面直角坐標系上的一個唯一坐標，而種子是網格的集合，這樣種子就可以編碼成一個二元組串的形式。

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

1) 交叉算子

交叉 [9] [10] 是指通過交換兩個個體中的部分基因位產生新的基因。從種群中選取兩個個體配對，在選定的節點上各截取一部分基因相互交換，即產生新的基因，組成兩個全新的個體。如圖2。

2) 變異算子

經過交叉過后的新基因某個或某些基因位會產生變異，從而產生一定概率的不可預測性性波動，進而增加種群進化的多樣性。通過變異不僅可以改善航路規劃的隨機性，使航路的可選擇性更加豐富多樣，通過種子的改變，產生下一步進行的更多可能的新的種子。還可以增加算法的局部搜索能力，使得路徑選擇的方向更加廣闊，在面對新的信息時有更多適合的航路。

對于橢圓形種子的基因變異，改變的是橢圓形的形狀參數(如位置、長軸與x軸夾角、軸的長短)。如圖3。

3) 合并算子

根據本問題的特殊性，提出一種新的算子，稱為合并算子，也就是將兩個種子基因進行直接合并而生成基因。如圖4。

Figure 2. Cross operation

圖2. 交叉操作

Figure 3. Variation operation

圖3. 變異操作

Figure 4. merge operation

圖4. 合并操作

3.3. 監視覆蓋航路生成

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

步驟1：初始化種子群，在種群中選擇一個種子，在任務區域網格中生成勢場，無人機位于起始位置 (x0,y0)(x0,y0) ， t=0t=0 ，設定種子更新的周期T。

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

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

4. 仿真實驗

為了對算法進行測試，我們建立了30*30的任務區域網格，每個網格看作圖 G=(V,E)G=(V,E) 中的一個點，所有的點構成圖G的點集V，對于一個網格，我們定義其鄰居為與其相鄰的八個網格，映射到圖G中，就是點之間只有存在鄰居關系的時候，才有邊相連。

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

在航路生成的過程中，每隔30*30仿真步長統計一次航路的性能參數，也就是轉彎角度總值、人工勢場勢總值、網格勢場最大值、網格勢場值的標準差等參數，其中目標函數中的不可預測性，認為其與種群更新周期T成反比，也就是T越大，不可預測性越差，反之，不可預測性越好，極端情況下，當T為無窮大的時候，不可預測性最差。

初始勢場采用點型種子生成，如圖5所示。

Figure 5. Initial potential field

圖5. 初始勢場

為了更加連貫和度量一致的觀察航路規劃算法的統計，在達到勢場更新周期，對勢場進行更新的時候，要進行一定的處理，使得任務網格的總勢保持不變，也就是假設新的種子生成的勢場總值為 P1P1 ，更新之前的總值為 P0P0 ，則要將新生成的勢場除以一個常數

P1/P0P1/P0

進行了50*900個仿真步長的仿真，也就是理想情況下可以對任務區域進行最大50次的覆蓋監視，得到的結果如圖6所示。

從仿真結果來看，轉彎角度總值分布比較平穩，位于111到245之間。勢場總值也比較平穩，初始幾個周期的總勢值比較大是因為初始勢場生成設置的原因，網格勢場最大值以及標準差也存在這樣的現象。

5. 小結

本文通過結合人工勢場法對無人機任務區域生成網格勢場，在監視覆蓋航路的約束條件下，將勢場

(a) 轉彎角度總值

(b) 勢場總值

(c) 網格勢場最大值

(d) 勢場標準差

Figure 6. Analysis of the results

圖6. 結果分析

種子編碼成二元串組基因后進行算子操作，產生更多新的種子，增加航路變化的多樣性。通過仿真驗證算例的轉彎角度總值、勢場總值、網格勢場最大值、勢場標準差等結果，表明本算法可以滿足監視覆蓋航路多樣性和對抗性的需求。

審核編輯：湯梓紅