無人機(jī)航跡算法綜述

1、無人機(jī)航跡算法綜述為促進(jìn)航跡規(guī)劃技術(shù)的發(fā)展，對航跡規(guī)劃常用算法進(jìn)行綜述。首先對航跡規(guī)劃的 規(guī)劃思想和構(gòu)成進(jìn)行分析；其次將航跡規(guī)劃算法分為傳統(tǒng)經(jīng)典算法和現(xiàn)代智能算法 兩大類，對其中幾種常用算法進(jìn)行分析總結(jié)；最后闡述現(xiàn)代智能算法在航跡規(guī)劃應(yīng)用 中的改進(jìn)、多重算法的融合改進(jìn)以及多無人機(jī)四維航跡規(guī)劃算法研究3個(gè)研究熱點(diǎn) 及未來發(fā)展趨勢。隨著航空技術(shù)日益發(fā)展,越來越多的無人機(jī)被用于替代飛行員執(zhí)行一些高危險(xiǎn)、 高強(qiáng)度或大范圍巡檢、搜救任務(wù)，因此完善的任務(wù)規(guī)劃系統(tǒng)是無人機(jī)順利完成任務(wù)的 重要保障。任務(wù)規(guī)劃系統(tǒng)一般由航跡規(guī)劃、導(dǎo)航、數(shù)據(jù)通信3大子系統(tǒng)組成，而航跡 規(guī)劃則是任務(wù)規(guī)劃系統(tǒng)的核心部分。無人機(jī)航跡規(guī)劃

2、就是在綜合考慮無人機(jī)到達(dá)時(shí)間、油耗、威脅以及飛行區(qū)域等 因素的前提下，為無人機(jī)規(guī)劃出最優(yōu)或滿意的飛行航跡，以保證圓滿地完成飛行任務(wù) 1。無論是在軍事還是民用領(lǐng)域，好的航跡規(guī)劃系統(tǒng)都是提高無人機(jī)安全性能，保證 無人機(jī)出色完成任務(wù)的重要手段。筆者將在對航跡規(guī)劃問題進(jìn)行分析的基礎(chǔ)上，對當(dāng) 前幾種常用航跡規(guī)劃算法進(jìn)行分類總結(jié)，最后指出目前研究熱點(diǎn)及未來發(fā)展趨勢。1航跡規(guī)劃問題分析在不考慮時(shí)間因素的情況下，無人機(jī)航跡規(guī)劃應(yīng)該是在三維空間中進(jìn)行的，但在 一些任務(wù)中，無人機(jī)保持在固定高度飛行，不需要考慮高度變化問題。因此在進(jìn)行航 跡規(guī)劃時(shí)可以將三維空間中的物體投影到二維平面，從而將三維航跡規(guī)劃問題降至二 維

3、，簡化問題的復(fù)雜度。但在軍事突防、電力巡線、山地救援等應(yīng)用中，二維航跡規(guī) 劃實(shí)用價(jià)值有限。筆者將從規(guī)劃思想和構(gòu)成兩方面對航跡規(guī)劃問題進(jìn)行分析。1.1規(guī)劃思想航跡規(guī)劃問題是一個(gè)包含多個(gè)優(yōu)化目標(biāo)和多個(gè)約束的非線性規(guī)劃問題2,其核 心就是建立目標(biāo)函數(shù)的數(shù)學(xué)模型和有效地處理各項(xiàng)約束。由于涉及約束條件較多，目 標(biāo)函數(shù)復(fù)雜,數(shù)學(xué)模型建立困難,為降低問題復(fù)雜性，目前大多數(shù)學(xué)者都采用分層規(guī)劃 的思想，將航跡規(guī)劃分為兩步進(jìn)行。首先根據(jù)已知的環(huán)境信息、任務(wù)要求等在無人機(jī) 起飛前為其規(guī)劃出一條滿足約束條件的全局最優(yōu)參考航跡。無人機(jī)在按照此航跡飛 行的過程中，當(dāng)出現(xiàn)未知或動(dòng)態(tài)威脅信息時(shí)，再進(jìn)行局部航跡動(dòng)態(tài)優(yōu)化。由于全

4、局參 考航跡規(guī)劃需要考慮整體的優(yōu)化，因此要在避免陷入局部最優(yōu)的情況下盡量減少計(jì)算 量。而局部航跡動(dòng)態(tài)優(yōu)化用于應(yīng)對突發(fā)威脅，因此要盡量縮短規(guī)劃時(shí)間以確保實(shí)時(shí) 性。1.2規(guī)劃構(gòu)成無人機(jī)航跡規(guī)劃一般由以下幾個(gè)部分組成：描述規(guī)劃空間，選擇航跡的表示形 式，分析約束條件,確定代價(jià)函數(shù)，選取航跡搜索算法和航跡平滑。1）描述規(guī)劃空間。其目的是建立一個(gè)便于計(jì)算機(jī)進(jìn)行航跡規(guī)劃所使用的環(huán)境模 型，即將實(shí)際的物理空間抽象成算法能處理的抽象空間，實(shí)現(xiàn)相互間的映射。規(guī)劃空 間的表示是否合理直接影響規(guī)劃的效率和結(jié)果的優(yōu)劣性。一種好的規(guī)劃空間表示法 應(yīng)能滿足如下要求：規(guī)劃空間能合理且盡量完善地反映飛行環(huán)境中的各種信息（地形

