基于多指標動態優先級的無人機協同路徑規劃

王祝，張夢通，張振鵬，徐廣通

1.華北電力大學（保定） 自動化系，保定 071003

2.浙江大學 湖州研究院，湖州 313002

近年來，無人機（Unmanned Aerial Vehicle，UAV）集群在物流配送、電力巡檢等領域發揮著越來越重要的作用［1-2］。為保證多架無人機在復雜環境中高效協同完成任務，需要對無人機集群的路徑進行科學合理的設計［3-4］。

多無人機協同路徑規劃需要在考慮協同約束的情況下，以最小代價合作完成任務為目標［5-7］，為多架無人機生成安全可行的飛行路徑。協同約束的處理是多無人機協同路徑規劃的關鍵，按照約束處理方式的不同，可分為耦合規劃和解耦規劃兩類［8］。與耦合規劃相比，解耦規劃結果雖然不能保證路徑最短，但具有顯著的效率優勢。

優先級規劃作為解耦規劃的主要方式［9-10］，最早由Erdmann 和Lozano-Pérez［11］提出，是指在規劃過程中優先級低的個體規避優先級高的個體，以實現集群個體之間避撞約束的解耦。目前，優先級解耦規劃方法在自動導引運輸車（Automated Guided Vehicle，AGV）領域已得到廣泛研究［12-15］。文獻［12］采取粒子群優化算法對多AGV 進行路徑規劃，提出基于時間優先級的粒子迭代更新機制，加快了求解收斂速度，但由于優先級固定，可能出現某個AGV 長時間等待導致系統效率變低。文獻［13］提出一種基于動態優先級和改進蟻群算法的多AGV 路徑規劃算法，根據AGV 電池剩余電量分配優先級，提高了AGV 電力使用效率，但仿真環境簡單，AGV規模小，當規模增加時，算法效率難以保證。文獻［14］提出基于時間窗的優先路徑規劃算法，計算受影響AGV 與延遲AGV 之間的相對距離來更新優先級，解決了多輛AGV 的時延問題。但在無延遲情況下，采用動態窗口算法規劃路徑，該方法可能會得到局部極小值。文獻［15］提出事件驅動的優先級更新邏輯，分為2 個優先級模塊以應對AGV 單機或編隊運動下的優先級更新，旨在保證編隊運動及單機通過交叉路口時避免碰撞。其中，在計算通過交叉路口AGV 優先級時，賦予更接近公共路點AGV 更高的優先級，雖然該方法能解決當前沖突，但降低了結果最優性。

在多無人機協同路徑規劃方面，文獻［16］提出了一種基于耦合度的優先級生成準則，利用無人機群潛在碰撞表示無人機間的耦合程度，提高了規劃效率，但沒考慮總路程等影響規劃質量的因素，路徑質量難以保證。文獻［8］將滾動規劃與優先級規劃結合，將無人機群路徑規劃問題分解成單無人機短時域路徑規劃問題，增強了算法實時性，但優先級固定，存在優先級不合理導致集群整體規劃效率變低的情況。文獻［9］考慮飛行時間短、剩余飛行空間大的無人機成功規避其他無人機的概率更大，提出了一種飛行時間驅動的動態優先級解耦機制，提高了收斂速度，但該機制僅考慮了飛行時間對協同規劃的影響，沒有充分考慮其他指標，如航路長度、碰撞風險等，這些因素對多無人機協同路徑規劃的有效性和實用性也具有重要意義。因此，需要綜合考慮多種因素，以制定更加全面、準確的優先級協同路徑規劃策略。

