基于改進遺傳算法的無人機路徑規(guī)劃

黃書召，田軍委，喬 路，王 沁，蘇 宇

（1.西安工業(yè)大學電子信息工程學院，西安 710021；2.西安工業(yè)大學機電工程學院，西安 710021）

（*通信作者1945980733@qq.com）

0 引言

近年來，受益于輕型高分子材料的發(fā)現(xiàn)以及嵌入式、自動化、信號處理、無線通信等技術的發(fā)展與成熟，無人機（Unmanned Aerial Vehicle,UAV)在田間信息獲取、農(nóng)業(yè)植保、設施巡檢、物流配送［1-2］等場景中廣受青睞。在借助UAV進行田間信息獲取時，所獲取的信息可能很多，覆蓋面積廣。由于民用UAV 的續(xù)航時間短，這就導致不同的信息獲取路線所耗費的作業(yè)時間相差甚遠。因此，UAV 路徑規(guī)劃［3］是田間信息獲取場景下的關鍵問題。

路徑規(guī)劃技術作為任務規(guī)劃系統(tǒng)的核心部分之一，受到了廣泛關注。在這一領域，國內(nèi)外已經(jīng)展開了大量的研究工作。文獻［4］中針對傳統(tǒng)A*（A Star）算法搜索路徑效率低、路徑存在許多冗余節(jié)點和轉折點的問題，引入啟發(fā)函數(shù)，得到了更優(yōu)質(zhì)的路徑。文獻［5］中為了實現(xiàn)全局路徑搜索，對A*算法進行了深入的探討并介紹了幾種A*算法的擴展算法。快速搜索隨機樹（Rapidly-exploring Random Tree，RRT）算法和概率路線圖（Probabilistic RoadMap，PRM）算法都是概率型算法：前者從起始位置開始，通過概率分布連續(xù)產(chǎn)生生成樹，當樹的節(jié)點到達目標位置時，算法停止［6］；后者通過對地圖進行概率畫點從而完成對地圖節(jié)點的離散，之后連接所有可視線段，結合使用A*等搜索算法實現(xiàn)路徑尋優(yōu)［7］。當前對于RRT算法和PRM 算法的研究主要集中在解決narrow-passage 問題上，Kalisiak 等［8］提出了動態(tài)規(guī)劃的RRT，Jiménez-Franco 等［9］提出了基于粒子濾波的RRT 來確保在不確定性地形中隨機樹的生長。上述算法在路徑規(guī)劃技術都有著不錯的發(fā)展，但A*算法在復雜地形下計算效率過于低下，RRT和PRM 存在著narrow-passage 等問題，這使得上述算法都難以應用至真實的三維路徑規(guī)劃上；但上述算法由于具有在簡單地形中搜索高效的特點，被廣泛地應用于動態(tài)在線規(guī)劃中［10］，而在離線規(guī)劃中，智能算法相比以上算法有著更大的優(yōu)勢。

遺傳算法（Genetic Algorithm，GA）［11］具有強大的全局搜索能力，特別是在復雜優(yōu)化問題中的搜索能力，使得GA 廣泛地應用于路徑規(guī)劃、任務分配等問題研究。目前對于GA 進行路徑規(guī)劃的幾個研究重點在于：航跡的表示［12］、GA 算子的設計及改進等；研究人員期望通過研究這些重點來解決GA中的早熟和收斂速度等問題。文獻［13］中針對傳統(tǒng)GA 不適用于轉彎情況較多的復雜地圖，首先將RRT 算法用于柵格環(huán)境產(chǎn)生初始路徑，接著提出一種新的插入算子，最后進行路徑優(yōu)化；文獻［14］中提出將極坐標與笛卡爾坐標結合的方式來表示航跡，從而降低計算消耗；文獻［15-16］中提出了一種多頻變異和交叉的思想，用于解決GA 中的早熟問題，并提出對種群初始化進行預處理，從而加快收斂；文獻［17］中將GA 與ACO相結合，提出了一種新的融合算法，重點對時序約束進行了考慮；文獻［18］中利用染色體路徑表示的GA，并使用部分映射交叉的另一種形式，提高了基于置換的GA 的效率。雖然針對GA 路徑規(guī)劃問題已經(jīng)進行了諸多研究，但仍然存在以下幾個不足：

