改進型Voronoi圖和動態(tài)權(quán)值A(chǔ)*算法的無人機航跡規(guī)劃

張?zhí)陨?，魯藝，張亮，呂躍

（空軍工程大學航空航天工程學院，西安710038）

改進型Voronoi圖和動態(tài)權(quán)值A(chǔ)*算法的無人機航跡規(guī)劃

張?zhí)陨?，魯藝，張亮，呂躍

（空軍工程大學航空航天工程學院，西安710038）

針對實際作戰(zhàn)環(huán)境中的不同威脅等級和不同威脅實體的威脅源，提出了改進型的Voronoi圖，并建立了基于改進型Voronoi圖的航跡規(guī)劃空間；基于A*算法的估價函數(shù)在不同階段對指標的敏感度不同，在傳統(tǒng)的啟發(fā)式A*搜索算法基礎(chǔ)上提出了動態(tài)權(quán)值A(chǔ)*搜索算法，提高了航跡搜索的效率，實現(xiàn)了航跡搜索過程快速性和準確性的結(jié)合。最后通過Matlab仿真計算出由動態(tài)權(quán)值A(chǔ)*算法得到的最優(yōu)航跡，并進行了航跡的平滑處理，仿真表明了該方法的可行性。

無人機，航跡規(guī)劃，改進型Voronoi圖，動態(tài)權(quán)值A(chǔ)*算法，航跡平滑

0　引言

Voronoi圖（以下簡稱V圖）作為一種基本的幾何結(jié)構(gòu)，以其十分接近于自然現(xiàn)象本質(zhì)的優(yōu)點，目前已經(jīng)被廣泛地應用于無人機航跡規(guī)劃。然而現(xiàn)有的關(guān)于V圖在無人機航跡規(guī)劃中的研究應用大多是將不同實體和相同實體不同威脅等級的威脅當作相同實體、相同等級的威脅來處理。A*算法作為一種啟發(fā)式搜索算法，能較好地滿足航跡規(guī)劃中的各種約束條件，在有限的可選狀態(tài)中確定一個最優(yōu)解，并在理論上保證收斂于全局最優(yōu)解，也已經(jīng)廣泛地應用于無人機航跡規(guī)劃的研究［1］。但無人機在執(zhí)行作戰(zhàn)任務(wù)的過程中，實際作戰(zhàn)環(huán)境并非總是和實際想象的完全相符合，為實現(xiàn)無人機航跡規(guī)劃快速性和準確性的結(jié)合，需要對傳統(tǒng)的A*算法做以改進。本文通過分析傳統(tǒng)V圖方法生成規(guī)劃空間的局限性，建立了基于不同威脅實體和威脅等級的規(guī)劃空間，采用動態(tài)權(quán)值A(chǔ)*算法進行航跡尋優(yōu)，得到全局最優(yōu)航跡。

1　基于改進型V圖的規(guī)劃空間建模

V圖生成規(guī)劃空間的方法是依據(jù)已知的威脅分布，以威脅源為中心，利用矢量生成法生成規(guī)劃空間，得到初始可行航跡點和航跡段。但這種傳統(tǒng)的生成規(guī)劃空間的方法在實際應用中存在較大的局限性，本文將指出該方法的不足，并對其進行改進，得到基于改進型的V圖規(guī)劃空間模型［2］。

1.1傳統(tǒng)V圖的局限性

實際的作戰(zhàn)環(huán)境中，存在不同種類和不同實體的威脅源，其威脅等級大小不同，如圖1所示。O1，O2，O3分別為威脅源中心，R1，R2，R3分別為威脅源O1，O2，O3在相同殺傷概率下的殺傷半徑，R1=3R2=3R3，CP，BP，AP分別為威脅源中心連線O1O2，O2O3，O1O3的中垂線，相交于P點，按傳統(tǒng)V圖的生成方法，線段PM，PN，PQ為規(guī)劃的初始航跡段。但該結(jié)果會使航跡段PM，PQ的一部分位于威脅源O1的殺傷半徑內(nèi)，增加了威脅源O1對無人機的殺傷概率。為此本文對V圖的生成規(guī)劃空間的方法做出改進。