在優先級協同約束處理機制的基礎上，單機路徑規劃算法也是影響協同路徑規劃效率的關鍵。針對個體路徑規劃，Daniel 等［17］將可視線引入A*算法，通過判斷擴展節點與父節點之間是否存在可視線，實現了任意角度搜索的Theta*算法。但Theta*算法要對所有遍歷過的節點進行視線檢查，因此當柵格規模很大時，算法效率較低。為提高路徑規劃效率，Nash 等［18］對Theta*算法的搜索過程進一步改進，提出了Lazy Theta*算法。Faria 等分別提出基于稀疏網格［19］和基于單一網格［20］的Lazy Theta*算法，減少了存儲空間和計算時間。但這2 種方法僅適用于稀疏環境的路徑規劃任務，對于密集環境下的路徑規劃存在不足。徐鵬飛等［21］針對機器人的運動學特性以及環境對路徑規劃結果的影響，提出了基于環境優化的Lazy Theta*算法，考慮環境中的動態障礙物，能夠考慮環境的動態變化。但該算法計算復雜度高，需要較長的計算時間。此外，上述工作都是針對單機的路徑規劃研究，在多機路徑規劃方面如何減少基于Theta*的協同規劃復雜度有待研究。

為了更好地權衡協同規劃效率以及路徑質量，本文的主要工作包括以下3 點。

1） 提出了一種基于多指標動態優先級的單邊避碰機制，克服固定優先級存在的死鎖問題；同時，考慮影響求解效率和路徑質量的多個指標，構建動態優先級的生成模型，實現無人機優先級的合理分配。

2） 針對優先級協同框架下的單機路徑規劃，提出基于擁堵權值地圖的Lazy Theta*算法，降低集群間沖突發生的可能性，提高求解速度。

3） 構建“路徑重規劃+起點等待”的局部沖突組合規避策略，可針對沖突情況選擇合理的消解策略，以提高集群協同規劃的求解速度。

1 問題描述

本節針對多無人機協同路徑規劃問題，完成任務指標和約束條件的構建。本文開展的無人機協同路徑規劃研究基于以下假設：

1） 無人機均以固定速度、高度飛行，因此只考慮二維平面的避障策略。

2） 無人機都能與中央控制器進行通信。

3） 處理局部沖突過程中，無人機存在一條能繞開其他無人機起點到達對應目標點的路徑。

1.1 任務指標

通過多無人機的整體任務完成時間評判任務完成質量。

整體任務完成時間T為無人機集群中最大任務完成時間，反映了無人機系統的任務完成效率，可表示為

式中：Ti為第i個無人機的任務完成時間。

1.2 協同路徑規劃約束

1） 電量約束

要保證每架無人機都能完成任務，完成任務時第i架無人機的剩余電量記為pie，剩余電量pie滿足：

式中：emin為保證無人機安全降落的最低電量。

2） 障礙規避約束

基于柵格化地圖描述，可用一定數量的柵格區域來近似障礙。在無人機飛行過程中，為了保證其能規避環境中的障礙，無人機中心與障礙物邊緣柵格中心之間距離D需滿足：

式中：L為無人機軸距；R為柵格分辨率；s為飛行安全距離。

路徑規劃中將無人機作為質點，因此需根據無人機實際尺寸與飛行安全距離對障礙物邊緣進行膨脹，以保證無人機不會與障礙發生碰撞。

3） 機間避撞約束

為確保無人機之間不會發生碰撞，需要考慮機間碰撞約束。因此無人機中心點之間的距離d需滿足：

式中：c為機間安全距離。

2 協同路徑規劃算法

2.1 協同規劃總體流程

協同路徑規劃分為單機路徑規劃層和多無人機系統協調層，單機路徑規劃層為每架無人機規劃出與環境中障礙無碰撞的全局路徑，再經過多無人機系統協調層完成無人機之間的協同運動。協同規劃總體流程如圖1所示。

圖1 協同路徑規劃總體流程圖Fig.1 Flow chart of cooperative path planning

單機路徑規劃層的流程說明具體見2.4 節，下面主要對多無人機系統協調層的關鍵步驟進行說明。

1） 路徑點對應時刻的近似計算

在解耦框架下，速度為v=[vxvy]，時間步長為dt，第i架無人機在第k個時間步長的橫縱坐標可由式（5）計算，并將第i架無人機的橫縱坐標集合分別存放到飛行橫縱坐標集合Φx=｛x1，x2，…，xn｝，Φy=｛y1，y2，…，yn｝。

式中：β為上一時刻位置到當前位置的方向角。

