無人機(jī)航跡規(guī)劃算法研究進(jìn)展

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

關(guān)鍵詞：無人機(jī)；航跡規(guī)劃；全局規(guī)劃算法；局部規(guī)劃算法；圖搜索算法；智能仿生算法

中圖分類號：TP301；V279 文獻(xiàn)標(biāo)識碼：A 文章編號：2096-4706（2024）17-0049-07

0 引 言

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

1 無人機(jī)航跡規(guī)劃算法分類

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

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

2 圖搜索算法

圖搜索算法是一種基于圖數(shù)據(jù)結(jié)構(gòu)搜索航跡的算法。其基本思想是從某個節(jié)點(diǎn)出發(fā)，沿著邊連接的其他節(jié)點(diǎn)，最后到達(dá)目標(biāo)節(jié)點(diǎn)，節(jié)點(diǎn)表示在空間中的位置，邊則代表位置之間的連接通路。在無人機(jī)航跡規(guī)劃中，無人機(jī)所處的環(huán)境可以被建模為一個圖形，圖中的節(jié)點(diǎn)是無人機(jī)可能出現(xiàn)的飛行位置，邊則代表無人機(jī)可以飛行的航跡，圖搜索算法可以有效地找出從起點(diǎn)到終點(diǎn)的最優(yōu)航跡。

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

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

2.1 A*算法

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

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

新的評估函數(shù)H1（n）=H（n）-wcosθ，其中H（n）為以往的評估函數(shù)，w為一個權(quán)重參數(shù)。這個新評估函數(shù)減少了對無用節(jié)點(diǎn)的探索，提高了運(yùn)行效率和航跡質(zhì)量。

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

2.2 RRT算法

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

顧子侶等[8]在隨機(jī)樹待擴(kuò)展節(jié)點(diǎn)的選取上引入目標(biāo)啟發(fā)信息，在新節(jié)點(diǎn)生成和添加過程中融入無人機(jī)動力學(xué)約束，在確保生成航路符合實(shí)際飛行的可行性的基礎(chǔ)上，針對突發(fā)威脅情況，提出一種動態(tài)擴(kuò)展隨機(jī)樹方法，該方法可以對原有隨機(jī)樹進(jìn)行剪枝和重構(gòu)，以快速避開威脅并生成一條安全航路。

為了能讓算法在有障礙物的環(huán)境中更高效地進(jìn)行航跡規(guī)劃，俞宬等[9]提出一種基于向量場直方圖算法啟發(fā)的改進(jìn)B-RRT*無人機(jī)往返航跡規(guī)劃算法。采用直角直方圖網(wǎng)格對工作空間中的障礙進(jìn)行統(tǒng)計(jì)表示，引入目標(biāo)扇區(qū)和可通行扇區(qū)的概念，使用成本函數(shù)來引導(dǎo)無人機(jī)的運(yùn)動，最后提出了一個航跡修剪操作，通過碰撞檢測來剔除無效節(jié)點(diǎn)，并進(jìn)一步修剪航路點(diǎn)，以得到一條更優(yōu)的航跡路線。

3 智能仿生算法

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

3.1 粒子群算法

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

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

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

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

3.2 蟻群算法

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

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

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

于全友等[16]構(gòu)建了一個帶續(xù)航約束的無人機(jī)全覆蓋航跡規(guī)劃的數(shù)學(xué)模型，并提出了無人機(jī)返航時機(jī)判斷機(jī)制和返航點(diǎn)計(jì)算方法，特別是設(shè)計(jì)了距離矩陣動態(tài)更新機(jī)制以處理返航點(diǎn)導(dǎo)致的節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)的動態(tài)變化問題，并設(shè)計(jì)了滾動權(quán)值加權(quán)和信息素更新機(jī)制來兼顧全局啟發(fā)性和局部啟發(fā)性信息，提高了蟻群算法的搜索能力，基于改進(jìn)蟻群算法優(yōu)化了有續(xù)航約束條件的無人機(jī)全覆蓋航跡規(guī)劃。

孔維立等[17]引入避障策略并改進(jìn)了人工勢場法加入到啟發(fā)函數(shù)中，使得螞蟻在啟發(fā)過程中不僅避開障礙物而且受到人工勢場的引導(dǎo)，增強(qiáng)了搜索過程中的方向性。并通過設(shè)置信息素?fù)]發(fā)因子的動態(tài)隨機(jī)更新機(jī)制，算法在增加局部搜索能力的同時，避免了過早陷入局部最優(yōu)。并結(jié)合了改進(jìn)人工勢能法進(jìn)行預(yù)搜索的信息素初始化，增加預(yù)搜索后螞蟻的局部搜索能力，加快了算法的收斂速度。

3.3 人工蜂群算法

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

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

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

Akay等[19]檢驗(yàn)了人工蜂群算法（ABC）在無約束大規(guī)?；鶞?zhǔn)問題上的性能。研究發(fā)現(xiàn)ABC算法在大規(guī)模無約束優(yōu)化問題上優(yōu)于差分算法（DE）和粒子群優(yōu)化算法（PSO）。這種優(yōu)越的性能歸功于ABC算法有效平衡探索和開發(fā)過程的能力，因?yàn)樗褂昧素澙返倪x擇、概率選擇、隨機(jī)選擇這三種不同的選擇算子。

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

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