1）不能最大限度保留優(yōu)質(zhì)基因；

2）進化過程中染色體長度固定，重復基因處理不當；

3）變異隨機性大，不一定能產(chǎn)生最優(yōu)基因。

本文針對上述問題，提出了混合無重串選擇算子、非對稱映射交叉、啟發(fā)式多次變異三種算子，并且引入三次B樣條曲線平滑算法解決了GA 在無人機路徑規(guī)劃中存在的問題。最后通過實驗結果證明，改進后算法規(guī)劃路徑相較其他算法規(guī)劃出的路徑更優(yōu)，具有很好的性能以及較強的適應性。

1 模型建立

1.1 環(huán)境模型

農(nóng)田信息的快速全方位獲取是實現(xiàn)水肥藥高效管理和精準施用的前提和基礎。為了獲取田間信息，無人機被用于承擔在某一特定區(qū)域實施信息獲取任務。

無人機路徑規(guī)劃過程所需信息需要從地形模型中提取，良好的地形建模能有效提高路徑規(guī)劃效率。本文考慮原始地形、障礙區(qū)域等因素來進行環(huán)境建模。基準地形模型［19］為：

式中：x和y為模型投影在水平面上的點坐標；Z1為水平面點對應的高程值；a、b、c、d、e、f、g為常系數(shù)，控制數(shù)字地圖中的基準地形起伏。

對于飛行環(huán)境中的較高的天然山體用指數(shù)函數(shù)來進行描述，數(shù)學模型可以表示為：

式中：()xi，yi是第i個山峰的中心坐標；hi為地形參數(shù)，控制高度；xsi和ysi分別是第i個山峰沿x軸和y軸方向的衰減量、控制坡度；n表示山峰總個數(shù)。環(huán)境模型如圖1所示。

圖1 環(huán)境模型Fig.1 Environment model

1.2 飛行路徑表示

無人機的飛行路徑是通過有序的點坐標進行表征的，各個相互接近的空間坐標點彼此使用三次B樣條平滑曲線進行關聯(lián)。假設這一組節(jié)點序列是{S，W1，W2，…，Wn-1，G}，此組節(jié)點序列由N+1 個節(jié)點構成；S和G分別代表了無人機的起點與終點；W1，W2，…，Wn-1是飛行過程中的各個節(jié)點；設定起飛點與終止點的三維表述是S=(x0，y0，z0)，G=(xn，yn，zn)；用Wi=(xi，yi，zi)(i=1，2，…，n-1)描述各個中間節(jié)點。

1.3 基于三次B樣條曲線的路徑平滑算法

為了保證航跡平滑可飛，減少算法計算時間，本文使用三次B 樣條曲線對路徑進行平滑，文獻［20］中主要是通過添加控制點來有效規(guī)避障礙并生成平滑飛行航跡。

1.3.1 路徑平滑基函數(shù)及控制點

給定空間頂點Pi(i=0，1，…，m+n)可以得到n次曲線段：

式中：Pi為第i個控制點對應的曲線方程，F(xiàn)i，k(t)為k階B 樣條基函數(shù)。由于k值代表曲線的平滑程度，k值越大，曲線平滑程度越好，但計算復雜度也越大。為了兼顧平滑度和復雜度，本文選取k=3，得到三次B樣條曲線基函數(shù)為：

將遺傳算法得到的點集稱為路徑規(guī)劃點M，假設M中有n+1 個有序空間位姿矢量Vi(i=0，1，…，n)，把相鄰的k+1個位置矢量作為一組進行線性組合，就可以得到第i段相鄰k+1個控制點的曲線公式為：

