基于賦權Voronoi圖的艦載機飛行甲板調運路徑規劃*

李曉杰　謝　君

(海軍工程大學電子工程學院　武漢　430033)

LI Xiaojie　XIE Jun

(Electronic Engineering College，Naval University of Engineering, Wuhan　430033)

?

基于賦權Voronoi圖的艦載機飛行甲板調運路徑規劃*

李曉杰謝君

(海軍工程大學電子工程學院武漢430033)

為解決艦載機這一不規則實體在飛行甲板環境中的調運路徑規劃問題，提出了一種基于Voronoi圖的路徑網絡生成方法。對艦載機的調運環境和調運實體進行幾何建模，采用Voronoi圖法進行規劃得到路徑網絡圖并賦權，用Dijkstra算法搜索出調運候選路徑，并進行了碰撞檢測。對某型航母某一時刻的艦載機布列調運進行仿真，結果表明該方法簡單合理，能夠為艦載機調運指控人員提供決策參考。

艦載機; Voronoi圖; 路徑規劃

LI XiaojieXIE Jun

(Electronic Engineering College，Naval University of Engineering, Wuhan430033)

Class NumberTP391.7

1　引言

航母是一個國家國力強盛的重要標志，其作戰任務的完成主要依靠艦載機。現代戰爭節奏加快，對艦載機的出動回收能力提出了新的要求。在較短的時間內為艦載機規劃出一條的合理的調運路徑，能夠有效縮短艦載機的出動準備時間，從而最大限度地發揮艦載機的作戰能力。

艦載機在航母上的調運作業可分為機庫調運和飛行甲板調運兩部分[1]，二者在調運路徑規劃方法上具有相似之處，但不同之處在于：機庫艦載機布列緊湊，若考慮單架艦載機在此密集環境內的調運移動大都沒有實際意義，因此機庫調運作業主要是對艦載機出庫順序的編排[2～3]；飛行甲板艦載機布列較為稀疏，且其調運作業的時間要求更高，路徑規劃意義明顯。文獻[4]創建了艦載機機庫調運作業交通網絡，但并沒有給出具體的路徑規劃方法。文獻[5～8]基于新興智能算法，將艦載機簡化成質點來搜索最短路徑，然而艦載機幾何形狀不規則，簡單的將艦載機視為質點處理并不準確，這就需要對艦載機實體進行合理建模。文獻[9]采用矢量數據和柵格數據結構相結合的方法對機庫內艦載機實體幾何模型進行了描述，可為本文艦載機飛行甲板調運的模型處理提供借鑒。

已有文獻大多以調運路徑長度為優化指標[10～11]，這實際上只考慮了艦載機沿線段運動的用時，由于艦載機轉向時移動較慢，因此艦載機在轉向結點處的用時不可忽略。本文以飛行甲板艦載機調運時間為優化指標，通過對調運環境和調運實體進行幾何建模，采用Voronoi圖進行規劃得到路徑網絡圖并賦權，然后采用Dijkstra算法搜索候選路徑，并進行碰撞檢測。Voronoi圖法的優勢在于：它傾向于使圖中運動實體與障礙物之間的距離最大化，并且Voronoi圖法具有超越其他大多數避障技術的可執行性。通過Voronoi圖法得到的路徑既保證了艦載機調運的安全性要求，又能滿足調運作業的時間要求，提高了調運作業效率。

2　調運環境和調運實體幾何模型

調運環境和調運實體建模的目的是建立一個便于進行路徑規劃使用的數學模型。飛行甲板是艦載機起降和停放的主要場所，艦載機是調運活動中最重要的實體。由于幾何法在建模方面具有精確、高效的優點，因此采用幾何法對飛行甲板和艦載機進行建模。

以美國“尼米茲級”核動力航母為例，其飛行甲板長332.8m，最大寬度78.4m，在對飛行甲板建模時，艦島、起飛裝置、升降機、飛行甲板邊緣以外部分可視為艦載機調運過程中的永久障礙物予以保留，作出其幾何輪廓模型，其他設施忽略。以左下角某一點為坐標原點，使飛行甲板平面都落入第一象限，x軸水平向右，沿艦艏方向，y軸垂直于x軸向上。作出飛行甲板的外接矩形，飛行甲板上面的永久障礙物等比例畫出并定位在坐標系中，并用深色區域表示。飛行甲板幾何模型如圖1所示(比例尺為1∶100)。

