基于改進(jìn)遺傳算法的無(wú)人機(jī)搜索路徑規(guī)劃的研究

摘要:?本文針對(duì)無(wú)人機(jī)搜索目標(biāo)時(shí)移動(dòng)速度的大小和方向不確定的問(wèn)題，設(shè)計(jì)了基于改進(jìn)遺傳算法的搜索路徑規(guī)劃算法。傳統(tǒng)的基于解析的辦法適應(yīng)性不強(qiáng)，不便于計(jì)算機(jī)自動(dòng)化計(jì)算的實(shí)現(xiàn)。本文提出了基于改進(jìn)遺傳算法的搜索路徑規(guī)劃算法，將目標(biāo)移動(dòng)方向的概率時(shí)間等參數(shù)作為動(dòng)態(tài)的人工勢(shì)場(chǎng)綜合考慮，提高了搜索路徑規(guī)劃問(wèn)題求解算法的適應(yīng)性，對(duì)于復(fù)雜的搜索區(qū)域和目標(biāo)移動(dòng)概率，均具有較高的適應(yīng)性和自動(dòng)化程度。根據(jù)遺傳算法中適者生存的思想，擇優(yōu)選出更加優(yōu)化的搜索路徑。在這個(gè)過(guò)程中，將無(wú)人機(jī)的路徑點(diǎn)當(dāng)作生物的基因，把搜索路徑看作是生物的染色體，然后通過(guò)雜交、選擇、變異等操作得到更加優(yōu)化的搜索路徑。設(shè)置算例進(jìn)行仿真計(jì)算，由仿真計(jì)算結(jié)果可知，本文提出的基于改進(jìn)遺傳算法的搜索路徑規(guī)劃算法是可行的，并且具有靈活性強(qiáng)、效率高和自動(dòng)化的優(yōu)點(diǎn)。

1. 引言

無(wú)人機(jī)搜索路徑規(guī)劃就是為執(zhí)行搜索任務(wù)的無(wú)人機(jī)規(guī)劃搜索路徑，以能夠盡早地發(fā)現(xiàn)被搜索的目標(biāo)。無(wú)人機(jī)搜索路徑是決定搜索任務(wù)成敗的關(guān)鍵因素，無(wú)人機(jī)搜索路徑規(guī)劃是無(wú)人機(jī)搜索任務(wù)規(guī)劃的核心和關(guān)鍵模型。

周延安，梅剛 [1] 提出的反輻射無(wú)人機(jī)的搜索路徑規(guī)劃，針對(duì)反輻射無(wú)人機(jī)，利用遺傳算法的雜交、變異操作，得到滿足反輻射無(wú)人機(jī)任務(wù)需求的搜索路徑。候岳奇 [2] 等人針對(duì)未知環(huán)境下無(wú)人機(jī)群的搜索路徑規(guī)劃進(jìn)行了研究。他們是在先驗(yàn)信息的基礎(chǔ)上，建立覆蓋分布地圖，然后通過(guò)多個(gè)無(wú)人機(jī)形成的集群，以覆蓋率作為搜索獎(jiǎng)勵(lì)，并以基于CDM計(jì)算得出的覆蓋率作為衡量搜索效果的指標(biāo)來(lái)進(jìn)行的無(wú)人機(jī)集群的搜索路徑規(guī)劃。李松等人 [3] 提出了一種轉(zhuǎn)換策略，將無(wú)人機(jī)搜索路徑規(guī)劃問(wèn)題轉(zhuǎn)換為車輛的路徑規(guī)劃問(wèn)題，并且在充分考慮無(wú)人機(jī)執(zhí)行搜索任務(wù)的實(shí)際情況后建立模型，通過(guò)求解混合整數(shù)線性問(wèn)題得出最優(yōu)的解，然后得到多無(wú)人機(jī)協(xié)同搜索的路徑。多無(wú)人機(jī)協(xié)同區(qū)域搜索路徑規(guī)劃在 [4] [5] 中有較多的研究，他們分別是基于D-S證據(jù)理論和基于Voronoi圖質(zhì)心進(jìn)行的路徑規(guī)劃，他們都是針對(duì)多無(wú)人機(jī)進(jìn)行的，并且根據(jù)任務(wù)特性，制定相應(yīng)的協(xié)同方式和策略，然后基于各自的算法得到搜索路徑。

