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

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

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

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

1 四旋翼無人機(jī)平臺(tái)

本設(shè)計(jì)使用基于英飛凌XMC4700與N3飛控的Onboard SDK平臺(tái)，并應(yīng)用了英飛凌的多種傳感器，實(shí)現(xiàn)對(duì)四旋翼無人機(jī)的控制。融合了動(dòng)力、飛控、導(dǎo)航、相機(jī)、圖傳與數(shù)傳等系統(tǒng)模塊，飛行的高度能夠達(dá)到50m以上，而且有著很強(qiáng)的負(fù)載能力，是一個(gè)比較穩(wěn)定的飛行平臺(tái)?？梢灾С侄喾N類型傳感器，能夠在復(fù)雜環(huán)境下實(shí)時(shí)計(jì)算。四旋翼無人機(jī)管理平臺(tái)如圖1所示。

圖1 四旋翼無人機(jī)管理平臺(tái)

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

圖2 無人機(jī)探測障礙物

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

圖3 航徑規(guī)劃總體框圖

2 模型搭建

考慮到四旋翼無人機(jī)是從障礙物中尋找最短航徑，本文將大小不同、不規(guī)則靜態(tài)障礙物用圓形圖標(biāo)來表示，如圖4所示環(huán)境模型。

圖4 靜態(tài)障礙物模擬模型

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

圖5 參考坐標(biāo)系

根據(jù)圖5結(jié)合數(shù)學(xué)知識(shí)，可以得到：

四旋翼無人機(jī)的運(yùn)動(dòng)學(xué)方程為：

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

3 航跡表示

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

圖6 單個(gè)靜態(tài)障礙物平面示意圖

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

四旋翼無人機(jī)規(guī)劃一條最佳航徑，不光要考慮周圍的環(huán)境，處于環(huán)境中的障礙物，復(fù)雜的地形，還要考慮無人機(jī)的自身?xiàng)l件，即最小轉(zhuǎn)彎半徑、航徑長度、爬升角等等。這里主要考慮解決最短航徑長度問題。

4 改進(jìn)遺傳算法

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

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

圖7是改進(jìn)遺傳算法航徑規(guī)劃過程。

圖7 改進(jìn)遺傳算法航徑規(guī)劃過程

4.1 選擇運(yùn)算

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

4.2 改進(jìn)交叉算子

修改后的交叉算子結(jié)合了兩個(gè)具有相同或不同數(shù)量的飛行坐標(biāo)點(diǎn)，以產(chǎn)生新的后代，這在預(yù)定義的目標(biāo)方面可能更好。第一個(gè)交叉算子通過計(jì)算兩個(gè)親本的平均值來找到一個(gè)新的后代：

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

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

4.3 改進(jìn)變異算子

變異算子可以增加群體多樣性、搜索環(huán)境區(qū)域以及能夠?qū)⒁唤M飛行坐標(biāo)點(diǎn)移動(dòng)到特定方向上，這些對(duì)于增加航徑平滑度和獲得最短航徑長度是非常有用的。第一個(gè)變異算子是一個(gè)算術(shù)變異算子，它在隨機(jī)方向上改變預(yù)定數(shù)量飛行坐標(biāo)點(diǎn)的位置。該算子對(duì)提高多樣性和避免過早收斂有很大的幫助。第二個(gè)變異算子修改飛行坐標(biāo)點(diǎn)的位置，以改善路徑的長度和平滑度。該算子通過將其當(dāng)前位置Pi和朝向兩側(cè)的飛行坐標(biāo)點(diǎn)方向（Pi-1和Pi+1）進(jìn)行積分來改進(jìn)飛行坐標(biāo)點(diǎn)的位置。

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

4.4 選擇刪除運(yùn)算算子

為了使算法性能穩(wěn)定，在改進(jìn)遺傳算法中使用刪除運(yùn)算算子，這與初始航徑中的飛行坐標(biāo)點(diǎn)無關(guān)，與下一坐標(biāo)點(diǎn)有關(guān)。刪除運(yùn)算算子刪除航徑的冗余飛行坐標(biāo)點(diǎn)。首先，從群體中選擇個(gè)體。然后刪除運(yùn)算算子有順序地評(píng)估每個(gè)飛行坐標(biāo)點(diǎn)。如果刪除任何選定的飛行坐標(biāo)點(diǎn)是有效的，那么就可以減少航徑的長度。

5 仿真驗(yàn)證與分析

根據(jù)航徑規(guī)劃遺傳算法的要求，經(jīng)改進(jìn)遺傳算法計(jì)算可得優(yōu)化后的最優(yōu)飛行航跡。

（1）實(shí)驗(yàn)環(huán)境：Intel（R）Xeon（R）CPU，運(yùn)行內(nèi)存為 32GB的 Win7 64位工作站［10］，編程環(huán)境使用MATLAB R2014a。

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

（3）實(shí)驗(yàn)結(jié)果及分析

首先使用未改進(jìn)算法進(jìn)行實(shí)驗(yàn)，通過設(shè)定障礙物數(shù)據(jù)，合理規(guī)劃二維空間，描述起點(diǎn)位置［20，160］，目標(biāo)位置［180，100］，進(jìn)行圖形標(biāo)注后，描繪障礙物圖形，得到不同的航徑后，用圖8中的實(shí)線描繪可行航徑。

圖8 未改進(jìn)算法航徑情況

圖9 未改進(jìn)算法迭代后航徑長度情況

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

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

圖10 改進(jìn)遺傳算法航徑情況

圖11 改進(jìn)遺傳算法迭代后航徑長度情況

仿真結(jié)果表明，未改進(jìn)算法適合求解，但是收斂速度較慢。迭代次數(shù)達(dá)到一定次數(shù)時(shí)，容易陷入局部最優(yōu)。而改進(jìn)遺傳算法對(duì)搜索空間里面的大量解完成評(píng)估后，降低了陷入局部最優(yōu)的機(jī)率，有利于整體最優(yōu)。

表1 綜合對(duì)比

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

6 結(jié)論

采用一種復(fù)雜環(huán)境下四旋翼無人機(jī)的改進(jìn)算法。保證在每個(gè)復(fù)雜環(huán)境中找到最佳（或接近最佳）航徑。改進(jìn)遺傳算法修改從初始航徑獲得的飛行坐標(biāo)點(diǎn)位置，以找到起始位置和目標(biāo)位置之間的最佳路徑。在算法中引入五個(gè)交叉算子和變異算子來改善飛行坐標(biāo)點(diǎn)的位置。改進(jìn)算法提高了時(shí)間效率，航徑長度大大縮短，在靜態(tài)障礙物環(huán)境中可以找到最優(yōu)航徑。