樊 嬌1， 雷 濤1， 韓 偉2， 王 銳3

(1.陜西科技大學 電子信息與人工智能學院，陜西 西安 710021；2.青島恒星科技學院 信息學院，山東 青島 266100；3.國防科技大學 系統工程學院，湖南 長沙 410073)

摘 要： 航跡規劃是無人機自主飛行的關鍵技術之一。典型的航跡規劃分為3個步驟：首先充分考慮各種威脅環境，進行飛行航跡的初步規劃，其次利用優化搜索算法找出最佳航跡，最后進行航跡平滑處理。系統梳理了近些年關于無人機航跡規劃的研究現狀，分析了航跡規劃過程中動力學約束和環境約束等因素；闡述了航跡規劃涉及的關鍵技術，包括地形獲取、威脅及代價建模、航跡規劃算法以及航跡平滑處理等，并進一步對常用的航跡規劃算法，如A*算法、遺傳算法、蟻群算法、粒子群算法，以及常用的航跡平滑算法B樣條曲線法進行了分析和歸納；總結了當前無人機航跡規劃模型構建與航跡規劃算法兩個方面存在的問題；最后對無人機航跡規劃未來可能的發展趨勢進行了展望，指出構建合理的航跡規劃的體系、先進的在線航跡規劃算法研究，以及多無人機協同航跡規劃是未來的研究趨勢。

關鍵詞： 無人機；航跡規劃；優化搜索算法；綜述

0 引言

隨著航空技術的日益成熟，無人機在各個領域展現出了良好的應用前景。無人機不僅成本低，而且能夠持續高強度作戰，同時可以避免人員傷亡。無人機航跡規劃是無人機任務分配中的一個重要問題，作為無人機執行任務的基礎，近些年來，引發了大量的研究。簡而言之，無人機航跡規劃就是在滿足無人機自身性能和各種威脅等約束條件下，規劃出從起始點到目標點的一條或多條實際可飛的航線。一般規劃的航跡要盡可能最優，盡量避開威脅，同時航跡代價要最小。

本文首先對無人機航跡規劃的研究現狀進行綜述，然后對航跡規劃過程中的影響因素等問題進行分析，其次對關鍵技術等方面進行綜述，最后分析存在的問題并對發展趨勢進行展望。

1 研究現狀

目前，國內外學者對無人機航跡規劃問題已經開展了大量研究工作。20世紀90年代初，國外很多學者將研究重點放在單架無人機靜態航跡規劃和平面二維環境建模的研究上。由于無人機在飛行過程中環境復雜、突發威脅較多，產生了許多動態實時航跡規劃和三維環境建模的研究成果，同時，考慮到單架無人機完成任務能力有限，為了提高效率，又對多無人機協同任務及航跡規劃進行研究。Ramchurn等[1]在動態環境下，對多無人機任務分配中的人機協作進行研究，采用多無人機監督和多主體協調算法在動態環境中對人為決策進行支持，避免了動態環境中執行許多搜索任務時可能導致無人機掉線的問題。Ruz等[2]在規劃中采用混合整數線性規劃對威脅和障礙進行檢測。威脅區域是雷達檢測區域，用該方法使非線性雷達檢測風險函數逼近線性。Shiri等[3]利用均場博弈理論控制方法研究了用于關鍵任務應用的大規模無人機自主控制。在初始源對無人機進行一次狀態交換，并采用機器學習模型解決多無人機狀態下計算量太大的問題，這種方法有效避免了碰撞。Hota等[4]研究了固定翼微型飛行器在三維空間中如何規劃航跡的問題，將軌跡用最小轉彎半徑的圓和直線相連，并用平滑的方式在2個連續的航路點之間進行過渡。

國內早些年由于經濟、政治等因素影響，對無人機的研究起步較晚，一直處于跟蹤國外技術的階段，但如今中國在無人機技術研究上已經取得了蓬勃的發展。張佳龍等[5]提出了復合矢量人工勢場方法，利用引力追蹤目標，利用斥力避開障礙，有效實現了多無人機編隊在三維空間的避障。Luo等[6]采用K-means算法和模擬退火算法對復雜約束下的多任務多無人機進行航跡規劃，增加了巡航有效區域中子目標區域的覆蓋范圍。Zhang等[7]在航跡規劃過程中，采用層次定向動態規劃解決了動態規劃在特殊地形環境的適用性和算法復雜性問題，提高了計算效率。楊健等[8]在使用應用分層優化法解決多協作式無人機任務規劃問題時，首先將Dubins和B樣條曲線融合并規劃出所有可選航線，然后估計每段航線的時間消耗，最后又把組合算法規劃的初始航線作為下一層使用最優控制方法規劃精細航跡的初始解，解決了B樣條算法在進行優化時不能考慮無人機始末狀態約束的問題。

