基于加權Voronoi圖的無人飛行器航跡規劃

聶俊嵐，張慶杰，王艷芬

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

0 引言

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

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

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

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

1 飛行空間預處理

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

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

1.1 輪廓外接圓法擬合威脅區域

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

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

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

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

1.2 輪廓均分法擬合威脅區域

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

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

①從S中取一定數量連續點作為S的子集Si;

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

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

④ 從S中去除Si，即執行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為半徑作圓。

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

2 航跡代價模型

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

式中:J1，J2，J3分別為該航跡段的長度代價、威脅代價和轉彎代價;w1，w2，w3為相應的權值。

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

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

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

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

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

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

3 基于加權Voronoi圖的航跡規劃

3.1 算法分析

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

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

生成加權Voronoi圖后，加權Voronoi圖邊的交點即為飛行器的可飛節點，所有可飛節點構成了飛行器的可飛節點集，可飛節點集與加權Voronoi邊共同構成了一個網絡，可用賦權圖來描述它［12］，對于這個可飛航跡構成的賦權圖，可以用Dijkstra算法尋找一條最短航跡。

圖2 加權Voronoi圖Fig.2 Weighted-Voronoi diagram

3.2 算法步驟

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

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

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

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

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

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

4 仿真試驗及分析

4.1 仿真試驗

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

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

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

圖4 加權Voronoi圖及最短航跡Fig.4 Weighted-Voronoi diagram and shortest path

圖5 灰度條帶Fig.5 Gray image

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

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

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

表1 航跡生成結果比較Table 1 Comparison of the paths

4.2 可視分析

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

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

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

圖7 可視分析Fig.7 Visualization analysis

5 結束語

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

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

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

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

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

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

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

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

［8］ 傅陽光，周成平，胡漢平.無人飛行器海上航跡規劃差分進化算法研究［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］傅陽光，周成平，丁明躍.基于混合量子粒子群優化算法的三維航跡規劃［J］.宇航學報，2010，31(12):2657-2664.

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