摘 要：提出一種基于遺傳算法和B樣條曲線的路徑規(guī)劃新方法。以B樣條曲線控制點的坐標作為遺傳因子用遺傳算法進行規(guī)劃，根據(jù)這些控制點，運用B樣條曲線在3維坐標系中生成飛行器路徑軌跡。由于只對控制點進行規(guī)劃減小了系統(tǒng)的計算量，極大地提高了系統(tǒng)的實時性。仿真表明運用該算法規(guī)劃的路徑可以以最優(yōu)的軌跡把飛行器指引到預定的目的地。

關(guān)鍵詞：路徑規(guī)劃；進化算法；B樣條函數(shù);無人飛行器

中圖分類號：TP183 文獻標識碼：A 文章編號：1004373X(2008)1806404

Evolutionary Algorithmbased Path Planning For UAVs

LIU Minghua

(Yangling Vocational Technical College，Yangling，712100，China)

Abstract：A combination of evolutionary algorithms incorporating BSplines functionbased framework is utilized to design a path planner for Unmanned Aerial Vehicles (UAVs).The coordinates of BSplines control points being the evolutionary algorithms′ artificial chromosome genes are used to produce the path for UAVs in a 3D rough terrain environment.Because of programming only the control points of BSplines not all the points of the path，the computation time of the system is reduced dramatically.A simulation is made to show that the algorithms is effective in guiding an UAV to its final destination，the simulation also shows that the planning time adopting by the proposed algorithms for the UAVs can decline to 74.5% of the time of original GA algorithms.

Keywords：path planning;evolutionary algorithm;BSplines curves;UAVs

飛行器的路徑規(guī)劃問題本質(zhì)上是一個多約束多目標的優(yōu)化問題。求解這類問題導致尋求某個目標函數(shù)在特定區(qū)域上的最優(yōu)解，傳統(tǒng)的非線性規(guī)劃類方法大多基于梯度計算^［14］，具有較高的計算效率，但由于其固有的局部優(yōu)化性及不穩(wěn)健性等缺陷，并不適合于全局優(yōu)化問題的求解。遺傳算法仿效生物的進化與遺傳，根據(jù)生存競爭和優(yōu)勝劣汰的法則，借助于遺傳操作，使所求解的問題逐步逼近最優(yōu)解。與其他方法相比，遺傳算法用單一字符串的形式描述所研究的問題，只需利用適應度函數(shù)進行優(yōu)化計算，而不需函數(shù)導數(shù)等輔助信息，特別適合于解決其他方法無法解決的復雜問題，因而成為人們關(guān)注的熱點之一。

從微觀的角度看，遺傳算法是一種隨機算法；從宏觀的角度看，它又有一定的方向性，因此它比一般的隨機搜索算法效率要高^［57］。在經(jīng)典遺傳算法的基礎上，許多學者對其進行多種改進，這些算法大都采用二進制編碼，然而對于很多問題，例如神經(jīng)網(wǎng)絡的訓練^［8］，由于涉及較多的設計變量，如果采用二進制編碼，則碼串會很長，編碼和解碼操作將占用較多時間，而且碼串過長會使算法的搜索效率降低。另外，對于連續(xù)變量的優(yōu)化問題，實數(shù)表示更加自然，并且計算精度不會受到編碼方式的影響。因此，本文嘗試在廣義遺傳算法的基礎上引入實數(shù)編碼，設計相應的遺傳操作，并用來解決函數(shù)優(yōu)化問題。

飛行器的路徑規(guī)劃由于其飛行包線和穩(wěn)定性要求，其不能像地面機器人一樣用直線段描述，它是由一些具有連續(xù)性的曲線光滑連接而成。B樣條曲線具有高階導數(shù)連續(xù)性，因此用B樣條曲線描述飛行器路徑具有極大的優(yōu)勢^［9］，可以滿足這個要求。同時，B樣條曲線描述可以用極少的數(shù)據(jù)量（控制點的坐標）產(chǎn)生非常復雜的曲線。

1 進化算法研究

1.1 進化算法算子

簡單的進化算法包括3個典型的操作算子：

（1） 選擇（selection）;

（2） 交叉(crossover);

（3） 變異(mutation)。

