無人機協同偵察路徑規劃研究*

劉澤原，趙佳宜，趙文棟，劉存濤，李艾靜

（陸軍工程大學，江蘇 南京 210000）

0 引言

近些年，無人機因其可操作性、高機動性、靈活性以及經濟性等特點被廣泛應用于軍事和民用領域[1]。例如，在民用領域，無人機用于執行救災救援、環境研究、天氣預報以及農業監控等任務[2]；在軍事領域，無人機能夠在危險復雜區域飛行，并利用裝載的攝像機或其他偵察設備獲取多種形式的目標信息，有效降低了人力資源損耗，且能夠更高效地執行偵察任務[3]。

相較于單架無人機，多架無人機協作可以創造更高的價值[4]。由于數量優勢，它可以輕易擴展偵察覆蓋范圍，具有可擴展性。同時，無人機系統中的某一架無人機受到損壞時可以由其他無人機替代，相較單架無人機具有更高的抗風險能力[5]。此外，軍事領域中，作戰要求不斷提高，偵察任務逐漸復雜化。尤其是隨著未來戰爭的信息化、網絡化、體系化對抗的發展，復雜環境下的情報偵察和戰場監控具備更加多元的任務要求[6]，需要以多無人機協同偵察代替單架無人機偵察，以應對更加復雜的偵察任務。

無人機協同偵察中，無人機既可以通過負載的偵察設備獲取目標區域信息[7]，也可以與地面傳感器網絡協同，獲取傳感器采集的偵察信息[8]。無人機協同偵察的方式和偵察任務的要求不同，因此其目標和約束具有多樣性，如偵察時間、偵察信息量、偵察價值等諸多目標，或者能耗、飛行距離等約束。為了實現不同任務目標，需要對無人機進行合理的路徑規劃。路徑規劃問題通過規劃無人機的飛行路徑，使其可以在約束條件下完成指定的任務[9]。單架無人機路徑規劃中，需要根據已有的信息確定訪問目標和訪問順序。它的路徑具有時間連續性，涉及到多個連續變量，并會受到各種現實因素的制約[10]。在多無人機協同偵察中，對無人機路徑規劃前需要對其分配相應的偵察任務，因而任務分配和路徑規劃兩個問題緊密耦合。任何一方的結果會對另一方問題的解決產生影響。為了滿足任務要求，必須同時考慮兩個問題。因此，無人機協同偵察的路徑規劃問題的研究具有重要的實際意義和挑戰性。

1 路徑規劃分類

從路徑類型上分類，無人機路徑規劃問題主要包括運動規劃、軌跡規劃和導航3 類[11]。運動規劃涉及到無人機的飛行軌跡和轉彎角度，通過優化最小路徑長度和旋轉角度來優化無人機路徑。該路徑為無人機在運動空間中的具體變化。軌跡規劃主要對路徑規劃中的軌跡和飛行時間進行處理，路徑大多表現為折線路徑，體現了無人機訪問的目標點和對目標點的訪問順序。導航主要研究無人機的碰撞規避和無人機定位問題，包括監控無人機從源點到目的點的拓撲變化。

從規劃過程來看，無人機路徑規劃問題分為靜態規劃和動態規劃兩類。靜態規劃主要指無人機在飛行前已經獲取全局的目標信息，根據所分配任務的要求預先規劃飛行路徑。靜態路徑規劃要求規劃結果更加準確可靠。動態路徑規劃則是在無人機飛行過程中進行實時路徑規劃，通常會出現由于其無法獲取全局信息或者在飛行過程中飛行環境發生新的變化以及偵察任務要求發生變化的情況。因此，動態路徑規劃要求無人機在極短時間內產生規劃結果。

2 路徑規劃問題表示方法

處理無人機路徑規劃問題過程包括預處理和路線規劃兩個階段[12]。預處理階段需要將無人機飛行環境和目標點表示出來，運用不同表示方法生成映射圖形。不同的路徑規劃技術會以不同的方式定義無人機的點和飛行路線。路線規劃階段，無人機根據任務的要求運用不同的路徑規劃算法求解飛行路徑。

