無人機航跡規劃算法研究進展

摘 要：目前，無人機技術的發展已取得了明顯的突破，無人機的應用領域從軍事擴展到了商業、科研、娛樂等多個領域。文章以無人機航跡規劃算法為研究對象，首先，根據航跡規劃算法的原理與特點，將其分為全局規劃算法和局部規劃算法兩大類，其中全局規劃算法又可分為圖搜索算法和智能仿生算法。其次，對算法的原理、工作流程、優缺點進行了深入分析，并介紹了相應的改進方法，結合算法自身特點闡述其在相應領域的應用；最后，探討上述算法在實際應用中的限制與挑戰，并對未來航跡規劃技術的發展趨勢進行了展望，為無人機航跡規劃算法的研究指出了方向。

關鍵詞：無人機；航跡規劃；全局規劃算法；局部規劃算法；圖搜索算法；智能仿生算法

中圖分類號：TP301；V279 文獻標識碼：A 文章編號：2096-4706（2024）17-0049-07

0 引 言

無人機航跡規劃的優劣決定著無人機是否能實現自主飛行，并獨立完成任務。航跡規劃的本質是在滿足任務要求的前提下尋找從起始點到目標點的最優航跡。在緝毒偵察、軍事行動[1-2]等領域中，飛手操作無人機只能進行一些簡單的避障操作，利用無人機進行動態瞄準等高難度操作則難以實現，若無人機可以實現自主飛行，將能夠改善無人機在任務執行時遇到的一系列問題，同時還可節省人力資源。在滿足任務需求的前提下，使得效率最大化的同時，將損耗降到最低，這其中飛行時間和距離往往被考慮為航跡優化過程中的關鍵因素，避免碰撞是該過程需要解決的關鍵問題。航跡規劃算法的研究起源于復雜科學問題的求解，逐漸發展成為一門交叉科學，涵蓋了計算機科學、人工智能、運籌學、控制理論等多個領域。隨著計算能力和算法理論的發展，無人機航跡規劃算法從最初的格點法、人工勢場法到后來的啟發式與進化算法，計算效率與航跡質量都得到了質的提升。本文對常見的航跡規劃算法進行分類，探討其基本原理、實現方式以及優缺點，最后對該領域的研究狀態、挑戰和未來趨勢進行了探討。

1 無人機航跡規劃算法分類

算法是航跡規劃的核心，目前有諸多方法對無人機航跡規劃算法進行分類，其中最常見的是基于對環境信息的掌握程度進行的分類，分別為全局航跡規劃算法與局部航跡規劃算法。全局航跡規劃算法需要掌握并根據環境地圖的所有信息進行航跡規劃，這將導致不能應對出現在環境中的未知障礙物；而局部航跡規劃算法可以實時采集環境信息，根據已知的環境信息確定出所在位置及障礙物分布情況，從而進行航跡規劃。

全局航跡規劃算法可分為圖搜索算法和智能仿生算法，如圖1所示。圖搜索算法主要包括A*算法、Dijkstra算法、Voronoi圖法、JPS算法、RRT算法，智能仿生算法主要有粒子群算法、蟻群算法、人工蜂群算法。局部航跡規劃算法主要包含人工勢場法和動態窗口法。

2 圖搜索算法

圖搜索算法是一種基于圖數據結構搜索航跡的算法。其基本思想是從某個節點出發，沿著邊連接的其他節點，最后到達目標節點，節點表示在空間中的位置，邊則代表位置之間的連接通路。在無人機航跡規劃中，無人機所處的環境可以被建模為一個圖形，圖中的節點是無人機可能出現的飛行位置，邊則代表無人機可以飛行的航跡，圖搜索算法可以有效地找出從起點到終點的最優航跡。