從總體來看，對航跡規劃的研究主要分為3個方面：一是在考慮各種威脅的環境中初步規劃無人機的飛行航跡；二是通過優化搜索算法進一步尋優，找到最佳航線；三是進行航跡平滑處理。在航跡規劃算法方面，主要是對各類智能算法(如A*算法、遺傳算法、蟻群算法、粒子群算法等)的改進應用，并且在具體運用中根據不同的特征對各類算法進行混合。

2 約束條件分析

無人機在飛行空域中以及進行航跡規劃時有很多影響因素，不僅需要無人機滿足自身性能約束，還需要滿足任務、環境等約束。自身性能約束包括最小航跡段長度、最小轉彎半徑、最大俯仰角、最低和最高飛行高度、最大航跡長度等；任務約束有任務完成時間、起始點、目標點、固定航向角等；環境約束有各種威脅場約束、禁飛區約束等[9]，同時要求無人機滿足突防要求，戰場環境中還需要注意無人機的隱蔽性。下面介紹幾種主要的約束條件。

2.1 空氣動力學約束

航跡規劃中對空氣動力學的研究比較少，但無人機飛行時處于大氣中，大氣對其有一定影響，所以不得不考慮空氣動力學約束。空氣對無人機的作用主要表現在空氣動力和空氣動力矩上，前者的升力和重力的相互作用可以使無人機飛行，阻力影響到無人機應裝燃料的多少，而后者可以使無人機保持穩定。

2.2 無人機自身性能約束

(1)最小航跡段長度。無人機在改變飛行姿態前必須保持的最短直飛距離，也即最小步長。這一約束不僅與無人機的機動性能有關，還與無人機的導航要求有關。一般情況下，希望無人機避免迂回行進或頻繁轉彎，因此要求每段飛行航跡不小于最小航跡段長度。

(2)最小轉彎半徑。無人機改變航向時需要相應的時間和轉彎半徑，航跡每一轉彎點的曲率半徑小于無人機最小轉彎半徑時航跡不可飛，因此航跡規劃過程中需要考慮最小轉彎半徑，并要求轉彎處航跡點的曲率半徑大于等于最小轉彎半徑。

(3)最大俯仰角。三維空間航跡規劃中影響無人機俯仰角的因素有無人機自身機動性能、飛行高度和氣候狀況等，該約束限制了無人機只能在特定角度內進行俯仰動作，要求無人機在某一航跡點的俯仰角不大于最大俯仰角。

(4)最低和最高飛行高度。無人機作戰時需要在盡可能低的高度上飛行，依賴地形保護無人機，使敵方探測器難以發現或避免被地面防御系統摧毀，但又要保證不與地形障礙物相撞，因此需要在兩者間進行折中。航跡搜索過程中每一個可達航跡點的最低高度要求不小于某一給定的安全高度，同時由于一些受地面站控制的無人機需要與地面站聯系，所以飛行高度也要求不大于最高飛行高度。

(5)最大航跡長度。整個飛行過程中，無人機的總航程受到油耗和時間配給的影響，因此飛行航跡的總長度必須小于等于預先設置的最大距離。

2.3 環境約束

(1)威脅場約束。無人機在飛行過程中需要考慮各種威脅(惡劣天氣、敵方武器陣地、鳥類等空中飛行物、地形障礙等)的位置、威脅半徑以及威脅程度等，并且必須及時地獲取威脅信息，保障無人機的安全。一些學者將惡劣天氣的威脅簡化為圓柱形，將山峰、坡地、雷達等威脅簡化為圓錐形等模型，很大程度上簡化了計算過程。

(2)禁飛區約束。無人機需要避免飛入國家法律明文規定的一些區域，比如軍事重地、機場和一些敏感地區，還要避開高壓線、高樓以及人群密集的地方等。

3 航跡規劃技術

無人機航跡規劃的關鍵技術主要包括地形獲取、威脅及代價建模、航跡規劃算法、航跡平滑處理等。下面針對每項關鍵技術，介紹近些年的研究現狀。

3.1 地形獲取

