摘要：

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

1. 引言

無人機(jī)航路規(guī)劃是指在特定約束條件下，尋找從起始點(diǎn)到目標(biāo)點(diǎn)并滿足無人機(jī)性能指標(biāo)的最優(yōu)或可行的航路。而覆蓋航路規(guī)劃的任務(wù)是確定一條路徑，該路徑通過感興趣的區(qū)域所有點(diǎn)，同時(shí)避免障礙。經(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ū)域，并對(duì)網(wǎng)格應(yīng)用完整的覆蓋路徑規(guī)劃算法。該方法設(shè)定一個(gè)起始單元格和一個(gè)目標(biāo)單元格。算法首先給目標(biāo)網(wǎng)格賦值0，給它周圍的所有單元格賦值1。然后，所有與標(biāo)記1相鄰的未標(biāo)記網(wǎng)格都標(biāo)記為2。這個(gè)過程不斷重復(fù)，直到標(biāo)記面到達(dá)開始單元格。經(jīng)過計(jì)算距離轉(zhuǎn)換，通過從開始單元格開始選擇未訪問的賦值最高的相鄰單元格來找到覆蓋路徑。如果兩個(gè)或兩個(gè)以上的鄰居單元格為相同的值，則隨機(jī)選擇其中一個(gè)單元格。

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

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

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

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

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

規(guī)劃監(jiān)視覆蓋航路時(shí)必須考慮到無人機(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)格要小于這個(gè)投影區(qū)域的大小，但又要盡可能的大。若無人機(jī)的飛行高度為h，垂直視場角為 αα ，水平視場角為 λλ ，俯視角為 ββ 。假設(shè)在地面的視場為梯形ABCD如圖1所示， N,K,FN,K,F 分別為邊 AB,PQ,CDAB,PQ,CD 的中點(diǎn)，OK為 ∠NOF∠NOF 的角平分線。則網(wǎng)格的邊長最大可以為：

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

Figure 1. UAV surveillance field of view

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

2.2. 人工勢(shì)場法生成覆蓋航路

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1. 基因編碼

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

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

1) 交叉算子

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

2) 變異算子

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

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

3) 合并算子

根據(jù)本問題的特殊性，提出一種新的算子，稱為合并算子，也就是將兩個(gè)種子基因進(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：初始化種子群，在種群中選擇一個(gè)種子，在任務(wù)區(qū)域網(wǎng)格中生成勢(shì)場，無人機(jī)位于起始位置 (x0,y0)(x0,y0) ， t=0t=0 ，設(shè)定種子更新的周期T。

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

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

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

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

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

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

初始勢(shì)場采用點(diǎn)型種子生成，如圖5所示。

Figure 5. Initial potential field

圖5. 初始勢(shì)場

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

P1/P0P1/P0

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

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

5. 小結(jié)

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

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

(b) 勢(shì)場總值

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

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

Figure 6. Analysis of the results

圖6. 結(jié)果分析

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

審核編輯：湯梓紅