式中，Pi(x)為第i條B 樣條曲線函數(shù)。當k=3 時，將式（4）代入式（6）得到曲線的矩陣形式為：

1.3.2 曲線差值

式（6）中的Vi-1，Vi，Vi+1，Vi+2是一組控制點，在無人機路徑規(guī)劃中，需要先知其所求路徑上的型值點，型值點即無人機運動學逆問題求解求出來的點。如果對已知型值點路徑規(guī)劃，首先要求控制點，設P為型值點，得到以下條件：

式（7）中，有m+2 個未知數(shù)，但只有m個方程，因此添加全局路徑點集首尾端點約束條件如下：

由給定邊界條件可以唯一確定一組Vi-1，Vi，Vi+1，Vi+2，式（6）確定的B樣條曲線表示為：

式（9）中，由Vi-1，Vi，Vi+1，Vi+2四個控制點控制，設控制點的坐標由(Xi，Yi，Zi)(i=1，2，…，n)表示，其中參數(shù)x均勻取0 到1 之間、間隔為0.01 的所有數(shù)，就可以得到第i段B 樣條曲線。曲線任意點坐標(Xt，Yt，Zt)表示如下：

最后，令k=3，依據(jù)式（9）、（10）就可以得到三次B 樣條曲線的連接點。為了降低計算復雜度，將重復連接點刪除，然后連接剩下連接點就可以得到三次B樣條曲線平滑效果圖如圖2所示。

圖2 三次B樣條曲線效果Fig.2 Effect of cubic B-spline curve

2 路徑規(guī)劃數(shù)學模型

無人機的路徑規(guī)劃有許多約束條件，這些約束限制了無人機的機動動作，導致尋找最優(yōu)路徑十分困難。本文路徑規(guī)劃研究考慮的約束條件和目標函數(shù)如下。

2.1 約束條件

約束條件的目的是保證規(guī)劃出可飛路徑，本文針對單無人機路徑規(guī)劃，因此，提出了地形和環(huán)境約束2個約束條件。

在完成信息獲取任務時，為了避免發(fā)生碰撞，無人機飛行高度應始終高于地形高度，故地形約束條件建模為：

式中，Z2()xi，yi為地形函數(shù)，用于返回位置()xi，yi處的地形高度值。

在執(zhí)行信息獲取任務的過程中，為了規(guī)劃出更好的路徑，同時降低代價，規(guī)定無人機只能在指定區(qū)域內(nèi)工作，環(huán)境約束條件模型為：

2.2 目標函數(shù)

對于可飛的路徑，將無人機的航程、障礙物和邊界約束綜合考慮，能夠歸納出飛行器的綜合代價函數(shù)表達式如下：

式中：Vc表示航程代價；Tc表示地形代價；Ec表示邊界代價。

航程代價Vc主要考慮無人機從起點到終點的飛行距離，與距離L成正比，如果總航跡由n個航點組成，那么航程總代價可以表示為：

地形代價Tc主要考慮無人機在完成信息獲取任務過程中山峰的威脅，通過該代價約束，可以使無人機躲避工作過程中的障礙，表達式如下：

邊界代價Ec主要考慮無人機在完成信息獲取任務過程中，保證無人機工作在指定空間區(qū)域中，表達式如下：

3 改進遺傳算法設計

對于田間信息獲取任務，遺傳算法若要規(guī)劃出更好路徑，在編碼方式、適應度函數(shù)、遺傳算子設計等方面必須更加符合實際，具體設計如下。

3.1 編碼方式與初始化

由于本文采用三次B 樣條曲線平滑路徑以減少計算時間，因此個體編碼采用實數(shù)直接編碼，路徑個體表示為從出發(fā)點到目標點的一系列中途點，可以用{S，W1，W2，…，Wn-1，G}進行表示，其中，S和G分別代表起點和終點，Wi代表路徑的中途點。編碼方式圖如圖3所示。

