無人機集群路徑規劃算法研究綜述

劉君蘭，張文博，姬紅兵，朱明哲

（西安電子科技大學電子工程學院，陜西 西安 710071）

0 引言

無人機集群具有抗毀重構強、分布協同性高、軍事經濟效益顯著等優勢，能完成目標偵察、精準打擊、通信干擾、通信中繼等多項任務。因此，相關研究得到了各國的廣泛關注。無人機集群控制技術主要包括編隊控制、任務分配、路徑規劃、避碰避障等。其中，無人機集群路徑規劃是在滿足一定約束條件下，規劃出從起始點到目標點的路徑，使得指定的性能指標最優。約束條件主要指環境約束、任務約束、空間協同約束、時序協同約束、無人機自身約束等。性能指標可以包括路徑長度、路徑光滑程度、路徑安全性、任務完成時間等。無人機集群路徑規劃算法本質上是一個多約束的組合優化算法，主要包括傳統的路徑規劃算法、智能優化算法和深度強化學習算法。本文首先梳理了傳統路徑規劃算法，再著重探討了深度強化學習算法在無人機集群路徑規劃上的應用，最后對無人機集群路徑規劃算法進行比較和總結。

1 傳統路徑規劃算法

傳統路徑規劃算法相對成熟，已經被廣泛應用于單無人機尋路問題上。多無人機路徑規劃需要考慮各種協同約束以及路徑交叉、飛行安全性問題。傳統路徑規劃算法主要分為基于圖搜索法、采樣法和人工勢場法。基于圖搜索法對整個環境進行建模，再進行路徑搜索，比較直觀，易求出最短路徑，適用于全局和連續區域內的路徑規劃，包括Dijkstra 算法、A*算法、D*算法等；人工勢場法原理簡單，易于實現，實時性好，局部尋路能力強，被廣泛應用于智能優化算法和深度強化學習算法中，解決收斂慢問題；采樣法通過采點構圖來表示環境，再進行路徑搜索，典型代表有快速擴展隨機樹算法（RRT）。

1.1 基于圖搜索法

Dijkstra 算法的核心思想是貪心和廣度優先搜索，以起始點為中心向四周擴散，以節點到起點的代價作為優先級選擇下一路徑點。這種算法能找到最優路徑，但是花費時間長。

A*算法是Dijkstra 算法的改進算法，在Dijkstra 算法的基礎上加了啟發式搜索思想，在選擇下一路徑點時不僅考慮它到起點的代價還考慮了它到終點的代價。A*算法相較于Dijkstra 算法，能更快找到最短路徑，原理簡單易實現。然而，A*算法也存在規劃路徑不平滑問題，主要是由于搜索領域太小、路徑轉角太大導致，可增大搜索領域來改進。針對A*算法規劃路徑距離障礙物太近、路徑安全性低問題，葛文雅等人提出了一種移動機器人路徑規劃安全A*算法，在啟發式函數中增加了安全性評估函數，使得算法在選擇下一路徑點時會考慮距離障礙物的距離。

1.2 人工勢場法

人工勢場法（APF）將物理學中“勢場”的概念引入無人機集群任務場景。核心思想是場景中的障礙物對無人機產生斥力，目標點對無人機產生引力，無人機在合力作用下運動。該算法實時性好,規劃路徑平滑，適用于局部路徑規劃。但是，由于無人機集群任務場景中元素復雜，合力為零的點較多，APF 易陷入局部最優,一種改進思路是設置虛擬障礙物或者虛擬目標點來擺脫局部最優點。對于APF 目標點不可達問題，可以通過設置最小吸引力大小、縮小無人機受斥力的方向范圍、斥力隨無人機靠近目標點而減小來改進。針對APF 應用在無人機集群任務場景中路徑交叉問題，毛遠航在文獻[8]中為碰撞可能性高的無人機重新規劃航點，來避免無人機發生碰撞。

1.3 采樣法

前文提到的基于圖搜索法、人工勢場法，都需要對環境進行建模。在多維復雜空間，建模會花費大量時間和計算成本。采樣法不需要對整個環境空間進行建模，以采樣點重構環境，計算量相對較少。以RRT 算法為例，RRT 算法通過在空間隨機采點來構建空間填充樹，以樹的軀干作為路徑。然而，RRT 算法存在較大的隨機性，收斂慢。郭梟鵬在文獻[9]中將RRT 算法與人工勢場法結合，利用RRT 隨機采樣特性幫助APF 跳出局部最優解。同時又通過APF 目標引力來引導隨機樹擴展，降低RRT 算法的隨機性，使得尋路更具方向性。

2 智能優化算法

智能優化算法大多是通過模仿群體生物覓食、圍捕行為等方式，來搜索空間最優解。算法能夠解決高維復雜、多約束的優化問題。常見算法有遺傳算法（GA）、蟻群算法（ACO）、粒子群算法（PSO）、蜂群算法、狼群算法等。

2.1 遺傳算法

遺傳算法是一種基于生物遺傳進化過程的自適應方法，可以用來解決搜索和優化問題。算法的優勢在于不受問題領域限制，具備快速啟發式搜索的能力。劣勢在于易早熟，易陷入局部最優解。改進方法有將GA 和傳統路徑規劃算法結合，優化路徑點；改進交叉算子或是變異算子；增加種群多樣性等。吳振等人針對早熟問題，采用一種動態的適應度值標定法，以減小個體間適應度差值，防止進化初期某些超常個體占據整個種群導致早熟。周加權將模擬退火法與GA 結合，并對遺傳過程中的交叉、變異進行調整，有效提升了GA 的全局搜索能力,克服了傳統遺傳算法陷入局部最優的問題。

