摘要：

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

1. 引言

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

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

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

陳海等 [3] 證明了同等能量下無人機(jī)轉(zhuǎn)彎過程比直線飛行過程效率低，定義了凸多邊形任務(wù)區(qū)域的長度和寬度，并將凸多邊形區(qū)域的覆蓋航跡規(guī)劃問題轉(zhuǎn)化為求解凸多邊形寬度的問題。他們按照“點邊式”寬度算法，找到凸多邊形寬度出現(xiàn)時支撐平行線的方向，如果無人機(jī)沿該方向利用掃描線對區(qū)域進(jìn)行掃描覆蓋，則可以獲得最少的轉(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)的頻繁性要求。基于此，我們提出了基于遺傳算法規(guī)劃監(jiān)視覆蓋航路。

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

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

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

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

Figure 1. UAV surveillance field of view

圖1. 無人機(jī)監(jiān)視視場

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

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

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

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

步驟1：選擇任務(wù)區(qū)域網(wǎng)格集合的一個子集作為種子S，并設(shè)其網(wǎng)格的勢值均為1，其他網(wǎng)格的勢值為0;

步驟2：并行地更新勢值為0的網(wǎng)格的勢值，從其鄰居網(wǎng)格中選擇勢值最大的網(wǎng)格作為激發(fā)格，并設(shè)當(dāng)前網(wǎng)格的勢值為激發(fā)格勢值 + 1;

步驟3：重復(fù)運行步驟2直到所有的網(wǎng)格勢值均為非零，轉(zhuǎn)步驟4;

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

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

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

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

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

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

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

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

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

其中， wiwi 為網(wǎng)格i的勢值。

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

監(jiān)視任務(wù)的性質(zhì)決定了無人機(jī)被發(fā)現(xiàn)的概率越小越好，所以覆蓋航路的可預(yù)測性至關(guān)重要。當(dāng)覆蓋航路越不容易被預(yù)測判斷時，無人機(jī)執(zhí)行任務(wù)越不容易被發(fā)現(xiàn)，任務(wù)的成功率和可靠性越高。若覆蓋航路被預(yù)測出時，敵方可根據(jù)預(yù)測避開無人機(jī)或采取措施迷惑無人機(jī)，導(dǎo)致任務(wù)失敗。

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

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

3.1. 基因編碼

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

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

1) 交叉算子

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

2) 變異算子

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

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

3) 合并算子

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

Figure 2. Cross operation

圖2. 交叉操作

Figure 3. Variation operation

圖3. 變異操作

Figure 4. merge operation

圖4. 合并操作

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

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

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

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

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

4. 仿真實驗

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

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

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

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

Figure 5. Initial potential field

圖5. 初始勢場

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

P1/P0P1/P0

進(jìn)行了50*900個仿真步長的仿真，也就是理想情況下可以對任務(wù)區(qū)域進(jìn)行最大50次的覆蓋監(jiān)視，得到的結(jié)果如圖6所示。

從仿真結(jié)果來看，轉(zhuǎn)彎角度總值分布比較平穩(wěn)，位于111到245之間。勢場總值也比較平穩(wěn)，初始幾個周期的總勢值比較大是因為初始勢場生成設(shè)置的原因，網(wǎng)格勢場最大值以及標(biāo)準(zhǔn)差也存在這樣的現(xiàn)象。

5. 小結(jié)

本文通過結(jié)合人工勢場法對無人機(jī)任務(wù)區(qū)域生成網(wǎng)格勢場，在監(jiān)視覆蓋航路的約束條件下，將勢場

(a) 轉(zhuǎn)彎角度總值

(b) 勢場總值

(c) 網(wǎng)格勢場最大值

(d) 勢場標(biāo)準(zhǔn)差

Figure 6. Analysis of the results

圖6. 結(jié)果分析

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

審核編輯：湯梓紅