Dijkstra算法不使用任何啟發式信息，只是簡單的探索所有航跡直到找到目標點，因此只適用于環境相對簡單的場景。A*算法將Dijkstra算法確保最短航跡的特點與貪心算法的高效搜索相結合，通過啟發式函數優化航跡，使得無人機能在復雜環境中快速找到目標點。Voronoi圖法通過對空間的有效分割，為無人機提供了避免障礙物和處理開放空間的能力，這對于城市和崎嶇地形的飛行尤為重要。JPS算法作為A*的一種優化，通過跳過不必要的節點來加快網格地圖中的搜索速度，提高了在標準化環境中的航跡規劃效率。而RRT算法以其隨機化的探索方式，特別適合于復雜和動態變化的飛行環境，如林區或急劇變化的城市景觀。

將這些算法綜合應用于無人機航跡規劃，可以實現一種既靈活又高效的航跡規劃策略，能夠在確保安全和效率的同時，優化航跡并縮短飛行時間。本章將著重介紹目前應用較多的A*算法和RRT算法。

2.1 A*算法

A*算法是1968年由Hart[3]提出的一種啟發式搜索算法，常用于計算兩點之間的最短航跡。該算法在搜索過程中引入了啟發式函數，即預估從當前節點至目標節點的最小代價。通過這種方式，在搜索范圍較大的情況下A*算法仍能保持較高的搜索效率。其基本原理是每次從待搜索的節點中選擇一個“最有希望”（即預計總代價最小）的節點進行搜索，直到找到目標為止。這種算法的特點是它可以找到一條最短航跡（前提是啟發式函數不大于實際代價）。

A*算法是一種很有效的尋路算法，它能保證在有解的情況下一定能找到最優解，為了進一步提高航跡搜索的方向性和減少無效探索，Chen等[4]通過比較當前節點到目標節點的航跡與最優直線航跡之間的角度，來判斷節點是否有利于朝目標方向前進。并有針對性地設計了

新的評估函數H1（n）=H（n）-wcosθ，其中H（n）為以往的評估函數，w為一個權重參數。這個新評估函數減少了對無用節點的探索，提高了運行效率和航跡質量。

針對傳統A*算法在無人機航跡規劃中效率低下、航跡點過多且航跡轉折頻繁的問題，唐嘉寧等[5]引入了雙向搜索機制，分別以起點和終點為對向搜索的起點，基于起點和終點所處的象限進行雙向定向搜索，通過雙向搜索獲得的初始航跡進行平滑處理，以減少冗余航跡點和轉折點。Zhang等[6]在此基礎上提出了一種雙向多層A*搜索方法，以提高搜索三維空間的效率。這種方法通過在起點和目的地之間同時進行正反向的搜索，并在兩個OPEN列表的軌跡點相遇時停止搜索。通過在特定角度扇區內進行多層可變步長搜索的策略，以進一步提高搜索效率，并在雷達威脅較大時調整搜索步長，在保證了航跡全局優化的同時，確保了航跡的安全性。

2.2 RRT算法

RRT（快速隨機探索樹）算法是由LaValle[7]提出的一種航跡規劃算法。該算法在無人機航跡規劃中主要用于在未知環境中尋找從起點到終點的最優航跡，該算法適用于包含障礙物和差分運動約束的場景。然而，由于其搜索過程中的隨機性，生成的航跡可能并非最優，而且可能存在大量冗余航點。針對這一問題，研究人員提出了例如調整步長或者結合啟發式步長調整策略對初步生成的航跡進行修剪處理，以縮短航跡長度等多種改進策略來優化RRT算法。

顧子侶等[8]在隨機樹待擴展節點的選取上引入目標啟發信息，在新節點生成和添加過程中融入無人機動力學約束，在確保生成航路符合實際飛行的可行性的基礎上，針對突發威脅情況，提出一種動態擴展隨機樹方法，該方法可以對原有隨機樹進行剪枝和重構，以快速避開威脅并生成一條安全航路。

為了能讓算法在有障礙物的環境中更高效地進行航跡規劃，俞宬等[9]提出一種基于向量場直方圖算法啟發的改進B-RRT*無人機往返航跡規劃算法。采用直角直方圖網格對工作空間中的障礙進行統計表示，引入目標扇區和可通行扇區的概念，使用成本函數來引導無人機的運動，最后提出了一個航跡修剪操作，通過碰撞檢測來剔除無效節點，并進一步修剪航路點，以得到一條更優的航跡路線。