2.2 蟻群算法

蟻群算法是一種隨機搜索算法，核心思想是利用蟻群的信息素，通過正反饋的方式尋求問題的最優解。針對ACO 自身收斂慢、易陷入局部最優解問題，陳俠等人引入自適應參數和雙向搜索機制，得到了理想的航跡。蟻群改進算法在無人機集群優化方面應用較多。蘇菲等人對ACO 引入協同策略，使得算法能用于多種協同約束條件下多機航跡規劃。針對無人機集群路徑規劃中路徑交叉問題，宋霏羽等人進行了交叉檢測與消除，提出的改進ACO 能增加解的多樣性，跳出局部最優。蘇梅梅等人改進ACO的信息素更新機制，增加了無人機數量約束，解決了無人機集群執行任務時路徑交叉、資源分配不均勻等問題。

2.3 粒子群算法

粒子群算法在1995 年被提出，源于對鳥群捕食行為的研究。核心思想是群體中每個粒子共享自己找到的極值，獲得整個粒子群的最值，然后對每個粒子進行調整，最終找到全局最優解。PSO 算法的主要優勢在于簡單、易實現、收斂快、可調參數少。

在相對較復雜的環境中，PSO 算法容易陷入局部最優，針對這一問題可通過調整PSO 的參數，如慣性權重，加速因子等來解決。謝勇宏等人采用線性遞減的慣性權重方式，來均衡不同迭代時期粒子的全局搜索與局部搜索能力，在速度更新公式中加入加速度量，幫助粒子跳出局部最優。萬路萍在文獻[19]中采用非線性遞減慣性權重，保證在算法迭代后期仍能保持良好的尋優能力；在粒子陷入局部最優時，也會在速度上給予一些擾動，讓粒子跳出局部最優。也有一些結合其他算法的改進PSO，付興武等人將天牛須搜索算法與PSO 結合，利用天牛個體對環境具有獨立判斷能力來克服PSO 中粒子完全受群體最優影響，最終改進算法在三維路徑規劃上效果更優。針對無人機路徑規劃中方案單一問題，蘇子美等人結合基于集的粒子群優化（S-PSO）和綜合學習粒子群優化（CLPSO），對速度更新公式進行改進，增加了最優解的多樣性。

3 深度強化學習算法

深度強化學習算法主要分為基于值函數的算法、基于策略函數的算法和結合兩者優勢的Actor-Critic 架構算法。基于值函數的算法擁有擬合動作價值函數的網絡，代表算法有DQN、Rainbow 等。基于策略函數的算法有擬合動作空間的概率分布函數的策略網絡，代表算法有PG、TRPO 等。結合兩家之長的Actor-Critic架構算法既有評價動作好壞的Critic 網絡，也有選擇動作的Actor網絡。其代表算法有A3C、DDPG 等。

傳統方法大多分開處理無人機集群路徑規劃及任務分配問題，忽視了兩者之間的耦合關系。強化學習算法更多的是以任務為導向，以獎勵函數為指引，在滿足各種約束條件的前提下，完成任務分配、路徑規劃、避碰避障。目前應用較多的是DQN 及其改進算法、DDPG 算法及其改進算法。針對稀疏獎勵，張仕充在文獻[24]中提出了APF-DQN 模型，在獎勵函數中設置人工勢場分量，保證在未到達目標點時，也有一定的引導性獎勵。對于訓練樣本獎勵低導致收斂慢問題，王軍等人將HER 與DQN 相結合來增加經驗池樣本有效性，從而提高收斂速度。張瀚等人結合人工勢場法來干預DDPG 算法的動作選擇，最終提升了路徑平滑度，縮短了路徑長度。于盛在文獻[27]中利用MADDPG 解決了多無人機二維空間的多目標路徑規劃問題，在設置獎勵函數時充分考慮到了避碰、避障、趨向目標這三點。

強化學習試錯-學習機制可能導致訓練初期盲目性問題，研究者通過引入遷移學習的相關知識來幫助強化學習適應更復雜的任務場景。遷移學習主要包括基于實例的遷移、基于特征的遷移和基于共享參數的遷移。其中基于共享參數的遷移最為常用，可以將二維環境訓練出來的模型參數映射到三維環境的模型中作為初始參數，也可以將靜態環境訓練出來的模型參數作為動態環境下模型的初始參數。胡曉東等人將靜態環境下訓練的深度神經網絡權重作為動態環境下深度神經網絡的初始權重，最終成功縮短了訓練收斂時間。

4 無人機集群路徑規劃算法比較

無人機集群路徑規劃不僅需要考慮復雜未知環境、無人機自身性能約束，還要考慮無人機之間的時間協同和空間協同約束。傳統路徑規劃算法、智能優化算法和深度強化學習算法在路徑規劃上有各自的優勢和劣勢以及適用的場景，如表1 所示。

表1 無人機集群路徑規劃算法

5 結束語

無人機集群的應用場景較為復雜，傳統的路徑規劃算法很難規劃路徑或者規劃路徑所花時間較長。智能優化算法和深度強化學習算法在復雜環境下更具優勢，能實現真正的群體智能，但是智能優化算法存在易陷入局部最優，深度強化學習算法存在稀疏獎勵等缺陷，需要結合其他算法來改善，所以在無人機集群在路徑規劃上應考慮各種算法相結合的混合算法。■