三種算子都分別作用于每一代種群中的所有個體，這樣經(jīng)過一定代數(shù)的進化就可以獲得比較滿意的效果了，具體詳見文獻［6］。

標準的遺傳算法在飛行路徑規(guī)劃中具有一定的應用價值，但也受到很多制約，人們對其染色體編碼方式、各個操作因子均進行了發(fā)展，但其基本思想仍舊不變，故又稱其為進化算法。

經(jīng)典的遺傳算法采用二進制編碼，這將使染色體編碼長度過長，導致編碼和解碼都費時，另外采用二進制編碼存在hamming懸崖，降低搜索效率。如果采用浮點數(shù)編碼則可避免這種情況，另外浮點數(shù)編碼使問題的描述更加接近實際情況。直接用搜索空間中的搜索變量作為染色體，有效克服了二進制編碼的缺點。

1.2 進化算法用于路徑規(guī)劃的過程

進化算法的一個重要特性是能相對容易地應用于實際問題。進化算法應用于軌跡規(guī)劃按下述幾個步驟：

(1)飛機軌跡的編碼表示；

(2)構(gòu)造軌跡評估函數(shù)；

(3)研究特定軌跡規(guī)劃的進化算法操作算子；

(4)進行測試，微調(diào)進化算子和參數(shù)。

軌跡規(guī)劃在地面確定可行的飛行軌跡，在空中則應具有軌跡實時重規(guī)劃的能力。軌跡規(guī)劃就是確定UAV完成任務目標的順序、路徑，同時滿足燃油、飛行性能、生存率等性能指標要求。

2 樣條函數(shù)理論

樣條理論最先由Shoenberg于1958年提出，主要用于數(shù)字分析、差值、函數(shù)擬合等場合，1991年Crouch^［10］最先把它引入飛機軌跡規(guī)劃中。近些年來，樣條理論得到了極大的發(fā)展，并在更多領(lǐng)域內(nèi)得到了廣泛的應用。

2.1 樣條函數(shù)定義

符號Ck=Ck［a，b］表示區(qū)間［a，b］上具有直到k次連續(xù)導數(shù)的函數(shù)的集合所形成的空間，其中k為正整數(shù)。符號C0表示連續(xù)函數(shù)空間，C－1表示具有第一類間斷點的分段連續(xù)函數(shù)空間。

考察n次多項式pn(x)，它在某個子區(qū)間［xi，xi+1］上，可以表示為:pn(x)=a0+a1x+…+anxn(1)

由于多項式pn(x)可以用n+1個系數(shù)a0，a1，…，an惟一確定，所以n次多項式pn(x)又稱為n+1階多項式。此外pn(x)在子區(qū)間［xi，xi+1］上還可以表示為:pn(x)=∑nj=0ai，j(x－xi)j

=ai，0+ai，1(x－xi)+…+ai，n(x－xi)n(2)或者:pn(x)=∑nj=0bi，j(x－xi+1)(3)

定義1 如果函數(shù)sn(x)滿足下面條件：

(1) 函數(shù)sn(x)在每個子區(qū)間［xi，xi+1］上是n次多項式；

(2) 函數(shù)sn(x)在區(qū)間［a，b］上具有直到n－1的連續(xù)導數(shù)，即sn(x)∈Cn－1［a，b］。

則稱sn(x)稱為關(guān)于區(qū)間［a，b］上的分劃Δ:a=x0

點xi(i=0，1，…，N+1)稱為樣條函數(shù)sn(x)的節(jié)點；其中xi(i=1，2，…，N)為內(nèi)節(jié)點，x0，xN+1為邊界節(jié)點或者端點。

符號sn(Δ)表示對于固定一個分劃Δ滿足定義1的樣條函數(shù)的全體所組成的空間。

定義2 函數(shù)sn，k(x)稱為關(guān)于分劃Δ且虧數(shù)為k的n次樣條函數(shù)，如果sn，k(x)滿足下面條件：

(1) 函數(shù)sn，k(x)是n次多項式，x∈［xi，xi+1］(i=0，1，…，N)；

(2) 函數(shù)sn，k(x)∈Cn－k［a，b］。

顯然sn(x)≡sn，1(x)，且樣條函數(shù)sn，k(x)具有直到n－k次的連續(xù)導數(shù)，高于n－k次的導數(shù)在內(nèi)節(jié)點xi上間斷的。