圖1　傳統(tǒng)V圖生成的規(guī)劃空間

1.2改進型V圖的規(guī)劃空間建模

（1）如果威脅源的威脅等級相同，仍按傳統(tǒng)V圖方法生成規(guī)劃空間。

（2）如果威脅源的威脅等級不同，將威脅源進行分組，任取3個為一組，如圖2所示。

O1，O2，O3分別為威脅源的中心，R1，R2，R3分別其表示威脅等級，且有2R1=3R2=6R3，A、B、C分別為中心連線的比例等分點，具體位置依據(jù)威脅源威脅等級確定；點P為A，B，C構(gòu)成三角形的內(nèi)心，也是ΔABC的內(nèi)接圓P的圓心。

圖2　不同威脅等級生成的規(guī)劃空間

這樣，對于威脅源O1，O2，O3構(gòu)成的威脅區(qū)域，A，B，C，P為其4個初始航跡點，線段AP，BP和CP為初始航跡段，再將其與相鄰威脅源所構(gòu)成的其他初始航跡段相連，便得到最后的航跡規(guī)劃空間，稱之為“改進型V圖”規(guī)劃空間［3］。

（3）如果威脅源為不同威脅實體，為了規(guī)劃簡便起見，將其看作相同類型威脅處理。如圖3所示：威脅區(qū)域是由一個雷達威脅源和兩個地形威脅源共同組成，殺傷范圍仍用殺傷半徑R1，R2，R3來表示，且滿足2R1=3R2=3R3，圖中標識符的含義與圖2相同，采用基于改進型V圖方法進行規(guī)劃空間的生成，則線段AP，BP和CP即為初始可行航跡段。

圖3　不同實體威脅源生成的規(guī)劃空間

1.3模擬仿真示意

選取飛行區(qū)域為500 km×500 km的高威脅空間，該空間內(nèi)有兩種類型的威脅：一是雷達威脅，威脅值的大小有兩種等級，在對無人機80%探測概率下的殺傷半徑為100 km和50 km。二是地形威脅，假設(shè)也有兩種威脅等級，威脅半徑分別為50 km和25 km。對于該規(guī)劃威脅空間，利用基于改進型V圖生成規(guī)劃空間方法，采用Matlab進行分析，得到如圖4所示仿真結(jié)果。

圖4　改進型V圖生成的規(guī)劃空間

這樣，就得到改進型的V圖的規(guī)劃空間，再將起始點和目標點與初始規(guī)劃空間中幾個最近的多邊形頂點相連，得到了一個從起始點到目標點的有向圖，然后便可找出若干條從起始點到達目標點的航跡。

2　航跡性能指標

無人機航跡規(guī)劃是一個約束條件復雜的多目標規(guī)劃問題，本文主要考慮無人機的威脅代價和燃油代價［4-5］。

2.1雷達威脅代價

假定無人機具有相同的RCS，則無人機沿著V圖每條邊的雷達威脅代價是該邊的積分。如式（1）：

為了簡化計算，將每條邊均勻地分為6等分，取其中的3個點L/6，L/2，5L/6來代替整條邊的代價，N為雷達的個數(shù)，這樣第i條邊的雷達威脅代價如式（2）［6］：

2.2地形威脅代價

對于地面的山脈、高大建筑物、禁飛區(qū)等威脅，將其簡化為一系列圓形區(qū)域，無人機規(guī)避這些區(qū)域飛行。假定無人機速度恒定，第i邊的地形威脅代價就是無人機飛過該邊的燃油代價，燃油代價與路徑長短成正比，記為Jfuel，i。

2.3航跡總代價

得到了無人機第i條邊的威脅代價和燃油代價之后，便可得到第i條邊的總代價，如式（3）：

式（3）中，k為安全系數(shù)，若要求無人機安全性最大，則k為0；若要求路徑最短，則k為1。

完成航路代價計算后，V圖每條邊的權(quán)值也就是該邊的航跡代價，稱之為加權(quán)V圖。在此基礎(chǔ)之上，使用相關(guān)的航跡搜索算法便可求出無人機的初始航跡［7］。假設(shè)該航跡由N段有向加權(quán)邊組成，則該航路總代價為：