2） 沖突判斷和優先級更新

考慮機間協同約束，每架無人機根據上一步迭代過程中其他無人機在對應時刻的位置，來計算局部沖突。將沖突點位置以及發生沖突的無人機編號分別存放到Φpos和ΦUAV集合中。計算在同一點存在機間碰撞的無人機的優先級，完成更新。

3） 沖突消解

在優先級引導的單邊避碰機制下，首先系統會先解決起點沖突，然后根據預設的避障策略選擇規則，令優先級低的無人機采取相應避障策略。一旦完成一輪沖突消解，系統會進行下一輪迭代，直至獲得滿足全部協同路徑規劃約束的飛行路徑。

2.2 多指標動態優先級更新策略

在協同規劃中，處理機間碰撞的方式直接影響到規劃效率和結果。由于每架無人機只能獲得他機上一次迭代的位置信息，在相互避碰機制下，若沖突雙方均采取路徑重規劃的策略，可能會出現路徑反復振蕩。為解決這個問題，采用動態優先級引導的單邊避碰機制，通過不斷更新優先級順序，使高優先級無人機具有更大的行駛權利，避免與低優先級無人機發生碰撞。此外，不同的優先級計算方法決定了局部沖突發生時的不同決策方案，對規劃速度和質量有重要影響。

本文動態優先級的確定考慮多個指標，具體包括以下4 個。

1） 碰撞風險

使用沖突次數作為指標衡量無人機之間的碰撞風險。各無人機之間的沖突次數計算公式如式（6）所示：

式中：Ci(ΦUAV)為編號為i的無人機在沖突無人機集合ΦUAV中出現的次數即沖突次數；D(ΦUAV)為沖突無人機集合長度。遍歷ΦUAV中每個元素，若等于i，沖突權值δ為1，Ci(ΦUAV)累加，直至遍歷結束。

2） 總路程S

無人機飛行路徑的累計距離。

3） 等待時間Tw

無人機為消解機間沖突執行等待策略所等待的時間步長。

4） 剩余路程比Sr

即發生沖突時的剩余路程Sc和總路程S的比值，其表達式為

優先級更新策略的確定分為如下2 個部分。

1） 當碰撞風險不同時，無人機的碰撞風險越大，優先級越低。

沖突次數越多代表對應無人機碰撞風險越大。此時令碰撞風險大的個體執行規避策略有更大概率規避更多無人機。因此具有較高碰撞風險的無人機被賦予較低的優先級。

2） 當碰撞風險相同時，考慮總路程S、等待時間Tw、剩余路程比Sr，構建綜合多指標的優先級計算模型，如式（8）所示。其中，無人機的綜合指標Pi越大，其優先級越高。

式中：α、β、γ為對應指標的影響權重；、和為歸一化后的各指標取值。其計算公式分別如式（9）～式（11）所示：

為優化任務完成效率，將更高的飛行權利分配給符合以下條件的無人機：總路程長、等待時間長、剩余路程比大。總路程越長的無人機需要更長的時間來完成任務，但其調整空間較小，因此其優先級較高。同時，過多地讓同一無人機執行等待策略會延長整體任務完成時間，降低系統執行效率，因此等待時間越長的無人機也具有較高的優先級。而剩余路程比大的無人機具有更多的剩余飛行距離，賦予其更高的飛行權利有助于降低整體的飛行時間。

各個指標的權重α、β、γ選用層次分析法（Analytic Hierarchy Process，AHP）來確定，具體做法如下所示。

1） 構建如圖2所示的層次模型。

圖2 層次模型Fig.2 Hierarchical model

2） 構造表1所示的比較判別對矩陣A。

表1 比較判別對矩陣Table 1 Pairwise comparison discriminant matrix

3） 權重計算

由各準則層對目標層權重aij根據式（12）計算特征向量的近似值Wi，再將特征向量標準化后得到式（13）所示的權重向量W。

4） 一致性檢驗

為了判斷比較判別對矩陣是否存在邏輯性矛盾，需要通過式（14）進行一致性檢驗：