5、、威脅、障礙 等），以利于航跡搜索；當(dāng)飛行環(huán)境中的某些信息發(fā)生變化時(shí)能實(shí)時(shí)地進(jìn)行更新，以滿足實(shí)時(shí)應(yīng)用的要 求；能滿足無人機(jī)自身性能約束條件，包括最大拐彎角、最大爬升/俯沖角、最大 航跡距離、最小航跡段長度和最低飛行高度等。常用的規(guī)劃空間表示方法有柵格法和圖形法。柵格法將規(guī)劃空間分解成為一些 簡單的單元，并為每個(gè)單元分配一個(gè)代價(jià)值,對應(yīng)于無人機(jī)經(jīng)過空間相應(yīng)區(qū)域的代價(jià), 并判斷這些單元之間是否存在可行路徑，找到包含起始點(diǎn)和目標(biāo)點(diǎn)的單元，從起始單 元開始，依次向柵格中代價(jià)最小的鄰域移動(dòng)，最后到達(dá)目標(biāo)單元3。航跡搜索算法中 的A*算法、動(dòng)態(tài)規(guī)劃法等就是利用柵格描述規(guī)劃空間。由于數(shù)字地圖采用柵格的形 式

6、存儲(chǔ)，所以多數(shù)的航跡規(guī)劃研究都是使用柵格法表示規(guī)劃空間。圖形法首先根據(jù)一 定規(guī)則將規(guī)劃空間表示成一個(gè)由一維線段構(gòu)成的網(wǎng)絡(luò)圖，然后采用某一搜索算法在該 網(wǎng)絡(luò)圖上進(jìn)行搜索。使用圖形法必須表示出所有可能的路徑，否則就可能丟失最優(yōu) 解。圖形法相比柵格法數(shù)據(jù)處理量少，但是更新較困難。常用的圖形法有Voronoi圖 法4、可視圖法(VisibilityGraph)5、隨機(jī)路標(biāo)圖法(PRM： ProbabilisticRoadMap)6 等。航跡表示。其形式有兩種：一種是基于無人機(jī)運(yùn)動(dòng)學(xué)、動(dòng)力學(xué)描述的連續(xù)平 滑航跡，采用此種表示方法可以省去最后的航跡平滑環(huán)節(jié)；另一種是用航跡點(diǎn)表示， 相鄰航跡點(diǎn)之間用直線段連

7、接幾何折線航跡。第2種表示方法有如下優(yōu)點(diǎn)：可以通過調(diào)整航跡節(jié)點(diǎn)的數(shù)目達(dá)到所需要的精度；將復(fù)雜的航跡規(guī)劃問題分解為一組統(tǒng)一形式的小規(guī)模子問題，對于每個(gè)子問 題，只需關(guān)心一個(gè)點(diǎn)的坐標(biāo)，從而將考察航跡是否可行變?yōu)閮H考察一個(gè)點(diǎn)或一條直線 段是否滿足要求；便于實(shí)現(xiàn)并行、分布式計(jì)算。分析約束條件。航跡規(guī)劃問題需要考慮的約束條件包括環(huán)境約束、任務(wù)約束 和無人機(jī)自身性能約束。環(huán)境約束有威脅約束(如被敵方雷達(dá)發(fā)現(xiàn)概率、敵方導(dǎo)彈高 炮擊落概率、撞地概率等)、禁飛區(qū)約束、復(fù)雜氣象區(qū)約束等；任務(wù)約束有任務(wù)完成 時(shí)間、起始點(diǎn)、目標(biāo)點(diǎn)、固定航向角、低空/超低空突防等；無人機(jī)自身性能約束有 最大/最小平飛速度、最大航程、最

8、高/最低飛行高度、水平最小轉(zhuǎn)彎半徑、最大爬 升角/俯沖角、最大縱向曲率、最大法向過載等7。若是進(jìn)行二維航跡規(guī)劃,則不需 要考慮無人機(jī)的爬升/俯沖角約束和飛行高度約束。確定代價(jià)函數(shù)。代價(jià)函數(shù)將算法與實(shí)際物理問題緊密聯(lián)系在一起。對于無人 機(jī)航跡規(guī)劃，代價(jià)函數(shù)是評價(jià)航跡優(yōu)劣的標(biāo)準(zhǔn)，代價(jià)值越小則表明航跡越優(yōu)，反之表明 航跡越差。確定代價(jià)函數(shù)需要綜合考慮影響航跡性能的各項(xiàng)因素，對各個(gè)指標(biāo)進(jìn)行量 化和計(jì)算。三維航跡規(guī)劃的代價(jià)函數(shù)通常包含航跡長度代價(jià)、威脅代價(jià)和高度代價(jià), 表示為J=3 1L+3 2T+3 3H(1)3 1+3 2+3 3 = 1(2)其中J為航跡總代價(jià),L為航跡長度代價(jià)，一些文獻(xiàn)也稱其為燃