航跡規劃中最先需要考慮的就是地形獲取問題，它對航跡質量有很大影響。地形獲取一般通過衛星獲得，目前常用的方法主要是構造數字地圖數據庫。2004年趙杰[10]在對數據地形的模擬中提出基于規則格網的數字高程模型的地形特征提取算法，對洼地、平坦地區等進行處理，有效地將主要的地形特征正確地提取出來。2006年巴海濤[11]采用數字地圖信息融合原理建立等效數字地形圖，把飛行區域內的已知地形、地物及威脅信息融合成一種綜合的地形信息，生成等效數字地圖；再經過對飛行數據的預處理，在一個類似于綜合考慮了地形、威脅以及飛行器性能的等效地形曲面上進行搜索，對無人機的飛行航跡進行規劃，達到了很好的規劃效果。2015年唐曉東[12]采用柵格方法建立原始數字地圖，并用雙線性的插值方法對原始數字高程數據進行插值處理，把各類威脅等效為山峰模型，然后將原始數字高程數據與威脅處理后的數據進行融合，這種方法能更有效地得到航跡規劃高程圖。

Bagherian等[13]在使用進化算法的三維無人機軌跡規劃中，采用數字地形模型DTM和地理信息系統GIS生成敵方位置信息，并在三維環境中顯示。這種方法可以通過推導無人機的運動方程對問題進行建模。Liang等[14]為解決惡劣環境中的避障和安全飛行問題，采用了基于數字高程圖(DEM)的導航模型，設計改進的A*算法獲取初始路徑，并結合了Bresenham畫線算法畫出初始路徑，最后使用Bezier曲線將路徑變平滑。這種與DEM結合的路徑規劃算法，隨著DEM分辨率的提高，規劃精度也更高。

3.2 威脅及代價建模

無人機威脅建模主要包括惡劣氣候、地形障礙以及敵方武器等。為了得到期望航線并保證無人機安全，很多學者都對各種威脅及代價進行了建模，通過機載傳感器獲取各類威脅信息，以采取有效措施進行規避。Anderson等[15]根據性能數據對飛機威脅進行建模，采用參數識別或多維曲線擬合來簡化模型的參數，直到建模威脅的性能與實際威脅的性能匹配，很大程度上減少了開發新的威脅模型所需的時間。Roberge等[16]通過將多個圓柱體并置來創建復雜區域，把危險區域輸入為一系列圓柱形狀，并仍用二維矩陣表示。李春華等[17]針對動態環境中預先未知威脅的情況，采用實時三維航跡規劃方法稀疏D*搜索SDS算法，當檢測到威脅時立即進行局部路徑重新規劃，有效地回避了各種突發威脅。張煜等[18]采用概率表示的方法對各種威脅進行建模，生成概率威脅地圖，很容易地得出無人機沿某航段飛行所受的威脅概率。溫乃峰[19]針對在線搜索提出直覺模糊集靜態威脅區建模和動態威脅可達集估計的方法，可靠地評估了無人機所受的威脅，提高了航跡搜索速度并降低了航跡代價。

3.3 航跡規劃算法

航跡規劃算法是航跡規劃的核心，傳統的航跡規劃算法包括單純形法、匈牙利算法、人工勢場法、A*算法等，然而鑒于航跡規劃問題通常呈現出高維、非線性、離散連續變量混合、多目標等特性，傳統算法很難有效應對。近些年，國內外學者結合計算智能方法，如遺傳算法、蟻群算法和粒子群算法，提出了很多先進有效的航跡規劃算法。本節重點介紹幾類典型的航跡規劃算法。

3.3.1 A*算法

A*算法是一種基于柵格的智能啟發式搜索算法，它將搜索空間表示為網格的形式，以網格的中心點或頂點作為航跡點，通過搜索鄰域內代價函數值最小的航跡點，從起始點逐步搜索到目標點，最后逆向回溯當前節點的父節點生成最優航跡，其中已被計算但待擴展的航跡節點存放在OPEN表中，已擴展的節點存放在CLOSE表中[20]。代價函數的表達式為

f(x)=g(x)+h(x)。

(1)

式中：g(x)表示從起始點到當前節點的實際代價；h(x)為啟發函數，表示從當前節點到目標點的估算。