式中：λmax為最大特征根；N為比較判別對矩陣階數；CI為一致性指標；平均隨機一致性指標RI可根據對比矩陣的階數給出［22］。當隨機一致性比率CR＜0.1 時認為計算所得的權重是正確且合理的。

2.3 沖突組合規避策略

針對局部機間碰撞規避，無人機一般采取路徑重規劃策略尋找規避沖突點的路徑，受AGV采用等待策略消解機間沖突啟發，等待策略可以避免大范圍路徑重規劃從而降低計算復雜度。考慮到多旋翼無人機能夠自主懸停，在安全點懸停等待一段時間同樣能規避沖突。基于第1 節中的假設3）可知，各個無人機的起點均可以作為安全點，因此本文采取“路徑重規劃+起點等待”的組合策略規避機間沖突。

采用路徑重規劃的方式協調能力強，但規劃耗時相對較長；采用起點等待的策略，由于無人機無需考慮避障，因此規劃耗時短，而對于圖3所示的沖突，起點等待策略下無人機飛行時間延長。因此需要結合2 種方式的特點，根據沖突情況建立策略選擇公式，可表示為

式中：θ為沖突向量之間的夾角，當θ≥180°-ε時，執行路徑重規劃策略，否則執行起點等待策略；ε為容許值，可人為給定，以權衡協調能力及求解速度。

在局部碰撞檢測中，需要將每架無人機ui（i=1，2，…，n）與其他無人機uj（j≠i）路徑進行比較，即根據式（3）依次計算同一時刻Tk時ui的路徑點pki和uj的路徑點pkj之間的距離是否滿足協同約束，將不滿足協同約束的坐標集合Φpos記為：

沖突無人機集合可表示為

沖突向量之間的夾角θ，可表示為

當θ=180°時，表示沖突無人機對沖飛行，若執行起點等待策略，會出現路徑更新后依然存在沖突的情況，起點等待策略效率變低，此時就應選擇路徑重規劃策略。

另外，有一種特別情況需要指出，如圖4所示的起點沖突，起點沖突定義為：假設UAVi的優先級大于UAVj的優先級，且UAVj的起點在UAVi的路徑上。

圖4 起點沖突示意圖Fig.4 Schematic diagram of start-point conflict

在多指標動態優先級的單邊避碰機制下，由于高優先級個體會無視優先低個體，當發生起點沖突時，由于UAVi的優先級更高，UAVi無視UAVj，但s2并非是安全點，UAVj采取起點等待策略無法成功規避沖突。

因此，當發生起點沖突時，將優先級高個體加入待調整無人機集合，執行沖突規避策略。

利用組合策略規避沖突偽代碼如算法1所示，具體流程如下所示。

步驟1（第1～3 行）確定規避策略

遍歷沖突無人機集合，r_flag 為重規劃標志位，當θ≥180°-ε時，r_flag 為True，即執行重規劃策略。否則執行起點等待策略。

步驟2（第4～13 行）執行重規劃策略

算法1 沖突規避偽代碼Input：待調整無人機集合Φ?adj、沖突無人機集合ΦUAV、沖突位置集合Φpos Output：飛行橫縱坐標集合Φx、Φy 1.Φwait←? ∥記錄執行過起點等待策略的無人機集合2.for i，uav in enumerate（ΦUAV）：3.（r_flag，col_p）←select_strategy（Φpos）4. if r_flag：5. rpath_uav←Φ?adj［i］6. k←uav.index（rpath_uav）7. Col_loc←Φpos［i］［0］［k］ ∥待避開位置8. new_path←Exe_replan_strategy（rpath_uav，Col_loc） ∥重規劃9. if not new_path： ∥無法重新路徑規劃10. if Φ?adj［i］ not inΦwait：11. （Φx，Φy）←Exe_wait_strategy（Φ?adj［i］）12. else：13. （Φx［Φ?adj［i］］，Φy［Φ?adj［i］］）←draw_pos（new_path）14. else：15. if Φ?adj［i］ not in Φwait：16. （Φx，Φy）←Exe_wait_strategy（Φ?adj［i］） ∥起點等待17. if not col_detection（）［0］：18. break 19.return Φx，Φy

