基于加權(quán)Voronoi圖的無人飛行器航跡規(guī)劃

聶俊嵐，張慶杰，王艷芬

(1.燕山大學 信息科學與工程學院，河北 秦皇島066004;2.燕山大學 河北省計算機虛擬技術(shù)與系統(tǒng)集成重點實驗室，河北 秦皇島066004)

0 引言

無人飛行器航跡規(guī)劃問題可定義為:在給定的規(guī)劃空間內(nèi)，尋找飛行器從起始點到目標點的滿足某種性能指標的最優(yōu)航跡［1］。航跡規(guī)劃的任務(wù)就是讓飛行器以較小的威脅穿越陣地，最終到達目的地［2］。近年來，國內(nèi)外研究人員已經(jīng)對飛行器的航跡規(guī)劃問題作了大量研究。目前用于航跡規(guī)劃的算法大致可分為兩類［3］:(1)確定型搜索算法，主要包括動態(tài)規(guī)劃法、Voronoi圖法、A*算法以及D*算法等;(2)隨機型搜索算法，主要包括神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、粒子群算法、蟻群算法和模擬退火算法等。其中Voronoi圖法與其他方法相比具有較強的直觀性和把復雜的空域問題轉(zhuǎn)換為區(qū)域劃分問題的能力，有較好的時間特性和空間特性，適合單飛行器的航跡規(guī)劃［4］，且 Voronoi圖法的航跡規(guī)劃結(jié)果具有固有的威脅回避能力［5］。對于確定的威脅區(qū)域，Voronoi圖邊到周圍威脅區(qū)域的距離是最遠的;因此相比其他航跡規(guī)劃方法，Voronoi圖法能夠計算得到更為安全的航跡。

目前，Voronoi圖法在無人飛行器航跡規(guī)劃領(lǐng)域已有較多進展。文獻［5］將威脅源處理成平面點集，在規(guī)劃空間內(nèi)威脅分布一致的情況下，采用Voronoi圖法進行飛行航跡的規(guī)劃，并對航跡進行平滑和修正，其缺點是只將威脅源處理成平面點而沒有考慮威脅源的覆蓋范圍，在實際應(yīng)用中有較大局限性?？紤]到威脅源的覆蓋范圍問題，文獻［6］以雷達位置作為圓心，以雷達探測半徑作圓，將雷達探測范圍擬合成圓形區(qū)域，但其只考慮了一種掃描類型的雷達，而在實際的飛行空間中，不同威脅源有不同的作用方式和距離，只有研究具有不同作用方式和距離的威脅源的航跡規(guī)劃才更有實際意義［7］。

此外，文獻［6］也未考慮山峰等地形障礙，這些威脅源形狀各異，如何對其進行擬合是無法回避的問題。文獻［8］雖然考慮了地形等威脅因素，但其簡單將海上島嶼擬合成橢圓形，造成了威脅源覆蓋范圍擴大的問題，進而可能會影響到最優(yōu)航跡的計算。

針對上述問題，本文主要研究了在面對不規(guī)則地形以及類型各異的雷達威脅時，無人飛行器的航跡規(guī)劃問題。首先對規(guī)劃空間中的威脅區(qū)域進行預(yù)處理，采用文獻［9-10］中提出的方法計算威脅區(qū)域的加權(quán)Voronoi圖，在考慮飛行代價的基礎(chǔ)上對計算得到的航跡進行平滑處理，最終規(guī)劃出滿足各項約束的最優(yōu)航跡。

1 飛行空間預(yù)處理

實際情況中，山峰、雷達等威脅源都是三維的，為簡化運算，本文將三維的雷達偵察區(qū)域和山峰等障礙物映射到二維空間進行處理。首先將威脅源處理成威脅區(qū)域，這些威脅區(qū)域的形狀輪廓都不太規(guī)則，對其進行擬合時考慮兩種解決方案:(1)輪廓外接圓法。如圖1(a)所示，首先提取其輪廓，然后用輪廓的外接圓擬合該威脅區(qū)域，如圖1(b)所示，顯然這種方案會造成威脅區(qū)域的擴大;(2)輪廓均分法。提取出輪廓后，用若干半徑相等的相交圓對威脅區(qū)域進行擬合，如圖1(c)所示，這種辦法依據(jù)山峰的輪廓繪制威脅區(qū)域，盡管計算量相比第一種方案要大，但其擬合出的威脅區(qū)域相比第一種方案要精確很多。本文采取將兩種方案相結(jié)合的思路，對于輪廓形狀近似于圓形的威脅區(qū)域用輪廓外接圓法對其進行擬合，而對于輪廓形狀較為復雜的威脅區(qū)域，則用輪廓均分法進行擬合。