圖3 編碼方式Fig.3 Encoding mode

初始化采用工作區(qū)域內(nèi)隨機初始化方式，這種初始化方式簡單，而且能保證產(chǎn)生的初始種群都在工作范圍內(nèi)，并且初始化染色體長度相等。

3.2 適應度函數(shù)

遺傳算法利用種群中每個個體的適應度值來進行搜索，適應度函數(shù)的選取直接影響到算法的收斂速度以及能否找到最優(yōu)解。本文是最小化問題，適應度函數(shù)是由目標函數(shù)變換而成，目標函數(shù)轉換為適應度函數(shù)，通過式（17）可以得到：

本文方法不需要對個體進行解碼，可以直觀地反映解的優(yōu)劣程度。

3.3 改進遺傳操作

遺傳操作分為選擇、交叉、變異算子三個部分，是遺傳算法的核心。本節(jié)對上述三種算子分別進行改進，期望得到更好的收斂效果。

3.3.1 混合無重串選擇算子

為了避免算法出現(xiàn)早熟現(xiàn)象，同時保證更好的個體可以直接進入下一代種群，本文提出了一種混合無重串的選擇算子，該算子是由兩種選擇方式按照一定比例組合產(chǎn)生，然后在此基礎上進行沒有重串的穩(wěn)態(tài)繁殖。第一種方式是錦標賽選擇，所占比例為α；第二種方式是輪盤賭選擇，個體的入選概率與其適應度值成正比，所占比例為1-α。選擇完成后，首先判斷該個體與種群中現(xiàn)有個體是否重復，如果重復就舍棄。

3.3.2 非對稱映射交叉算子

根據(jù)積木塊假設［21］，在基本遺傳算法中，定義距長的模式很容易受到破壞，這對進化模擬而言是十分不利的。為了克服這一缺點，同時提高算法的收斂效果，本文提出了非對稱映射交叉算子，該算子在不影響模式定義距的情況下，使優(yōu)良的種群得以增值。

設計上，首先設計截斷和拼接交叉算子，以適應染色體長度的變化；在截斷操作中，隨機選擇兩個不同的父代染色體，然后隨機產(chǎn)生兩個交叉點位，在交叉點截斷生成四個基因段；最后，對基因段進行組合生成兩條子代染色體。截斷和拼接操作如圖4所示。

圖4 染色體截斷和拼接操作Fig.4 Chromosome truncation and splicing operations

第二步，完成截斷和拼接操作后，消除子代染色體產(chǎn)生的重復基因。

由于本文規(guī)劃環(huán)境較大，基因變化較小時，在地圖中差別不大，因此，本文提出了一種重復基因定義的方法：當某個點基因都在這區(qū)間范圍內(nèi)變化時，視為重復基因，需要對其做相應的處理。相似區(qū)間的定義可以結合區(qū)間劃分的思想。

假設D為搜索空間，[Smin，Smax]為n個區(qū)間長度變量取值范圍，Smin=[S1_min，S2_min，…，Sn_min]為n個區(qū)間長度變量的最小集合，Smax=[S1_max，S2_max，…，Sn_max]為n個區(qū)間長度變量的最大集合，則劃分為m個區(qū)間，需要m+1 個區(qū)間向量對[Smin，Smax]進行劃分，則m個區(qū)間可通過式（18）得到：

其中，l代表兩個區(qū)間長度的間隔，由式（19）確定。

重復基因確定之后，通過截斷前映射和截斷后順序復制兩種方法處理。

截斷前映射是使截斷點之前的重復基因不變，對截斷點之后的重復基因用*表示，處理結果如圖5（a）所示。

然后，通過截斷點之前部分消除重復基因，例如：子代1中2→20，3→10，6→15，與子代1 中基因不重復，則選擇此基因替代重復基因。按照此方法依次消除重復基因得到最終結果如圖5（b）所示。截斷后順序復制是使截斷點之后重復基因不變，對截斷點之前重復基因用*表示，處理結果如圖5（c）所示。最后，從父代2 中找出子代1 中沒有的基因，并將其按順序給子代*位置，得到最終結果如圖5（d）所示。