令連續沖突點的第一個為待規避位置，將其視為障礙后進行路徑規劃，生成新路徑new_path，若無法生成新路徑，即new_path 為空，則執行起點等待策略規避沖突。

步驟3（第14～16 行）執行起點等待策略

為避免在同一輪迭代過程中某無人機重復執行起點等待策略，Φwait記錄一輪迭代中執行過起點等待策略的無人機。判斷當前無人機在本輪迭代是否執行過起點等待策略，若沒有，在起點等待一個時間步長dt。

步驟4（第17～19 行）判斷是否存在沖突

處理完本輪迭代中所有沖突后，判斷系統是否還存在沖突，若系統中已無沖突，則跳出循環，否則繼續下一輪迭代。

2.4 單機路徑規劃的改進Lazy Theta*算法

在協同規劃總體流程中，每架無人機需要進行路徑規劃以達到任務點，Lazy Theta*算法［17］作為A*的改進算法，能實現任意角度的路徑規劃，消除了A*算法結果存在的“Z 字”抖動現象。

本文為了降低沖突發生的可能性，在Lazy Theta*算法基礎上加入擁堵權值地圖（記為Weighted Map Lazy Theta*，簡稱WM-Lazy Theta*），使無人機在單機規劃層能避開“擁堵路段”，提高飛行效率。

WM-Lazy Theta*算法流程如圖5所示，下面主要對本文改進所涉及的擁堵權值地圖更新和節點代價計算進行說明。

圖5 WM-Lazy Theta*算法流程圖Fig.5 Flowchart of WM-Lazy Theta*

1） 擁堵權值地圖初始化和構建

將柵格地圖劃分為m個擁堵檢測區域，構成擁堵權值地圖。擁堵檢測區域大小影響路徑規劃的效率及質量，若將每個柵格都作為擁堵檢測區域，會增加路徑規劃復雜度；若合并過多的柵格構成大的擁堵檢測區域，則會導致規劃失去更優的路徑結果。文中的擁堵檢測區域劃分方法如下。

步驟1確定最小擁堵檢測區域

在構建柵格地圖時，柵格分辨率與無人機軸距相同，即為L。每個柵格即為一個最小擁堵檢測區域。

步驟2設置比例因子τ

擁堵檢測區域面積為WH τ2，W和H分別為柵格地圖的寬和高。

步驟3確定擁堵檢測區域柵格數量

根據擁堵區域面積及柵格分辨率即可求得每個擁堵檢測區域包含柵格數量為WH(τ2L2)。

步驟4為每個擁堵檢測區域編號排序

從柵格地圖左上角開始，按照從左到右、從上到下的順序遍歷所有的擁堵檢測區域，分配從0 開始的連續整數作為編號。

每規劃好一條路徑后更新擁堵權值地圖：記錄該路徑在每塊區域的占有時間（進入和離開時間），并給定初始擁堵權值。若第i塊區域（i=1，2，…，m）存在重復時間段，對應的擁堵權值進行疊加。

2） 節點代價計算

在擴展節點的過程中，計算到達當前節點的時間，查詢當前節點所在區域的占有時間。若當前時間在占有時間內，則令M等于占有時間對應的擁堵權值，否則令M=0。節點價值的評估函數表示為

式中：f為節點的代價值；g為累計代價值，表示當前點到起點的路徑長度；h為估計代價值，表示當前點到終點的路徑長度；w為估計代價值的權重，w越大表示節點越傾向于“接近終點”。

圖6 給出了一個權值地圖的示例。想定為一個20×20 的柵格環境，每個柵格大小為1 m×1 m，比例因子設為10，因此將2×2 的柵格劃分為一個擁堵檢測區域，飛行速度為0.5 m/s，給定10 組起始點和終點，利用WM-Lazy Theta*按序號依次規劃路徑，圖6 是規劃完成后t=10 s 時的擁堵權值地圖。若繼續添加任務點進行路徑規劃，則在現有擁堵權值地圖基礎上進行節點代價計算。