3 智能仿生算法

智能仿生算法是一種模擬自然界生物行為和思維規律的優化算法，其運行原理主要基于神經網絡規劃、模糊邏輯規劃以及基于仿生的行為模型。智能仿生算法可以在短時間內對復雜的連續問題和離散的非確定性多項式問題（Nondeterministic Polynomially， NP）組合優化找到可行的解決方案。智能仿生算法常具有以下共同特點：操作都是在每一代的個體上進行的；搜索是基于迭代進化的；多種群方案的并行執行是一種簡便方法；這些方案通常能找到比較接近最佳的較優解；但由于迭代過程具有一定的隨機性，無法保證每次得到完全相同的解。可以通過統一抽象問題變量，使用適應度函數來表示目標，隨后利用每次迭代操作和進化來修改解空間中的種群。該算法主要基于種群迭代模式，通過操作每一代中的個體，獲取解決方案空間中的有益信息，并逐步找到更優的位置。在無人機航跡規劃中，智能仿生算法能夠為無人機快速找到一組具備適應性和良好魯棒性的可行解。

3.1 粒子群算法

粒子群優化（Particle Swarm Optimization， PSO）是一種通過模擬鳥群覓食行為來進行全局優化的方法，由Kennedy等[10]于1995年首次提出。粒子群算法是一種用于解決連續空間優化問題的啟發式算法，并且可以輕易地擴展到解決離散空間的優化問題。PSO算法的基本思想是：在搜索空間中隨機生成一群粒子，每個粒子都有一個“個體最優解”（pBest）記錄自己歷史上的最佳位置，同時群體中的所有粒子共同分享一個“全局最優解”（gBest）記錄整個群體歷史上的最佳位置，在每一次迭代中，粒子會根據個體最優解和全局最優解來更新自己的速度和位置，如圖2所示。PSO算法的優勢在于它的簡單性和易于實現，同時它也已經被成功應用于許多優化問題中。然而，PSO算法也有其局限性，例如可能會陷入局部最優解，或者在高維復雜的搜索空間中收斂速度較慢等。

李銳君等[11]將細菌覓食算法的趨向算子和遷徙算子結合至基礎粒子群算法中，趨向算子有效提高了算法的局部搜索性能，解決了因粒子速度過快而錯過最優解的問題。遷徙算子則擴大了尋優范圍，并有助于避免算法陷入局部最優解。

吳鈞皓等[12]提出了一個新的多無人機航跡規劃問題（MUAVPP）的數學模型，設計了帶交叉策略的粒子群算法（PSO-X）以解決此問題。將粒子群分為優勢子群和普通子群，由此提高了粒子群對全局和局部的搜索能力。優勢子群通過加入一種交叉策略進行更新，普通子群則使用樣例學習策略進行更新并開發了一套編解碼策略，使得算法能夠有效地處理無人機航跡規劃的決策變量，考慮到MUAVPP中存在續航約束，在適應度函數中加入懲罰系數，可以處理不可行解的同時引導算法向可行解收斂，確保算法能夠更快找到可行解。

針對復雜和危險環境下的無人機航跡規劃，智瀚宇等[13]提出了一種基于粒子群優化（PSO）算法和灰狼優化（GWO）算法的復合算法，稱為PSO-GWO復合算法。該算法利用了非線性控制參數和加權自適應的個體位置更新策略來加快算法的收斂速度和提高算法解的最優性；采用隨機指導策略來增加算法解的多樣性，以此來提高算法的全局搜索能力，有助于避免陷入局部最優解。此外，使用了B樣條曲線來平滑航跡，使得其更符合無人機的飛行姿態，進一步節省無人機的耗能。

3.2 蟻群算法