一般規(guī)定樣條函數(shù)右連續(xù)，即:sn，k(xi)=sn，k(xi+0)， i=1，2，…，N(4)

符號sn，k(Δ)表示對于固定分劃Δ滿足定義2的全體樣條函數(shù)組成的空間。樣條函數(shù)空間與多項式空間Pn有下列邏輯關(guān)系：Pnsn(Δ)sn，2(Δ)…sn，n+1(Δ)(5)

函數(shù)sn，v(x)稱為關(guān)于分劃Δ且虧數(shù)向量為ν=(v1，v2，…，vN)T的n次樣條函數(shù)，如果sn，v(x)滿足條件：

(1) 函數(shù)sn，k(x)是n次多項式，x∈［xi，xi+1］(i=0，1，…，N)；

(2) 函數(shù)s(j)n，v(x)在除了首端點外其他節(jié)點處連續(xù)，即s(j)n，v(xi－0)=s(j)n，v(xi+0)，i=1，2，…，N；j=0，1，…，n－vi。

在實軸上取節(jié)點序列:…

在(t－x)n+中將x看作參數(shù)，關(guān)于t=xi，xi+1，…，xi+n+1作函數(shù)(t－x)n+的n+1階差商［xi，xi+1，…，xi+n+1］(t－x)n+，稱此差商是以x為變量的B樣條函數(shù)，并且稱:Bi，n+1(x)=(xi+n+1－xi)［xi，…，xi+n+1］(t－x)n+(7)為第i個n次規(guī)范B樣條函數(shù)。

根據(jù)上面介紹的差商概念可知:Bi，n+1(x)=(xi+n+1－xi)∑i+n+1k=i(xk－x)n+wi′(xk)(8)其中:wi，n+1(x)=∏i+n+1k=i(x－xk)由上式易知，Bi，n+1(x)為分段n次多項式。

2.2 樣條函數(shù)的迭代算法

根據(jù)上面的結(jié)論，B樣條函數(shù)迭代算法構(gòu)造如下：

首先，令N0，0(s)=1，然后計算下列公式:N0，k(s)=1－skN0，k－1(s)

Nk，k(s)=skNk－1，k－1(s)

Nj，k(s)=k－j+skNj－1，k－1(s)+

1+j－skNj，k－1(s)，j=1，2，…，k－1(9)

最后定義B樣條基元素Bk(s):Bk(s)=Nk－j，k(s－j)，j≤s≤j+1

j=0，1，…，k

0，s≤0，k+1≤s(10)

這樣，B樣條函數(shù)表示為:Sk(t)=∑Mi=1ciBk(t－i+1)(11)ci為控制點坐標。由式（10）可以得到B(l)k(0)=0，B(l)k(k+1)=0，其中l(wèi)=0，1，…，k－1，B(l)k(·)表示l階偏導數(shù)。

3 路徑規(guī)劃設計

3.1 適應度函數(shù)的確定

適應度函數(shù)可看作是由以下4項組合而成:f=1/∑4i=1aifi(12)其中ai是權(quán)值；具體值根據(jù)經(jīng)驗來確定；fi分別代表路徑長度、安全距離、飛行包線；f1代表通過邊界條件的不合理的路徑；f2代表目標點和初始點之間的距離；f3代表路徑和障礙物之間的安全距離，f3=∑nlinei=1∑ngroundj=11/(ri，j/rsafe)2 ；f4代表最小轉(zhuǎn)彎半徑，如圖1所示：規(guī)劃路徑的角度Θ不能小于預定的最小值。Θ角和最小轉(zhuǎn)彎半徑滿足關(guān)系式：Θ=2arccos(ΔT·V2R)，其中，ΔT為采樣周期；R為轉(zhuǎn)彎半徑；V為飛行速度。

由于規(guī)劃的路徑首先要具有可實現(xiàn)性，因此式（12）中的f1的權(quán)值最大。

3.2 障礙物規(guī)劃研究

如圖2所示為系統(tǒng)在實時威脅下的路徑規(guī)劃，為了簡單說明問題，本文選擇2維平面內(nèi)規(guī)劃算法。