預處理階段主要負責對無人機飛行環境進行表示，而環境表示的合理與否影響著無人機路徑規劃效果的好壞[13]。表示飛行環境時，需要考慮訪問目標、地形環境、飛行障礙、威脅區域等因素。對于不同的任務，無人機面臨的飛行環境各不相同。合適的表示方式需要準確表示出當前環境的空間狀態，并能夠根據環境中部分因素的變化隨時更新[14]。通常，無人機的飛行環境包括連續表示、圖表示和網格法表示3 種數學表示方法。

2.1 連續數學表示方法

在連續數學表示方法中，無人機的飛行環境和飛行路線被視為連續的值。通常采用歐式空間表示二維或三維的環境空間[15-16]，利用一系列連續的航跡點表示無人機的飛行路徑。此外，無人機的目標被視為一個點，環境空間存在的威脅被視為一個函數。例如：文獻[17]將飛行環境表示為一個連續的勢場，無人機被設計為一個受勢場控制運動的粒子，其路徑根據初始點到目標點的合成場進行計算；文獻[18]運用連續方法表示一個農業系統環境，并設計了基于改進勢場方法的威脅模型，被用于尋找局部最小點和生成隨機目標點。連續數學表示方法能夠精確表示無人機的路徑規劃問題，但是需要極大的儲存空間，復雜度較高，不適合一般的優化計算。

2.2 圖表示方法

圖表示方法通過在三維環境中定義網絡曲線，計算環境空間中各目標點的連通性，并構建路線圖，在規劃階段求解起始點和目的點，通過曲線拼接找到無人機在這些點之間的路徑。其中，各點之間的曲線權重表示無人機的飛行代價，在規劃階段根據無人機任務目標確定最優或次優的路徑[19]。路線圖的表示技術能夠較好地解決靜態環境下移動的無人機路徑規劃問題。文獻[20]提出了基于最優控制的無人機路徑規劃算法，利用路線圖解決了旅行商問題（Traveling Salesman Problem，TSP），同時計算了覆蓋所有遙感區域的最小飛行時間，以執行無人機的所有通信任務。

根據圖的來源不同，可以將構建路線圖的方法分為構建概率圖、快速隨機探索樹和Voronoi 圖（Voronoi Diagram，VD）3 類。概率圖（Probabilistic Roadmaps，PRM）由直邊連接的隨機節點組成。文獻[21]基于PRM 提出了一種用于在城市環境中跟蹤和搜索路徑的路線圖算法。文章中調查發現，該技術可以用于無人機的碰撞避免和發現通信缺口故障。構建快速隨機探索樹（Rapid-exploring Random Trees，RRT）通過構建隨機空間填充樹來表示高維空間。文獻[22]提出了RRT 與人工勢場相結合的方法，給出了最優無人機路徑規劃。Voronoi 圖方法中，針對一個特定的平面，根據到路徑點的距離將曲面劃分為不同區域。對于不同的任務要求，該方法對路線圖的節點和邊的定義不同。文獻[23]提出了無人機最優性的一致性理論，使用VD 設計路線圖和尋找障礙，然后采用協同控制的方法對多障礙物進行探測，最后利用VD 中的一致性理論確定了最優路徑，并計算了總飛行成本。

2.3 網格表示法

網格方法將場景分成多個網格，根據網格大小形狀區別將其分為均勻網格和非均勻網格，其中均勻網格主要體現為正三角形網格、正方形網格和六邊形網格。網格方法將無人機及目標用單一網格表示，將障礙物和禁飛區用多個連續網格表示[24]。同時，該表達方式可以簡明判斷出同一網格或相鄰網格內兩點的安全路徑。在對環境空間的網格進行計算后，根據網格順序規劃出無人機飛行路徑。此外，通過網格表示法得到的路徑需要進行平滑處理。

