多無人機飛行路徑自動規劃算法研究

馬傳焱

(中國人民解放軍63961部隊，北京100012)

0 引言

隨著無人機技術的發展，作戰任務應用領域不斷擴大，無人機作戰樣式也由單機工作，朝著一站多機、多站多機的網絡式協同作戰方式發展。任務的增加、多機協同戰術應用的變化，迫切需要對無人機任務實行有效組織與科學管理。基于此，面向多無人機作戰的任務規劃重要性凸顯，其能力要求也越來越高。

美國是世界上最先發展任務規劃技術的國家，典型的聯合任務規劃系統(Joint Mission Planning System，JMPS)主要用來制定飛行威脅分析、飛機航路和攻擊協調等航空任務計劃;使用靈活的集成模型，允許用戶根據需要進行系統配置和開發。我國的任務規劃研究才剛剛開始，許多技術尚處于探索階段。在無人機自動任務規劃方面，主要針對單機的路徑規劃，對多機協同、任務分配、載荷使用和戰術運用等方面較少涉及，尚不具備執行復雜戰術任務規劃的能力。

簡單說來，無人機路徑規劃的目的是尋找最佳飛行航線，確定該航線上對載荷設備的控制策略，使無人機在確保飛行安全的前提下，發揮載荷設備的作用，完成各項任務。從多無人機路徑規劃問題抽象出的數學物理模型，實質上屬于協調控制問題。隨著戰場環境、武器系統、作戰樣式復雜度的增加以及對無人機性能和多任務要求的提高，無人機控制難度和效果之間的矛盾更加突出，這些實戰要求用傳統的人員智力無法完成，需要借助現代智能計算的優勢，從作戰任務、指揮決策、環境影響、飛行控制和無人機能力等方面，優化出多種滿足不同作戰目的的解決方案。

常用的路徑規劃算法有遺傳算法［1-5］、Dijkstra求最短路徑法［6，7］、Voronoi圖搜索法［8］(以下簡稱“V 圖”)、A* 算法［9，10］、啟發式搜索法［11］和神經網絡［12］等多種方法。

本文給出了基于V圖的多無人機飛行路徑自動規劃算法，對傳統V圖進行了改進，并對應用中的威脅源建模、估價函數的組織及航路優化等技術進行了說明，為多無人機協同航路自動生成過程提供參考。

1 威脅建模

威脅建模(Threat Modeling)是指對地面和空中各種不同類型的固定障礙物或具有輻射覆蓋特征的威脅源進行形式化描述，以便于無人機在飛行過程中進行威脅規避。主要包括探測性威脅和殺傷性威脅。

1．1 探測性威脅建模

探測性威脅主要是探測雷達對無人機產生的威脅，其威脅區域投影在垂直面上為一個扇形區域，最大威脅半徑為Rmax，張角為α，雷達水平最大威脅距離Rm=Rmaxsinα，無人機與雷達之間的水平距離為R，威脅系數為k，雷達的探測概率為:

1．2 殺傷性威脅建模

殺傷性威脅主要來源為各種地空導彈和高炮等，常用的一種模型認為威脅源作用范圍內的無人機所受威脅程度與其到威脅源的距離成泊松分布關系，即無人機距離威脅源越遠，所受威脅度越小，反之亦然。具體計算方法如下:

2 算法描述

2．1 V圖的建立

從數學上理解，平面N個點中兩鄰點直線的垂直平分線連接組成連續多邊形，多個多邊形拼接組成V圖。賦予其物理意義時，取威脅源為中心點并視作生長目標，按威脅度將垂直平分線向四周擴張直到相遇，構造出威脅分布的V圖具有這一性質:相鄰2個威脅源生長目標的公共Voronoi邊是其間威脅度最小的位置。根據式(1)和式(2)威脅度計算模型來看，簡單依據歐式、大圓或等角距離所構建的普通V圖不足以具備這一性質，需根據各威脅源的威脅度等價關系，確定其在距離意義上的相對擴展速度來建立擴展V圖。當威脅源同類型時，僅存在戰技指標(威脅強度)上的差別，根據無人機與威脅源的距離—威脅度—相對擴張速度的方式即可計算。當存在探測性和殺傷性2種不同類型的威脅源時，因威脅度性質不同，無法直接比較大小。將威脅度轉換為距離來確定相對擴張速度的方式已不可行，需依據專家知識確定威脅等價系數，建立威脅之間的等價關系程度，然后在V圖中求解。

如圖 1所示，圖 1(a)為數學意義上的 V圖，圖1(b)為考慮威脅類型和強度差別建立等價關系，確定威脅源生長目標的相對擴張速度所建立V圖。其中，威脅源1是威脅源2、3、4和5擴張速度的1.5倍。比較圖1(a)和圖1(b)可以看出，由于威脅源1的擴張速度快，V圖的邊明顯遠離威脅源1而靠近威脅源2和3。當以擴展V圖的邊作為無人機路徑段時，其威脅度是對各類威脅源作用的綜合度量，可更真實反應戰場中威脅源對無人機任務的影響。

圖1 2類V圖的比較

2．2 基于V圖的多無人機路徑表示

