基于Voronoi圖的無人機航路改進規(guī)劃

史紅玉, 劉淑芬

(1. 河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院, 河南 焦作 454150； 2. 吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院, 長春 130012)

無人機的航路規(guī)劃是指在最低油耗、最小威脅和最短距離等約束條件下, 對無人機在起點與終點間的路徑進行的優(yōu)化設(shè)計. 考慮到一般無人機的巡航高度, 其無法利用地形躲避威脅, 所以航路規(guī)劃可簡化為一個二維模型問題, 只考慮其水平航跡.

Voronoi圖作為一種基本的幾何結(jié)構(gòu), 目前已被廣泛應(yīng)用于無人機航路規(guī)劃中[1]. 根據(jù)威脅區(qū)域分布的情形生成由初始可選路徑集構(gòu)成的Voronoi圖, Voronoi邊是離散威脅源的中垂線, 能使無人機在飛行過程中有效降低威脅代價. 目前, 基于Voronoi圖規(guī)劃航路的方法已有許多, 如趙文婷等[2]根據(jù)威脅源基于Voronoi圖建模, 計算航路代價, 并針對算法中存在的優(yōu)缺點, 提出了對算法的改進； 趙艷麗等[3]首先基于Voronoi圖建模, 然后獲得初始規(guī)劃解集, 最后通過引入Cauchy變異隨機數(shù)和擾動對量子粒子群(QPSO)算法進行改進, 確定了最終航路規(guī)劃的改進算法; 劉平等[4]首先由Voronoi圖生成了初始航路, 然后在各種約束條件下賦予各邊相應(yīng)的權(quán)值, 最后應(yīng)用離散型粒子群算法搜索出滿意的規(guī)劃解； 劉森琪等[5]根據(jù)威脅源生成Voronoi圖, 計算航路代價, 采用改進的蟻群算法計算最優(yōu)航路； Asano等[6]通過給定一組線段, 在線段中點視角的大小確定屬于線段的Voronoi區(qū)域, 提出一種尋找最大視角的有效算法; Bhattacharya等[7]基于Voronoi圖算法, 在簡單分離的情形下計算起點與目標(biāo)節(jié)點之間的距離. 這些算法雖然都能實現(xiàn)無人機的航路規(guī)劃, 但仍存在收斂速度慢、易陷入局部優(yōu)化等問題[8-9]. 無人機在戰(zhàn)場上對環(huán)境的預(yù)先設(shè)想不一定與實際環(huán)境一致, 因此為實現(xiàn)航路規(guī)劃的準(zhǔn)確快速, 需要初始路徑有一個更精確合理的優(yōu)化. 本文在得到初始路徑的基礎(chǔ)上, 針對傳統(tǒng)算法的不足, 提出一種新的快速優(yōu)化算法, 并通過仿真實驗驗證了該算法的可行性.

1 基于Voronoi圖的威脅區(qū)域建模

Voronoi圖是在其組成點集中連接兩個鄰點直線的垂直平分線構(gòu)成的一組連續(xù)多邊形, 它是計算幾何的重要組成部分, 廣泛應(yīng)用于與區(qū)域劃分相關(guān)的領(lǐng)域, 其中的最近點、n點的凸包和最小樹問題均可由Voronoi圖解決[10].

1.1 Voronoi圖的定義與性質(zhì)

定義1[11]在二維空間2上, 有n個離散的生成元p={p1,p2,…,pn}, 其中任意兩個生成元互不重疊,p對應(yīng)的Voronoi圖是平面的一個子區(qū)域劃分, 整個平面S被劃分為n個單元,Vs={Vp1,Vp2,…,Vpn}. 對于生成元pi的Voronoi區(qū)域, 有