2.4航跡目標隸屬度函數(shù)

V圖的每條邊都被賦予威脅代價和燃油代價，但不能簡單相加就作為其總代價。因為威脅和燃油代價屬于不同的物理量，必須對其進行歸一化［8］。對于燃油代價或威脅代價f（x），存在一個最高代價值M和一個最低代價值m，利用式（5）進行歸一化，得到目標隸屬度函數(shù)Af（x）。

則基于目標隸屬度函數(shù)的航跡性能指標如式（6）所示：

式（6）中：k為安全系數(shù)，取值范圍為［0，1］，當k取值越大時，表明無人機為減小燃油代價而不惜犧牲威脅代價。k取值越小時，意義相反。

2.5航跡平滑處理

在進行航跡規(guī)劃時并沒有充分考慮無人機的運動學和動力學性能，因此，必須要對最后的航跡規(guī)劃結(jié)果進行平滑處理，以滿足無人機的機動約束，形成無人機的可飛航跡。

本文主要考慮無人機的最大法向過載，為此將圓弧擬合思想引入無人機的航跡平滑，利用式（7）對規(guī)劃的初始航跡進行平滑處理，詳見文獻［9］。

式（7）中，Vmin為無人機的最小飛行速度，nymax為無人機最大法向過載。

3　基于動態(tài)權(quán)值的A＊搜索算法

3.1A*搜索算法

A*算法估價函數(shù)的一般形式為：f（m）=g（m）+h（m），g（m）為初始節(jié)點到當前節(jié)點實際付出的代價；h（m）是當前節(jié)點m到目標節(jié)點的估計代價，體現(xiàn)啟發(fā)式信息，其形式通常根據(jù)問題的特性而定，將h（m）稱為啟發(fā)函數(shù)［10-11］。

3.2動態(tài)權(quán)值A(chǔ)*搜索算法

實際作戰(zhàn)環(huán)境中，為兼顧航跡搜索過程的快速性和準確性，本文提出動態(tài)權(quán)值的估價函數(shù)［12］，定義為估價函數(shù)式：

式（8）中λ是一個正數(shù)，其取值范圍為［0，1］。

（1）λ=0，意味著搜索過程不依賴任何啟發(fā)信息，此時算法蛻化成相同代價的搜索，適用于規(guī)劃空間中待擴展節(jié)點規(guī)模不大時的情形。

（2）λ為非0的固定正值時，f（m）為常權(quán)函數(shù)。當λ取值較大時，估價函數(shù)過分強調(diào)啟發(fā)式信息，突出搜索過程的深度優(yōu)先性，減少節(jié)點的擴展量，算法的快速性提高，但準確性變差；當λ取值較小時，突出搜索過程的廣度優(yōu)先性，算法的準確性提高，但搜索過程的實時性變差，即λ在不同階段對兩項指標的敏感度不同。

（3）λ為動態(tài)值時，通過對搜索初期、后期賦予λ不同的權(quán)值，實現(xiàn)了搜索初期要求搜索的快速性，搜索后期要求準確性的目的。

在此，給出深度的定義Mm，是指將整條航跡上的節(jié)點按照先后順序編碼，當前節(jié)點在整條航跡上的位置就稱為當前節(jié)點的深度。編碼越小，深度越淺；編碼越大，深度越深。

選擇權(quán)值系數(shù)λ與當前節(jié)點的深度Mm成反比，即：λ=1/Mm。即在深度較淺時，λ值較大，搜索過程以深度優(yōu)先，注重搜索過程的快速性；隨著深度的增加，λ逐漸變小，搜索后期會逐漸以廣度優(yōu)先，提高搜索過程的準確性［12-13］。

4　仿真分析

參數(shù)設(shè)置：

（1）選取2.3所選取的威脅空間；

（2）假設(shè)單部雷達具有如下的性能：對于δ為10 dB·m2的目標，當虛警概率為1.0e-6時，探測概率為80%；