圖6 t=10 s 時擁堵權值地圖Fig.6 Congestion weighted map at t=10 s

圖7 為引入擁堵權值地圖后擴展節點示意圖。當規劃第4 條路徑時，P點擴展的節點Pnext1、Pnext2占有時間分別為（9.4，12.2）s、（9，11）s，t=10 s 時對應區域內柵格的擁堵權值M=3，而在Pnext節點的占有時間（9，11）s 內所在區域沒有被訪問過，M記為0。分別對這3 個節點計算代價值得到fnext2＞fnext1＞fnext。因此Pnext為最優節點，達到避開擁堵區域的效果。

圖7 引入擁堵權值地圖后擴展節點Fig.7 Expanded nodes after introducing congestion weighted map

3 仿真試驗與分析

為驗證所提算法的可行性和優勢，開展多無人機協同路徑規劃仿真對比試驗。試驗中，無人機飛行區域為20 m×12 m，設置柵格規模為50×30，使柵格分辨率與無人機軸距相同為0.4 m，每架無人機飛行速度均相同且恒定，設置為0.2 m/s。容許值ε=30°，最低安全電量emin設為5%，機間安全距離c設為0.1 m，飛行安全距離s設為0.1 m。

為模擬無人機運動過程中的電量損耗，采用下式表示t時刻的電量Et。

式中：stepw為等待步長；Es為無人機的起始電量。

3.1 協同路徑規劃算法有效性驗證

分別選取無人機數量為5、10、15，開展協同路徑規劃算法有效性試驗。擁堵權值地圖設置中，比例因子設為10，即每個區域大小為5×3。

首先確定多指標動態優先級的指標權重。根據文獻［23］所示的標度方法構造表2所示的比較矩陣，利用式（12）和式（13）求得各項指標權重。α=0.599 5，β=0.274 9，γ=0.122 9，再通過式（14）計算CR得CR=0.039＜0.1，通過一致性檢驗，說明該權重合理。

表2 權重計算兩兩比較矩陣Table 2 Weight calculation pairwise comparison matrix

圖8 給出了5、10、15 架無人機的協同路徑規劃結果圖。圖9 給出了3 種規模下最小距離變化曲線。針對障礙規避約束，根據仿真試驗設定可得式（3）中()L+R2+s=0.5 m。由圖9（a）可知，3 種規模下，無人機與障礙物之間的最小距離在任意時刻均大于0.5 m，因此，全局路徑滿足障礙規避約束。從圖9（b）可知，3 種規模下機間最小距離均大于無人機軸距與機間安全距離之和0.5 m，滿足協同約束。圖10 展示了3 種集群規模下完成任務的剩余電量，由圖10 可知，每個無人機的剩余電量均大于最低安全電量5%，即滿足電量約束。

圖9 3 種規模下最小距離變化曲線Fig.9 Minimum distance for three swarm-scale scenarios

圖10 3 種集群規模下完成任務的剩余電量Fig.10 Remained electricity for three swarm-scale scenarios

3.2 對比試驗

本文提出的規劃算法主要包含3 個改進部分：多指標動態優先級、WM-Lazy Theta*和組合規避策略，為驗證每一部分的改進效果，分別開展優先級方法對比、單機路徑規劃方法對比和規避策略對比試驗。

3.2.1 多指標動態優先級效果分析

為了分析本文提出的多指標動態優先級方法的求解效果，將其與飛行時間驅動的動態優先級方法［9］進行對比。

表3 為3 種無人機規模下，2 種優先級協同路徑規劃算法求得的的任務完成時間與規劃耗時。由表3 可知，無人機規模為5 架時，多指標動態優先級相比飛行時間驅動的動態優先級雖然任務完成時間略有增加，但規劃耗時減少85.0%，當規模增加至10、15 架時，多指標方法不僅任務完成時間較飛行時間驅動方法減少了8.23、3.8 s，規劃耗時分別減少74.4%和47.8%。

表3 不同優先級方法的求解結果對比Table 3 Comparison of results of two priority-based methods

