基于改進遺傳算法的無人機搜索路徑規劃的研究

摘要:?本文針對無人機搜索目標時移動速度的大小和方向不確定的問題，設計了基于改進遺傳算法的搜索路徑規劃算法。傳統的基于解析的辦法適應性不強，不便于計算機自動化計算的實現。本文提出了基于改進遺傳算法的搜索路徑規劃算法，將目標移動方向的概率時間等參數作為動態的人工勢場綜合考慮，提高了搜索路徑規劃問題求解算法的適應性，對于復雜的搜索區域和目標移動概率，均具有較高的適應性和自動化程度。根據遺傳算法中適者生存的思想，擇優選出更加優化的搜索路徑。在這個過程中，將無人機的路徑點當作生物的基因，把搜索路徑看作是生物的染色體，然后通過雜交、選擇、變異等操作得到更加優化的搜索路徑。設置算例進行仿真計算，由仿真計算結果可知，本文提出的基于改進遺傳算法的搜索路徑規劃算法是可行的，并且具有靈活性強、效率高和自動化的優點。

1. 引言

無人機搜索路徑規劃就是為執行搜索任務的無人機規劃搜索路徑，以能夠盡早地發現被搜索的目標。無人機搜索路徑是決定搜索任務成敗的關鍵因素，無人機搜索路徑規劃是無人機搜索任務規劃的核心和關鍵模型。

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

本文針對目標移動速度和方向均存在不確定性的情況，首先建立了目標分布概率模型和無人機探測模型以及搜索區域網格化模型，然后設計了基于改進遺傳算法的搜索路徑規劃算法，并設置算例對算法進行了驗證。

2. 目標分布概率模型

3. 無人機探測模型建模

假設無人機的傳感器對地面進行探測時形成的視場在地面的投影是一個等腰梯形，如圖1所示。為了簡化模型，本文將搜索區域方格化。

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

根據圖中我們可得：

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

圖1. 無人機探測視場地面投影示意圖

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

Figure 2. View angle range diagram of UAV

圖2. 無人機視角角度范圍示意圖

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

Figure 3. Grid diagram

圖3. 網格化示意圖

4. 算法設計

4.1. 路徑編碼

無人機的搜索路徑可以用無人機經過的網格序列來表示。每個網格又可以使用網格的中心坐標x，y來表示。因此，無人機的路徑可以使用?(x,y,t)(x,y,t)?組成的序列來表示(t為無人機經過網格的時間)。

另外，網格還可以使用網格的索引?gigi?來表示，則無人機的路徑可以表示為?(gi,t)(gi,t)?的序列。

4.2. 交叉算子

假設有兩條父路徑分別為：

Figure 4. Schematic diagram of cross operation

圖4. 交叉操作示意圖

4.3. 變異算子

變異包含在兩個點之間插入一個點、在路徑上刪除一個點、在路徑上刪除一個點同時增加一個點這三種情況，圖5為在路徑上刪除一個點之后再增加一個點的變異過程的示意圖。

假設一個父路徑：

Figure 5. Schematic diagram of mutation operation

圖5. 變異操作示意圖

4.4. 適應度函數

適應度函數，是評價路徑優劣的重要指標。計算搜索路徑的適應度，需要綜合考慮影響搜索效果的諸多因素，并對這些因素進行量化、分配權重、綜合、擇優。

式中，F表示路徑的適應度值，?(xi,yi,ti)(xi,yi,ti)?代表第i個搜索方格的中心點坐標。

5. 算例

目標速度在20至30 km/h之間、初始位置為(0, 0)、初始速度方向為50? (以正東為0，逆時針方向旋轉)。目標的航向分布概率如表1所示。

Table 1. Probability table of possible target heading distribution

表1. 目標可能的航向分布概率表

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

設遺傳算法進行時交叉概率?pc=0.6pc=0.6?、變異概率?pd=0.05pd=0.05?、增益系數?km=2km=2?、初始種群數量?N=20N=20。

按照本文設計的基于改進遺傳算法的搜索路徑規劃算法，基于上述的搜索背景和搜索相關的數據，進行搜索路徑規劃的仿真計算。

當目標的移動速度為一個固定的值的時候，由目標可能的航向分布概率表中的目標航向分布概率可以得到目標的概率分布密度函數計算公式：

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

圖6. 計算得到的無人機搜索路徑

在某次計算中，得到一條搜索路徑如圖6所示。得到的是一條弓形的搜索路徑，和傳統的“之”字行掃描方法得到的搜索路徑有所區別，因為本文的搜索目標的移動速度存在一個速度區間，在第一階段搜索沒有尋找到目標的情況時，會重新對目標移速進行預估并再次進行第二階段的搜索，依次類推直到搜索到目標為止。按照本文適應度的計算方法可以求出每一條搜索路徑的適應度值。適應度值可以作為衡量搜索路徑可靠程度的重要指標。當適應度函數的值等于1的時候，可以認為有100%的概率可以搜索到目標。

6. 總結展望

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

審核編輯：湯梓紅