本文針對(duì)目標(biāo)移動(dòng)速度和方向均存在不確定性的情況，首先建立了目標(biāo)分布概率模型和無(wú)人機(jī)探測(cè)模型以及搜索區(qū)域網(wǎng)格化模型，然后設(shè)計(jì)了基于改進(jìn)遺傳算法的搜索路徑規(guī)劃算法，并設(shè)置算例對(duì)算法進(jìn)行了驗(yàn)證。

2. 目標(biāo)分布概率模型

3. 無(wú)人機(jī)探測(cè)模型建模

假設(shè)無(wú)人機(jī)的傳感器對(duì)地面進(jìn)行探測(cè)時(shí)形成的視場(chǎng)在地面的投影是一個(gè)等腰梯形，如圖1所示。為了簡(jiǎn)化模型，本文將搜索區(qū)域方格化。

設(shè)無(wú)人機(jī)飛行高度為h、水平視角為λ (λ為圖中的∠BOA)、垂直視角為α、俯視角為β，如圖2所示。在AB邊、PQ邊和CD邊上分別取它們的中點(diǎn)N、K、F，其中OK邊是∠NOF的角平分線。網(wǎng)格的邊長(zhǎng)不能大于梯形的最長(zhǎng)邊CD，也不宜小于最短邊AB，本文取梯形的中線PQ為網(wǎng)格的邊長(zhǎng)。

根據(jù)圖中我們可得：

Figure 1. Ground projection diagram of UAV detection field of view

圖1. 無(wú)人機(jī)探測(cè)視場(chǎng)地面投影示意圖

x、y、z軸的單位是m。

Figure 2. View angle range diagram of UAV

圖2. 無(wú)人機(jī)視角角度范圍示意圖

x、y軸的單位是km。下同。

Figure 3. Grid diagram

圖3. 網(wǎng)格化示意圖

4. 算法設(shè)計(jì)

4.1. 路徑編碼

無(wú)人機(jī)的搜索路徑可以用無(wú)人機(jī)經(jīng)過(guò)的網(wǎng)格序列來(lái)表示。每個(gè)網(wǎng)格又可以使用網(wǎng)格的中心坐標(biāo)x，y來(lái)表示。因此，無(wú)人機(jī)的路徑可以使用?(x,y,t)(x,y,t)?組成的序列來(lái)表示(t為無(wú)人機(jī)經(jīng)過(guò)網(wǎng)格的時(shí)間)。

另外，網(wǎng)格還可以使用網(wǎng)格的索引?gigi?來(lái)表示，則無(wú)人機(jī)的路徑可以表示為?(gi,t)(gi,t)?的序列。

4.2. 交叉算子

假設(shè)有兩條父路徑分別為：

Figure 4. Schematic diagram of cross operation

圖4. 交叉操作示意圖

4.3. 變異算子

變異包含在兩個(gè)點(diǎn)之間插入一個(gè)點(diǎn)、在路徑上刪除一個(gè)點(diǎn)、在路徑上刪除一個(gè)點(diǎn)同時(shí)增加一個(gè)點(diǎn)這三種情況，圖5為在路徑上刪除一個(gè)點(diǎn)之后再增加一個(gè)點(diǎn)的變異過(guò)程的示意圖。

假設(shè)一個(gè)父路徑：

Figure 5. Schematic diagram of mutation operation

圖5. 變異操作示意圖

4.4. 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)，是評(píng)價(jià)路徑優(yōu)劣的重要指標(biāo)。計(jì)算搜索路徑的適應(yīng)度，需要綜合考慮影響搜索效果的諸多因素，并對(duì)這些因素進(jìn)行量化、分配權(quán)重、綜合、擇優(yōu)。