3.4 算法對比

在實(shí)際應(yīng)用中，需要根據(jù)無人機(jī)的具體任務(wù)和實(shí)戰(zhàn)環(huán)境選擇合適的算法或?qū)⒍喾N算法結(jié)合起來，不同的算法有著不同的特點(diǎn)，根據(jù)以上對全局航跡規(guī)劃算法的探討，對于這些算法的總結(jié)如表1所示。

4 局部規(guī)劃算法

局部規(guī)劃算法是指在已知環(huán)境中，通過分析當(dāng)前所處位置的局部信息來進(jìn)行航跡規(guī)劃的方法。局部規(guī)劃算法因其較高的適應(yīng)性，常被用于解決動態(tài)環(huán)境變化下的避障問題。

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

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

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

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

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

5 存在的問題與建議

不同的航跡規(guī)劃算法有著不同的特點(diǎn)，國內(nèi)外學(xué)者對于算法改進(jìn)也做出了大量的研究，但仍存在幾方面的難題亟待解決，如未知環(huán)境下無人機(jī)環(huán)境感知問題，多無人機(jī)航跡協(xié)同問題等，具體如下：

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

2）對于無人機(jī)在未知環(huán)境內(nèi)進(jìn)行航跡規(guī)劃，無人機(jī)必須利用傳感器實(shí)時探測環(huán)境數(shù)據(jù)，傳統(tǒng)的算法可能無法處理龐大的計(jì)算量，導(dǎo)致航跡生成效率偏低。

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

針對上述問題與無人機(jī)航跡規(guī)劃算法的發(fā)展，建議如下：

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

2）未知環(huán)境下的無人機(jī)航跡規(guī)劃可在RRT算法基礎(chǔ)上進(jìn)行改進(jìn)，如融合A*算法將航跡規(guī)劃分為高層和底層決策，其中高層負(fù)責(zé)生成大致方向和目標(biāo)點(diǎn)，低層負(fù)責(zé)處理具體的避障和航跡細(xì)節(jié)，以實(shí)現(xiàn)快速尋找合理航跡并在環(huán)境變化下實(shí)時更新的目的；還可使用訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)來快速預(yù)估最佳航跡或行動方案，以期減少實(shí)時規(guī)劃的計(jì)算量。

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

6 結(jié) 論

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

參考文獻(xiàn)：

[1] 金泉，高顯忠，郭正，等.無人機(jī)集群在機(jī)場封控作戰(zhàn)中的應(yīng)用研究 [J].飛航導(dǎo)彈，2021（10）：52-58.

[2] 王辰.多旋翼無人機(jī)在軍事后勤領(lǐng)域中的應(yīng)用及發(fā)展趨勢分析 [J].飛航導(dǎo)彈，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] 唐嘉寧，彭志祥，李孟霜，等.基于改進(jìn)A*算法的無人機(jī)路徑規(guī)劃研究 [J].電子測量技術(shù)，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ī)動態(tài)航路規(guī)劃算法 [J].計(jì)算機(jī)科學(xué)，2023，50（S1）：65-69.

[9] 俞宬，陳謀，雍可南.基于改進(jìn)RRT*算法的無人機(jī)往返航跡規(guī)劃 [J].中國科學(xué)：技術(shù)科學(xué)，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ī)滅火路徑規(guī)劃仿真 [J].計(jì)算機(jī)仿真，2023，40（9）：43-48.

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

[13] 智瀚宇，賈新春，張學(xué)立.無人機(jī)路徑規(guī)劃：一種粒子群和灰狼復(fù)合算法 [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ìn)的蟻群優(yōu)化算法求解旅行商問題 [J].計(jì)算機(jī)工程與設(shè)計(jì)，2022，43（4）：962-968.

[16] 于全友，徐止政，段納，等.基于改進(jìn)ACO的帶續(xù)航約束無人機(jī)全覆蓋作業(yè)路徑規(guī)劃 [J].航空學(xué)報，2023，44（12）：303-315.

[17] 孔維立，王峰，周平華，等.改進(jìn)蟻群算法的無人機(jī)三維路徑規(guī)劃 [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ìn)混沌蜂群算法的無人戰(zhàn)斗機(jī)路徑規(guī)劃 [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ìn)人工勢場法的四旋翼飛行器航跡規(guī)劃 [J].火力與指揮控制，2018，43（11）：119-122+127.

[25] 涂柯，侯宏錄，蘇煒.改進(jìn)人工勢場法的無人機(jī)避障路徑規(guī)劃 [J].西安工業(yè)大學(xué)學(xué)報，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—），男，漢族，天津人，碩士在讀，研究方向：無人機(jī)航跡規(guī)劃；通信作者：張志學(xué)（1982—），男，漢族，河北滄州人，講師，博士，研究方向：無人機(jī)警務(wù)應(yīng)用。

收稿日期：2024-03-13

基金項(xiàng)目：公安部理論與軟科學(xué)項(xiàng)目（2022LL56）；河北省省級科技計(jì)劃（20375601D）；警察大學(xué)學(xué)生科技創(chuàng)新計(jì)劃項(xiàng)目（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