2000年，Szczerba等[21]提出的稀疏A*算法(sparse A* search，SAS)，是一種改進的A*算法，該算法結合航跡的約束條件，裁剪搜索空間的多余節點，縮短了搜索時間。Zammit等[22]提出一種A*紋波減少算法，衰減了因分辨率變化使路徑長度產生的波紋效應，并通過對平滑算法的改進，縮短了路徑長度。曹棟等[23]提出一種對規劃點前后段航跡評估進行加權的改進A*算法，在航跡優化效果和計算時間之間得到平衡，提高了算法計算效率，又對OPEN表中插入刪除節點的方式進行改進，采用雙向OPEN鏈表的方法，不僅節省了計算時間，還提升了效率。劉群芳[24]使用改進型稀疏A*算法進行優化，在稀疏A*算法的基礎上提取路徑特征點后，再進行二次優化，通過稀疏A*算法和進化算法的結合對無人機靜態航跡規劃進行了設計，有效解決稀疏A*算法的繞徑問題，規劃出了具有較小航跡長度代價的航跡。李軍華等[25]為了解決不確定環境下稀疏A*算法的繞徑問題，提出改進稀疏A*算法與文化算法相結合的混合算法實現路徑修徑，首先采用改進稀疏A*算法剔除冗余特征點得到最優路徑的特征點，然后采用進化算法對這些特征點進行進化，并將得到的最優個體定期傳遞給“信仰空間”，以進一步指導群體進化，該混合算法最大限度地優化了航跡。

3.3.2 遺傳算法

遺傳算法(genetic algorithm, GA)是1975年美國計算機專家John Holland教授根據達爾文進化論中的“適者生存，優勝劣汰”的理論提出的。該算法是一種基于自然生物進化的隨機全局搜索算法，利用編碼技術將某個問題的設計變量用稱作染色體的數據串進行表示，其優點是具有適應性、全局優化性和隱含并行性，全局搜索能力非常強，缺點是收斂速度慢、容易過早陷入局部最優等，因此出現了很多對基本遺傳算法的改進方法。

Dai等[26]在用遺傳算法對無人機進行路徑規劃前，為感知幾何復雜目標區域，提出了一種新的無人機覆蓋和路徑規劃方案，采用基于遮擋感知的道路點生成算法得到了良好的時空分辨率，并設計最小化最大能量路徑規劃算法解決飛行器路徑問題。結果表明，該方法具有更好的覆蓋和更低的能耗。Arantes等[27]將啟發式算法和遺傳算法應用于緊急迫降的無人機路徑規劃問題中，使用遺傳算法在合理的計算時間內得到更全質量的解決方案。Yan等[28]提出了一種基于遺傳算法和Dubins曲線的固定翼無人機路徑規劃算法，采用新的編碼方案將遺傳算法用于二維環境中生成最短的威脅規避路徑，并通過添加路徑角度將2D Dubins路徑轉換為Dubins路徑，最終在復雜三維環境下生成最短的威脅規避路徑。呂文鵬等[29]為了解決基本遺傳算法易過早局部收斂的問題并提高局部搜索能力，在無人機災情巡查路徑優化中引入多生境遺傳算法，在適應值共享基礎上，將排擠機制、間隔交叉兩種方法分別引入選擇和交叉算子中，并在種群中使用最相似個體中適應度最差的個體替換技術，提高了搜索種群的多樣性，很大程度地避免了早熟問題。

3.3.3 蟻群算法

1996年Dorigo等[30]提出的蟻群算法(ACO)是一種用來在圖中尋找優化路徑的概率型技術，其靈感來源于螞蟻在尋找食物過程中發現路徑的行為，該方法具有正反饋、分布式計算和富于建設性的貪婪啟發式搜索的特點。為了提高無人機作戰任務的成功率，Dorigo等[30]提出了基于改進蟻群算法的適用于航跡規劃的優化方法，該方法可以保證無人機以最小的被發現概率及可接受的航程到達目標點，保留算法的最優解、自適應狀態轉換規則和信息激素更新規則，能夠有效提高算法收斂速度、搜索效率以及解的性能。

Konatowski等[31]采用蟻群算法與解決TSP(旅行商)問題類似的工作原理，很大程度上簡化了對優化問題的表述，在各種任務參數中規劃了無人機的路徑。Daryanavard等[32]在地理區域無線物聯網節點數據收集的無人機路徑規劃問題中，為找到傳感器之間的最短路徑，采用了蟻群算法和模擬退火算法兩種優化方法進行三維建模對比，在傳感器數量比較多的情況下，蟻群算法有更好的性能。王芳[33]在蟻群算法中融合了量子計算的量子特性，通過量子旋轉門策略與最優路徑的結合實現信息素的更新規則，不但延續了蟻群算法正反饋、易于分布式計算以及高魯棒性等優點，而且繼承了量子計算的并行性等高效機制，使算法的收斂效果更好，全局尋找最優解的能力也大大加強。劉蓉等[34]將混沌優化理論應用在蟻群算法的初始化階段來設置初始信息素值，采用變尺度調節系數，先大范圍粗略搜索，后逐步縮小范圍，然后引入混沌擾動的信息素更新策略，使算法在解的雙側鄰域內進行搜索，并對通過尋優得到的航路進行全局信息素更新，最終有效克服了局部最優的缺點，提高了搜索效率。

