四旋翼無人機航徑規劃遺傳算法研究

王世凱，耿振野，劉智，黃丹丹，李艷山

（長春理工大學 電子信息工程學院，長春 130022）

航徑規劃的核心內容是根據所要到達的目標，在符合約束條件的情況下，設計出合理的飛行路線。對于四旋翼無人機來說，自主航路規劃是必不可少的重要部分。特別是當隊伍參加“英飛凌”杯全國高校無人機創新設計應用大賽以來，更明白航徑規劃的重要性。航徑規劃的目的，就是在規定的時間范圍內，通過自身的運算，來得到最優或者次優的航線，從而能夠有效地規避障礙物。而自動避障技術［1］是四旋翼無人機安全飛行的重要保證。飛行航徑規劃最終負責產生軌跡空間，四旋翼無人機在進行飛行任務時，需要根據地形、障礙物等信息，有效實時地做出判斷，準確地計算出飛行航路，實現到達目標位置的飛行任務。目前，無人機航徑規劃算法主要有可行性方向算法、實時優化算法、A*搜索算法［2］、啟發式搜索算法［3］、神經網絡算法［4］、蟻群算法［5］等，這些方法能在一定程度上達到相應代價的航路規劃功能。但是，大多數傳統的方法都存在著很大的缺陷。例如，規劃結果需要進一步優化后，才能實現四旋翼無人機的穩定飛行，不能保證實時性和安全性。針對傳統的遺傳算法［6］，本文對遺傳算法做出改進，使其能夠對四旋翼無人機進行最短的航路規劃。本文提出了一種改進的遺傳算法，可以更加有效地規劃飛行航徑。

傳統的四旋翼無人機航徑規劃方法處理流程，一般情況下可以劃分成兩部分來得到完美實現。第一個部分是從整體的角度上分析，獲取參考航徑規劃；第二個部分是從局部的角度分析，進行航徑動態優化。結合無人機在飛行過程中所需要完成的目標、安全標準、持續時間等因素，經過綜合考量，得到最佳的性能指標。在此基礎上，利用航徑規劃算法，便能夠獲取最佳的參考航徑。針對處理流程，本文做出了分析，在實際情況下，必須考慮到參考路徑旁邊的障礙物分布情況，還有無人機存在的約束條件，比如轉動的角度、所處的位置、當前的速度等，它們都會對無人機的飛行狀態造成影響。因此，需要對參考航徑做出改良，通過優化處理，來得到最佳的飛行路線。在四旋翼無人機執行系統的控制下，平穩的向下一個目標運動，這具有很好的應用前景［7］。當四旋翼無人機起飛、懸停完畢后，開始自主飛行命令，通過設置的障礙物，加以傳感器的信息補償，及時調整飛行位置，無人機根據感知到的信息，融合改進遺傳算法，從而確定最佳的飛行路線，來確定在漫游飛行過程中，合理的規避當前感知到的障礙物。

1 四旋翼無人機平臺

本設計使用基于英飛凌XMC4700與N3飛控的Onboard SDK平臺，并應用了英飛凌的多種傳感器，實現對四旋翼無人機的控制。融合了動力、飛控、導航、相機、圖傳與數傳等系統模塊，飛行的高度能夠達到50m以上，而且有著很強的負載能力，是一個比較穩定的飛行平臺。可以支持多種類型傳感器，能夠在復雜環境下實時計算。四旋翼無人機管理平臺如圖1所示。

圖1 四旋翼無人機管理平臺

如圖2，四旋翼無人機通過障礙物信息估算距離、高度及導航位置。通過改進遺傳算法來計算出比例信息，得到已知尺度下的障礙物（高度、位置）信息的數據估計，再通過判斷獲取的障礙物信息對兩者的距離估計信息進行篩選，以保證四旋翼無人機始終處于飛行安全位置。

圖2 無人機探測障礙物

四旋翼無人機航徑規劃首先進行環境的規劃，包括建立障礙物模擬模型和無人機參考坐標系，接著是巡航階段的航跡表示，考慮到約束條件，需要使用目標函數，合理地規劃算法，最后統計分析出最佳航徑?？傮w框圖如圖3所示。

圖3 航徑規劃總體框圖

2 模型搭建

考慮到四旋翼無人機是從障礙物中尋找最短航徑，本文將大小不同、不規則靜態障礙物用圓形圖標來表示，如圖4所示環境模型。

圖4 靜態障礙物模擬模型

通過圖4的靜態障礙物模擬模型，本文給出了圖5搭建的二維空間環境模型，四旋翼無人機被簡化為質點，四旋翼無人機從起始位置(x(t),y(t))飛向目標位置(xs,ys)，定義四旋翼無人機的質心為轉向點，α為四旋翼無人機的當前運動方向與質心到目標位置連線的夾角，L為四旋翼無人機到目標位置的距離。

圖5 參考坐標系

根據圖5結合數學知識，可以得到：

