智能航跡規劃算法研究現狀與展望

謝凱利，楊海濤，謝海平

(航天工程大學， 北京 101416)

航跡規劃是指在給定的約束條件下，基于某種性能指標求取運動物體從初始點到目標點的最優運動軌跡[1]。60年代，航跡規劃的研究主要基于數學理論，經過幾十年的發展，航跡規劃算法已十分豐富，并逐步應用于無人機、導彈、機器人等領域[2-6]。目前，對航跡規劃的研究主要由規劃環境建模和優化搜索兩部分組成。

在規劃環境建模上，由于實際的空間環境比較復雜，為降低求解問題的規模，通常根據幾何學原理，按照特定的規則對規劃空間進行結構劃分，常用的劃分方法包括單元分解法、路標圖法、勢場法等。針對航跡規劃存在約束條件多、復雜性強、時效性高、規劃領域大、難以直接求解等特征，近年來國內外學者提出了許多不同的規劃搜索方法[7]，大多數是轉化為狀態空間的路徑搜索問題，利用搜索算法獲得最優解。按照規劃策略，可將航跡規劃算法分為傳統經典算法和智能優化算法。Dijkstra算法、人工勢場法等傳統算法已經發展成熟，對于小規模以及簡單的空間環境，在獲取最優航跡方面具有明顯優勢。但當空間環境規模增大時，傳統算法的時間呈指數倍增長，而智能優化算法在提高航跡搜索效率方面有著較好表現。其中，遺傳算法[8]、模擬退火算法[9]、粒子群算法[10]、神經網絡算法[11]等，是航跡規劃技術中較為常用的一些智能算法，對解決實際規劃問題具有重要意義。

下面將從傳統經典算法和智能規劃算法兩方面，對現有航跡規劃算法進行綜述，同時對未來航跡算法的研究重點和發展方向進行展望。

1 傳統經典算法

傳統的航跡規劃算法有可視圖法、自由空間法、柵格法、人工勢場法、梯度方法、Dijkstra算法、模擬退火算法等，本節主要對以Dijkstra算法為代表的圖搜索算法、人工勢場法、模擬退火算法這幾種常用的搜索算法進行分析[12]。

1.1 Dijkstra算法

Dijkstra算法[13]于1959年由狄克斯特拉提出，其核心是解決有權圖中固定點之間的最短路徑問題，在搜索過程中，處理邊權為正的情況。采用貪心思想將有權圖中起始頂點與各個頂點的距離保存在數組d[i]中，其中i代表頂點，從起始點開始，向周圍節點進行遍歷，選擇與起點距離最短且沒有被擴展過的頂點，將其保存在集合T中，以此循環，直至遍歷到終點，其中集合T中的頂點為單源最短路徑點。

Dijkstra算法進行航跡規劃，將航跡規劃問題轉化為有權圖求最短路徑問題，其中有權圖的頂點和邊代表航跡點和可行航跡。Dijkstra算法在簡單環境空間下獲取最短路徑的效率較高，由于工程應用中飛行器的規劃區域較大，算法擴展節點數量增多，導致搜索時間增加，規劃效率較低，因此在實際應用中需要對Dijkstra航跡規劃算法進行改進[14-16]。文獻[14]改進Dijkstra航跡規劃算法，基于人工勢場法建立新的威脅模型，在工程應用中，減少算法搜索時間，降低內存的占有率。文獻[15]基于voronoi方法對威脅源建模，獲得的航跡能夠安全的躲避威脅物，采用Dijkstra算法搜索最優航跡。文獻[16]Dijkstra算法基于可視圖方法將多邊形中的各個阻礙點表示為航跡點，加入航跡轉角約束，得到最短航跡點，但規劃的航跡緊貼障礙物，容易發生碰撞。

由上述可知，目前Dijkstra算法的應用多是在二維靜態環境中，利用voronoi圖、可視圖或者是與其他航跡算法結合建立環境模型，在此基礎上搜索最優航跡，但得到的航跡在安全性和有效性很難達到平衡。

1.2 人工勢場法