3.3.4 粒子群算法

1995年Kennedy等[35]提出的粒子群優化(particle swarm optimization, PSO)算法是一種新的進化優化算法，算法的運行機理是對生物群體的社會行為進行模擬，利用群智能建立簡化的模型，最早啟發于對鳥類搜尋食物行為的研究，同時，利用信息共享機制，使生物群體中的個體之間、個體與群體之間相互作用、相互影響，以促進整個群體的發展。

Patley等[36]采用正交設計的方法對粒子群算法進行改進，通過最小化預定目標函數來確定無人機在每個時間步長的最優位置，在獲取3D航路點時使用傾斜平面策略并制定航路點排序策略，為每個無人機規劃出最佳路徑，同時又縮短了收斂時間。Vijayakumari等[37]采用滾動優化的PSO算法實現了基于感知與回避的碰撞避免，用動態約束和分散控制計算最佳控制輸入，為多個無人機規劃出了最優軌跡，這種方法是十分有效的防撞方法。宋宇等[38]采用模糊C均值算法與粒子群算法相結合的方法，通過調用模糊C均值算法得到停止分類后的隸屬度矩陣，然后用輪盤賭算法確定粒子所屬類別并進行下一步改進，使算法的全局尋優能力增強，尋優精度提高。Li等[39]在對多農用無人機飛行路線進行規劃時，采用了可變鄰域下降的增強型遺傳粒子群優化算法，以最小的制造跨度優化了整個無人機組的飛行路徑，該算法在離散PSO的基礎上，結合GA算法對粒子位置進行了更新，有效地縮短了無人機群的飛行時間。梁靜等[40]克服靜態約束機制參數不好設置的缺陷，采用結合交叉策略和動態約束的動態多組群粒子群優化算法對路徑進行優化，不僅找到有安全距離的路徑并避免陷入局部最優。

3.4 航跡平滑處理

航跡平滑是無人機航跡規劃的最后階段，即對無人機航跡進行平滑處理，使無人機與威脅源保持一定距離并且滿足可飛要求。初步規劃的航跡往往具有一定的角度，由許多最短直線首尾連接而成，而無人機受飛行性能約束，轉角有限不可能全都達到，因此需要對這些尖角進行平滑處理，使無人機沿滿足飛行性能約束的曲線航跡飛到終點。目前航跡平滑研究方法有圓弧段串聯法、地形光滑法、力平衡法、平滑算子法、濾波法、B樣條曲線法和Dubins path法等[41]。而比較實用有效的一種航跡平滑算法是B樣條曲線法，該算法不僅能對某個航跡段進行局部平滑，更能進行整體全局的平滑，平滑后的航跡在轉折點前后曲率變化不大，能較好解決轉折點處大角度控制的問題，因此所獲得的航跡整體過渡自然，能滿足無人機的機動性能約束，并且局部控制能力較強，不會出現突發反復轉向操作。考慮到計算的復雜度及實際飛行效果，一般只要曲線曲率不小于無人機最小轉彎半徑，選擇2次或3次B樣條曲線進行平滑即可，更高次的沒有太大實際意義。

Foo等[42]結合B樣條曲線法和粒子群算法對無人機進行路徑規劃，其中將生成的備用路徑用B樣條曲線表示，最大限度地減少了計算量，并且將B樣條曲線限制為3次，確保了生成的曲線盡量靠近控制點。Bai等[43]提出改進的人工勢場方法對多UAV編隊路徑進行規劃，其中引入了B樣條插值方法對所規劃的路徑進行平滑處理，插補后的曲線路徑更短更平滑，并且性能穩定、具有最小的均值誤差。趙明[44]提出3次B樣條曲線和反求控制點的3次B樣條曲線相結合的方法，當關鍵路徑點與最近威脅中心的距離較大時，采用3次B樣條曲線法，得到比較平滑的航跡；距離較小時，采用反求控制點的B樣條曲線法擬合，避免航跡接近威脅區。段彩萍等[45]在存在威脅的二維飛行環境中，采用3次非均勻B樣條曲線插補的航跡平滑方法，對用蟻群算法所得到的航跡進行平滑處理，獲得了較好的平滑效果。

4 存在的問題

盡管目前針對無人機航跡規劃的研究已經取得了豐富的成果，然而，從實際使用需求出發，當前的研究還存在一定的不足，具體表現在如下幾個方面。