四旋翼無人機的運動學方程為：

其中，(x,y,θ)是四旋翼無人機的位姿，四旋翼無人機與目標距離的距離為L，Ld為距離目標位置的安全距離。記四旋翼無人機與目標位置的距離誤差為L誤=L-Ld，則四旋翼無人機的位姿誤差極坐標方程為：

3 航跡表示

很多情況下，由于四旋翼無人機在起飛后將保持一定的高度進入巡航階段［8］，飛行的過程中通常只需要關注其水平方向的軌跡，按照事先設定好的高度參數，利用平面幾何的原理進行規劃。周圍的環境可能是未知的，四旋翼無人機只能通過搭載的傳感器探測障礙物，所以無人機的航徑規劃問題應該考慮兩個方面的問題：一個是單個靜態障礙物航徑規劃問題，一個是多個障礙物航徑規劃問題。在圖6中，給出單個障礙物的處理方法，A代表最初起飛的地方，B代表所要到達的地方，h代表巡航高度。當無人機飛行到h高度的時候，A與B中間的障礙物所存在的地方，用圓形圖標來顯示。當h改變的時候，A與B中間的障礙物存在的地方亦會隨之改變。

圖6 單個靜態障礙物平面示意圖

如圖6所示，在初始位置A和目標位置B之間有1個靜態障礙物。線段AB經過障礙區，需要做Aa，Ac，bB，dB切圓，還需要計算出線段Aa，Ac，bB，dB和弧線ab，cd的長度作為節點代價。對于單個障礙物問題選擇用圖中所展示的方法，同樣地，多個靜態障礙物處理方法相同。通過一系列運算，得到切點、切線以及圓弧的長度，并由此來獲取下一個層次的節點與節點代價，如此依次類推。

四旋翼無人機規劃一條最佳航徑，不光要考慮周圍的環境，處于環境中的障礙物，復雜的地形，還要考慮無人機的自身條件，即最小轉彎半徑、航徑長度、爬升角等等。這里主要考慮解決最短航徑長度問題。

4 改進遺傳算法

航徑規劃應該在具有任意形狀障礙物的連續空間中解決。利用五個定制的交叉和變異算子來改善初始航徑，并根據上述目標生成最優解。為了評估所提出的算法的效率，檢查了具有復雜度的平面環境，以在連續環境中找到航徑長度，平滑度和安全性的最佳航徑。該航徑不受離散網格化環境中的網格的限制。本文考慮二維環境中的航徑規劃問題，其中充滿了任意形狀的靜態障礙物，其與自由空間沒有相互作用（正面或負面屬性）。同時，本文把四旋翼無人機標記為點。飛行路線定義為航徑或軌跡［9］。可以通過在二維環境中選擇適當的飛行節點集來定義四旋翼無人機可以飛行的路徑。因此，改進遺傳算法為所有節點分配適當的潛在值。然后，四旋翼無人機確定起始位置和目標位置之間的所有可行航徑。

本文提出了一種帶有改進遺傳算子的改進遺傳算法，以確定定義的飛行坐標點，使四旋翼無人機在連續環境中找到最佳位置。改進遺傳算法的主要特征是：具有可變長度染色體群，增加尋找最佳路徑的靈活性；具有五個交叉算子和變異算子，能夠找到飛行坐標點的最佳位置；改進遺傳算法重復演變，一直到達到終止條件。在本文中，使用固定迭代次數作為終端條件。

圖7是改進遺傳算法航徑規劃過程。

圖7 改進遺傳算法航徑規劃過程

4.1 選擇運算

選擇算子隨機或基于預定義的度量從總體中選擇一些個體。在本文中，使用輪盤轉輪選擇（RWS）來選擇交叉算子的親本。每個個體的選擇概率與其質量成反比關系。因此更好的個體有更多的機會被RWS選中。同時，秩的選擇是被用于第i次迭代，其包括第(i-1)次迭代的群體和由遺傳算子獲得的新后代。

4.2 改進交叉算子

修改后的交叉算子結合了兩個具有相同或不同數量的飛行坐標點，以產生新的后代，這在預定義的目標方面可能更好。第一個交叉算子通過計算兩個親本的平均值來找到一個新的后代：

其中，x1p，y1p和x2p，y2p是兩個親本的飛行坐標點的x和y坐標，xf，分別是個體的飛行坐標點。當兩個親本的飛行坐標點不相等時。首先，選擇具有較小飛行坐標點的親本Ps。然后，通過取Ps的每個飛行坐標點的平均值，以及另一個親本最近的飛行坐標點來計算后代的飛行坐標點(xf,)。在第二個交叉算子中，兩個親本以隨機方式組合以增加多樣性并搜索整個自由空間：

其中，γ是[- 1,1]范圍內隨機數的向量。在兩個親本的飛行坐標點不相等的情況下，類似于第一交叉算子，將具有最小距離的飛行坐標點組合在一起。第一交叉算子可以用于生成更短更平滑的航徑，第二交叉算子可以用于隨機搜索環境，以避免過早收斂。