式中，F(xiàn)表示路徑的適應(yīng)度值，?(xi,yi,ti)(xi,yi,ti)?代表第i個(gè)搜索方格的中心點(diǎn)坐標(biāo)。

5. 算例

目標(biāo)速度在20至30 km/h之間、初始位置為(0, 0)、初始速度方向?yàn)?0? (以正東為0，逆時(shí)針?lè)较蛐D(zhuǎn))。目標(biāo)的航向分布概率如表1所示。

Table 1. Probability table of possible target heading distribution

表1. 目標(biāo)可能的航向分布概率表

無(wú)人機(jī)的最大飛行速度為80 km/h、初始位置(2, 2)、最大航偏角為50?、完成搜索任務(wù)的時(shí)間上限為?tg=60mintg=60min。

設(shè)遺傳算法進(jìn)行時(shí)交叉概率?pc=0.6pc=0.6?、變異概率?pd=0.05pd=0.05?、增益系數(shù)?km=2km=2?、初始種群數(shù)量?N=20N=20。

按照本文設(shè)計(jì)的基于改進(jìn)遺傳算法的搜索路徑規(guī)劃算法，基于上述的搜索背景和搜索相關(guān)的數(shù)據(jù)，進(jìn)行搜索路徑規(guī)劃的仿真計(jì)算。

當(dāng)目標(biāo)的移動(dòng)速度為一個(gè)固定的值的時(shí)候，由目標(biāo)可能的航向分布概率表中的目標(biāo)航向分布概率可以得到目標(biāo)的概率分布密度函數(shù)計(jì)算公式：

Figure 6. A schematic of the calculated UAV’s search path

圖6. 計(jì)算得到的無(wú)人機(jī)搜索路徑

在某次計(jì)算中，得到一條搜索路徑如圖6所示。得到的是一條弓形的搜索路徑，和傳統(tǒng)的“之”字行掃描方法得到的搜索路徑有所區(qū)別，因?yàn)楸疚牡乃阉髂繕?biāo)的移動(dòng)速度存在一個(gè)速度區(qū)間，在第一階段搜索沒(méi)有尋找到目標(biāo)的情況時(shí)，會(huì)重新對(duì)目標(biāo)移速進(jìn)行預(yù)估并再次進(jìn)行第二階段的搜索，依次類推直到搜索到目標(biāo)為止。按照本文適應(yīng)度的計(jì)算方法可以求出每一條搜索路徑的適應(yīng)度值。適應(yīng)度值可以作為衡量搜索路徑可靠程度的重要指標(biāo)。當(dāng)適應(yīng)度函數(shù)的值等于1的時(shí)候，可以認(rèn)為有100%的概率可以搜索到目標(biāo)。

6. 總結(jié)展望

本文研究了無(wú)人機(jī)針對(duì)移動(dòng)速度的大小和方向不確定的目標(biāo)進(jìn)行搜索的問(wèn)題，在建立了目標(biāo)分布概率模型和無(wú)人機(jī)探測(cè)模型的基礎(chǔ)上，設(shè)計(jì)了基于改進(jìn)遺傳算法的無(wú)人機(jī)搜索路徑規(guī)劃算法。本文的算法和解析方法相比，具有更高的適應(yīng)性和自動(dòng)化程度。本文針對(duì)移動(dòng)目標(biāo)進(jìn)行的搜索路徑規(guī)劃研究，搜索目標(biāo)不是單純的固定目標(biāo)，是具有一定速度范圍的移動(dòng)目標(biāo)，并且移動(dòng)的方向也是不確定的，增強(qiáng)了無(wú)人機(jī)搜索路徑規(guī)劃的靈活性和實(shí)用性。下一步的研究將會(huì)著眼于考慮目標(biāo)變向移動(dòng)以及環(huán)境、天氣以及其他特殊原因的影響，考慮無(wú)人機(jī)飛行高度的不確定性，以此來(lái)提高無(wú)人機(jī)搜索路徑規(guī)劃算法應(yīng)對(duì)各種復(fù)雜的搜索環(huán)境的適應(yīng)性。

審核編輯：湯梓紅