人工勢場法[17]的基本思想是將運動體所處的工作環境抽象為一個虛擬力場空間(如圖1所示)，把障礙物和威脅看成排斥力，目標點當作吸引力，通過合力控制物體的運動，有效規避行進過程中障礙物的阻礙，使得規劃出來的路徑是平滑、安全的。

圖1 人工勢場航跡規劃二維圖

人工勢場法作為傳統算法，研究和發展較為成熟，算法簡單、規劃時間短，廣泛應用于局部靜態航跡規劃。在實際應用中，規劃環境復雜，目標點周圍有障礙物出現的情況下，飛行器會受到明顯的斥力作用，此時無法到達目標點；當飛行器在動態環境規劃時，障礙物和目標點發生運動，容易造成局部震蕩或與障礙物發生碰撞的現象。對此許多學者對人工勢場算法進行研究并提出多種改進方法，文獻[18]提出一種混沌理論的人工勢場算法，解決航跡規劃過程中，容易陷入局部較小值和在目標點徘徊的情況。文獻[19]加入最大轉角約束，解決了傳統人工勢場法存在的局部最小值和震蕩問題。文獻[20]在威脅指標確定的情況下，引入相對速度斥力勢場和斥力增益模糊控制器，有效地解決人工勢場法的動態規避障礙物和陷入局部極小值的問題。

針對上述所述，國內外學者提出的多種改進方法，可以有效的解決人工勢場算法容易陷入局部最小的缺陷，而對于動態規劃環境下，局部震蕩和與障礙物發生碰撞的改善效果明顯不足，是其未來研究的方向。

1.3 模擬退火算法

模擬退火算法[21](Simulated Annealing,SA)是一種基于蒙特卡洛思想設計的近似求解最優化問題的方法，應用于規模較大的組合優化問題。基于固體物質的退火原理，設定較高的初始溫度，隨著溫度的降低，為避免陷入局部最優，結合概率突跳特性，進行隨機搜索，尋找全局最優解。

在模擬的過程中，設置初始溫度T和初始解x，將溫度T作為控制參數，對當前解采用metropolis準測，不斷進行“產生新解—判斷—接受或舍棄”迭代，當參數T逐漸減少直至零時，算法結束，當前即為航跡最優解。通過冷卻進度表控制T和每個T值的迭代次數、產生新解過程的計算增量Δt。

模擬退火算法在航跡搜索過程中，不依賴于初始狀態，具有通用性，應用廣泛，同時具有較好的全局收斂性，適合求解多數組合優化問題，例如二維航跡規劃中的TSP問題[22]。但算法對當前解的求解方法和冷卻進度表的依賴性較強，在實際應用中，問題規模過大，容易影響最優解的質量。目前對模擬退火算法的主要研究和應用，將模擬退火算法與容易陷入局部最優的航跡算法結合，即克服了局部最優的不足又提高算法搜索效率和精度[23]。

1.4 算法小結

傳統的航跡規劃算法發展成熟，采用一定的搜索技術可以獲得最優路徑，但是，在路徑搜索效率和航跡優化等方面存在不足，需要進一步完善。傳統算法間的對比分析如表1所示。

表1 傳統算法間的對比分析

2 智能優化算法

本節將智能航跡規劃算法分為兩類；一類是確定型搜索算法，如確定性計算方法的最小化原理和確定性狀態的空間搜索方法，包括以A*算法為代表的圖搜索算法和動態規劃法等；另一類為隨機型搜索算法，如遺傳算法、蟻群算法和神經網絡算法等，以隨機搜索為特征的優化算法。智能航跡規劃算法分類如圖2所示。

圖2 智能航跡規劃算法分類框圖

2.1 確定型搜索算法

2.1.1A*算法

A*算法[24]在20世紀60年代由Hart等提出，以Dijkstra算法為基礎，采用啟發式思想，引入當前結點的估價函數，對擴展節點的代價值進行評估和比較，選擇代價值最小的節點作為最優節點進行下一步擴展，直到搜索到終點。A*算法搜索時使用OPEN和CLOSE表進實現節點的擴展和最優節點的選取，其中，擴展節點按照估價值大小的順序保存在OPEN表中，CLOSE表存儲估價值最小的擴展節點，這些節點的連線組成最優航跡。

其中，當前結點的估價函數定義為:

f*(n)=g*(n)+h*(n)

(1)

式中：f*(n)為起始節點到目標節點的估計代價；g*(n)為起始節點到當前節點n的實際代價；h*(n)為當前節點n到目標點的估計代價。h*(n)作為啟發函數可選用歐氏距離、曼哈頓距離、對角線距離三種公式計算，常用曼哈頓距離公式計算h*(n)，有:

h*(n)=D*(abs(n.x-goal.x)+abs(n.y-goal.y))

(2)

式中：D表示移動代價；abs表示絕對值；x、y分別表示橫坐標和縱坐標。

A*算法相比于其他算法來說簡單，代碼容易實現，其中航跡最優解的獲取以及算法搜索效率的提高，與h*(n)的選擇、OPEN表的維護有著直接的關系以及規劃空間的規模，適應于二維靜態規劃環境。提高搜索算法效率的同時獲取最優航跡，是當前A*算法在航跡規劃中主要的研究方向[25-28]。文獻[25]將動態加權A*算法應用于無人機航跡規劃，減少了航跡代價，提高了算法的航行速度。文獻[26]對廣義搜索A*算法增加約束條件，將改進的A*算法應用到動態規劃環境中，解決了A*算法搜索空間大的復雜問題，具有較強的工程實用性。文獻[27]結合無人機的性能和任務約束改進的A*算法，同時對OPEN表的管理方式進行優化解決三維環境下空間搜索節點數量增多和內存消耗較大的問題，提高了算法搜索的時間。

由于規劃環境的復雜性，學者們通過各種改進的方法提高了A*算法的搜索效率，但選擇合適的啟發函數，平衡算法搜索效率和搜索精度，仍然是A*算法重點考慮的問題。

2.1.2D*算法

D*算法[29]是動態的A*算法，由Stentz[29]提出，是火星探測器的尋路算法。D*算法的核心思想：在Dijkstra和A*算法的基礎上，從目標G向起始點進行反向搜索，建立一個“路徑場”，搜索過程中將節點信息保存在OPEN和CLOSE中。當路徑環境發生變化或者路徑上的節點遇到阻礙時，通過建立的“路徑場”信息，避免二次規劃，減少運算量，提高搜索效率。文獻[30]提出有向D*算法，在提高搜索方面引入導向函數以控制單次搜索的節點搜索范圍。

D*算法進行路徑尋優時，能夠很好的感知到當前節點或者臨近節點的信息變化，但D*算法不能很好解決環境中較遠節點信息發生改變的狀況。

2.2 隨機型搜索算法

2.2.1基于采樣算法

快速擴展隨機樹(Rapidly-Exploring Random Tree，RRT)算法[31]，于1998年由S.M.LaValle首次提出，如圖3所示為RRT算法的發展時間軸。RRT算法是典型的基于隨機采樣的算法，在搜索空間中快速擴張，生成一顆連接根節點和目標點的搜索樹。其中路徑起點做為擴展樹的根節點，采用隨機采樣方法進行葉子節點的擴展，直到終點或者終點所在的區域包含在葉子節點中。

圖3 RRT的發展時間軸框圖

該算法與其他算法相比，計算簡單，能夠結合當前環境狀況進行快速有效地搜索，其搜索速率在空間維度較高的情況下尤為明顯，廣泛應用于不具備完整系統的航跡規劃[32]。同時RRT算法具有較為明顯的缺點，使得后續算法的應用受到限制：沒有對航跡代價進行綜合考慮，造成較大的損耗代價；節點選擇的隨機性太強，不能夠得出最優或者接近最優的航跡。

面對上述算法存在的不足，國內外專家對算法進行通過大量的研究和改進，在簡單的規劃環境下，保證了算法在實際應用中的可行性和高效性[33-36]。其中，文獻[33]對算法節點的采樣和擴展方式進行改進和優化，解決算法節點隨機性較強而無法獲取最優航跡的問題，減少了擴展節點數量，提高算法航跡搜索的效率；文獻[34]針對算法節點隨機性強、不能夠得到最優航跡等缺點，通過改變隨機樹的生長方向的角度對RRT算法進行改進和優化，降低了規劃時間，規劃航跡接近最優；文獻[35]結合A*算法的啟發思想，改變RRT中擴展節點的方式，建立滿足航跡規劃的約束條件，減少巡航時間，降低航跡代價的損耗，易于工程的實現。然而在約束條件較多的復雜規劃環境，對RRT算法性能有著更高的要求。