Vpi={q∈2|d(pi,q)

(1)

其中d(q,pi)和d(pj,q)分別為q到pi和pj的距離.

性質(zhì)1對于Voronoi多邊形中的點q, 若q在pi所在的多邊形中, 用d(q,pi)表示兩點間的直線距離, 則有d(pi,q)

性質(zhì)2Voronoi圖中任意n個基點(n>3)的平面, 平面頂點數(shù)不超過2n-5, 且邊的數(shù)目不超過3n-6.

性質(zhì)3Voronoi圖在增減生成元時, 通過局域動態(tài)特性只影響相鄰的空間區(qū)域, 不影響整個空間的劃分.

由Voronoi圖的定義和性質(zhì)可知, Voronoi圖各邊上的點到相對應(yīng)的兩個點距離相等, 即Voronoi邊上的點是到威脅點最遠的點, 無人機沿Voronoi邊飛行可獲得相對的安全保障.

1.2 Voronoi圖算法的主要思想

基于Voronoi圖的航路規(guī)劃算法思想： 首先確定所有威脅源, 將該威脅源等價為點, 作為Voronoi圖的點集, 將威脅源范圍的大小作為Voronoi圖相鄰區(qū)域的“距離”度量長度, 然后生成Voronoi圖, 圖上各條邊在相應(yīng)的領(lǐng)域內(nèi)與威脅源“距離”越大, 則受到的威脅相應(yīng)越小. Voronoi圖中線段與線段相交的點構(gòu)成了無人機飛行時的航跡節(jié)點, 且可以由威脅源的強度大小和Voronoi圖各邊的長短計算出各邊相應(yīng)的權(quán)值. 其次, 利用最短路徑搜索算法[12]得到初始的最優(yōu)路徑, 該初始路徑根據(jù)威脅代價有效避開了威脅值較大的區(qū)域, 同時也盡可能以較短的路徑抵達目標(biāo)點. 最后利用本文提出的優(yōu)化初始航路算法, 求得最終的航路圖.

1.3 Voronoi圖建模

在無人機執(zhí)行任務(wù)時, 經(jīng)常會在飛行環(huán)境中遇到一些包括地形威脅、雷達探測威脅等情形, 針對上述威脅信息, 本文基于威脅作用半徑, 以威脅場空間形狀的威脅信息量化處理方法建模. 根據(jù)地貌特征, 將絕對高度在500 m以上的地形概括為高山和陡坡. 地形威脅主要指地面上的山峰或一些較高的物體, 模擬公式為

(2)

其中： Temp(x,y)為地圖中該點的高度值;k為威脅區(qū)域的威脅程度;x,y為坐標(biāo)點; VarX,VarY為方差, 方差數(shù)越小, 表示沿對應(yīng)軸方向的地形越陡峭. 將威脅元素山峰定高在H的二維平面時, 威脅模型可表示為

{(x,y)}={(x,y)|(x-ox)2+(y-oy)2≤max{a,b}2},

(3)

其中:a,b分別為地形威脅模型橢圓橫切面的長、短軸長； max{a,b}表示a,b中最大值; 點o為地平面橫切面的中心點. 該區(qū)域定義為無人機禁飛區(qū), 無人機在該區(qū)域內(nèi)的損壞概率為1, 存活率為0.

在無人機航路研究中, 雷達探測威脅也是構(gòu)成威脅點的一個主要因素, 雷達方程可表示為

p=K/R4,

(4)

其中：p是距雷達接收機R處收到的回波信號功率, 表示雷達的威脅強度;K表示對應(yīng)于具體雷達的常數(shù). 飛行器對目標(biāo)的距離R是影響p的重要因素,p與距離R的四次方成反比,R表示為

(5)

其中(x1,y1)與(x2,y2)分別為無人機的坐標(biāo)和雷達位置的坐標(biāo). 第i個雷達對無人機的威脅程度表示為

(6)

圖1 威脅分布的Voronoi圖Fig.1 Voronoi diagram of threat distribution

其中:j表示由n個航跡點組成的航路上的一點;pj表示該點的回波強度. 假設(shè)無人機在飛行過程中遇到n個雷達, 則無人機受到的雷達威脅Wz可表示為Wz=f(W1,W2,…,Wn).

無人機在高空平飛時, 其航路規(guī)劃區(qū)域可認(rèn)為是一個二維平面. 在平面內(nèi)的威脅分布主要是雷達等設(shè)備或很高的山峰, 可以把這些雷達或山峰在地圖上等效為點, 然后以這些點作為基點集, 構(gòu)造出由威脅點分布的Voronoi圖, 最后可在構(gòu)造好的Voronoi圖中進行航路規(guī)劃. 圖1為根據(jù)威脅模型建立的Voronoi圖, 圖中的圓點表示威脅源.

2 基于Voronoi圖的航路代價計算

無人機航路規(guī)劃是在滿足約束條件的基礎(chǔ)上規(guī)劃出一條由起點到目標(biāo)點的飛行軌跡. 它是一個約束條件較復(fù)雜的多目標(biāo)規(guī)劃問題[13], 其約束條件一般包括無人機的安全性能和燃油性能[14], 因此, 本文考慮的航路代價包括與距離有關(guān)的威脅代價和燃油代價.

2.1 威脅代價

圖2 威脅代價的計算Fig.2 Calculation of threat cost

雷達作為威脅源構(gòu)成了與其相接的Voronoi邊的威脅元素, 假設(shè)無人機具有的雷達反射截面均相同, 則可用Voronoi圖每條邊的積分表示該邊的雷達威脅代價, 如圖2所示. 無人機反射雷達回波的強度與其到雷達距離的四次方成反比[15], 則Voronoi圖中邊的雷達威脅代價為

(7)

其中,r1,r2為加權(quán)系數(shù), 分別表示威脅和距離在弧的權(quán)值中所占的比.

將線上的積分轉(zhuǎn)化為線上5個點的積分, 本文采用十等分法, 用ftemp(Vi,pj)表示經(jīng)過十等分后威脅源對Voronoi邊的威脅權(quán)值, 則

(8)

2.2 燃油代價

假設(shè)無人機在飛行過程中速度恒定, 則其在飛行過程中所消耗的燃油與飛行航路的長度成正比, 燃油代價為

ffurl=kli,

(9)

其中k為比例系數(shù).

2.3 總代價

由于無人機航行過程中的代價主要包括威脅代價fweight(Vi)和燃油代價ffurl, 所以無人機的航路總代價可表示為

fzong=kfweight(Vi)+(1-k)ffurl,

(10)

其中,k為安全性能與燃油性能的系數(shù), 若要求無人機安全性能最大, 則k=0； 若要求航路最短, 則k=1.

3 對初始航路的優(yōu)化

3.1 B樣條插值

由Voronoi圖經(jīng)過最短路徑搜索算法計算后, 可得到一條初始的優(yōu)化路徑, 由于未考慮到無人機的運動約束, 所以該路徑必須進一步優(yōu)化路徑中包含的一些不可飛的尖銳轉(zhuǎn)彎角. 一般情形下, 使用B樣條插值[16-17]、三次樣條插值法或K-path法解決航路中存在的尖角問題. 下面以B樣條插值法為例進行說明.

B樣條插值(簡稱B-Spline插值)屬于逼近樣條類, 與控制多邊形的外形更接近, 而且還具有局部修改能力, 應(yīng)用廣泛.

定義2由(m+n+1)個平面或Pi(i=0,1,2,…,m+n)個空間頂點組成的曲線, 稱為n次參數(shù)曲線段：

(11)

其中：Pk,n(t)表示第k段n次B樣條曲線段(k=0,1,2,…,m), 曲線段全體構(gòu)成n次B樣條曲線, 由點Pi(i=0,1,2,…,m+n)構(gòu)成的多邊形表示B樣條曲線的特征多邊形;Gi,n(t)表示基函數(shù), 可定義為

(12)

在無人機給定的航路離散點中, 選取(n+1)個控制點Pj(j=0,1,2,…,n), 則K階B樣條曲線方程為

(13)

其中, 參數(shù)u的范圍由B樣條其他參數(shù)的選取確定.

B樣條插值函數(shù)一般用于消除路段間的轉(zhuǎn)折, 使整條航路趨于平滑, 滿足了無人機的可飛條件, 但僅解決了路徑的尖角問題, 使初始航路的路線變得圓潤平滑適合飛行. 無人機在飛行過程中對時間節(jié)點的要求較嚴(yán)格, 期望優(yōu)化后的航程基本不變, 在遇到緊急任務(wù)或燃料告急時, 則希望航程最短, 因此, 在出現(xiàn)上述情形時就需要采取其他規(guī)劃方式實現(xiàn)規(guī)劃要求. 本文提出一種新的快速對初始航路優(yōu)化的算法, 不僅能解決航路不能飛的問題, 同時也對威脅代價和燃油代價進行進一步的優(yōu)化.

3.2 優(yōu)化初始航路改進算法

本文提出的優(yōu)化初始航路改進算法描述如下.

1) 初始化. 首先備份原始路徑中的節(jié)點坐標(biāo), 確定當(dāng)前的迭代次數(shù)和迭代次數(shù)最大值.