圖1　“尼米茲級”核動力航母飛行甲板模型

對艦載機進行建模時，根據機型特點，艦載機幾何結構模型被表示成不同的對稱多邊形，這里每個多邊形就是包圍艦載機實體邊界的簡單平面多邊形。為簡化問題，以艦載機幾何中心作為其旋轉中心，若艦載機模型幾何中心坐標p(x0,y0)確定，則模型其他頂點坐標即可確定。以“尼米茲級”核動力航母上搭載的兩種飛機(F/A-18、E-2C)為例，F/A-18機長17.1m，機寬11.4m；E-2C機長17.54m，機寬24.56m，其模型如圖2所示(單位：cm，艦載機比例尺為1∶100)。

圖2　航母艦載機幾何模型

3　Voronoi圖概述

Voronoi圖由一組連接兩鄰點直線的垂直平分線組成的連續多邊形組成，對于點集{P1,P2,…,Pn}中某一點Pk，其Voronoi區域Sk定義為

Sk={x∈X|d(x,Pk)

(1)

其中，稱點集{P1,P2,…,Pn}為該Voronoi圖劃分的生成元，規劃得到的線段稱為Voronoi邊。普通Voronoi圖如圖3所示。

圖3　普通Voronoi圖

一般圖形的Voronoi圖將生成元擴展到任意形狀的平面多邊形、線段和點。算法思想是首先在這些幾何圖形的邊界上設點(稱為母點)，然后將這些母點視為生成元作出Voronoi圖[12]，然后抹去多邊形內部的Voronoi邊。如圖4為一般圖形的Voronoi圖。

其中小圓點即為母點。本文將圖中規劃出的Voronoi邊視為艦載機調運路徑網絡來求取艦載機調運候選路徑。

圖4　一般圖形Voronoi圖

4　基于賦權Voronoi圖的艦載機調運路徑規劃

艦載機調運路徑規劃是指艦載機按照某一性能指標，搜索出一條從起始狀態到目標狀態的最優或近似最優的無碰撞路徑。基于Voronoi圖法進行艦載機路徑規劃的思路是：艦載機在調運前進過程中時刻滿足一個條件，即若存在可行路徑，則路徑寬度一定大于等于艦載機本身的寬度，基于此，可以以艦載機機寬的一半長度對障礙物進行緩沖區擴充，而將被調運艦載機視為質點，進而采用Voronoi圖法規劃出路徑網絡圖，則若存在可行路徑，可行路徑必存在此路徑網絡圖中，然后對路徑網絡圖進行賦權處理，進而通過Dijkstra算法搜索出候選路徑并進行碰撞檢測。

基于Voronoi圖法的艦載機路徑規劃步驟為：

1)對非調運艦載機和障礙物進行緩沖區擴充，合理設置母點，作出Voronoi圖。

2)將Voronoi圖中非調運艦載機和障礙物緩沖區內的Voronoi邊刪去，得到路徑網絡圖并對圖中各條線段賦權。

3)采用Dijkstra算法在賦權路徑網絡圖中找出候選路徑。

4)進行碰撞檢測，驗證所得候選路徑的可行性。若可行，則該條候選路徑即為所求；若不可行，則只需對已有的賦權路徑網絡圖進行修改，然后返回第3)步。

其流程如圖5所示。

4.1作出Voronoi圖

以艦載機F/A-18為例，當被調運艦載機為機型F/A-18時，其余艦載機為障礙物，需要進行緩沖區擴充。對于非調運艦載機，以被調運艦載機寬度kf的一半長度進行緩沖區擴充，一種擴充模型如圖6所示。

對飛行甲板上的障礙物做相同處理。在調運過程中，由于艦載機可適度伸出飛行甲板邊緣，取被調運艦載機機寬kf的四分之一長度，對飛行甲板邊緣做緩沖區擴充。

圖5　路徑規劃流程圖

圖6　艦載機F/A-18緩沖區擴充

艦載機路徑規劃中Voronoi圖法的運用主要在于母點的設置，母點的設置依據以下原則:

1)將障礙物緩沖區邊界的端點設置為母點。

2)障礙物緩沖區上的母點個數原則上與其邊界長度成正比。