圖1 威脅區(qū)域輪廓的擬合Fig.1 Fitting of threatening area’s outline

1.1 輪廓外接圓法擬合威脅區(qū)域

對圖1(a)中的威脅區(qū)域進行外接圓的擬合。確定一個圓需要有圓心坐標(x0，y0)、半徑(或直徑)兩個參數(shù)，設(shè) S{(xi，yi)|i=1，…，n}為威脅區(qū)域輪廓上的n個點所構(gòu)成的集合。用圓對威脅區(qū)域進行擬合的過程就是尋找外接圓的過程。其步驟為:

(1)計算邊界點集S中任意兩點間的距離dij(i，j=1，…，n;i≠j);

(2)尋找 dij中的最大值 max dij，記為 d，在 S中與d對應(yīng)的兩個點記為A(x1，y1)和B(x2，y2);

(3)求出線段AB的中點O(x0，y0)，點O即為所需圓的圓心，線段AB為圓的直徑。

1.2 輪廓均分法擬合威脅區(qū)域

對圖1(a)中的威脅區(qū)域進行相交圓的擬合。同樣設(shè)S{(xi，yi)|i=1，…，n}為待擬合威脅區(qū)域上的n個點所構(gòu)成的集合，設(shè)一個偏離閾值p，最大圓半徑Rmax，其步驟為:

(1)對威脅區(qū)域的輪廓進行直線擬合:

①從S中取一定數(shù)量連續(xù)點作為S的子集Si;

②用最小二乘法對Si中的點進行直線擬合，并計算每個點到直線的距離d;

③如果d＞p，則從Si中去除一些連續(xù)點，再執(zhí)行步驟②，直到滿足需求，得到一條線段l;

④ 從S中去除Si，即執(zhí)行S－Si;

⑤重復步驟①～④，直到S為空，最終得到擬合后的線段集合L{li|i=1，…，m}。

(2)取一條線段 li，若 li的長度 di＞2Rmax，則令圓半徑 R=Rmax，若 di≤2Rmax，則令 R=3di/4;

(3)從li的一個端點開始，每隔5/3R的長度取采樣點，直到到達另一個端點，得到采樣點集P{pi|i=1，…，n};

(4)以P中每個點為圓心，R為半徑作圓。

通過以上工作，即可將不規(guī)則的輪廓用一系列相交的圓來覆蓋。

2 航跡代價模型

航跡代價是衡量飛行器受到地形威脅或被雷達發(fā)現(xiàn)的可能性的指標。在現(xiàn)有文獻中無人飛行器的代價函數(shù)通常包含長度代價和威脅代價［11］?？紤]到飛行器轉(zhuǎn)彎時物理性能的制約，文獻［8］將最大轉(zhuǎn)彎角引入到代價函數(shù)中。為提高飛行器完成任務(wù)的成功率，本文為飛行器加入警戒半徑Rm，僅當航跡上任意一點到威脅區(qū)域的距離大于Rm時該航跡才可飛，因此為代價函數(shù)引入警戒半徑參數(shù)θ，將航跡中兩個轉(zhuǎn)彎點之間的航跡稱為一個“航跡段”，θ由航跡到威脅區(qū)域的距離s和Rm共同決定:若s＞Rm，則θ=1，表示θ對于該航跡段的代價沒有影響;若s≤Rm，則θ→∞，使航跡段代價為無窮大。對于某一航跡段Xi而言，其代價J為:

式中:J1，J2，J3分別為該航跡段的長度代價、威脅代價和轉(zhuǎn)彎代價;w1，w2，w3為相應(yīng)的權(quán)值。

對于某一航跡段Xi，若θ(Xi)→∞，則該航跡段的代價為∞;若θ(Xi)=1，則應(yīng)計算其長度代價、威脅代價和轉(zhuǎn)彎代價的加權(quán)和。長度代價與Xi的長度Li成正比，即J1(Xi)=Li。威脅代價指該航跡段上某個位置到周圍威脅區(qū)域的距離，距離越近其威脅代價越大。轉(zhuǎn)彎代價的計算模型和具體計算方式參見文獻［11］。下面重點介紹威脅代價的計算方法，對于某一航跡段Xi，設(shè)一個實數(shù)K＞1，其威脅代價計算方法為:

(1)以一定的步長對Xi進行采樣，假設(shè)總共有n個采樣點，則得到采樣點序列P{1，…，n};

(2)設(shè)點Pj(j=1，…，n)距周圍威脅區(qū)域的最短距離為sj，威脅代價為Tj，則有:

① 如果sj≥KRm，則 Tj=0;

② 如果 Rm≤sj＜KRm，Tj=1 －sj/(KRm);

(3)Xi的威脅代價J2(Xi)即為Xi航跡段所有采樣點的威脅代價之和:

3 基于加權(quán)Voronoi圖的航跡規(guī)劃

3.1 算法分析

首先，對于近似圓形的威脅區(qū)域用“輪廓外接圓法”直接進行擬合。而對不規(guī)則區(qū)域進行擬合時，為了使參與計算的幾何圖形一致從而減少計算的復雜性，本文采用“輪廓均分法”進行擬合，得到一系列相交的圓形區(qū)域，相交圓之間生成的加權(quán)Voronoi圖邊會與這兩個圓相交，因此通過判斷某一條邊是否與圓相交來決定是否摒棄這條邊。

其次，加權(quán)Voronoi圖邊到其周圍圓的距離都相等，如圖2所示，在邊上任取A，B兩點，其到周圍兩個圓的距離都相等，生成的飛行航跡處于距離威脅區(qū)域盡可能遠的位置，使危險性降到相對最低。

生成加權(quán)Voronoi圖后，加權(quán)Voronoi圖邊的交點即為飛行器的可飛節(jié)點，所有可飛節(jié)點構(gòu)成了飛行器的可飛節(jié)點集，可飛節(jié)點集與加權(quán)Voronoi邊共同構(gòu)成了一個網(wǎng)絡(luò)，可用賦權(quán)圖來描述它［12］，對于這個可飛航跡構(gòu)成的賦權(quán)圖，可以用Dijkstra算法尋找一條最短航跡。

圖2 加權(quán)Voronoi圖Fig.2 Weighted-Voronoi diagram

3.2 算法步驟

(1)采用輪廓外接圓和輪廓均分相結(jié)合的方法對飛行空間內(nèi)的威脅區(qū)域進行預(yù)處理，得到一系列圓形區(qū)域，并讀入起始點和目標點;

(2)計算所有圓的加權(quán)Voronoi圖，圖的所有邊構(gòu)成了航跡段集合X{Xi|i=1，…，n}。加權(quán)Voronoi圖的邊大多為曲線段(在計算機中曲線段由若干直線段組成，因此每條曲線段上都有若干折點)，每條邊都是一條航跡段，邊的交點即為拐彎點;

(3)設(shè)飛行器的警戒半徑為Rm，對于某一航跡段Xi，若Xi的飛行代價為無窮大，則Xi為不安全航跡段，將其從集合X中剔除;

(4)從圖上尋找距離飛行器的起始點和目標點最近的兩個拐彎點，用Dijkstra算法求取這兩個拐彎點之間的最短航跡W;

(5)以航跡W上的每個拐彎點以及每個航跡段的折點作為控制點，用2次B樣條函數(shù)對航跡進行平滑，得到平滑的航跡W';

(6)輸出平滑后的最短航跡W'。

4 仿真試驗及分析

4.1 仿真試驗

本文使用的飛行空間為600 km×600 km，如圖3所示。其中，a為飛行器起始點(70 km，50 km)，b為目標點(430 km，420 km)，虛線區(qū)域為雷達偵察區(qū)域。采用“輪廓均分法”對大型山脈的輪廓進行擬合，對小型的山峰和雷達威脅用“輪廓外接圓法”擬合。

圖3 飛行空間示意圖Fig.3 Flying space

當警戒半徑Rm=5 km時，經(jīng)本文算法處理，得到加權(quán)Voronoi圖如圖4所示，黑色細線為加權(quán)Voronoi圖的邊，即航跡段，較寬的曲線為平滑后的最短航跡，該航跡是由一系列采樣點組成。每個采樣點的灰度值是根據(jù)該點的威脅代價從灰度條帶上采集得到，顏色越深則威脅代價越大(見圖5)。

圖4 加權(quán)Voronoi圖及最短航跡Fig.4 Weighted-Voronoi diagram and shortest path

圖5 灰度條帶Fig.5 Gray image

在同樣的飛行空間中僅用輪廓外接圓法對威脅區(qū)域進行擬合并生成航跡，當警戒半徑Rm=5 km時，得到如圖6所示的仿真結(jié)果。

圖6 輪廓外接圓法生成的航跡Fig.6 Paths Generated by using circumcircle fitting method