2.2.2遺傳算法

1975年，美國John Holland教授基于“物競天擇，適者生存”理論提出遺傳算法[37](Genetic Algorithms,GA)，其算法原理基于基因重組和自然進化選擇，如圖4所示，在航跡搜索過程中，將待求解問題進行編碼(基因)，若干基因組成一個染色體，每一個染色體代表一條可行性航跡，通過對染色體進行自然選擇、交叉和變異操作得到新的個體，并不斷地循環迭代，直到產生最優的個體。

圖4 遺傳算法原理示意圖

遺傳算法是當代人工智能科學研究的一個重要分支，遺傳算法具有自身迭代的優勢，適用全局航跡搜索，易與其他算法相結合，魯棒性強，能夠很好地應用到三維航跡規劃空間。對該算法進行改進是目前研究的熱點，通過引入量子，改進適應度函數參數和遺傳算子等方面，彌補算法規劃后期收斂速度慢、容易陷入局部最優等不足。文獻[38]進入差分進化變異策略，增加算法變異的多樣性，改進的算法在全局搜索后期加快了收斂速度，抑制了算法的早熟，防止陷入局部最優；文獻[39]提出改進量子遺傳算法，針對量子遺傳算法初始種群的單一性，引入關于概率劃分的小生境協同進化策略，并對各種群采用動態量子旋轉角，并借鑒狼群分配原則對種群進行更新，改進后的算法提高了算法的精度和穩定性。

改進后的遺傳算法能夠有效平衡全局搜索精度和搜索速度，但單一的遺傳算法應用于實時航跡規劃中效果不佳，需要與其他的智能航跡優化算法進行結合，如文獻[40]針對 GA 算法早熟問題改進適應度函數，構造一種隨進化代數動態調整的非線性適應度函數，提高算法的收斂速度，同時與稀疏A*算法結合，應用于三維在線航跡規劃問題，具有一定的工程意義。

2.2.3蟻群算法

蟻群算法[41]基于螞蟻覓食的群體思想，是群體智能算法的一種，1992年Marco Dorigo在他的學術論文中第一次提出了該算法，并用該算法解決了實際問題。

算法思想是基于螞蟻覓食方式，在尋找食物的過程中，螞蟻會釋放一種稱為信息素的分泌物，所經過的地方會留下前繼螞蟻的信息素，后繼螞蟻通過信息素獲取路徑信息，并通過狀態轉移概率以大概率選擇其中信息素濃度較高的一條路徑，同時也會留下自身的信息素，使得該條路徑上的信息素濃度逐漸加深，信息素的濃度和路徑長度成反比，最終信息素濃度較高的路徑為最優路徑。該算法采用正反饋機制，加快搜索速度，在分享和尋找信息素之間能夠達到很好的動態平衡，具有較強的抗干擾性、全局計算能力。

與其他搜索算法相比，蟻群算法的收斂速度相對較慢，搜索空間較大時容易出現滯留現象，容易陷入局部最優。針對上述算法的缺點，許多學者針對算法的不足進行改進。文獻[42]通過對參數進行自適應調節，使蟻群的搜索能力和個體之間的交互能力有所提高，解決傳統算法存在易陷入局部最優的問題。文獻[43]引入偽隨機狀態轉移規則對基本蟻群算法進行改進，克服基本蟻群算法容易陷入局部最優和迭代停滯的現象。文獻[44]設計一種分層模型，使改進的蟻群算法更能夠應用到復雜的三維航跡空間，并對相關的算法模型進行優化，提高三維空間下航跡規劃的適應性和安全性。

目前，對蟻群算法的改進大多針對算法陷入局部最優問題，對算法的搜索精度優化的研究較少。同時利用蟻群算法的魯棒性強的優點，與其他智能算法相融合也是其未來主要的研究方向。

2.2.4神經網絡算法