一般來說，母點設置密度越大，則路徑規劃結果越準確，但路徑線段也會越多，造成計算量加大。在設置母點時，應均衡考慮路徑規劃的精度和計算復雜度。以艦載機F/A-18為例，在其邊界端點設置母點以后，在其邊長以kf/2的長度為一個區間，均勻設置母點，如圖7所示為艦載機F/A-18母點設置(單位：cm，比例尺為1∶100)。

圖7　艦載機F/A-18母點設置

利用Voronoi圖法規劃得出的路徑網絡圖中，并不一定包含給定的起始點和目標點，因此需要對已經建立的路徑網絡按就近無碰規則生成包含起始點和目標點的路徑圖。如果起始點和目標點都在路徑網絡中，則不需要處理。如果起始點和目標點都不在路徑網絡中，則在起始點和目標點附近網絡路徑上作一點并分別與起始點和目標點相連接，這樣就可以找到一條從起始點到目標點的路徑。

4.2Dijkstra算法找出候選路徑

對得出的路徑網絡圖進行最優路徑搜索，必要時可先對路徑賦權值，然后進行路徑搜索。本文以調運時間為優化指標，設置艦載機在沿直線段調運時的單位距離用時為tl，線段距離為s，在某結點處(轉向角度為θ，順時針轉向θ取值為正，反之為負)的轉彎用時為tz，并規定tz的取值滿足以下條件：

(2)

由于結點處轉向值具有多個維度，因此需要分別計算各條路徑通過該結點的時間長短。處理方法是將該結點所連各條線段的另一端點(即非此路徑結點)相連接，從而將該結點轉彎用時等價為直線調運用時。圖8(a)為某一結點連接的各條邊，則將時間長短作為權值賦值如圖8(b)所示。

艦載機調運路徑網絡圖經賦權處理后，便可以采用圖論中的Dijkstra算法求解。Dijkstra算法用于計算一個節點到其他所有節點的最短路徑，其主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。算法思想為：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合(用S表示，初始時S中只有一個源點，以后每求得一條最短路徑，就將頂點加入到集合S中，直到全部頂點都加入到S中)，第二組為其余未確定最短路徑的頂點集合(用U表示)，按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。

圖8　路徑網絡圖賦權

根據Dijkstra算法，在當前賦權網絡圖中可以求出一條最短路徑，稱之為艦載機調運候選路徑。

4.3艦載機碰撞檢測模型

這樣得到的候選路徑不一定是可行路徑，以艦載機F/A-18為例，其形狀機長大于機寬，導致在結點處轉彎時有可能與障礙物發生碰撞，因此需要在路徑結點處進行艦載機碰撞檢測[13]。

進行碰撞檢測需要在結點處進行艦載機轉向計算。以艦載機外接矩形作為其碰撞檢測模型，假設艦載機長度為cf，寬度為kf，艦載機的轉向中心坐標為p(x0,y0)，則艦載機的轉向半徑r為

(3)

圖9　艦載機轉向影響區

轉向影響區的計算方法為：艦載機以點p為圓心，以r為半徑，旋轉角度為θ。如圖9所示，深色區域即為轉向影響區。

通過計算轉向影響區與障礙物是否有重疊，即可判斷艦載機在結點處是否與障礙物發生碰撞。若檢測到碰撞，則在賦權網絡圖中刪除連接此結點的兩條線段或將兩條線段權值設置為無窮大，表示此路不可行，然后返回步驟3)重新對修改后的賦權網絡圖進行候選路徑搜索。

5　仿真驗證

以“尼米茲級”核動力航母為例，某一時刻艦載機在飛行甲板上的布列如圖10所示，其中位置S為被調運艦載機起始位置，G為被調運艦載機目標位置。

圖11為對飛行甲板障礙物進行緩沖區處理。在緩沖區邊緣取母點，然后作出Voronoi圖。為簡化計算，已將緩沖區合并處理，并取合并后的緩沖區母點坐標進行計算。圖12為使用Matlab進行Voronoi圖規劃得到的路徑網絡圖，圖13中實線段為使用Dijkstra算法搜索得到的調運候選路徑。

圖10　艦載機飛行甲板布列圖

圖11　飛行甲板障礙物緩沖區處理

圖12　飛行甲板Voronoi圖

圖13　艦載機調運最短路徑