9、油代價(jià),T為威脅 代價(jià)川為高度代價(jià)；3 1、32、33為相應(yīng)的權(quán)系數(shù)，根據(jù)任務(wù)需要設(shè)置其值。二維 航跡規(guī)劃則不需要考慮高度代價(jià)。選取搜索算法。根據(jù)任務(wù)需求選取合適的算法規(guī)劃出滿足約束條件、規(guī)避障 礙、使代價(jià)函數(shù)獲得最優(yōu)值的航跡是航跡規(guī)劃問題的核心部分。航跡平滑。通過相應(yīng)算法搜索出的航跡對于無人機(jī)實(shí)際飛行而言并不一定可 行，例如規(guī)劃出的航跡拐彎點(diǎn)較多,而無人機(jī)在實(shí)際飛行中由于自身機(jī)動(dòng)限制不能頻 繁轉(zhuǎn)彎，因此需要對規(guī)劃出的航跡進(jìn)行平滑處理，消除不必要的拐彎點(diǎn)以利于無人機(jī) 實(shí)際飛行。常用航跡平滑方法有三次樣條插值法8、貝塞爾曲線 (BezierCurve)9、k-trajectory 算法10等。2

10、常用航跡規(guī)劃算法無人機(jī)航跡規(guī)劃的本質(zhì)是路徑規(guī)劃，即尋找適當(dāng)?shù)牟呗詷?gòu)成連接起點(diǎn)到終點(diǎn)位置 的由序列點(diǎn)或曲線組成的路徑，因此用于航跡規(guī)劃的算法實(shí)際上也就是路徑規(guī)劃算 法。路徑規(guī)劃算法有很多，每種算法都有其自身的優(yōu)缺點(diǎn)和適用范圍,按照規(guī)劃決策 可以將算法分為傳統(tǒng)經(jīng)典算法和現(xiàn)代智能算法11兩類。2.1傳統(tǒng)經(jīng)典算法近年來常用于航跡規(guī)劃的傳統(tǒng)經(jīng)典算法有Dijkstra算法、人工勢場法(APF： Artificial PotentialField)和模擬退火算法(SAA:SimulatedAnnealingAlgorithm) o Dijkstra算法是圖論中求解最短路徑的經(jīng)典算法,適用于每條邊的權(quán)數(shù) 為非

11、負(fù)的情況，能得到從指定頂點(diǎn)到其他任意頂點(diǎn)的最短路徑。使用Dijkstra算法 進(jìn)行航跡規(guī)劃，構(gòu)建的賦權(quán)圖的頂點(diǎn)代表航跡點(diǎn)，賦權(quán)圖的邊代表所有可行航 跡,Dijkstra算法的作用就是在這些可行航跡里找到最優(yōu)航跡。Dijkstra算法實(shí)現(xiàn) 簡單，但其運(yùn)算時(shí)間和所用內(nèi)存與搜索空間中節(jié)點(diǎn)個(gè)數(shù)平方成正比，在大范圍高維空 間中搜索時(shí)間長，對內(nèi)存要求也很高，因此多用于二維靜態(tài)航跡規(guī)劃12,13。由于航 跡規(guī)劃空間范圍大，對于Dijkstra算法在航跡規(guī)劃中的應(yīng)用，如何選取有效航跡點(diǎn)， 減少航跡點(diǎn)數(shù)量,縮短規(guī)劃時(shí)間是問題的關(guān)鍵。文獻(xiàn)12在Voronoi圖的基礎(chǔ)上使用 Dijkstra算法尋找最優(yōu)航跡，將威脅

12、看作一個(gè)點(diǎn)，選取各威脅點(diǎn)之間連線的中垂線的 交點(diǎn)為航跡點(diǎn)。這種方法能保證航跡最大化避開各個(gè)威脅，安全性高,但航跡較長。 并且沒有考慮無人機(jī)最大轉(zhuǎn)彎角約束，航跡不一定可飛。文獻(xiàn)13在可視圖的基礎(chǔ)上 使用Dijkstra算法尋找最短航跡，將多邊形障礙的各個(gè)頂點(diǎn)看作航跡點(diǎn)，并建立轉(zhuǎn)彎 角約束機(jī)制。這種方法得到的航跡短,滿足無人機(jī)最大轉(zhuǎn)彎角約束，但由于航跡貼近 障礙物，安全性較低。此外，可視圖不能表達(dá)物體運(yùn)動(dòng)的方向性約束的缺陷導(dǎo)致 Dijkstra算法在搜索時(shí)可能找不到路徑。雖然Dijkstra算法多用于二維航跡規(guī)劃， 但也有學(xué)者將其應(yīng)用于三維航跡規(guī)劃。文獻(xiàn)14 將飛行空間映射到由若十個(gè)四面體 組成的