蟻群算法是一種模擬自然界蟻群覓食行為的計算機算法，由Dorigo[14]等人于20世紀90年代初提出。這種算法主要應用于求解組合優化問題。在搜尋食物時，螞蟻會在其走過的道路上釋放一種被稱作信息素的標記物質，并依據這種物質的濃度來決定其移動的方向。螞蟻傾向于向信息素濃度較高的地方移動，當大量螞蟻一起尋找食物時，它們的行為就能產生一種正向的信息素反饋機制。螞蟻覓食的運行軌跡模式如圖3所示。

除以上通過螞蟻利用信息素進行相互通信之外，常見的人工螞蟻搜索還會建立禁忌表，即一只螞蟻搜索過的航跡在下次搜索時就不再被該螞蟻選擇，并通過螞蟻的集群活動使得算法更加智能化。通過這種方式，蟻群能夠在一定程度上找到問題的最優解或者近似最優解。蟻群算法為解決處理復雜的組合優化問題提供了新的思路，并且由于蟻群算法的求解結果不依賴于初始路線的選擇，而且在搜索過程中不需要進行人工調整，因此蟻群算法具有較強的魯棒性。對于大規模問題，即使每只螞蟻的探索過程相對獨立，僅通過信息素交流，可以在問題空間的多個地點同時開始獨立搜索，但是在大規模問題下算法的計算效率仍會無法滿足實際需求，且常會陷入局部最優解。因此，在實際應用中通常需要引進新的改進策略來優化蟻群算法。

針對基本蟻群算法在解決TSP時遇到的停滯和早熟問題，趙鑫等[15]提出了一種帶有遺忘因子的蟻群優化算法（FFACO）。通過在人工螞蟻中加入遺忘因子，建立了一個新的狀態轉移公式，并修改了信息素更新策略。通過新的狀態轉移公式與當前解的誤差率組合調整了對應的狀態轉移方程，以期降低最優值的誤差和其追蹤能力。修改后的航跡模型可以計算每條航跡到當前最優解的概率，此種算法優化不僅能縮短耗時，還能提供更好的航跡尋優結果。

于全友等[16]構建了一個帶續航約束的無人機全覆蓋航跡規劃的數學模型，并提出了無人機返航時機判斷機制和返航點計算方法，特別是設計了距離矩陣動態更新機制以處理返航點導致的節點拓撲結構的動態變化問題，并設計了滾動權值加權和信息素更新機制來兼顧全局啟發性和局部啟發性信息，提高了蟻群算法的搜索能力，基于改進蟻群算法優化了有續航約束條件的無人機全覆蓋航跡規劃。

孔維立等[17]引入避障策略并改進了人工勢場法加入到啟發函數中，使得螞蟻在啟發過程中不僅避開障礙物而且受到人工勢場的引導，增強了搜索過程中的方向性。并通過設置信息素揮發因子的動態隨機更新機制，算法在增加局部搜索能力的同時，避免了過早陷入局部最優。并結合了改進人工勢能法進行預搜索的信息素初始化，增加預搜索后螞蟻的局部搜索能力，加快了算法的收斂速度。

3.3 人工蜂群算法

人工蜂群算法（Artificial Bee Colony， ABC）由Karaboga[18]在2005年提出，主要用于解決實值函數優化問題。這個算法主要是模擬蜜蜂覓食過程中的信息交流和搜索行為。在蜜蜂群體中，蜜蜂可以被劃分為三類：工蜂、觀察蜂和偵查蜂。

工蜂負責搜索食物源，隨后返回巢穴，通過舞蹈來傳達搜索到的食物源；觀察蜂在巢穴內部等候，觀察工蜂的舞蹈以獲取食物源信息，并根據這些信息決定去哪個食物源采集食物；當食物源被采集完或者長時間找不到新的食物源時，偵查蜂就會隨機搜索新的食物源。

人工蜂群算法是以自然現象為原理得出的，具有良好的動態響應性。在ABC算法中，食物源對應于問題的解，而食物源的質量則對應于解的優越程度。工蜂和觀察蜂通過搜索和學習食物源（解）來尋找最優解，偵查蜂則通過隨機搜索來保持算法的多樣性，避免算法過早陷入局部最優。ABC算法的主要步驟包括初始化、工蜂階段、觀察蜂階段和偵查蜂階段。在每個階段，蜜蜂會根據預定的搜索策略更新當前的解，并通過貪心選擇規則選擇一個更優的解。