將候選路徑結點坐標按照路徑順序取出，其坐標和轉向角度如表1所示。

表1　路徑節點數據

然后采用作圖法在實體圖中將路徑結點處調運影響區域標出，若與障礙物有重疊，則此路不可行；否則，此路即為所求路徑。如圖14艦載機在調運結點處與障礙物無重疊區域，表明此路可行。

仿真結果表明，該算法簡單合理，在路徑客觀存在的情況下，能在已知給定的環境中利用Voronoi圖法迅速規劃出路徑網絡圖，并由此求解得到艦載機調運路徑。

6　結語

本文在對已知的飛行甲板環境和艦載機實體進行建模的基礎上，研究了Voronoi圖法在艦載機調運作業中的應用，為飛行甲板艦載機調運尋找一條從給定的起始點到目標點的滿足無碰條件的最優路徑，并進行了仿真驗證。結果表明，將Voronoi圖法應用于航母艦載機調運路徑規劃是可行的，該方法能夠有效提高艦載機的調運效率，并且能夠為其他工程領域的優化問題提供借鑒。

圖14　路徑結點碰撞檢測

[1] 劉欽輝,邱長華,王能建.考慮空間約束的艦載機作業調度模型研究[J].哈爾濱工程大學學報，2012，33(11)：1435-1439.

[2] 劉亞杰,李忠猛,謝君.基于Petri網的艦載機出庫調度建模方法[J].火力與指揮控制，2015，40(9)：152-156.

[3] 桂周，劉愛東.某型航母艦載機機庫內調運方法設計[J].計算機與現代化，2014(11)：110-112.

[4] 楊炳恒，韓峰，王海東等.艦載機機庫調運作業路徑[J].艦船科學技術，2012，34(8)：141-143.

[5] 熊華，齊玉東，司維超等.基于GA算法的艦載機艦面移動路徑規劃[J].價值工程，2014，7：35-37.

[6] 李耀宇，朱一凡，齊鳴等.艦載機甲板布列調運優化方法研究[J].指揮控制與仿真，2013，35(2)：125-131.

[7] 司維超，韓維，史瑋韋.基于PSO算法的艦載機艦面布放調度方法研究[J].航空學報，2012,33(11)：2048-2056.

[8] 司維超，韓維，宋巖等.基于多種群協作混沌智能算法的艦載機出動調度[J].計算機應用研究，2013，30(2)：454-457.

[9] 劉亞杰，翁輝，陳曉山.一種基于“矢柵結合”的機庫艦載機調運作業環境建模方法[J].裝甲兵工程學院學報，2014，28(2)：75-78.

[10] 司維超，齊玉東，韓維.基于融合Dijkstra的凸殼算法的艦載機機庫調運規劃[J].系統工程與電子技術，2015，37(3)：583-588.

[11] 劉亞杰，李忠猛，陳曉山.考慮空間約束的機庫艦載機調運路徑規劃方法[J].海軍工程大學學報，2014，26(3)：100-103.

[12] 張有會.關于一般圖形Voronoi圖的近似構造法的研究[J].數值計算與計算機應用，2002(3)：216-225.

[13] 張智，林圣琳，夏桂華等.艦載機甲板調運過程避碰路徑規劃研究[J].哈爾濱工程大學學報，2014，35(1)：9-15.

Path Planning of Carrier-borne Aircrafts on Flight Deck Motion Schedule Based on Assigned Weights Voronoi Diagram*

To solve the problem of path planning of irregular carrier-borne aircrafts motion schedule on flight deck, a generation method of path network was proposed based on Voronoi diagram. This paper modeled the motion schedule environment and entities of carrier-borne aircrafts, used Voronoi diagram method plan path to get path network diagram and assigned weights to the segments of path network diagram, used Dijkstra algorithm search out motion schedule candidate path, and did the collision detection. The motion schedule simulation result of a certain time carrier-borne aircrafts allocation showed that this method was simple and reasonable, and can provide decision reference for command and control officer of carrier-borne aircrafts motion schedule.

carrier-borne aircrafts, Voronoi diagram, path planning

2016年2月31日,

2016年3月12日

李曉杰,男,碩士研究生,研究方向：系統工程。謝君，女，博士，副教授，研究方向：系統工程。

TP391.7

10.3969/j.issn.1672-9730.2016.08.011