13、三維Delaunay三角網(wǎng)中，四面體的頂點(diǎn)對應(yīng)威脅的位置，四面體內(nèi)切球的中心 作為航跡點(diǎn)，所有相鄰四面體內(nèi)切球中心點(diǎn)的連線構(gòu)成一個(gè)三維網(wǎng)絡(luò),這個(gè)三維網(wǎng)絡(luò) 就是所有可行航跡。然后用Dijkstra算法在這個(gè)三維網(wǎng)絡(luò)上尋找最短航跡。最后用 人工勢場法對初始航跡進(jìn)行優(yōu)化，獲得平滑可飛的航跡。該方法與Voronoi圖法類 似，規(guī)劃出的航跡能最大化避開威脅，安全性高，但航跡相對較長。目前使用Dijkstra 算法進(jìn)行航跡規(guī)劃多是利用Voronoi圖、概率地圖或可視圖描述規(guī)劃環(huán)境，然后在此 基礎(chǔ)上利用Dijkstra算法尋找最短航跡，但得到的航跡若安全性高則航跡長,若航跡 短則安全性低，沒有在航跡長度與安

14、全性之間尋找到一個(gè)好的平衡。人工勢場法是一種模擬電勢場分布的規(guī)劃方法，任務(wù)區(qū)域內(nèi)的目標(biāo)點(diǎn)產(chǎn)生引力 場，威脅源產(chǎn)生斥力場，無人機(jī)在引力和斥力的共同作用下向目標(biāo)點(diǎn)運(yùn)動(dòng)。傳統(tǒng)人工 勢場法定義如下。航跡點(diǎn)X的引力勢函數(shù)和斥力勢函數(shù)分別為 U而(X)=!k”0(X,Xg) - (4)其中Katt和Krep分別為引力和斥力增益系數(shù)，且均為正常數(shù)；p(X，XG)為航跡 點(diǎn)X與目標(biāo)點(diǎn)XG之間的距離；p(X，XO)為航跡點(diǎn)X與威脅源XO之間的距離；PO為 威脅源最大影響距離。無人機(jī)在X處受到的引力和斥力分別是相應(yīng)勢函數(shù)的負(fù)梯度Fatt=- Uatt(X)=-KattP(X，XG)(5)D上e = . f昧M -

15、 g E 心 l y即Frep=_，- - -(6)總勢場力為目標(biāo)點(diǎn)產(chǎn)生的引力和各個(gè)威脅源產(chǎn)生的斥力的矢量和Ftotal=Fatt+EFrep(7)人工勢場法的優(yōu)點(diǎn)是算法簡明、實(shí)時(shí)性好、規(guī)劃速度快，在局部規(guī)劃和實(shí)時(shí)規(guī)劃 領(lǐng)域應(yīng)用廣泛。缺點(diǎn)是當(dāng)無人機(jī)離目標(biāo)點(diǎn)比較遠(yuǎn),Fatt Frep時(shí)，合力方向更趨近目 標(biāo)點(diǎn)方向，無人機(jī)可能會(huì)進(jìn)入威脅區(qū)；當(dāng)目標(biāo)點(diǎn)附近有威脅源時(shí)，斥力將會(huì)非常大，而 引力相對較小，無人機(jī)將很難到達(dá)目標(biāo)點(diǎn)；在復(fù)雜環(huán)境中，容易產(chǎn)生局部極小值，使算 法停滯或震動(dòng)；在障礙物附近有抖動(dòng)現(xiàn)象，在狹窄通道間頻繁擺動(dòng)；在動(dòng)態(tài)環(huán)境下規(guī) 劃效果減弱；計(jì)算勢場負(fù)梯度的方法因?yàn)闆]有優(yōu)化變量，將航跡規(guī)劃問題

16、轉(zhuǎn)換成了非 優(yōu)化問題，因此缺乏評價(jià)指標(biāo)衡量航跡的優(yōu)劣,勢場的建立直接決定了航跡的質(zhì)量，相 同的環(huán)境下，不同的勢場形式也可能得到不同的航跡。針對該問題，學(xué)者們結(jié)合無人 機(jī)航跡規(guī)劃的特點(diǎn)提出了多種改進(jìn)方法。文獻(xiàn)15 在斥力勢函數(shù)中加入無人機(jī)與目 標(biāo)點(diǎn)的距離，減小斥力，改善障礙物在目標(biāo)附近時(shí)，目標(biāo)不可達(dá)的問題。設(shè)置引導(dǎo)點(diǎn)為 無人機(jī)提供方向隨機(jī)的勢場力,解決局部極小值和震蕩問題。文獻(xiàn)16 在人工勢場法 搜索陷入威脅區(qū)時(shí)，構(gòu)造懲罰勢函數(shù)替代斥力勢函數(shù)，并使用模擬退火算法取代虛擬 力引導(dǎo)的方法搜索逃離位置，有效避免了局部極小值和抖動(dòng)現(xiàn)象，得到的航跡能成功 避開威脅，但增大了計(jì)算量，降低了人工勢場法的實(shí)時(shí)性