4.3 改進變異算子

變異算子可以增加群體多樣性、搜索環境區域以及能夠將一組飛行坐標點移動到特定方向上，這些對于增加航徑平滑度和獲得最短航徑長度是非常有用的。第一個變異算子是一個算術變異算子，它在隨機方向上改變預定數量飛行坐標點的位置。該算子對提高多樣性和避免過早收斂有很大的幫助。第二個變異算子修改飛行坐標點的位置，以改善路徑的長度和平滑度。該算子通過將其當前位置Pi和朝向兩側的飛行坐標點方向（Pi-1和Pi+1）進行積分來改進飛行坐標點的位置。

其中，δ和β是小的正系數。第二個變異算子產生的航徑具有更高的平滑度和更短的長度。第三個變異算子將任意選擇的飛行坐標點移向到目標位置。這三種變異算子的組合為改進遺傳算法的探索和開發提供了支持。

4.4 選擇刪除運算算子

為了使算法性能穩定，在改進遺傳算法中使用刪除運算算子，這與初始航徑中的飛行坐標點無關，與下一坐標點有關。刪除運算算子刪除航徑的冗余飛行坐標點。首先，從群體中選擇個體。然后刪除運算算子有順序地評估每個飛行坐標點。如果刪除任何選定的飛行坐標點是有效的，那么就可以減少航徑的長度。

5 仿真驗證與分析

根據航徑規劃遺傳算法的要求，經改進遺傳算法計算可得優化后的最優飛行航跡。

（1）實驗環境：Intel（R）Xeon（R）CPU，運行內存為 32GB的 Win7 64位工作站［10］，編程環境使用MATLAB R2014a。

（2）設定改進遺傳算法控制參數：控制參數主要是種群大小、迭代次數、交叉概率以及變異概率。種群大小和迭代次數直接影響質量。因此，用未改進算法和改進遺傳算法通過MATLAB仿真進行了比較，證明改進遺傳算法對四旋翼無人機航徑規劃問題的有效性。

（3）實驗結果及分析

首先使用未改進算法進行實驗，通過設定障礙物數據，合理規劃二維空間，描述起點位置［20，160］，目標位置［180，100］，進行圖形標注后，描繪障礙物圖形，得到不同的航徑后，用圖8中的實線描繪可行航徑。

圖8 未改進算法航徑情況

圖9 未改進算法迭代后航徑長度情況

由圖8可得最短航徑，未改進算法種群數量設定為30，設定100次迭代次數，經過循環搜索和一系列航徑長度的計算，不斷更新全局最短航徑，在其飛行空間中找到一條從起始位置到目標位置的，能避開靜態障礙物的最短航徑。由圖9可知，當算法的迭代次數一定時，航徑總長度達到最優，但是得到的曲線不是平滑的。這在實際應用中，會導致獲得的航徑長度誤差較大，不利于無人機的續航。同時，不能保證無人機安全著陸［11］。

本實驗中改進遺傳算法的參數設定如下：種群個數設定為30，迭代次數設定為100。適應值歸一化淘汰加速指數設定為2，交叉和變異概率分別設定為0.35和0.2。飛行空間由直角坐標系組成，如圖10所示，實線是改進遺傳算法經過計算得出的無人機最短航徑，圖11所示獲得的航徑長度情況曲線相對光滑，這可以更好地規劃無人機的航道，提高了飛行效率，增加了續航時間，有很好的技術價值。

圖10 改進遺傳算法航徑情況

圖11 改進遺傳算法迭代后航徑長度情況

仿真結果表明，未改進算法適合求解，但是收斂速度較慢。迭代次數達到一定次數時，容易陷入局部最優。而改進遺傳算法對搜索空間里面的大量解完成評估后，降低了陷入局部最優的機率，有利于整體最優。

表1 綜合對比

通過表1綜合對比，雖然兩者的運行時間幾乎相同，但是圖9所示未改進算法獲得的曲線經過62次迭代，最優目標函數值收斂，航徑長度為199.1836，而圖11所示改進遺傳算法在經歷了55次迭代已經收斂，62次迭代后已經最優，航徑長度為171.3615，比未改進算法獲得的航徑更短，效率更高，曲線更平滑。相對來說，優于未改進算法，證明了改進后的算法對解決四旋翼無人機航徑規劃問題是高效的。

6 結論

采用一種復雜環境下四旋翼無人機的改進算法。保證在每個復雜環境中找到最佳（或接近最佳）航徑。改進遺傳算法修改從初始航徑獲得的飛行坐標點位置，以找到起始位置和目標位置之間的最佳路徑。在算法中引入五個交叉算子和變異算子來改善飛行坐標點的位置。改進算法提高了時間效率，航徑長度大大縮短，在靜態障礙物環境中可以找到最優航徑。