3 路徑規劃求解算法

在規劃階段，無人機根據預處理階段中對環境的數學表示，通過規劃算法求解無人機飛行路徑。無人機路徑規劃需要根據任務和實際要求綜合考慮無人機到達時間、能耗限制、威脅區域、時間要求等因素，并根據任務目標規劃出最優或次優的飛行路徑，保證無人機圓滿完成任務并返回基地[25]。可見，路徑規劃算法的優劣決定著規劃的路徑能否滿足無人機的任務要求。當前路徑規劃算法可分為以數學推導為主的傳統算法和以生物與自然規律為啟發的智能算法。

3.1 傳統算法

傳統算法通常以尋找唯一全局最優點為目標，主要包括數學規劃法、動態規劃法、最優控制法、牛頓法以及梯度法等優化方法。文獻[26]中基于凸優化理論，提出了一種有人/無人機協作系統的軌跡規劃方法。文章建立系統的運動模型，分析控制過程，隨后設計無人機的路徑規劃，分別以能量消耗最小和到達時間最短為優化目標，在時空約束條件下對規劃模型進行了逼近和凸優化，最后利用凸優化算法求解問題。文獻[27]探討了自主監控跟蹤目標的路徑規劃問題，包含探測、生存和跟蹤等多個任務目標。文章通過對單目標的凸組合進行優化，在性能空間中找到了一組無人機的最優航跡點。

文獻[28]針對四旋翼無人機路徑規劃中產生的軌跡位移、速度和加速度函數中存在大量不可微點的問題，提出了一種基于貝塞爾曲線最小和高階位移導數軌跡的優化方法。采用最小位移導數法對軌跡進行優化，將貝塞爾曲線引入優化函數，通過討論四旋翼無人機飛行約束，將其軌跡轉化為凸二次規劃問題，采用內點法進行求解。文獻[29]研究了無人機空間覆蓋類型應用的路徑規劃問題，將其看作旅行商問題和覆蓋路徑規劃問題的組合，隨后針對此類問題建模為混合整數線性規劃問題，并分別利用動態規劃和啟發式方法對其進行求解。文獻[30]研究了固定翼無人機U2U（UAV-to-UAV）的通信系統，通過規劃無人機路徑使信息傳輸時間最小化。文章提出了一個包含信息吞吐量、地面發射機干擾、無人機速度限制等因素的通用通信框架，并在此基礎上提出了一種基于精確懲罰法和逐次凸逼近的路徑規劃算法。

3.2 智能算法

智能算法主要來源于人類智能、生物行為或自然規律的啟發，包括進化算法、群體智能算法、模擬退火算法、禁忌搜索算法以及神經網絡算法5 類，主要特點是能夠通過迭代在短時間內獲取路徑規劃問題的次優解。文獻[31]提出了用于無人機航跡規劃的改進人工蜂群算法，參數少，收斂速度快，能夠使無人機避免實時環境下的動態威脅。文獻[32]提出了一種經過模擬退火的遺傳算法，稱為GASA算法，用于改進無人機航跡規劃。該算法具有成本最小、魯棒性強、路徑最佳以及速度快等優點。文獻[33]提出了改進的遺傳算法（Improved Genetic Algorithm，IGA）和基于蟻群優化算法的粒子群算法（Particle Swarm Optimization Based on Ant Colony Optimization，PSO-ACO）來解決無人機TSP 問題。文獻[34]結合聚類算法和遺傳算法對多無人機的任務分配和路徑規劃問題進行求解，有效滿足了偵察任務的時間約束。