17、。文獻(xiàn)17通過引入相對速 度斥力勢場和斥力增益模糊控制器實(shí)現(xiàn)人工勢場法的動(dòng)態(tài)避障，避免局部極小值。文 獻(xiàn)18 通過增加高度調(diào)節(jié)引力勢函數(shù)以增強(qiáng)人工勢場法在三維航跡規(guī)劃中對高度的 控制，同時(shí)引入飛行器的動(dòng)力學(xué)約束條件，使航跡更具可飛性，并改善了人工勢場法的 局部極小值、障礙物附近抖動(dòng)、狹窄通道間頻繁擺動(dòng)等缺點(diǎn)。然而文獻(xiàn)15-18 中均 未衡量航跡優(yōu)劣的評價(jià)指標(biāo)，對此文獻(xiàn)19引入附加控制力作為優(yōu)化變量，通過優(yōu)化 出適當(dāng)?shù)母郊涌刂屏Γ篃o人機(jī)在滿足各種物理約束的條件下，規(guī)劃出的航跡可使代 價(jià)指標(biāo)最優(yōu)，降低了勢場建立的任意性對航跡結(jié)果的影響。但文獻(xiàn)19 在考慮無人機(jī) 動(dòng)力學(xué)模型時(shí)將無人機(jī)看作質(zhì)點(diǎn)，與實(shí)

18、際動(dòng)力學(xué)模型有一定差異。總之，對于極小值 等問題，前人提出的各種改進(jìn)方法都在一定程度上彌補(bǔ)甚至消除了這些缺陷，但對于 障礙物附近抖動(dòng)、狹窄通道間頻繁擺動(dòng)這一缺陷的改善效果還有待提高。模擬退火算法是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索算法。它模擬 固體物質(zhì)的退火過程，在某一初始溫度下，伴隨溫度控制參數(shù)按照降溫函數(shù)不斷下降, 結(jié)合概率的突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即能概率性地跳出 局部最優(yōu)解并最終趨于全局最優(yōu)解。退火過程由冷卻進(jìn)度表(CoolingSchedule )控 制，包括溫度控制參數(shù)的初值t及其衰減因子At、每個(gè)t值時(shí)的迭代次數(shù)和終止條 件。模擬退火算法的優(yōu)點(diǎn)是算

19、法求得的解與初始解狀態(tài)無關(guān)，具有漸近收斂性，是一 種以概率1收斂于全局最優(yōu)解的全局優(yōu)化算法。缺點(diǎn)是解的質(zhì)量依賴于當(dāng)前解產(chǎn)生 新解的變換方法和冷卻進(jìn)度表的設(shè)計(jì)。在航跡規(guī)劃中，模擬退火算法的一個(gè)解代表一 條航跡，目標(biāo)函數(shù)則是代價(jià)函數(shù)，常用于求解二維航跡規(guī)劃中的TSP問題20，但該算 法多數(shù)沒有考慮無人機(jī)的機(jī)動(dòng)性能約束，得到的航跡可飛性不高。模擬退火算法也可 與易陷入局部最優(yōu)解的算法相結(jié)合幫助其跳出局部最優(yōu)找到全局最優(yōu)解，如遺傳模擬 退火算法21,在交叉和變異過程中使用Metropolis準(zhǔn)則判斷是否接受新解，當(dāng)然， 這會(huì)增大原算法的計(jì)算量。2.2現(xiàn)代智能算法相較于傳統(tǒng)經(jīng)典算法，現(xiàn)代智能算法的應(yīng)用更

20、為廣泛。在航跡規(guī)劃中常用的現(xiàn)代 智能算法有A*算法、遺傳算法(GA： Genetic Algorithm)、蟻群優(yōu)化(ACO： AntColony Optimization)算法和粒子群優(yōu)化(PSO： Particle Swarm Optimization) 算法。A*算法是一種智能啟發(fā)式搜索算法,它將搜索空間表示為網(wǎng)格的形式，以網(wǎng)格的 中心點(diǎn)或頂點(diǎn)作為航跡點(diǎn)，通過搜索鄰域內(nèi)代價(jià)函數(shù)值最小的航跡點(diǎn),從起始點(diǎn)逐步 搜索到目標(biāo)點(diǎn)，最后逆向回溯當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)生成最優(yōu)航跡，其中待擴(kuò)展航跡節(jié)點(diǎn) 存放在OPEN表中，已擴(kuò)展節(jié)點(diǎn)存放在CLOSE表中。代價(jià)函數(shù)的表達(dá)式如下所示f(x)=g(x)+h(x)(8

21、)其中g(shù)(x)表示從起始點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià),h(x)稱為啟發(fā)函數(shù)，表示從當(dāng)前 節(jié)點(diǎn)到目標(biāo)點(diǎn)的估算代價(jià)，常用的啟發(fā)函數(shù)可選用歐氏距離、曼哈頓距離、對角線距 離等。啟發(fā)函數(shù)是A*算法的核心，它能在搜索效率和最優(yōu)解之間權(quán)衡。若h(x)小于 從當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的實(shí)際代價(jià),則搜索得到最優(yōu)路徑，但這時(shí)搜索節(jié)點(diǎn)增多,搜索效 率降低；若h(x) 一直等于從當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的實(shí)際代價(jià)，此時(shí)A*嚴(yán)格按照最優(yōu)路 徑搜索，搜索效率最高；若h(x)大于從當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的實(shí)際代價(jià),則搜索結(jié)果可 能不是最優(yōu)路徑，但搜索效率會(huì)提高。此外,OPEN表的維護(hù)方式也會(huì)影響A*算法的搜 索效率，當(dāng)路徑很長時(shí)，這種影響會(huì)更明顯。