（3）殺傷概率為80%時，不同等級威脅的火力殺傷半徑25 km和50 km。依據(jù)第2節(jié)所建立的性能指標和第3節(jié)動態(tài)權(quán)值A(chǔ)*算法，選取不同燃油系數(shù)k和啟發(fā)式函數(shù)的組合。

4.1動態(tài)權(quán)值系數(shù)，分析生成航跡的變化情況

（1）k=0，λ=0，不考慮燃油代價，只考慮威脅代價，搜索過程不依賴任何啟發(fā)信息，其生成的航跡R1如圖5所示。

由圖5知：為規(guī)避雷達威脅集中的區(qū)域，無人機選擇最遠路徑R1，威脅代價最小，燃油代價最大。

圖5　k=0，λ=0，時生成的航跡R1

（2）k=0.25，λ=0，考慮25%權(quán)重的燃油代價和75%權(quán)重的威脅代價，搜索過程不依賴任何啟發(fā)信息，生成的航跡R2如圖6所示。由圖6知，此時生成航跡R2向威脅比較集中的區(qū)域靠近，生成的航跡R2比航跡R1的距離略短，但仍消耗了較大的燃油代價。

圖6　k=0.25，λ=0，時生成的航跡R2

（3）k=0.5，λ=0，考慮50%權(quán)重的燃油代價和50%權(quán)重的威脅代價，搜索過程中不依賴于任何啟發(fā)信息，生成的航跡R3如圖7所示。由圖7知，此時航跡R3由原來威脅稀疏的區(qū)域移動到地面威脅相對集中的區(qū)域，燃油代價明顯減少，威脅代價明顯的增加。

（4）k=1，λ=0，只考慮燃油代價，不考慮威脅代價。航跡搜索過程不依賴任何啟發(fā)信息，生成的航跡R4如圖8所示，由該圖可知若只考慮燃油代價，不考慮威脅代價，使得生成航跡進一步移動到R4，此時燃油代價最小，但威脅代價達到最大。

圖7　k=0.5，λ=0，時生成的航跡R3

圖8　k=1，λ=0，時生成的航跡R4

以上生成的航跡R1，R2，R3和R4，顯示了航跡從威脅稀疏區(qū)域向最集中的區(qū)域移動的過程，航跡規(guī)劃的結(jié)果是合理的，顯示了權(quán)值變化對航跡規(guī)劃結(jié)果的影響。

4.2燃油系數(shù)k=0.5生成航跡的變化情況

（1）k=0.5，λ=0時，搜索過程中不依賴任何啟發(fā)信息，此時生成的全局最優(yōu)航跡為R3，見圖7所示。

（2）k=0.5，λ=1，時，考慮50%權(quán)重的燃油代價和50%權(quán)重的威脅代價，此時的動態(tài)啟發(fā)式估價函數(shù)變?yōu)椋篺（m）=g（m）+h（m），采用此估價函數(shù)進行航跡搜索，生成的航跡R5如下頁圖9所示。

圖9　k=0.5，λ=0，時生成的航跡R5

（3）k=0.5，考慮50%權(quán)重的燃油代價和50%權(quán)重的威脅代價，λ為動態(tài)變化權(quán)值時；此時的動態(tài)啟發(fā)式估價函數(shù)變?yōu)楦鼮橐话愕耐ㄊ剑篺（m）=g（m）+（1/Mm）·h（m），生成的航跡R6如圖10所示。

圖10　k=1，λ為動態(tài)權(quán)值時生成的航跡R6

由圖10知，搜索初期，深度Mm比較小，動態(tài)權(quán)值系數(shù)λ=1/Mm較大，航跡搜索主要依賴于啟發(fā)式信息，體現(xiàn)搜索過程的快速性。此時生成航跡更接近于k=0.5，λ=1時生成的航跡R5。

搜索后期，隨著深度逐漸增大，啟發(fā)式權(quán)值系數(shù)逐漸減少，節(jié)點的擴展以廣度搜索優(yōu)先，生成航跡R6逐漸向全局最優(yōu)航跡R3靠近，體現(xiàn)了算法的準確性。

總之，通過對當k=0.5，λ為動態(tài)權(quán)值時生成航跡的仿真分析，實現(xiàn)了搜索過程中快速性和準確性的結(jié)合。