表4 給出了5、10、15 架無人機協同規劃過程中的優先級計算結果示例，來分析2 種優先級確定方法對規劃結果的影響。表4 中｛i，j｝表示無人機i和無人機j存在沖突，且為無人機i優先級小于無人機j。圖11～圖13 分別給出了3 個示例下利用飛行時間驅動方法和多指標方法計算優先級過程中的指標值。

圖11 5 架無人機第4 次迭代時的優先級指標值Fig.11 Priority index values at 4th iteration for 5 drones

由圖11（a）可以看出，在5 架無人機協同規劃的第4 次迭代中，對于飛行時間驅動的動態優先級方法，由于UAV3的總飛行時間最短，因此UAV3在與其他無人機發生沖突時，總是UAV3執行規避策略。在5 架協同規劃的后續迭代過程中，也存在上述情況，使得UAV3的等待時間到達20 s，任務完成時間至104.57 s，但由表3 可知，該規模下整體任務完成時間為112.10 s，因此該規模下整體任務完成時間并沒有受到影響。

而對于多指標動態優先級方法，發生沖突的無人機中，UAV5與其他2 架無人機存在沖突，其余均為與其他1 架無人機發生沖突，因此UAV5碰撞風險最大，優先級最低。其余4 架無人機的優先級由圖11（b）中無人機各個指標的歸一化值代入式（8）得出：P1=0.524 5，P2=0.305 7，P3=0.07，P4=0.65。設定的指標權重中，總路程與等待時間占主導地位且當前迭代步中各無人機的等待時間均為0 s，因此4 架無人機優先級的確定是由總路程確定。

由于整體任務完成時間并未受等待時間影響，此時2 種算法的主要區別在于對碰撞風險大的無人機的處理，多指標優先級優先令碰撞風險大的無人機做出規避，在任務時間上最優性受到限制，但縮短了規劃耗時。

由圖12（a）可知，在10 架無人機協同規劃的第10 次迭代示例中，對于飛行時間驅動的動態優先級方法，UAV5的總飛行時間最短。當UAV5與其他無人機發生沖突，始終令UAV5執行避障策略，導致UAV5等待時間達到43 s，最終使整體任務時間延長至128.05 s。而對于多指標動態優先級方法，首先由沖突次數計算各無人機的碰撞風險：UAV8＞UAV9=UAV1＞UAV6。若碰撞風險不同優先級即可確定。優先級相同時，將圖12（b）中各指標歸一化值代入式（8）得到：P1=0.689 2、P6=0.786 6、P8=0.039 3、P9=0.845 5。多指標動態優先級考慮了等待時間，因此即使UAV1的總路程大于UAV9，由于UAV9等待時間過長，最終計算結果P9＞P1。多指標動態優先級解決了某架無人機長時間等待的問題，于是多指標動態優先級的的整體任務完成時間及規劃時間較飛行時間驅動的動態優先級都有所降低。

圖12 10 架無人機第10 次迭代時的優先級指標值Fig.12 Priority index values at 10th iteration for 10 drones

當無人機數量增加至15 架時，飛行時間驅動的動態優先級會根據圖13（a）中的總飛行時間計算優先級，持續令同一無人機做出規避策略的問題難以避免，進而發生某一無人機長時間等待的情況。多指標動態優先級在確定UAV11碰撞風險最大后，根據圖13（b）所示的歸一化數據計算各無人機優先級數值：P2=0.640 2、P9=0.937 1、P11=0.563 5、P14=0.061 5、P15=0.476 5，更加準確地量化了各無人機之間的協調性，因此多指標動態優先級在整體任務完成時間和規劃耗時也均優于飛行時間驅動的動態優先級。

圖13 15 架無人機第22 次迭代時的優先級指標值Fig.13 Priority index values at 22nd iteration for 15 drones

可見，多指標動態優先級方法相比飛行時間驅動的動態優先級方法，不僅可以提高多無人機系統的協調能力，還能夠提高多無人機協同路徑規劃的計算效率。

3.2.2 WM-Lazy Theta*算法效果分析