Akay等[19]檢驗了人工蜂群算法（ABC）在無約束大規模基準問題上的性能。研究發現ABC算法在大規模無約束優化問題上優于差分算法（DE）和粒子群優化算法（PSO）。這種優越的性能歸功于ABC算法有效平衡探索和開發過程的能力，因為它使用了貪婪的選擇、概率選擇、隨機選擇這三種不同的選擇算子。

Gao等[20]將多群體技術（Multipopulation Technique）與兩種搜索機制結合到人工蜂群算法（ABC）中。多群體技術通過將整個種群P基于個體的空間位置劃分為多個子群體，從而促進鄰域的利用，而不會損失種群多樣性。這種劃分方式可以使算法將個體分配到不同的子區域，從而在每個子群體中通過ABC生成候選個體。并提出了兩種搜索機制用作雇傭蜂和觀察蜂的搜索方程，來促進每個子群體內部以及不同子群體之間的信息交流，并使得更優個體具有指導搜索方向的潛力。這種改進能使其更好地利用鄰近個體信息，并通過新的搜索方程來獲得更優解。

伍鵬飛等[21]圍繞無人戰斗機（UCAV）的航跡規劃問題展開研究，構建了Zaslavskii混沌序列與蜂群算法相結合的方法，優化了蜜源的選擇和搜索策略，加快了收斂速度，提高了算法的優化精度。

3.4 算法對比

在實際應用中，需要根據無人機的具體任務和實戰環境選擇合適的算法或將多種算法結合起來，不同的算法有著不同的特點，根據以上對全局航跡規劃算法的探討，對于這些算法的總結如表1所示。

4 局部規劃算法

局部規劃算法是指在已知環境中，通過分析當前所處位置的局部信息來進行航跡規劃的方法。局部規劃算法因其較高的適應性，常被用于解決動態環境變化下的避障問題。

人工勢場法是一種常見的局部規劃算法，最早由Khatib[22]在1985提出。它通過構建一個虛擬的力場來引導無人機沿著期望的航跡移動。當無人機接近障礙物時，斥力對其作用使之改變方向，反之，引力的作用會使其向目標點靠近。通過調整斥力和引力的大小和方向，可以使無人機在復雜環境中實現穩定、平滑的航跡規劃，如圖4所示。人工勢場法所具備的實時性好以及計算簡便等特點，使其在簡單障礙物環境下的實時航跡規劃中具有良好的適應性。但易陷入局部極小值，難以處理復雜環境中的航跡規劃，可以選擇引入其他策略或算法產生擾動來逃離局部極小點。

動態窗口法是另一種適用于無人機航跡規劃的局部規劃算法，最早由Fox[23]在1997年提出。它通過將無人機的運動范圍劃分為多個小區域，并為每個區域分配一個權重值，以表示該區域對無人機運動的影響程度。在規劃過程中，無人機會根據當前位置和目標位置選擇具有最大權重的區域作為下一個運動目標。動態窗口法具有較強的適應性和實時性，能夠在不斷變化的環境中為無人機提供合適的移動策略，但搜索空間受到速度空間采樣的限制，可能無法找到最優解，可以通過調整窗口大小、采樣密度或結合其他航跡規劃算法來改善性能。

當目標引力與障礙物斥力大小相等且方向相反時，無人機由于對周圍環境的感知存在局限性，容易在傳統的人工勢場法作用下陷入局部極小點，盧艷軍等[24]提出了“選擇穿越法”以解決此種情況。當無人機飛到一個局部極小點且無法繼續前進時，則激活選擇穿越行為。局部極小點的特點是無人機懸停，且兩邊緊鄰障礙物。此時判斷無人機在航跡規劃上的下一個位置是否能更接近目標點，如果不能，就激活選擇穿越行為。使用傳感器來獲取兩個障礙物之間的距離，判斷它們之間的距離是否滿足安全的穿越條件，如果滿足，則提高引力函數中的引力系數。通過加大目標點對無人機的吸引力，使無人機能夠跳出局部極小點并繼續向目標前進。如果不滿足，則調整合斥力的作用方向，將其沿逆時針增加π/2 rad，以此來使無人機改變運動方向，逃離局部極小點。