文獻[35]考慮了無人機和無人車協同偵察和監視的任務場景，提出了一種結合分布估計算法（Estimation of Distribution Algorithm，EDA）和遺傳算法（Genetic Algorithm，GA）的混合算法來解決無人機的路徑規劃問題。文獻[36]提出了一種基于多智能體深度確定性策略的梯度（Multi-Agent Deep Deterministic Policy Gradient Algorithm，MADDPG）算法，同時使用人工智能方法解決動態環境下的路徑規劃問題。文獻[37]研究無人機輔助的蜂窩網絡，由無人機充當飛行中繼將信息在蜂窩之間進行傳遞，隨后針對接入點選擇子問題具有NP 困難的特點，提出了一種基于博弈論的分布式算法，指導用戶自主選擇基站或無人機作為接入點。同時，為了實現最優信道狀態，采用基于深度強化學習（Deep Reinforcement Learning，DRL）的方法求解無人機路徑規劃子問題，指導無人機在各個位置采取最優行動。

4 優化目標和約束

4.1 路徑規劃優化目標

無人機協同偵察路徑規劃的優化目標主要包括能耗優化、時間優化以及效益優化3 類。能耗優化的目的是在完成規定任務的前提下，減少多無人機執行偵察任務時的能量損耗，延長無人機壽命，主要包括能耗公平性、總能耗最小和最大能耗最小化3 類問題。文獻[38]研究了無人機對目標區域進行視頻偵察并將信息傳回基站的場景，綜合考慮了無人機偵察時的飛行能耗、通信能耗和懸停能耗，并提出了一種基于能耗公平性的路徑規劃算法。文獻[39]研究了無人機輔助地面傳感節點通信的場景，通過聯合優化無人機軌跡和地面節點之間的通信時間分配和任務完成時間，實現無人機的能耗最小化。文獻[40]將能量消耗建模為與飛行速度和飛行狀態等因素相關的函數，并找到使總能耗最小的飛行速度。

時間優化是為了無人機提高完成偵察的效率，在保證規定任務完成的情況下減少無人機執行任務的時間。無人機通常在執行延遲容忍的偵察任務時將時間作為約束和優化目標。文獻[41]考慮了多無人機從數據中心出發為傳感器提供數據采集場景，以無人機返回數據中心時間最短為目標，并通過聯合傳感器調度和無人機路徑規劃優化任務完成時間。文獻[42]研究了無人機成輔助采集傳感器信息中信息年齡最小化問題，將問題建模為最大時間最小化的路徑規劃問題，并利用基于強化學習的策略求解問題。文獻[43]主要利用無人機作為空中平臺，通過聯合優化無人機路徑和通信資源分配方法，在滿足各目標點的數據需求的同時，最大限度地縮短無人機的周期飛行時間和任務完成時間。

效益優化主要是為了提高無人機在規定時間或其他限制下偵察收益的最大化。偵察收益包括無人機訪問目標點所獲得的數據量、信息價值等。文獻[44]考慮了無人機采集水下多模態無線傳感器網絡的場景，將感知的數據價值與一個隨時間衰減的值相關聯，并利用基于貪婪的自適應尋路算法，以最大化接收數據的信息價值。文獻[45]考慮到不同偵察點的信息價值不同，為多架異構無人機提供偵察信息價值最大化的路徑規劃方案。文獻[46]則將目標區域劃分為簇，根據信息價值和節點功率確定簇頭及數據轉發規則。傳感器節點以事件驅動的方式收集周圍的信息。無人機作為移動匯聚節點收集簇頭節點的數據。

4.2 路徑規劃約束

無人機的約束來自3 個方面。

一是由無人機自身的約束，如電池容量限制、飛行速度限制、運動性能限制、加速度和轉角等約束。文獻[47]針對無人機具有不同飛行速度時的路徑規劃問題進行了數學建模，并提出了以最小化偵察時間為目標的路徑算法。文獻[48]則考慮了無人機存在起飛時間間隔的情況，研究了偵察區域覆蓋率最大化的路徑規劃問題。

二是無人機需要滿足環境的約束，如禁飛區、障礙物等。文獻[49]考慮了不同類型的禁飛區存在的場景，提出了一種基于A*算法解決多類型禁飛區并存的無人機避障路徑規劃問題。文獻[50]則利用改進的人工勢能算法解決無人機在追蹤目標的過程中實時避障的問題。