為了評估WM-Lazy Theta*算法在協同規劃中的性能表現，在不同無人機規模下，將其與Lazy Theta*進行對比試驗。試驗中，將柵格地圖劃分為100 塊區域，在每個固定大小的擁堵檢測區域內，有3 架及以上無人機在同一時間段經過則認定為“擁堵區域”。

表5 給出了在無人機規模分別為5 架、10 架、15 架時，2 種單機規劃算法下的整體任務完成時間及規劃耗時。由表5 可知，雖然在整體完成任務時間上會略有增加，但WM-Lazy Theta*方法的求解速度較Lazy Theta*方法分別提高了59.6%、67.3%、65.0%。對比表明WM-Lazy Theta*通過考慮不同區域的擁堵情況，能夠更好地協調不同無人機之間的沖突，從而更快速地完成多機系統規劃全局路徑規劃。

表5 不同單機規劃算法的求解結果對比Table 5 Comparison of results of different UAV planning algorithms

圖14 展示了15 架無人機協同時2 種算法所規劃路徑對應的擁堵區域結果。由圖14 可知，WM-Lazy Theta*方法中“擁堵區域”相比Lazy Theta*大幅減少，且根據擁堵持續時間統計，改進算法對應“擁堵區域”的持續時間降低了72.1%。上述對比結果表明，WM-Lazy Theta*方法在規劃時能夠是使得無人機盡可能避開“擁堵路段”，擁有更快的協同規劃求解速度。

圖14 15 架無人機的擁堵區域對比Fig.14 Comparison of congestion area for 15 UAVs

3.2.3 組合策略效果分析

為驗證組合策略對規劃的性能影響，在3 種無人機規模下，開展組合策略、重規劃策略、起點等待策略對比試驗。表6 為3 種規模下3 種算法的任務完成時間和規劃耗時對比。通過表6 可知，僅有5 架無人機時，3 種策略下無人機整體任務完成時間幾乎相同。然而，隨著規模的增加，只執行等待策略的無人機的整體任務完成時間明顯高于另外2 種策略。因此在整體任務完成時間方面，重規劃策略最佳，而組合策略和起點等待策略的整體任務完成時間分別增加了2.81%、1.70%、1.60% 和4.70%、16.3%、28.5%。由于執行等待策略的時間復雜度更低，因此在規劃耗時上，起點等待策略表現出最優的性能，較組合策略、重規劃策略分別提高86.4%、85.5%、50.0%和90.5%、90.4%、70.3%。

表6 3 種規避策略的求解結果對比Table 6 Comparison of results of three avoidance strategies

通過上述分析可知，安全點等待策略求解速度快，但協調能力差，重規劃策略的協調能力好，但求解速度慢，而組合策略算法的協調能力與重規劃策略相當的情況下，求解速度得到提高。在避障過程中，求解速度和協調能力存在一定矛盾關系。求解速度快但可能會在協調能力上犧牲一定的表現，而協調能力強可能導致求解速度較慢。因此，在選擇避障策略時，需要綜合考慮實際場景的需求，以確定具體采用哪種算法。如果在緊急情況下需要快速應對，那么起點等待策略可能是更好的選擇；而如果需要較高的協調能力，那么重規劃策略算法可能更為合適。在一些需要求解速度和協調能力平衡的場景下，組合策略算法則可能成為一個更好的選擇。

4 結 論

本文針對多無人機協同路徑規劃提出了一種基于優先級的解耦規劃方法，主要包括：① 發展了基于多指標動態優先級的單邊避碰機制，并構建了動態優先級生成模型，實現了無人機優先級的合理分配；② 提出了基于擁堵權值地圖的Lazy Theta*算法，降低全局路徑中發生集群間沖突的概率，提高求解速度；③ 構建了“路徑重規劃+起點等待”的局部沖突組合規避策略，在保證協調能力的同時，提高了求解速度。最后通過對比試驗驗證了在不同無人機規模下，多指標動態優先級與WM-Lazy Theta*均提高了規劃質量及求解速度，組合規避策略在保證協調能力與路徑重規劃策略相當的情況下，實現了求解速度提升，證明了本文提出方法的有效性。