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

馬傳焱

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

0 引言

隨著無人機技術(shù)的發(fā)展，作戰(zhàn)任務(wù)應(yīng)用領(lǐng)域不斷擴大，無人機作戰(zhàn)樣式也由單機工作，朝著一站多機、多站多機的網(wǎng)絡(luò)式協(xié)同作戰(zhàn)方式發(fā)展。任務(wù)的增加、多機協(xié)同戰(zhàn)術(shù)應(yīng)用的變化，迫切需要對無人機任務(wù)實行有效組織與科學管理?；诖耍嫦蚨酂o人機作戰(zhàn)的任務(wù)規(guī)劃重要性凸顯，其能力要求也越來越高。

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

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

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

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

1 威脅建模

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

1．1 探測性威脅建模

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

1．2 殺傷性威脅建模

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

2 算法描述

2．1 V圖的建立

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

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

圖1 2類V圖的比較

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

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

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

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

V圖中第i條邊的權(quán)值采用以下代價函數(shù)計算:

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

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

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

3 仿真結(jié)果

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

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

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

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

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

圖3 基于V圖的路徑規(guī)劃

圖4 路徑規(guī)劃的優(yōu)化

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

4 結(jié)束語

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

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

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

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

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

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

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

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

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

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

［10］穆中林，魯 藝，任 波，等.基于改進A*算法的無人機航路規(guī)劃方法研究［J］.彈箭與制導(dǎo)學報，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.