基于構建的戰場環境V圖，無人機的飛行路徑可以表示為:V圖的頂點為路徑中途點，邊為路徑段，從無人機起飛點到目標的V圖邊的組合構成多條路徑。依該方法分別為各個無人機選擇，可構成多無人機協同初始路徑圖，如圖2所示，粗實線表示無人機的飛行路徑。

圖2 基于V圖的多無人機路徑示意

2．3 基于V圖的多無人機路徑規劃算法

V圖中第i條邊的權值采用以下代價函數計算:

式中，Ji為第i條邊的權值;Jt，i為第i條邊的威脅代價;Jf，i為第i條邊的油耗代價。綜合考慮威脅及油耗對航路影響引入系數k，其值由航路制訂者根據實踐經驗和按作戰要求設定。

威脅代價與無人機的雷達可探測性指標和殺傷性威脅參數指標相關聯。當無人機沿V圖第i條邊飛行時，所受威脅代價可以理解為該條邊上所有點的威脅代價積分。近似地在每條邊上平均采樣若干點，計算所有威脅對各點的影響，積分求和后獲得近似每條邊的威脅代價。

式中，N為探測性威脅的數目;M為火力威脅的數目;d代表第i條邊上的采樣點到任意一個威脅點的距離。

3 仿真結果

仿真實例中，整個戰場上分布24個作用范圍不同的威脅，要求為UAV規劃出當前點到目標點的初始路徑。

設置規劃參數K=0.5，算法仿真結果如圖3(a)所示，從圖3(a)中可以看出，路徑完全避開了威脅區，并選擇了代價最小的路徑。且由于采用Dijkstra最小路徑搜索方法獲得的路徑，因此獲得的是確定的解。

下面驗證不同的規劃參數對于規劃結果的影響。K越大越考慮燃油消耗對規劃結果的影響，K越小則更傾向考慮威脅接近代價。調整參數K=0，初始路徑規劃結果如圖3(b)所示。從規劃結果可以看出，圖3(b)為了盡量規避威脅，需要付出較多的燃油代價。

經過1次優化后，路徑在避開威脅區的前提下被盡量拉直;經過2次優化后，消除了航路上的角度較小的轉彎，規劃出的路徑更符合無人機的機動特性，如圖4所示。

當無人機和目標數量均增加到16個，在已經進行了任務分配的基礎之上，同時生成多架無人機的飛行路徑，如圖5所示。

圖3 基于V圖的路徑規劃

圖4 路徑規劃的優化

圖5 多無人機路徑自動生成

4 結束語

上述的路徑自動規劃算法可以應用在2種典型的多無人機任務(協同攻擊和協同偵察)。仿真結果表明，本文基于V圖解決了多無人機航路規劃問題中的威脅源建模、估價函數的建立以及航路優化算法等方面問題，給出的方法能夠在保證算法有效性的基礎上，減小了搜索空間，提高了規劃的實時性。算法兼顧了生存能力、飛行距離和人為決策等多個約束條件，具有較好的魯棒性。

［1］ 鄭昌文，李 磊，徐帆江，等.基于進化計算的無人飛行器多航跡規劃［J］.宇航學報，2005，26(2):224-227.

［2］ 羅亞中，唐國金，梁彥剛.基于分解策略的SSO發射軌道遺 傳 全 局 優 化 設 計［J］.航 空 學 報，2004，25(5):443-446.

［3］ 張 旺，王黎莉，伍 洋.基于遺傳算法的陣列天線綜合及分析［J］.無線電通信技術，2011，37(4):28-30.

［4］ 梁曉輝，吳 威，趙沁平.大規模真實地形數據中的全局路徑規劃方法——基于遺傳算法的研究［J］.計算機研究與發展，2003，39(3):301-306.

［5］ 吳曉濤，孫增圻.用遺傳算法進行路徑規劃［J］.清華大學學報(自然科學版)，1995，35(5):14-19.

［6］ 胡曉磊，胡朝暉，江洋溢.基于Dijkstra算法的水平航跡規劃［J］.火力與指揮控制，2004，29(4):86-92.

［7］ 馬云紅，周德云.飛行器低空突防威脅建模與航跡優化算法［J］.火力與指揮控制，2004，29(5):31-37.

［8］ 趙文婷，彭俊毅.基于VORONOI圖的無人機航跡規劃［J］.系統仿真學報，2006，18(增 2):159-162.

［9］ 周成平，陳前洋，秦 筱.基于稀疏A*算法的三維航跡并行規劃算法［J］.華中科技大學學報(自然科學版)，2005，33(5):42-45.

［10］穆中林，魯 藝，任 波，等.基于改進A*算法的無人機航路規劃方法研究［J］.彈箭與制導學報，2007，27(1):297-300.

［11］ IKEDA T，HSU M Y，IMAI M.A Fast Algorithm for Finding Better Routes by AI Search Techniques［C］∥IEEEVehicleNavigation＆InformationSystems Conference Proceedings，1994:291-296.

［12］ ARAúJO F，RIBEIRO B，RODRIGUES L.A Neural Network for Shortest Path Computation ［J］.IEEE Transactions on Neural Networks，2001，12(5):1 067-1 073.