2) 根據(jù)初始的航路路線, 首先從起點開始確定兩條線段, 即確定3個順序排列的節(jié)點坐標(biāo)， 如圖3所示.

3) 圖3中point2,point1,point3分別對應(yīng)Voronoi圖中節(jié)點坐標(biāo)Pi-1,Pi,Pi+1, 利用夾角公式計算兩條線段構(gòu)成的夾角, 如果該夾角大于120°, 則符合航行要求不做處理; 如果該夾角小于120°, 則進行以下處理：

① 如圖4所示, 分別在兩條線段上用linspace函數(shù)在對應(yīng)的線段上選5個點, 以一邊為例.

② 由中間節(jié)點到兩邊線段最近的間隔點pointA和pointB再次用linspace函數(shù)將對應(yīng)的線段劃分成中間節(jié)點到該間隔點線段長度10倍的小段, 即將每條線段都以長度0.1分隔開.

③ 由interp2函數(shù)可分別求得由中間節(jié)點到兩端最近間隔點的權(quán)重值以及兩個間隔點間的權(quán)重值, 如圖5所示. LengthWeightA=interp2(x,y,Plane,SegXA,SegYA,‘linear’) 存放point1到pointA上由②中劃分后每個間隔點的油耗值和威脅值, 其中:x,y表示坐標(biāo)點； Plane表示初始化帶有Voronoi圖上每點油耗值和威脅程度值的矩陣； SegXA和SegYA表示插值后的坐標(biāo)點. point1到pointA線段的權(quán)重值為