圖5 重復基因處理方法Fig.5 Duplicate gene treatment method

綜上所述，截斷前映射可以保證后代染色體不會有重復基因，保留父代優(yōu)秀基因；截斷后順序復制擴大了染色體改變范圍，增大了搜索空間。因此，考慮用兩種方法來對重復基因進行處理。在進化初期，適應度值比較分散（i≤k*β，i表示當前迭代次數(shù)，k表示總迭代次數(shù)，β控制比例），采用截斷前映射消除重復基因；進化后期個體適應度值趨于一致或趨于局部最優(yōu)（i＞k*β），采用截斷后順序復制消除重復基因。

3.3.3 啟發(fā)式多次變異算子

針對傳統(tǒng)隨機變異算子早熟問題，本文提出了一種啟發(fā)式多次變異算子來探索未知區(qū)域，抑制早熟現(xiàn)象，即通過多次啟發(fā)式變異，尋求其中代價值最低的個體進入下一代。該算子流程如下：

1）發(fā)生變異時，先檢查其中途點Pi與Pi+2是否有障礙物或者有不在工作區(qū)域內(nèi)的點。

2）如果有，對穿越障礙物的點，或者不在工作區(qū)域的點進行變異，之后返回步驟1），直到該路徑是可行路徑為止。

3）如果沒有，對其中途點隨機變異，并且將Pi記錄到R中。

4）如果R不為空，則從R中隨機選取一點進行刪除；否則，隨機選取路徑中一點刪除。

5）返回步驟1）進行多次變異（變異次數(shù)一般取3或4），最終尋求其中代價值最低的個體進入下一代。

4 算法仿真與結果分析

為了驗證所提路徑規(guī)劃算法和有效性，利用Matlab 進行了仿真驗證，本文的主要參數(shù)設置如表1所示。

表1 改進GA與ACO算法的主要參數(shù)Tab.1 Main parameters of improved GA and ACO algorithm

為了驗證本文改進GA的合理性，對比了改進GA、傳統(tǒng)遺傳算法（GA）、蟻群優(yōu)化（Ant Colony Optimization，ACO）算法的收斂速度和代價值。在Matlab 2016a（主機Intel i5-5200U，CPU@2.20 GHz，4 GB RAM，Windows 10 系統(tǒng)）上運行了10次，并統(tǒng)計了10 次實驗算法的平均收斂速度、代價值和程序運行時間，最終結果如表2 所示。由表2 可知，改進GA 平均代價值為392，平均在第5 代收斂，而GA 和ACO 算法代價值和收斂速度明顯要低。

圖6 是這三種算法的規(guī)劃結果，從中可以看出，改進GA的規(guī)劃結果最優(yōu)。這是因為改進GA 的染色體在進化過程中是變化的，更加符合實際，而啟發(fā)式多次變異過程中擴大了隨機搜索范圍，保證了可行解的質(zhì)量。

表2 改進GA與傳統(tǒng)GA和ACO算法的代價值與收斂速度對比Tab.2 Comparison of cost value and convergence iterations between improved GA with traditional GA and ACO algorithm

4.1 啟發(fā)式變異與隨機變異對算法的影響

為了驗證改進后變異算子和交叉算子的性能，表3 給出了不同變異和交叉算子的代價值對比結果。由于收斂后代價值基本不再變化，所以為了展示方便，本文值選取了前15 代數(shù)據(jù)進行展示。通過表3 可以看出，采用啟發(fā)式多次變異在第2代開始收斂，而隨機變異在第12代才收斂，使用啟發(fā)式變異相比隨機變異代價值減小了32%；采用非對稱映射交叉在第5 代開始收斂，而模擬二進制交叉在第9 代才收斂，使用非對稱映射交叉相比模擬二進制交叉代價值減小了50%?？梢?，本文所設計的交叉和變異算子可以獲得更好的效果。這是因為啟發(fā)式變異既保證了種群多樣性，又使變異目標更加明確，避免種群陷入局部最優(yōu)。