(1)無人機規劃模型構建方面：①二維模型多，三維模型少。無人機所處的真實環境是三維空間環境，為了模擬更真實的環境需要規劃三維空間模型進行仿真，二維模型在平面上進行模擬，所建立的模型并不能反映真實的情況。②空氣動力學考慮較少。對無人機動力學的約束考慮較少也較簡單，造成所規劃的路徑實際并不可飛。③在線航跡規劃模型的設計較少。大多數模型都是離線的，將威脅和障礙物簡化為幾何靜態模型，使無人機按已經規劃好的航跡飛行。而在線實時航跡規劃中，環境數據會不斷發生變化。④較少考慮規劃過程中出現的不確定性因素。實際環境中不確定因素很多，一旦遇到突發情況，無人機便難以順利完成任務。

(2)無人機航跡規劃算法方面：①較少進行多重算法的融合。每種算法都有各自的優點，但單一算法多具有局限性，需要融合不同的算法形成混合智能算法，提高算法的適用性和尋優效率。②針對在線航跡規劃算法的研究較少。在線航跡規劃過程中當無人機獲取到變化信息時需要對航跡進行局部調整，研究在線航跡規劃算法能夠提高無人機避碰避障的能力。③較少考慮針對不確定性環境下的規劃算法研究。不確定性規劃模型較少，導致不確定性環境下的規劃算法研究偏少。靜態環境的算法用在不確定環境中時，算法復雜度增大、性能差，因此需要對不確定性環境下的規劃算法進行研究。

5 展望

隨著對無人機航跡規劃研究的深入，航跡規劃的各種技術更加完善，成果也越來越多，但不確定環境下的研究和多機協同的研究還在發展階段。從目前的研究動向來看，無人機航跡規劃有以下發展趨勢：①提高航跡規劃的性能指標要求。航跡規劃中對可達性、安全性和實時性等性能指標要求越來越高，無人機在動態的、不確定環境中飛行，環境信息瞬息萬變，實時性差將會增加避碰避障的失敗率。并且提高可達性、安全性可以保證無人機安全順利到達目的地。②高效在線航跡規劃算法的研究。可以使無人機在動態環境中邊規劃邊飛行，遇到突發狀況時能夠更好完成局部路徑調整。③多無人機協同航跡規劃。隨著任務要求越來越復雜，單個無人機很難完成規定任務，這就需要多個無人機之間進行協同工作，形成無人機網，協作完成任務。目前已經出現一些多無人機協同航跡規劃的研究，但遠遠不夠，需要繼續研究多無人機的在線協同航跡規劃。

6 結束語

在無人機航跡規劃技術的研究中，已知環境下的靜態航跡規劃技術研究已經相對成熟，研究技術被廣泛應用。然而，與此同時暴露出了一些新的問題，需要通過進一步的研究來解決，其中主要的問題是在不確定的、充滿未知威脅信息的環境中對無人機航跡進行在線調整，規劃時的實時性、精確性要求給規劃方法及規劃結果帶來挑戰。另外，目前的研究較少考慮動力學約束，對無人機自身狀態等約束不能更好處理，所以航跡規劃技術還需要不斷地完善。

參考文獻：

[1] RAMCHURN S D, FISCHER J E,IKUNO Y, et al. A study of human-agent collaboration for multi-UAV task allocation in dynamic environments[C]// Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Buenos Aires, Argentina: IJCAI, 2015: 1184-1192.

[2] RUZ J J,AREVALO O,DE LA CRUZ J M,et al.Using MILP for UAVs trajectory optimization under radar detection risk[C]//2006 IEEE Conference on Emerging Technologies and Factory Automation. Piscataway: IEEE, 2006:957-960.

[3] SHIRI H,PARK J,BENNIS M. Massive autonomous UAV path planning:a neural network based mean-field game theoretic approach[C]//2019 IEEE Global Communications Conference (GLOBECOM). Piscataway: IEEE, 2019:1-6.

[4] HOTA S,GHOSE D.Waypoint-based trajectory planning of fixed-wing MAVs in 3D space[J].Journal of intelligent & robotic systems,2017,86(1):95-113.

[5] 張佳龍,閆建國,張普,等.基于改進人工勢場的無人機編隊避障控制研究[J].西安交通大學學報,2018,52(11):112-119.

[6] LUO G C,YU J Q,MEI Y S,et al.UAV path planning in mixed-obstacle environment via artificial potential field method improved by additional control force[J].Asian journal of control,2015,17(5):1600-1610.