三是任務約束，根據任務要求決定，如訪問目標要求、任務完成時間要求等。例如，文獻[51]中無人機偵察多個目標區域，其獲取目標區域的信息大小取決于其在目標區域的停留，其路徑規劃面臨最大飛行時間和目標區域最低停留時間的雙重約束。

5 下一步研究方向

5.1 面向多用戶的無人機協同能耗問題

當前無人機協同偵察路徑規劃研究大多只考慮無人機服務單個用戶或者無人機只向一個分發信息的基站傳遞信息的情況。然而，有多個用戶存在且缺少分發信息的基礎設施的情況下，無人機則必須進行對目標的偵察和對用戶的信息分發兩個過程。無人機協同偵察目標后，每架無人機可能具有多個用戶需要的信息，在信息分發過程中則會導致多架無人機對用戶的冗余訪問，進而造成較大的能耗。因此，對于面向多個用戶，無人機同時進行偵察和信息分發兩個過程的協同路徑規劃問題需要進一步研究。

5.2 不同優先級用戶的信息獲取時間問題

在面向多用戶的偵察場景中，由于用戶的重要程度不同和對信息需求的緊迫程度不同，其信息獲取的優先級也不同。相對于優先級較低的用戶，優先級高的用戶需要更快地獲取信息。當前針對偵察任務時間的研究中，大多沒有考慮不同優先級用戶存在的情況。一方面，大多研究以無人機偵察時間為優化目標，沒有綜合考慮不同優先級用戶的信息獲取時間，其優化目標不能基于優先級情況平衡各用戶信息獲取時間，因而需要建立一套面向不同優先級用戶信息獲取時間的評價指標。另一方面，相關路徑規劃研究中，無人機通常采取一次性偵察或多次往返偵察的模式，即無人機所有需要目標后前往信息接收節點，或者無人機多次往返于偵察區域與信息接收節點，每一次往返無人機只帶回部分目標的信息。一次性往返的偵察模式無法保證高優先級用戶更快地獲取信息，多次往返偵察模式則會導致低優先級用戶信息獲取時延過大。因此，在多優先級用戶存在的情況下，需要對無人機偵察模式和路徑規劃方法進行進一步研究。

5.3 多用戶決策效用問題

無人機為戰場用戶提供偵察服務時，需要考慮到用戶的決策效用問題。用戶決策的效用同時取決于其進行決策的時間和進行決策時所依據的信息的總價值。前者決定了用戶決策的時機性，后者決定了用戶決策的正確性。前者要求無人機減少偵察時間以盡快帶回信息，后者則要求無人機增加偵察時間以獲取更多目標的信息。在無人機資源有限的情況下，如何平衡相互矛盾的兩個需求以最大化用戶決策的戰略價值是一個嚴峻的挑戰。此外，戰場中通常存在多個決策用戶，它們具有不同的信息需求且所作決策的重要程度不同。如何對各用戶的決策效用進行綜合衡量并設計相應的路徑規劃方案也需要進一步研究。

6 結語

路徑規劃問題從路徑類型上分為運動規劃、軌跡規劃和導航3 類問題，從規劃類型上分為靜態路徑規劃和動態路徑規劃2 類。無人機路徑規劃環境和路徑表示方法包括連續數學表示、圖表示方法以及網格表示法。無人機路徑規劃算法主要分為智能算法和傳統數學算法兩大類。傳統數學算法利用數學推導求解路徑規劃問題，智能算法則通過迭代方式在短時間內獲取次優解。此外，路徑規劃算法還需要考慮偵察目標約束，通常包括能耗約束、時間約束和偵察收益約束3 類。下一步工作還需要考慮無人機為不同優先級用戶提供偵察服務的情況，包括面向多個用戶的協同偵察能耗問題，面向不同優先級用戶的信息獲取時間問題和多用戶決策效用問題。