WeightA=sum(LengthWeightA).

同理可求出另外兩條邊的權(quán)重值.

圖5 權(quán)重比較示意圖Fig.5 Schematic diagram of weight comparison

④ 將①中一條線段上的間隔點遍歷另一條線段上的所有間隔點, 根據(jù)③可求出對應(yīng)的權(quán)重值. DifWeighti,j=WeightAi,j+WeightBi,j-WeightABi,j(i,j∈[2,5])表示三邊權(quán)重值的比較: 其中i,j分別表示兩條線段上第i個和第j個間隔點.

由max(DifWeight((:)))獲取最優(yōu)的節(jié)點, 即在該兩點時油耗和威脅值均最小. 假設(shè)圖5兩邊大于第三邊的權(quán)值是在所有間隔點中最大的, 則pointA,pointB即為本文新獲取的節(jié)點, 原來的節(jié)點為point2,point1,point3, 現(xiàn)在新路徑節(jié)點為point2,pointA,pointB.

4) 根據(jù)對權(quán)重值的比較, 找到最優(yōu)線路的節(jié)點坐標(biāo), 獲取新的兩點坐標(biāo)若是初始節(jié)點中的坐標(biāo)則不做改變, 如果不是則替換相應(yīng)的初始節(jié)點坐標(biāo).

5) 更新完節(jié)點后, 回到初始化, 對新得到的路徑節(jié)點進行再次判斷是否符合無人機的飛行條件, 然后再次進行優(yōu)化、更新、迭代, 從而得到最終的符合飛行要求的新路徑節(jié)點, 生成最后的路徑圖.

本文得出的最終路徑不僅解決了航路中存在的尖角不可飛問題, 減少了路程時間, 而且航行中的油耗和威脅值也是最優(yōu)的.

4 仿真實驗

為了驗證本文提出的對初始路徑優(yōu)化算法的有效性, 對圖1所示的具有40個威脅源的區(qū)域進行航路規(guī)劃. 實驗環(huán)境為: Inter CPU 2.20 GHz, 4.00 GB內(nèi)存, 操作系統(tǒng)為Win7專業(yè)版, 仿真環(huán)境采用MATLAB R2014a實現(xiàn).

假設(shè)飛機在飛行中一直勻速行駛, 飛行高度固定. 圖1中的點表示航路中存在的雷達、山峰等構(gòu)成的威脅源, 規(guī)劃空間中共有40個威脅. 航路的起始點坐標(biāo)為(-30,-40), 目標(biāo)點坐標(biāo)為(18,30). 下面分3種情形討論.

