基于Voronoi圖的無人機航路改進規劃

史紅玉, 劉淑芬

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

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

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

1 基于Voronoi圖的威脅區域建模

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

1.1 Voronoi圖的定義與性質

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

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

(1)

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

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

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

性質3Voronoi圖在增減生成元時, 通過局域動態特性只影響相鄰的空間區域, 不影響整個空間的劃分.

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

1.2 Voronoi圖算法的主要思想

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

1.3 Voronoi圖建模

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

(2)

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

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

(3)

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

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

p=K/R4,

(4)

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

(5)

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

(6)

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

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

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

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

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

2.1 威脅代價

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

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

(7)

其中,r1,r2為加權系數, 分別表示威脅和距離在弧的權值中所占的比.

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

(8)

2.2 燃油代價

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

ffurl=kli,

(9)

其中k為比例系數.

2.3 總代價

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

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

(10)

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

3 對初始航路的優化

3.1 B樣條插值

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

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

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

(11)

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

(12)

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

(13)

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

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

3.2 優化初始航路改進算法

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

1) 初始化. 首先備份原始路徑中的節點坐標, 確定當前的迭代次數和迭代次數最大值.

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

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

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

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

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

WeightA=sum(LengthWeightA).

同理可求出另外兩條邊的權重值.

圖5 權重比較示意圖Fig.5 Schematic diagram of weight comparison

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

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

4) 根據對權重值的比較, 找到最優線路的節點坐標, 獲取新的兩點坐標若是初始節點中的坐標則不做改變, 如果不是則替換相應的初始節點坐標.

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

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

4 仿真實驗

為了驗證本文提出的對初始路徑優化算法的有效性, 對圖1所示的具有40個威脅源的區域進行航路規劃. 實驗環境為: Inter CPU 2.20 GHz, 4.00 GB內存, 操作系統為Win7專業版, 仿真環境采用MATLAB R2014a實現.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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