[7] ZHANG Z X,WU Q H,ZHANG B,et al.UAV flight strategy algorithm based on dynamic programming[J].Journal of systems engineering and electronics,2018,29(6):1293-1299.

[8] 楊健,董力勇,王鴻,等.應用分層優化法的多協作無人機任務規劃方法[J].指揮與控制學報,2019,5(1):41-46.

[9] 胡中華,趙敏,姚敏,等.無人機航跡規劃技術研究及發展趨勢[J].航空電子技術,2009,40(2):24-29,36.

[10] 趙杰.數字地形模擬-地形數據獲取與數字地形分析研究[D].武漢:武漢大學,2004.

[11] 巴海濤.無人機航跡規劃研究[D].西安:西北工業大學,2006.

[12] 唐曉東.基于A*算法的無人機航跡規劃技術的研究與應用[D].綿陽:西南科技大學,2015.

[13] BAGHERIAN M,ALOS A.3D UAV trajectory planning using evolutionary algorithms: a comparison study[J]. The aeronautical journal, 2015,119(1220):1271-1285.

[14] LIANG H J, BAI H Y, SUN R, et al. Three-dimensional path planning based on DEM[C]//2017 36th Chinese Control Conference (CCC). Piscataway: IEEE,2017:5980-5987.

[15] ANDERSON M, SCHAB D. Aircraft threat modeling from performance data[C]//Flight Simulation and Technologies. Reston, USA: AIAA, 1993:3553.

[16] ROBERGE V,TARBOUCHI M,LAB ONTé G.Fast genetic algorithm path planner for fixed-wing military UAV using GPU[J].IEEE transactions on aerospace and electronic systems,2018,54(5):2105-2117.

[17] 李春華,周成平,丁明躍,等.動態環境中的飛行器實時三維航跡規劃方法研究[J].宇航學報,2003,24(1):38-42,70.

[18] 張煜,陳璟,沈林成.基于概率地圖的軍用飛行器航跡規劃方法研究[J].計算機仿真,2007(9):62-66.

[19] 溫乃峰.低空復雜環境下小型無人機的在線航跡規劃算法研究[D].哈爾濱:哈爾濱工業大學,2016.

[20] 王瓊,劉美萬,任偉建,等.無人機航跡規劃常用算法綜述[J].吉林大學學報(信息科學版),2019,37(1):58-67.

[21] SZCZERBA R J, GALKOWSKI P, GLICKTEIN I S, et al. Robust algorithm for real-time route planning[J].IEEE transactions on aerospace and electronic systems,2000,36(3):869-878.

[22] ZAMMIT C,VAN KAMPEN E J. Advancements for A* and RRT in 3D path planning of UAVs[C]//AIAA Scitech 2019 Forum. Reston, USA: AIAA, 2019:1-17.

[23] 曹棟,王瑞,曹越.基于A*算法的無人機攻擊編隊航跡規劃[J].沈陽航空航天大學學報,2016,33(4):61-65.

[24] 劉群芳.基于稀疏A*算法與進化算法的無人機動態航跡規劃研究[D].南昌:南昌航空大學,2016.

[25] 李軍華,劉群芳.基于稀疏A*算法與文化算法的無人機動態航跡規劃[J].應用科學學報,2017,35(1):128-138.

[26] DAI R,FOTEDAR S,RADMANESH M,et al.Quality-aware UAV coverage and path planning in geometrically complex environments[J].Ad hoc networks,2018,73:95-105.

[27] ARANTES J D S, ARANTES M D S, TOLEDO C F M, et al. Heuristic and genetic algorithm approaches for UAV path planning under critical situation[J]. International journal on artificial intelligence tools,2017,26(1):1760008.

[28] YAN P, YAN Z, ZHENG H X, et al. A fixed wing UAV path planning algorithm based on genetic algorithm and dubins curve theory[C]//2018 2nd International Conference on Mechanical, Material and Aerospace Engineering. Wuhan, China: MATEC Web of Conferences, 2018:3003.

[29] 呂文鵬,許峰.基于多生境遺傳算法的無人機航跡規劃[J].軟件導刊,2018,17(7):166-168.

[30] DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE transactions on systems, man, and cybernetics, part B (cybernetics), 1996,26(1):29-41.

[31] KONATOWSKI S,PAWOWSKI P. Ant colony optimization algorithm for UAV path planning[C]//2018 14th International Conference on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET). Piscataway: IEEE,2018:177-182.

[32] DARYANAVARD H,HARIFI A.UAV path planning for data gathering of IoT nodes:ant colony or simulated annealing optimization[C]//2019 3rd International Conference on Internet of Things and Applications (IoT).Piscataway：IEEE,2019:1-4.