表1為從對威脅區(qū)域擬合的不同方法和警戒半徑大小兩方面，考察不同因素對最終生成的航跡的影響。當Rm=8 km或Rm=11 km時，輪廓外接圓法已經(jīng)無法得到符合條件的航跡，說明這種擬合方法會造成威脅區(qū)域范圍擴大的問題，盡管計算時間較短，但其生成的航跡較長，且當警戒半徑較大時容易出現(xiàn)“不可飛”的情況。采用輪廓均分和輪廓外接圓相結(jié)合的方法可以很好地解決這些問題，盡管計算時間較長，但其仍然能滿足即時性需求。

表1 航跡生成結(jié)果比較Table 1 Comparison of the paths

4.2 可視分析

為了使最終生成的航跡能夠更好地支持決策，采用了多種可視化和交互式的手段來展示航跡規(guī)劃結(jié)果，最終規(guī)劃的航跡如圖7(a)所示，通過航跡上不同位置的顏色深淺能直觀地看出該位置的危險程度。

作為一個支持決策的工具，提供具體數(shù)據(jù)的可視化展示同樣非常必要，圖7(b)所示為圖7(a)中的航跡上各個采樣點到威脅區(qū)域的詳細距離信息。與圖7(a)中的航跡類似，圖7(b)中的曲線也用不同灰度值的顏色表示距離的遠近，即威脅的大小。

在圖7(b)上可以進行一些交互式操作。用鼠標滾輪可以放大或縮小圖表的大小，右鍵可以對圖表進行拖拽操作，左鍵可以在圖表上進行框選，選中一定區(qū)域后，實時地在航跡圖上標識出對應(yīng)的航跡段，如在圖7(b)中用鼠標左鍵進行框選后，圖7(a)中會圈出相應(yīng)的航跡位置。

圖7 可視分析Fig.7 Visualization analysis

5 結(jié)束語

本文主要研究了在二維空間采用加權(quán)Voronoi圖對無人飛行器進行航跡規(guī)劃的問題。相比傳統(tǒng)Voronoi圖法，加權(quán)Voronoi圖可用于處理具有不同覆蓋范圍的威脅源的航跡規(guī)劃，更具實際意義。此外，采取輪廓均分與輪廓外接圓相結(jié)合的方法擬合各種威脅區(qū)域的輪廓，有效地解決了傳統(tǒng)擬合方法造成的威脅區(qū)域擴大問題。將警戒半徑引入航跡代價模型，使最終生成的航跡更為安全。另外，程序還提供了可視分析功能，決策者可以從多角度分析生成的航跡。試驗結(jié)果表明，本文方法能規(guī)劃出更安全且長度較短的航跡，可視化方法的加入為決策者分析航跡提供了交互手段。為簡化運算，本文將飛行空間簡化到二維空間，而三維空間的航跡規(guī)劃更具實際意義，因此三維空間內(nèi)的航跡規(guī)劃將會是今后的主要研究方向。

［1］ 嚴平，丁明躍，周成平，等.飛行器多任務(wù)在線實時航跡規(guī)劃［J］.航空學報，2004，25(5):485-489.

［2］ 劉振，史建國，高曉光.Voronoi圖在航跡規(guī)劃中的應(yīng)用［J］.航空學報，2008，29(S1):15-19.

［3］ 王維平，劉娟.無人飛行器航跡規(guī)劃方法綜述［J］.飛行力學，2010，28(2):6-10.

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

［5］ 閻代維，谷良賢，王興治.基于Voronoi圖的巡航導彈突防路徑規(guī)劃研究［J］.彈箭與制導學報，2005，25(2):11-13.

［6］ 單提曉，蔣蓁.一種基于分割法的無人機路徑規(guī)劃新方法［J］.彈箭與制導學報，2014，34(2):185-188.

［7］ 馬培蓓，紀軍.3種多導彈航跡規(guī)劃算法的比較［J］.電光與控制，2010，17(10):28-32.

［8］ 傅陽光，周成平，胡漢平.無人飛行器海上航跡規(guī)劃差分進化算法研究［J］.兵工學報，2012，33(3):295-300.

［9］ Karavelas Menelaos I，Emiris Ioannis Z.Predicates for the planar additively weighted Voronoi diagram［R］.ECGTR-122201-01，2002.

［10］ Karavelas M I，Emiris I Z.Root comparison techniques applied to computing the additivelyweighted Voronoi diagram［R］.ACM-SIAM SODA-15，2003.

［11］傅陽光，周成平，丁明躍.基于混合量子粒子群優(yōu)化算法的三維航跡規(guī)劃［J］.宇航學報，2010，31(12):2657-2664.

［12］張同法，于雷，劉文杰，等.基于Dijkstra算法的巡航導彈航跡規(guī)劃方法研究［J］.彈箭與制導學報，2008，28(4):65-67.