4.3航跡平滑處理

針對運用動態(tài)權(quán)值A(chǔ)*算法生成的航跡R6，采用上文中航跡平滑思想進行仿真得到平滑航跡，可得到滿足無人機機動約束的可行航跡，圖11即為平滑后的航跡結(jié)果與威脅空間的疊加顯示，驗證了航跡的可飛性。

5　結(jié)束語

本文提出利用基于改進型V圖和動態(tài)權(quán)值A(chǔ)*算法求解無人機在實際作戰(zhàn)環(huán)境中的航跡規(guī)劃問題，既克服了傳統(tǒng)的V圖在規(guī)劃空間建模時的局限性，又實現(xiàn)了在航跡搜索過程中快速性和準確性的結(jié)合，仿真表明該方法具有很好的可行性，同時動態(tài)權(quán)值法也為實際運用中可飛航跡的調(diào)整提供了好的思路。

圖11　平滑之后的航跡與威脅空間疊加

［1］康樂.無人機三維航跡規(guī)劃方法研究［J］.計算機工程與應用，2009，45（33）：236-239.

［2］肖秦琨，高曉光.基于空間改進型Voronoi圖的無人機路徑規(guī)劃研究［J］.計算機工程與應用，2005，26（S）：204-206.

［3］Timothy W M，Randal W B.Trajectory Planning for Coordinated Rendezvous of Unmanned Air Vehicles［R］.AIAA-2000-4399-CP，2000.

［4］劉振，史建國，高曉光.Voronoi圖在航跡規(guī)劃中的應用［J］.系統(tǒng)仿真學報，2008，29（S）：15-17.

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

［6］葉媛媛，閔春平，沈林成，等.基于VORONOI圖的無人機空域任務(wù)規(guī)劃方法研究［J］.系統(tǒng)仿真學報，2005，17（6）：1353-1355.

［7］楊遵，雷虎民，曾康斌.不同威脅源下無人機的攻擊航路規(guī)劃算法與仿真［J］.系統(tǒng)仿真學報，2010，22（8）：1938-1941.

［8］馮慧，屈香菊.基于多目標模糊優(yōu)化方法的無人機航跡規(guī)劃［J］.飛行力學，2007，25（2）：25-28.

［9］周煒，魏瑞軒，董志興.基于層次分解策略無人機編隊避障方法［J］.系統(tǒng)工程與電子技術(shù)，2009，31（5）：1152-1156.

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

［11］李季，孫秀霞.基于改進A*算法的無人機航跡規(guī)劃算法研究［J］.兵工學報，2008，29（7）：778-780.

［12］李少華，魏海光，周成平，等.一種無人飛行器的快速航跡規(guī)劃方法［J］.四川兵工學報，2011，32（12）：73-76.

［13］李銳.基于啟發(fā)式算法的無人機三維航跡規(guī)劃仿真研究［J］.電光與控制，2009，16（8）：28-29.

UAV Path Planning Based on Improved Voronoi Diagram and Dynamic Weights A*Algorithm

ZHANG Tao-sha，LU Yi，ZHANG Liang，Lü Yue
（Engineering College of Aeronautics and Astronautics，Air Force Engineering University，Xi’an，710038，China）

Aiming at different threat level and different kinds of threat in actual operational environment，the path planning space on the basis of improved Voronoi diagram is established.Because evaluation function of A*algorithm requires different sensitiveness to indicator at different stage，based on traditional heuristic A*algorithm，dynamic weights A*algorithm is proposed to improve efficiency of path searching and combine the rapidity and the veracity of path planning.By Matlab software，the optimal path is acquired and the path is smoothed.The simulation shows the feasibility of improved Voronoi diagram and dynamic weights A*algorithm.

UAV，path planning，improved Voronoi diagram，dynamic weights A*algorithm，path smooth

TJ012.4

A

1002-0640（2015）02-0156-05

2014-01-03

2014-02-03

張?zhí)陨常?990-），男，江蘇宿遷人，碩士研究生。研究方向：飛行器航跡規(guī)劃，指揮控制與引導。