涂柯等[25]在無人機陷入局部極小時引入調控力，幫助無人機逃離陷阱。此外，由于障礙物的影響可能導致無人機躲避障礙物時偏離原有航跡，使得航跡過長。故作者引入了一個檢測因子，該因子確保在障礙物產生斥力為有效斥力時，無人機能夠檢測并避開障礙物，而當斥力被視為無效時，則無人機將不會改變其航跡以躲避障礙物，該改進方法可以在不犧牲安全性的情況下減小航跡長度，從而優化避障航跡。

Wu等[26]提出了旋轉人工勢場法（R-APF）。它針對傳統的APF算法進行了改良，使其適應三維空間的應用，R-APF增加了目標點對無人機的吸引力，并賦予了無人機一種逃逸力，使得無人機在遇到局部最小點時能夠“逃離”，并將應用范圍拓寬到了三維空間。還結合了優化的VINS-Mono障礙物檢測算法來感知周圍環境，并創建環境中障礙物的柵格化地圖，進一步利用R-APF進行航跡規劃以實現避障。R-APF有效提高了無人機避障航跡規劃的穩定性和成功率，在無人機障礙物避讓和大范圍區域操作方面表現優越，這些改進使得算法在實際應用場景的可靠性和適用性方面得到了提升。

5 存在的問題與建議

不同的航跡規劃算法有著不同的特點，國內外學者對于算法改進也做出了大量的研究，但仍存在幾方面的難題亟待解決，如未知環境下無人機環境感知問題，多無人機航跡協同問題等，具體如下：

1）在航跡規劃算法中，常將飛行距離和飛行時間作為規劃的重點條件，諸如燃料損耗、飛行轉角等因素往往沒有被充分考慮，如在固定翼無人機航跡規劃中需考慮dubins轉角；多旋翼無人機若轉角航跡不夠平滑，速度損耗過大，將會導致飛行時間過長等問題。

2）對于無人機在未知環境內進行航跡規劃，無人機必須利用傳感器實時探測環境數據，傳統的算法可能無法處理龐大的計算量，導致航跡生成效率偏低。

3）多無人機航跡協同存在著信息共享方面的問題，并且需權衡單架無人機的航跡優化和整個無人機群的任務分配，需做到航跡最短、能耗最小、任務完成時間最短等要求，單個簡單的算法面對這種問題往往顯得捉襟見肘，需融合多個算法進行處理。

針對上述問題與無人機航跡規劃算法的發展，建議如下：

1）可通過在航跡規劃算法中引入額外代價來優化大轉角，或者以使轉角變化最小化為目標進行算法設計，這樣可以在平滑航跡的同時，減少因轉向而產生的額外損耗；還可以通過將無人機的飛行動力學模型整合到航跡規劃中，輔助生成符合飛行性能限制的航跡以確保其可飛性，還可使用如貝塞爾曲線、B樣條或者樣條插值等樣條曲線來平滑航跡。

2）未知環境下的無人機航跡規劃可在RRT算法基礎上進行改進，如融合A*算法將航跡規劃分為高層和底層決策，其中高層負責生成大致方向和目標點，低層負責處理具體的避障和航跡細節，以實現快速尋找合理航跡并在環境變化下實時更新的目的；還可使用訓練好的神經網絡來快速預估最佳航跡或行動方案，以期減少實時規劃的計算量。

3）處理多無人機航跡協同問題的關鍵是將多種算法和優化策略有效融合，并確保各個算法在特定情境下能使效果最優化，具體可以使用粒子群算法等智能仿生算法來優化整個無人機群的航跡配置，并采用動態窗口法、人工勢場法等進行無人機的實時避障來保證飛行安全，使無人機群體適應性策略能夠應對環境變化和每架無人機的實時動態變化。