22、總之，啟發(fā)函數(shù)的選擇決定了 A*算法是否 能找到最優(yōu)解,OPEN表的維護(hù)方式和搜索節(jié)點(diǎn)數(shù)量決定了 A*算法的運(yùn)行速度。隨著 搜索空間增大,A*算法的計(jì)算量會(huì)呈指數(shù)增長，導(dǎo)致規(guī)劃時(shí)間過長，一般用于靜態(tài)航跡 規(guī)劃。在航跡規(guī)劃中，如何提高A*算法的運(yùn)行速度并得到最優(yōu)航跡是學(xué)者們重點(diǎn)考慮 的問題。文獻(xiàn)7 采用結(jié)構(gòu)體式最小二叉堆和三層嵌套的二叉堆技術(shù)分別維護(hù)管理 OPEN表和CLOSE表，相比較于傳統(tǒng)的數(shù)組式最小二叉堆維護(hù)OPEN表和單向鏈表管理 CLOSE表的方式，提高了最優(yōu)節(jié)點(diǎn)的提取速度，克服了數(shù)組二叉堆的容量可能導(dǎo)致 OPEN表溢出的問題，有效解決了動(dòng)態(tài)二叉樹易出現(xiàn)的極度不平衡問題，保證了節(jié)點(diǎn)查

23、找的高效率，較大幅度提高了 A*算法的規(guī)劃效率。文獻(xiàn)22提出使用2.5維網(wǎng)格模型 描述三維規(guī)劃空間,每個(gè)網(wǎng)格點(diǎn)包含經(jīng)度、緯度和高程信息，此方法計(jì)算效率要遠(yuǎn)大 于三維網(wǎng)格劃分方式。文獻(xiàn)23 將三維航跡規(guī)劃分解為二維規(guī)劃和高度規(guī)劃,使用動(dòng) 態(tài)時(shí)間規(guī)整(DTW:Dynamic Time Warping)距離作為A*算法的啟發(fā)函數(shù)進(jìn)行二維規(guī)劃, 再由二維航跡結(jié)合高程數(shù)字地圖，利用粒子沉降法賦予每個(gè)航跡點(diǎn)高度信息,生成三 維航跡。這種方法有效地將三維空間的搜索節(jié)點(diǎn)刪減至二維，大大減少了搜索節(jié)點(diǎn)數(shù) 量，縮短了規(guī)劃時(shí)間。使用DTW距離作為啟發(fā)函數(shù)得到的航跡也要優(yōu)于常用的歐氏距 離、曼哈頓距離和對角線距離，但

24、仍不是最優(yōu)航跡。由于航跡規(guī)劃問題的復(fù)雜性，雖 然學(xué)者們通過各種改進(jìn)方法提高了 A*算法的搜索效率，但仍沒有找到值恒等于從當(dāng)前 節(jié)點(diǎn)到目標(biāo)點(diǎn)真實(shí)代價(jià)的啟發(fā)函數(shù)，實(shí)現(xiàn)A*算法的高效最優(yōu)搜索。遺傳算法的基本思想是模擬生物遺傳進(jìn)化過程，根據(jù)“適者生存”、“優(yōu)勝劣 汰”的原則，借助選擇、交叉、變異等操作，使所要解決的問題從初始解一步步逼近 最優(yōu)解。在航跡規(guī)劃中,遺傳算法每條染色體(個(gè)體)代表無人機(jī)的一條航跡,基因的 編碼方式也就是航跡節(jié)點(diǎn)的編碼方式，適應(yīng)度函數(shù)由代價(jià)函數(shù)變化而來。遺傳算法的 優(yōu)點(diǎn)是不要求優(yōu)化函數(shù)具備連續(xù)、可導(dǎo)和單峰等條件，具有較強(qiáng)的魯棒性，是一種高 效、并行、全局的搜索方法，適用于三維全

25、局航跡規(guī)劃。缺點(diǎn)是種群失去多樣性而導(dǎo) 致早熟收斂，尋優(yōu)時(shí)間長，局部搜索能力差等。針對該問題，學(xué)者們提出了不同的改進(jìn) 方法，如引入量子、自適應(yīng)等因子,但這些改進(jìn)方法仍然存在較多不足。文獻(xiàn)24 針 對量子遺傳算法初始種群的單一性，引入關(guān)于概率劃分的小生境協(xié)同進(jìn)化策略，并對 各種群采用動(dòng)態(tài)量子旋轉(zhuǎn)角；采用精英選擇機(jī)制，保留每一代中的最優(yōu)個(gè)體，并借鑒 狼群分配原則對種群進(jìn)行更新。該方法提高了量子遺傳算法的穩(wěn)定性和尋優(yōu)精度，但 在收斂速度上沒有改善，且沒有考慮無人機(jī)自身性能約束。文獻(xiàn)25使用并行遺傳算 法結(jié)合概率地圖實(shí)現(xiàn)多無人機(jī)協(xié)同航跡規(guī)劃，并行遺傳算法很好地克服了遺傳算法早 熟的缺陷，但文獻(xiàn)同樣沒有考