[33] 王芳.基于量子蟻群算法的多無人機協同航跡規劃研究[D].哈爾濱:哈爾濱工業大學,2015.

[34] 劉蓉,楊帆,張衡.基于改進混沌蟻群算法的無人機航路規劃[J].指揮信息系統與技術,2018,9(6):41-48.

[35] KENNEDY J,EBERHART R.Particle swarm optimization[C]//Proceedings of ICNN′95-International Conference on Neural Networks. Perth, Australia: IEEE,1995:1942-1948.

[36] PATLEY A,BHATT A,MAITY A,et al.Modified particle swarm optimization based path planning for multi-UAV formation[C]//AIAA Scitech 2019 Forum.Reston,USA:AIAA,2019:1167.

[37] VIJAYAKUMARI D M,KIM S,SUK J, et al. Receding-horizon trajectory planning for multiple UAVs using particle swarm optimization[C]//AIAA Scitech 2019 Forum. Reston, USA: AIAA,2019:1165.

[38] 宋宇,王志明. 面向無人機三維航跡規劃的改進粒子群優化算法[J].傳感器與微系統,2019,38(3):144-146.

[39] LI X H,ZHAO Y,ZHANG J,et al.A hybrid PSO algorithm based flight path optimization for multiple agricultural UAVs[C]//2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI).Piscataway:IEEE, 2016:691-697.

[40] 梁靜,宋慧,瞿博陽,等.基于改進粒子群算法的路徑優化問題研究[J].鄭州大學學報(工學版),2014,35(1):34-38.

[41] 田疆.無人機三維約束多目標航跡規劃[D].蘭州:蘭州理工大學,2018.

[42] FOO J L, KNUTZON J, KALIVARAPU V, et al. Path planning of unmanned aerial vehicles using B-splines and particle swarm optimization[J].Journal of aerospace computing, information, and communication, 2009, 6(4): 271-290.

[43] BAI W B,WU X D,XIE Y E,et al.A cooperative route planning method for multi-UAVs based-on the fusion of artificial potential field and B-spline interpolation[C]//2018 37th Chinese Control Conference (CCC).Piscataway:IEEE,2018:6733-6738.

[44] 趙明.多無人機系統的協同目標分配和航跡規劃方法研究[D].哈爾濱:哈爾濱工業大學,2016.

[45] 段彩萍,劉超,王琪. B樣條理論在無人機航跡平滑中的應用[J]. 無線互聯科技, 2018, 15(3): 141-144.

A Survey of UAV Path Planning

FAN Jiao1, LEI Tao1, HAN Wei2, WANG Rui3

(1.School of Electronic Information and Artificial Intelligence, Shaanxi University of Science and Technology, Xi′an 710021, China; 2.Information School, Qingdao Hengxing University of Science and Technology, Qingdao 266100, China; 3.College of Systems Engineering, National University of Defense Science and Technology, Changsha 410073, China)

Abstract: Path planning is one of the key technologies of UAV autonomous flight. The typical path planning can be divided into three steps: firstly, the preliminary planning of flight path should be carried out by fully considering various threat environments; secondly, the optimal path should be found by using the optimization search algorithm; finally, the path should be smoothed. This paper systematically summarizes the studies of UAV path planning in recent years; analyzes the flight airspace, dynamic constraints and environmental constraints in the process of path planning; expounds the key technologies involved in path planning, including terrain acquisition, threat and cost modeling, path planning algorithm and path smoothing; and further analyzes and summarizes the common path planning algorithms, such as A* search algorithm, genetic algorithm, ant colony algorithm, particle swarm optimization algorithm, and the common path smoothing algorithm B-spline curve method; and summarizes the problems of the current UAV path planning model construction and path planning search algorithm. Finally, some potential future development trends of UAV path planning are proposed, including the construction of reasonable path planning system, the study of advanced online path planning algorithm, and the cooperative path planning of multi-UAV.

Key words: UAV; path planning; optimization algorithm; survey

收稿日期:2020-08-10；修訂日期：2020-10-23

基金項目：國家自然科學基金資助項目(61773390)；湖南省“湖湘青年英才”支持計劃(2018RS3081)

通信作者：王銳(1986— )，男，陜西延安人，國防科技大學副研究員，博士，主要從事智能優化理論方法及其應用研究，E-mail:ruiwangnudt@gmail.com。

文章編號:1671-6833(2021)03-0039-08

中圖分類號：TP18;V279

文獻標志碼：A

doi:10.13705/j.issn.1671-6833.2021.03.007