6 結 論

本文在無人機航跡規劃算法方面進行了詳細概括，并給出了相應的結論與評價。全局規劃算法在動態環境中存在變化不夠靈活的弊端，但優勢在于可結合全局特點規劃出最優航跡；相反地，局部航跡規劃算法雖動態適應性較強，但在全局狀態下無法保障解的最優性。盡管當前的航跡規劃算法已經取得了巨大進展，但在如何更好地應對無人機在不斷變化的任務需求下的實際運作狀況方面仍有很大的發展空間。因此，算法的實時執行性能、對環境變化的響應速度以及對計算資源的有效利用能力將成為未來航跡規劃算法的重要評價指標。同時，目前在已知環境下存在簡單障礙物的靜態航跡規劃算法已經非常成熟，未來的研究應著力于算法的融合與優化，結合全局規劃的優勢和局部規劃的靈活性，針對多無人機問題以及動態變化的復雜環境提出更加高效和準確的混合型航跡規劃算法，為實現更加智能、高效的無人機自主飛行打開新的篇章。

參考文獻：

[1] 金泉，高顯忠，郭正，等.無人機集群在機場封控作戰中的應用研究 [J].飛航導彈，2021（10）：52-58.

[2] 王辰.多旋翼無人機在軍事后勤領域中的應用及發展趨勢分析 [J].飛航導彈，2021（8）：56-60.

[3] HART P E，NILSSON N J，RAPHAEL B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths [J].IEEE Transactions on Systems Science and Cybernetics，1968，4（2）：100-107.

[4] CHEN J C，LI M Y，YUAN Z Y，et al. An Improved A* Algorithm for UAV Path Planning Problems [C]//2020 IEEE 4th Information Technology，Networking，Electronic and Automation Control Conference （ITNEC）.Chongqing：IEEE，2020，1：958-962.

[5] 唐嘉寧，彭志祥，李孟霜，等.基于改進A*算法的無人機路徑規劃研究 [J].電子測量技術，2023，46（8）：99-104.

[6] ZHANG Z，WU J，DAI J Y，et al. Optimal Path Planning with Modified A-Star Algorithm for Stealth Unmanned Aerial Vehicles in 3D Network Radar Environment [J].Proceedings of the Institution of Mechanical Engineers， Part G： Journal of Aerospace Engineering，2022，236（1）：72-81.

[7] LAVALLE S M. Rapidly-exploring Random Trees： A New Tool for Path Planning [R].Ames：Iowa State University，1998.

[8] 顧子侶，劉宇，孫文邦，等.基于RRT的無人機動態航路規劃算法 [J].計算機科學，2023，50（S1）：65-69.

[9] 俞宬，陳謀，雍可南.基于改進RRT*算法的無人機往返航跡規劃 [J].中國科學：技術科學，2023，53（11）：1911-1921.

[10] KENNEDY J，EBERHART R. Particle Swarm Optimization [C]//Proceedings of ICNN'95 International Conference on Neural Networks.Perth：IEEE，1995：1942-1948.

[11] 李銳君，董素鴿.基于粒子群算法的無人機滅火路徑規劃仿真 [J].計算機仿真，2023，40（9）：43-48.

[12] 吳鈞皓，戚遠航，羅浩宇，等.帶交叉策略的粒子群算法求解多無人機路徑規劃問題 [J].工業控制計算機，2023，36（10）：94-95+168.

[13] 智瀚宇，賈新春，張學立.無人機路徑規劃：一種粒子群和灰狼復合算法 [J/OL].控制工程，2023：1-8（2023-11-28）.https：//doi.org/10.14107/j.cnki.kzgc.20221058.

[14] 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.

[15] 趙鑫，楊雄飛，錢育蓉.改進的蟻群優化算法求解旅行商問題 [J].計算機工程與設計，2022，43（4）：962-968.

[16] 于全友，徐止政，段納，等.基于改進ACO的帶續航約束無人機全覆蓋作業路徑規劃 [J].航空學報，2023，44（12）：303-315.