情形1) 圖6和圖7分別為不考慮燃油代價, 只考慮航行中威脅代價時生成的初始航路和優(yōu)化后的航路. 由圖6和圖7可見, 無人機在規(guī)劃路線時基本避開了威脅區(qū), 威脅代價最小, 選擇了一條路徑最遠的航路, 此時燃油代價最大. 航路的數(shù)據(jù)信息列于表1. 由表1可見, 當(dāng)不考慮燃油只考慮威脅代價的權(quán)值時, 新規(guī)劃的航路比初始航路值在航程、時間等方面均有明顯改善, 證明了本文提出優(yōu)化算法的正確性.

圖6 情形1)的初始航路Fig.6 Initial route chart of case 1)

圖7 情形1)優(yōu)化后的航路Fig.7 Optimized route chart of case 1)

無人機航路點數(shù)/個航路航程/km生存概率航路時間/s迭代次數(shù)航路代價原航路18162.12117.882001 731.66新航路25131.41113.252001 405.56

情形2) 圖8和圖9分別為考慮50%權(quán)重燃油代價和50%權(quán)重威脅代價后生成的初始航路和優(yōu)化后航路. 由圖8和圖9可見, 與圖6和圖7相比, 此時無人機規(guī)劃的航路移動到了威脅點較集中的區(qū)域, 威脅代價增加, 燃油代價相對減少. 航路的數(shù)據(jù)信息列于表2. 由表2可見, 當(dāng)將燃油和威脅代價各考慮50%權(quán)重時, 新優(yōu)化的航路較初始航路, 多項數(shù)據(jù)都得以更新, 航路具有可行性, 航路所用算法能規(guī)劃出一條最優(yōu)路線.

圖8 情形2)的初始航路Fig.8 Initial route chart of case 2)

圖9 情形2)優(yōu)化后的航路Fig.9 Optimized route chart of case 2)

無人機航路點數(shù)/個航路航程/km生存概率航路時間/s迭代次數(shù)航路代價原航路17148.72115.732001 512.43新航路25125.75113.162001 277.32

情形3) 圖10和圖11分別為只考慮了燃油代價, 未考慮威脅代價生成的初始航路和優(yōu)化后航路. 由圖10和圖11可見, 航路將進一步移動到威脅更集中的區(qū)域, 此時的燃油代價最小, 但威脅代價最大. 航路的數(shù)據(jù)信息統(tǒng)計列于表3. 由表3可見, 該算法能快速為無人機規(guī)劃出新的滿足各項約束的航路, 在威脅區(qū)域密度相對小的情形下, 航路避開了威脅區(qū), 減少了不必要的代價.

圖10 情形3)的初始航路Fig.10 Initial route chart of case 3)

圖11 情形3)優(yōu)化后的航路Fig.11 Optimized route chart of case 3)

無人機航路點數(shù)/個航路航程/km生存概率航路時間/s迭代次數(shù)航路代價原航路16117.44112.432001 279.63新航路893.67110.01200956.78

以上生成的3條最優(yōu)航路顯示了無人機航路由威脅點較少的區(qū)域移動到威脅點較集中區(qū)域的過程, 新航路對比原航路不僅縮短了航行路程, 同時也減少了航路時間和航路代價. 無人機航路規(guī)劃路線合理, 航路規(guī)劃結(jié)果顯示了權(quán)值變換對該結(jié)果的影響. 實驗結(jié)果表明, 本文提出的無人機航路規(guī)劃算法計算原理簡單、易于實現(xiàn), 生成的最優(yōu)航路既可以保證整個飛行任務(wù)的全局最優(yōu)特性, 也可以滿足飛行任務(wù)的需求.

綜上所述, 本文根據(jù)威脅源的分布, 基于Voronoi圖建模生成了初始的航路規(guī)劃圖, 并運用新的優(yōu)化初始航路算法得到了最終航路. 仿真實驗驗證了由該算法在Voronoi圖中進行航路規(guī)劃的可行性和有效性. 實驗結(jié)果表明, 該航路圖保證了無人機能在航行時間和花費代價更少的情形下成功回避航路中的各種威脅, 并順利到達目標(biāo)點.