神經網絡算法作為目前應用較為廣泛的一種人工智能算法，其雛形由心理學家W.MeCulloch和數學家W.Pitts[45]提出，通過模仿人類大腦的神經結構處理問題的方式建立算法的計算模型。人工神經網絡作為非線性動態系統，引入能量函數的概念，其在航跡規劃過程中，通過不斷調整神經網絡中的各項權值，使能量達到一個穩定的狀態，基于此獲取航跡最優解。

人工神經網絡算法在結構、實現原理和功能各方面都模擬生物神經網絡，因此具有較強的并行處理能力和自主學習能力，容錯性和魯棒性較強，神經網絡作為重要學科，引起眾多學者的廣泛關注[46-48]。目前，對神經網絡的研究還在探索階段，在實際應用中，航跡搜索環境的復雜化和空間區域范圍廣，使得選取合適的權值較為困難，增加了規劃時間。

2.3 算法小結

通過分析上述兩種類型算法的適用性和優缺點可知(如表2所示)，隨機型搜索算法具有方向性自適應搜索的優點。在適應度函數的推動下，依據各種引導信息，如遺傳算法的交叉、變異等，產生新的個體，不斷擴大搜索范圍，向目標方向逐步優化，易找到全局最優解。

表2 智能優化算法間對比分析

隨機型搜索算法與確定型搜索算法相比，搜索空間不受限制，假設條件不受約束，對于優化函數不要求其特殊性，并且可以并行性，但在搜索精度和規劃時間等方面不如確定型搜索算法。

3 總結與展望

現代高技術信息化的發展對航跡規劃技術的要求不斷提高，靜態環境下的航跡規劃算法已經無法滿足復雜作戰任務和多樣化規劃環境的需求，例如：城市環境中建筑物的復雜性和多樣性、戰場環境所面臨的敵方防御系統和未知環境下障礙物的動態變化等。這些更為復雜和多約束規劃環境下，提高航跡規劃技術的實時性，是航跡規劃算法未來發展的主要方向，其算法的改進和創新也是未來研究的重點與難點，下面對其發展趨勢進行深入分析。

1) 實時航跡規劃技術的發展不僅對計算機的性能和硬性條件有要求，也對算法在時間和空間復雜度方面提出更高的需求。航跡規劃技術實時性的提高，目前主要考慮航跡規劃過程中的突發威脅，引入知識集成和模型預測控制對復雜環境中的威脅物進行處理。未來，為滿足實時航跡規劃技術，航跡規劃算法在求解優化問題方面需要具備更高的搜索效率和較短的規劃時間，是智能航跡規劃算法未來的發展趨勢。

2) 智能航跡規劃算法存在規劃時間長、范圍廣的缺點，因此不斷完善算法自身的缺陷，提高算法的搜索效率和準確度，是目前算法改進的主要目的。然而在實際應用中，面對交叉學科的新問題時，單一的規劃算法存在局限性，無法得出問題的最優解。因此，未來航跡規劃算法的研究方向趨向于將兩種或多種算法結合。同時，多種算法的融合需要考慮其算法在工程中的應用效果，需要學者對融合算法的性能進一步研究。

3) 同時，原有的航跡規劃智能算法的不足依舊存在，例如：RRT算法不適應高緯度、復雜化的戰場環境，神經網絡算法訓練結果的準確性和可靠性無法得到保證，遺傳算法、蟻群算法的收斂速度慢等缺點，在2014年Mirjalili 等人提出的一種新的智能化航跡算法-灰狼優化算法，具有參數少、容易實現和收斂性能高等優點，彌補了其他智能算法的部分缺陷，與該算法進行融合在性能上也有明顯的優勢。因此，新的智能航跡算法的提出是必要的，也是未來航跡規劃算法研究的難點和發展方向。

4 結論

航跡規劃算法的發展，在機器人系統、無人駕駛系統和多飛行器系統等導航方面的發展具有一定的價值。人工智能技術在航跡規劃領域的發展、規劃環境的復雜性和約束條件的多樣性，對智能化航跡算法有著更高的要求。在航跡規劃算法發展的基礎上不斷改進和優化，將航跡規劃智能算法的研究重點放在實時在線航跡規劃技術和算法創新與改進方面，是廣大學者主要研究的方向。