[17] 孔維立，王峰，周平華，等.改進蟻群算法的無人機三維路徑規劃 [J].電光與控制，2023，30（3）：63-69.

[18] KARABOGA D. An Idea Based on Honey Bee Swarm for Numerical Optimization [R].Technical Report TR06.Kayseri：Erciyes University，2005.

[19] AKAY B，KARABOGA D. Artificial Bee Colony Algorithm for Large-scale Problems and Engineering Design Optimization [J].Journal of Intelligent Manufacturing，2012，23（4）：1001-1014.

[20] GAO W F，HUANG L L，LIU S Y，et al. Artificial Bee Colony Algorithm Based on Information Learning [J].IEEE Transactions on Cybernetics，2015，45（12）：2827-2839.

[21] 伍鵬飛，李濤，曹廣旭，等.基于改進混沌蜂群算法的無人戰斗機路徑規劃 [J].中國科技論文，2021，16（3）：301-306.

[22] KHATIB O. Real-time Obstacle Avoidance for Manipulators and Mobile Robots [C]//1985 IEEE International Conference on Robotics and Automation.Saint Louis：IEEE，1985：500-505.

[23] FOX D，BURGARD W，THRUN S. The Dynamic Window Approach to Collision Avoidance [J].IEEE Robotics & Automation Magazine，1997，4（1）：23-33.

[24] 盧艷軍，李月茹.基于改進人工勢場法的四旋翼飛行器航跡規劃 [J].火力與指揮控制，2018，43（11）：119-122+127.

[25] 涂柯，侯宏錄，蘇煒.改進人工勢場法的無人機避障路徑規劃 [J].西安工業大學學報，2022，42（2）：170-177.

[26] WU Z Y ，DONG S P，YUAN M，et al. Rotate Artificial Potential Field Algorithm Toward 3D Real-time path Planning for Unmanned Aerial Vehicle [J].Proceedings of the Institution of Mechanical Engineers， Part G： Journal of Aerospace Engineering，2023，237（4）：940-955.

DOI：10.19850/j.cnki.2096-4706.2024.17.010

作者簡介：張琪（2001—），男，漢族，天津人，碩士在讀，研究方向：無人機航跡規劃；通信作者：張志學（1982—），男，漢族，河北滄州人，講師，博士，研究方向：無人機警務應用。

收稿日期：2024-03-13

基金項目：公安部理論與軟科學項目（2022LL56）；河北省省級科技計劃（20375601D）；警察大學學生科技創新計劃項目（yjskc22035）

Research Progress on UAV Trajectory Planning Algorithm

ZHANG Qi1， REN Yuchen1， GU Tengda1， JI Jinqi2， ZHANG Zhixue3

（1.Graduate School， China People's Police University， Langfang 065000， China;

2.School of Chemistry and Chemical Engineering， Tianjin University of Technology， Tianjin 300384， China;

3.School of Policing Command， China People's Police University， Guangzhou 510663， China）

Abstract： At present， the development of UAV technology has made obvious breakthroughs， and the application fields of UAV have expanded from military to commerce， scientific research， entertainment and other fields. This paper takes the UAV trajectory planning algorithm as the research object. Firstly， according to the principle and characteristics of the trajectory planning algorithm， this paper divides it into two categories of global planning algorithm and local planning algorithm， among which the global planning algorithm can be divided into the graph search6exMr82U53J61mdrAS4ZRw== algorithm and intelligent bionic algorithm. Secondly， the principles， workflow， advantages and disadvantages of the algorithms are analyzed in depth， the corresponding improvement methods are introduced， and their applications in the corresponding fields are elaborated in combination with the characteristics of the algorithms. Finally， it discusses the limitations and challenges of the above algorithms in the practical application， looks forward to the development trend of the future trajectory planning technology， and points out the direction for the research of UAV trajectory planning algorithm.

Keywords： UAV; trajectory planning; global planning algorithm; local planning algorithm; graph search algorithm; intelligent bionic algorithm