26、慮無人機(jī)自身性能約束。文獻(xiàn)26 通過在遺傳算法主種 群上附加一個(gè)病毒種群的方法，保證可行引導(dǎo)段的有效積累并維持種群多樣性。采用 定長實(shí)值和變長實(shí)值兩種編碼方式分別為染色體和病毒個(gè)體編碼，通過采用反轉(zhuǎn)錄和 轉(zhuǎn)導(dǎo)這兩種病毒感染操作實(shí)現(xiàn)兩個(gè)種群間模塊的信息交換，使進(jìn)化信息在種群內(nèi)迅 速、定向地傳播，消除了尋優(yōu)過程的盲目性。該方法改善了遺傳算法早熟和局部收斂 慢的問題，提高了收斂速度，但對于搜索精度幾乎沒有提高。文獻(xiàn)27 提出多頻振動(dòng) 遺傳算法，在遺傳操作中使用兩次變異操作，分別作用于整個(gè)種群和精英個(gè)體，為種群 提供全局多樣性和局部多樣性，從而有效避免早熟，提高搜索精度，達(dá)到快速收斂的目 的。蟻群優(yōu)化

27、算法模擬螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為特性，利用信息素濃度 進(jìn)行后繼行為。T時(shí)刻螞蟻n從節(jié)點(diǎn)a轉(zhuǎn)移到節(jié)點(diǎn)b的概率為|0.其他(9)其中Tab為節(jié)點(diǎn)b上的信息素濃度；nab為節(jié)點(diǎn)a與節(jié)點(diǎn)b之間的能見度，也 叫啟發(fā)函數(shù)，它可以是距離開銷，也可以是距離開銷與其它開銷的組合,如高度、安全 度等；a、B為Tab與nab的相對重要性的權(quán)值；為節(jié)點(diǎn)a的所有相鄰節(jié)點(diǎn) 的集合。信息素具有揮發(fā)性，隨著時(shí)間的增加其濃度會(huì)降低。信息素的更新分為局部更新 和全局更新，局部信息素更新是用在螞蟻完成一個(gè)航跡點(diǎn)的選擇時(shí)，相應(yīng)的減少該點(diǎn) 的信息素，降低此點(diǎn)對后來螞蟻的吸引程度，從而增加螞蟻的探尋范圍，減小算法陷入 停滯的概

28、率。其更新公式為Tab(t+1)=；Tab(t)(10)其中E為信息素減少因子,用于控制信息素減少的大小。全局信息素更新是經(jīng) 過m時(shí)刻，當(dāng)螞蟻完成尋路任務(wù)后對其經(jīng)過的所有航跡點(diǎn)上的信息素進(jìn)行更新，通過 這種方式增加這條航路上的信息素，其表達(dá)式為Tab(t+m) = (1-p)Tab(t) + pATab(11) Tab二Q/J(12)其中P為信息素?fù)]發(fā)因子；J為這條航跡的性能指標(biāo)；Q為性能指標(biāo)對于信息 素的更新的比例系數(shù)。蟻群優(yōu)化算法的優(yōu)點(diǎn)是具有良好的并行性、協(xié)作性和魯棒性，后期收斂速度快。 缺點(diǎn)是前期搜索時(shí)間長,參數(shù)多并且解的質(zhì)量受參數(shù)影響大，容易陷入局部最優(yōu)解，適 用于三維全局航跡規(guī)劃。由

29、于信息素的分布情況、揮發(fā)方式和螞蟻選擇前進(jìn)方向的 盲目性影響著解的質(zhì)量和獲得解的時(shí)間，學(xué)者們也通常從這幾個(gè)方面,結(jié)合航跡規(guī)劃 的特性對蟻群算法進(jìn)行改進(jìn)。文獻(xiàn)28 將螞蟻按數(shù)量均勻分組,并在信息素濃度更新 過程中使用差分進(jìn)化算法的交叉、變異、選擇操作，合理分配各路徑上螞蟻留下的信 息素，避免某條路徑上信息素累積過多而導(dǎo)致陷入局部最優(yōu)解,從而引導(dǎo)螞蟻找到最 優(yōu)路徑。該混合算法在保證基本蟻群算法優(yōu)點(diǎn)的同時(shí)提高了全局收斂的速度，但得到 的航跡過長。文獻(xiàn)29 提出一種文化蟻群算法，設(shè)計(jì)了由蟻群算法演化的群體空間和 由群體空間最優(yōu)解構(gòu)成的信仰空間，兩個(gè)空間同時(shí)演化，彼此促進(jìn)。在群體空間中加 入懲獎(jiǎng)機(jī)制，對

30、到達(dá)終點(diǎn)的螞蟻?zhàn)哌^的路徑，提高其信息素濃度，反之，則降低,從而提 高了螞蟻找到可行路徑的概率。信仰空間利用選擇、交叉、變異這3種遺傳操作進(jìn) 行更新。此外，文獻(xiàn)在啟發(fā)式函數(shù)中加入了航路點(diǎn)的方差，計(jì)算待選節(jié)點(diǎn)和其前面n 個(gè)點(diǎn)的方差,使選出的節(jié)點(diǎn)與前面節(jié)點(diǎn)的波動(dòng)相對較小，從而獲得更平滑的航跡。該 方法的雙層進(jìn)化模型加快了航跡的搜索速度，但懲獎(jiǎng)機(jī)制的評判標(biāo)準(zhǔn)單一，到達(dá)終點(diǎn) 的螞蟻?zhàn)哌^的路徑并不一定就好,此機(jī)制可能會(huì)降低解的質(zhì)量。文獻(xiàn)30首先限制信 息素?fù)]發(fā)因子的范圍，防止其過大或過小影響算法的全局搜索能力，并在信息素調(diào)整 規(guī)則中引入航跡評價(jià)指標(biāo)，提高解的質(zhì)量。然后將起始點(diǎn)和目標(biāo)點(diǎn)之間的連線這一最 短航