圖1 轉(zhuǎn)彎半徑角度圖2 障礙下的路徑規(guī)劃如圖2所示，當障礙物沒在規(guī)劃的兩點之間時，兩點的連線就是直接路徑；當障礙物位于兩點之間時，首先用一個坐標變換把威脅變換為一個以原點為中心單位圓。假設威脅可以描述為：{x:(x－xc)R－1(x－xc)≤1}(13)其中R為一正定矩陣；xc為中心坐標。坐標變換為：z=R－1/2(x－xc)，就可以把威脅變換為z域內(nèi)的一個單位圓，把z域看成是一個復平面，并做保形變換ω=1/z如圖2右圖，這樣威脅區(qū)域的里面和外面做了相互映射。這樣最優(yōu)路徑問題就轉(zhuǎn)換為在單位圓內(nèi)沿著單位圓兩點之間的距離問題。然后通過逆映射可以轉(zhuǎn)換為初始坐標系中的軌跡優(yōu)化問題。

4 仿真實驗

三維立體邊界條件采用式（3）所描述的函數(shù)產(chǎn)生的3D網(wǎng)格邊界模擬一個有山谷的地形條件，目的是用來對算法進行驗證。z(x，y)=sin(y+a)+bsin(x)+ccos(dy2+x2)+

ecos(y)+fsin(fy2+x2)+gcos(y)(14)

其中a，b，c，d，e，f，g，h，m，n是由經(jīng)驗確定的常數(shù)值。

仿真條件為初始點坐標為(0，0，0)，終止點坐標分別為(10，10，2)和(5，10，2)。

圖3、圖4分別為2種情況下的路徑規(guī)劃圖，其中圖(a)和圖(b)分別表示最短路徑規(guī)劃和躲開障礙物規(guī)劃兩種情況下的仿真結(jié)果?？梢钥闯?，在設定的3D地形圖上，本文的算法得到一條符合無人機轉(zhuǎn)彎半徑，并且光滑的可飛路徑。

圖3 路徑規(guī)劃效果圖圖4 路徑規(guī)劃效果圖5 結(jié) 語

考慮到B樣條的高階導數(shù)連續(xù)性和樣條函數(shù)只用少量的控制點就可以產(chǎn)生整個樣條曲線的特點，詳細研究B樣條理論并將其用于飛行器路徑規(guī)劃中，用進化算法直接優(yōu)化樣條函數(shù)的控制點，進而形成B樣條飛行路徑，既保證了路徑的可飛性，又保證了規(guī)劃過程的快速性和實時性。

參 考 文 獻

［1］Ioannis K Nikolos，Kimon P Valavanis.Evolutionary Algorithmbased Offline/Online Path Planner for UAV Navigation\\.IEEE Trans.on SMAC-Part B:Cybernetics，2003，33(6):898912.

［2］吳曉濤，孫增圻.用遺傳算法進行路徑規(guī)劃\\.清華大學學報，1995，35(5):1419.

［3］馬云紅，周德云.無人機路徑規(guī)劃算法與仿真\\.火力與指揮控制，2007，32(6):3336.

［4］魯藝，周德云.無人機初始路徑規(guī)劃空間建模方法研究\\.系統(tǒng)仿真學報，2007，19(3):491509.

［5］Crouch P，Jackson J.Dynamic Interpolation and Application to Flight Control\\.Guidance，Control and Dynamics，

1991，14:814822.

［6］賈秋玲，李廣文，閆建國.基于遺傳算法的多無人機協(xié)同逆推式路徑規(guī)劃\\.西北工業(yè)大學學報，2007，25(4):590594.

［7］Bead R W，Timothy W M，Goodrich M A，et al.Coordinated

target Assignment and Intercept for Unmanned Air Vehicles［J］ .IEEE Transactions on Robotics and Automation，2002，18 (6):911922.

［8］Napolitano M R，Kincheloe M.Online Learning Neuralnetwork Controllers of Autopilot Systems ［J］.AIAA Journal of Guidance，Control and Dynamics，1995，6(16):1 0081 015.

［9］Judd K B，Mclain T W.Splinebased Path Planning for Unmanned Air Vehicles\\.Proceedings of Guidance，Navigation and Control Conference\\.2001:1 1821 190.

［10］吳文海，沈春林，劉國剛，等.飛行控制系統(tǒng)設計的特征結(jié)構(gòu)配置法\\.哈爾濱工業(yè)大學學報，2002，34(5):639642.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文