表3 不同變異算子和交叉算子的路徑規(guī)劃代價值對比單位：mTab.3 Cost value comparison of path planning with different mutation operators and crossover operators unit：m

圖7對比不同交叉率和變異率對求解算法的影響，從圖7實驗結果可以看出，不同的交叉率和變異率對代價值和收斂速度都有一定的影響。當交叉率小于變異率時代價值為837，收斂速度為10；當變異率大于交叉率時代價值為422，收斂速度為3。這是因為在變異操作中變異率太高，算法退化為隨機搜索，變異率太小不容易產(chǎn)生新的結構。交叉概率過大新個體產(chǎn)生速度越快，種群被破壞的可能性也越大；交叉概率太小又會導致算法停滯不前。經(jīng)過多次實驗發(fā)現(xiàn)，當交叉率為1/ChromoSize時效果最好，ChromoSize表示染色體大小。

此外，染色體大小的選擇對路徑規(guī)劃結果也有很大影響，不同染色體大小規(guī)劃結果對比如圖8所示。

圖6 GA、ACO算法與改進GA的路徑規(guī)劃結果Fig.6 Path planning results of GA，ACO algorithm and improved GA

圖7 不同交叉率和變異率的路徑規(guī)劃代價值對比Fig.7 Cost value comparison of path planning with different crossover rates and mutation rates

圖8 不同染色體大小的路徑規(guī)劃代價值對比Fig.8 Cost value comparison of path planning with different chromosome sizes

從圖9實驗結果可以看出，當染色體長度為12時，平均代價值為1 870；染色體長度為6 和9 時，代價值分別為11 400 和1 158。但是，通過圖9 可以看出，染色體長度為6 時，規(guī)劃結果不可飛，不能保證每次都能規(guī)劃出可飛路徑；染色體長度為12 時，雖然規(guī)劃的結果可飛，但是代價高，路徑有冗余，計算復雜度增大。因此，選擇適當?shù)娜旧w大小對規(guī)劃的最優(yōu)結果是至關重要的。

4.2 不同環(huán)境對算法的影響

圖10 展示了不同障礙物分布對無人機路徑規(guī)劃的影響，從圖中可以看出，無論面對何種障礙物，該算法都可以規(guī)劃出較好的路徑。

圖11 是算法在大尺寸地圖上的表現(xiàn)，在不考慮無人機工作時間的情況下，仍能規(guī)劃出很好的結果，表明該算法具有很強的適應性，面對不同的環(huán)境，可以完成信息獲取任務。

圖9 不同染色體長度的路徑規(guī)劃結果對比Fig.9 Path planning results comparison of different chromosome lengths

圖10 不同障礙物分布對無人機路徑規(guī)劃的影響Fig.10 Influence of different obstacle distribution on UAV path planning

圖11 算法在大尺寸地圖上的規(guī)劃結果Fig.11 Planning results of algorithm on large maps

5 結語

本文提出了改進遺傳算法的路徑規(guī)劃方法。首先，為了模擬真實環(huán)境，考慮原始地形和障礙區(qū)域進行環(huán)境建模；其次，提出了混合無重串選擇算子擴大了種群的分布范圍，能在一定程度上避免算法過早收斂，在此基礎上，還提出了非對稱映射交叉算子和啟發(fā)式多次變異算子，能加快收斂；然后，采用三次B 樣條曲線對航跡平滑，保證最終航跡更平滑。通過Matlab 仿真表明，改進遺傳算法得到的路徑更優(yōu)，并且得到選取變異率和交叉率的更好方法，能夠解決三維環(huán)境下路徑規(guī)劃問題。由于無人機工作時間有限，無法長時間工作，后期將針對無人機長時間作業(yè)進行研究。