31、跡信息反饋到系統(tǒng)中作為搜索的指導(dǎo)信號，將能見度改進(jìn)為當(dāng)前節(jié)點(diǎn)與待擴(kuò)展節(jié) 點(diǎn)的距離和待擴(kuò)展節(jié)點(diǎn)到最短航線的垂直距離加權(quán)和的倒數(shù)，降低算法尋找航跡的盲 目性，加快了搜索效率。最后在該能見度的基礎(chǔ)上，將轉(zhuǎn)移概率與一個(gè)01之間的隨 機(jī)數(shù)相乘，選擇鄰域中轉(zhuǎn)移概率最大的節(jié)點(diǎn)擴(kuò)展。該方法在保證基本蟻群算法優(yōu)點(diǎn)的 同時(shí)提高了解的質(zhì)量，大大縮短了搜索時(shí)間。粒子群優(yōu)化算法模擬鳥群飛行捕食行為，把每個(gè)粒子看作優(yōu)化問題的一個(gè)可行 解,并將其延伸到N維空間，每個(gè)粒子主要通過跟蹤兩個(gè)位置決定自己下一步的飛行， 一個(gè)是粒子本身所找到的最優(yōu)解Pbest,即個(gè)體最好位置；另一個(gè)是種群中所有粒子 當(dāng)前找到的最優(yōu)解Gbest,即全

32、局最好位置，最終群體成員逐漸移入問題空間的更好區(qū) 域。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值,每個(gè)粒子還有一個(gè)決定其飛 行方向和距離的速度。粒子群算法的速度和位置更新方式分別為vij(k+1) = 3vij(k)+c1r1(pij(k) -xij(k)+c2r2(gij(k)-xij(k)(13) xij(k+1)=xij(k)+vij(k)(14)其中下標(biāo)i、j、k分別表示第i個(gè)粒子，第j維空間，第k代粒子；3為慣性權(quán) 重，描述了粒子對之前速度的“繼承”；c1、c2為常數(shù),稱為學(xué)習(xí)因子，體現(xiàn)了粒子向 全局最優(yōu)粒子學(xué)習(xí)的特性；r1、r2為(0,1)之間的隨機(jī)數(shù)。與其他進(jìn)化算法相比，粒子群

33、算法具有兩個(gè)顯著的不同特點(diǎn)。一是沒有“優(yōu)勝劣 汰”的機(jī)制，所有的粒子在迭代過程中始終作為種群的成員保留；二是沒有交叉、變 異等進(jìn)化算子，每個(gè)粒子通過追隨當(dāng)前搜索到的最優(yōu)值尋找全局最優(yōu)。粒子群算法的 優(yōu)點(diǎn)是具有較強(qiáng)的魯棒性，對種群大小敏感性不高,參數(shù)少，前期收斂速度快,缺點(diǎn)是 后期收斂速度慢，容易早熟陷入局部最優(yōu)解，可用于三維全局航跡規(guī)劃。在航跡規(guī)劃 中學(xué)者們對粒子群算法的改進(jìn)也多是通過提高種群的多樣性避免局部最優(yōu)。文獻(xiàn)31在量子粒子群優(yōu)化算法(QPSO： Quantum-behavedParticleSwarmOptimization) 的基礎(chǔ)上引入繁殖機(jī)制，整個(gè)種群中粒子位置更新后不直接進(jìn)入

34、下一代，而是以一定 概率將粒子放入繁殖池，種群中最優(yōu)個(gè)體不參與繁殖操作，以便保護(hù)其不被破壞。該 方法與QPSO算法和PSO算法相比，能找到更優(yōu)的航跡，但由于增加了繁殖機(jī)制，每次 迭代時(shí)間要比QPSO算法多。文獻(xiàn)32在基本PSO算法中引入病毒種群，以增強(qiáng)主群 體粒子的多樣性，提高局部搜索能力，解決基本PSO算法容易陷入局部最優(yōu)、收斂速 度慢的問題。文獻(xiàn)33在？5。算法中引入潛在網(wǎng)格構(gòu)造算子，在整個(gè)種群中粒子位置 更新后，為每個(gè)粒子運(yùn)用相應(yīng)的算子，以克服PSO算法易陷入局部最優(yōu)和后期收斂速 度慢的問題，該方法能得到質(zhì)量更好的航跡。3目前研究熱點(diǎn)及發(fā)展趨勢3.1現(xiàn)代智能算法的改進(jìn)航跡規(guī)劃是一個(gè)NP-hard問題,要得到最優(yōu)航跡需要極大