基于賦權(quán)Voronoi圖的艦載機(jī)飛行甲板調(diào)運(yùn)路徑規(guī)劃*

李曉杰　謝　君

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

LI Xiaojie　XIE Jun

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

?

基于賦權(quán)Voronoi圖的艦載機(jī)飛行甲板調(diào)運(yùn)路徑規(guī)劃*

李曉杰謝君

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

為解決艦載機(jī)這一不規(guī)則實(shí)體在飛行甲板環(huán)境中的調(diào)運(yùn)路徑規(guī)劃問題，提出了一種基于Voronoi圖的路徑網(wǎng)絡(luò)生成方法。對艦載機(jī)的調(diào)運(yùn)環(huán)境和調(diào)運(yùn)實(shí)體進(jìn)行幾何建模，采用Voronoi圖法進(jìn)行規(guī)劃得到路徑網(wǎng)絡(luò)圖并賦權(quán)，用Dijkstra算法搜索出調(diào)運(yùn)候選路徑，并進(jìn)行了碰撞檢測。對某型航母某一時(shí)刻的艦載機(jī)布列調(diào)運(yùn)進(jìn)行仿真，結(jié)果表明該方法簡單合理，能夠?yàn)榕炤d機(jī)調(diào)運(yùn)指控人員提供決策參考。

艦載機(jī); Voronoi圖; 路徑規(guī)劃

LI XiaojieXIE Jun

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

Class NumberTP391.7

1　引言

航母是一個(gè)國家國力強(qiáng)盛的重要標(biāo)志，其作戰(zhàn)任務(wù)的完成主要依靠艦載機(jī)?，F(xiàn)代戰(zhàn)爭節(jié)奏加快，對艦載機(jī)的出動回收能力提出了新的要求。在較短的時(shí)間內(nèi)為艦載機(jī)規(guī)劃出一條的合理的調(diào)運(yùn)路徑，能夠有效縮短艦載機(jī)的出動準(zhǔn)備時(shí)間，從而最大限度地發(fā)揮艦載機(jī)的作戰(zhàn)能力。

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

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

2　調(diào)運(yùn)環(huán)境和調(diào)運(yùn)實(shí)體幾何模型

調(diào)運(yùn)環(huán)境和調(diào)運(yùn)實(shí)體建模的目的是建立一個(gè)便于進(jìn)行路徑規(guī)劃使用的數(shù)學(xué)模型。飛行甲板是艦載機(jī)起降和停放的主要場所，艦載機(jī)是調(diào)運(yùn)活動中最重要的實(shí)體。由于幾何法在建模方面具有精確、高效的優(yōu)點(diǎn)，因此采用幾何法對飛行甲板和艦載機(jī)進(jìn)行建模。

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

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

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

圖2　航母艦載機(jī)幾何模型

3　Voronoi圖概述

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

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

(1)

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

圖3　普通Voronoi圖

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

其中小圓點(diǎn)即為母點(diǎn)。本文將圖中規(guī)劃出的Voronoi邊視為艦載機(jī)調(diào)運(yùn)路徑網(wǎng)絡(luò)來求取艦載機(jī)調(diào)運(yùn)候選路徑。

圖4　一般圖形Voronoi圖

4　基于賦權(quán)Voronoi圖的艦載機(jī)調(diào)運(yùn)路徑規(guī)劃

艦載機(jī)調(diào)運(yùn)路徑規(guī)劃是指艦載機(jī)按照某一性能指標(biāo)，搜索出一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或近似最優(yōu)的無碰撞路徑?；赩oronoi圖法進(jìn)行艦載機(jī)路徑規(guī)劃的思路是：艦載機(jī)在調(diào)運(yùn)前進(jìn)過程中時(shí)刻滿足一個(gè)條件，即若存在可行路徑，則路徑寬度一定大于等于艦載機(jī)本身的寬度，基于此，可以以艦載機(jī)機(jī)寬的一半長度對障礙物進(jìn)行緩沖區(qū)擴(kuò)充，而將被調(diào)運(yùn)艦載機(jī)視為質(zhì)點(diǎn)，進(jìn)而采用Voronoi圖法規(guī)劃出路徑網(wǎng)絡(luò)圖，則若存在可行路徑，可行路徑必存在此路徑網(wǎng)絡(luò)圖中，然后對路徑網(wǎng)絡(luò)圖進(jìn)行賦權(quán)處理，進(jìn)而通過Dijkstra算法搜索出候選路徑并進(jìn)行碰撞檢測。

基于Voronoi圖法的艦載機(jī)路徑規(guī)劃步驟為：

1)對非調(diào)運(yùn)艦載機(jī)和障礙物進(jìn)行緩沖區(qū)擴(kuò)充，合理設(shè)置母點(diǎn)，作出Voronoi圖。

2)將Voronoi圖中非調(diào)運(yùn)艦載機(jī)和障礙物緩沖區(qū)內(nèi)的Voronoi邊刪去，得到路徑網(wǎng)絡(luò)圖并對圖中各條線段賦權(quán)。

3)采用Dijkstra算法在賦權(quán)路徑網(wǎng)絡(luò)圖中找出候選路徑。

4)進(jìn)行碰撞檢測，驗(yàn)證所得候選路徑的可行性。若可行，則該條候選路徑即為所求；若不可行，則只需對已有的賦權(quán)路徑網(wǎng)絡(luò)圖進(jìn)行修改，然后返回第3)步。

其流程如圖5所示。

4.1作出Voronoi圖

以艦載機(jī)F/A-18為例，當(dāng)被調(diào)運(yùn)艦載機(jī)為機(jī)型F/A-18時(shí)，其余艦載機(jī)為障礙物，需要進(jìn)行緩沖區(qū)擴(kuò)充。對于非調(diào)運(yùn)艦載機(jī)，以被調(diào)運(yùn)艦載機(jī)寬度kf的一半長度進(jìn)行緩沖區(qū)擴(kuò)充，一種擴(kuò)充模型如圖6所示。

對飛行甲板上的障礙物做相同處理。在調(diào)運(yùn)過程中，由于艦載機(jī)可適度伸出飛行甲板邊緣，取被調(diào)運(yùn)艦載機(jī)機(jī)寬kf的四分之一長度，對飛行甲板邊緣做緩沖區(qū)擴(kuò)充。

圖5　路徑規(guī)劃流程圖

圖6　艦載機(jī)F/A-18緩沖區(qū)擴(kuò)充

艦載機(jī)路徑規(guī)劃中Voronoi圖法的運(yùn)用主要在于母點(diǎn)的設(shè)置，母點(diǎn)的設(shè)置依據(jù)以下原則:

1)將障礙物緩沖區(qū)邊界的端點(diǎn)設(shè)置為母點(diǎn)。

2)障礙物緩沖區(qū)上的母點(diǎn)個(gè)數(shù)原則上與其邊界長度成正比。

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

圖7　艦載機(jī)F/A-18母點(diǎn)設(shè)置

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

4.2Dijkstra算法找出候選路徑

對得出的路徑網(wǎng)絡(luò)圖進(jìn)行最優(yōu)路徑搜索，必要時(shí)可先對路徑賦權(quán)值，然后進(jìn)行路徑搜索。本文以調(diào)運(yùn)時(shí)間為優(yōu)化指標(biāo)，設(shè)置艦載機(jī)在沿直線段調(diào)運(yùn)時(shí)的單位距離用時(shí)為tl，線段距離為s，在某結(jié)點(diǎn)處(轉(zhuǎn)向角度為θ，順時(shí)針轉(zhuǎn)向θ取值為正，反之為負(fù))的轉(zhuǎn)彎用時(shí)為tz，并規(guī)定tz的取值滿足以下條件：

(2)

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

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

圖8　路徑網(wǎng)絡(luò)圖賦權(quán)

根據(jù)Dijkstra算法，在當(dāng)前賦權(quán)網(wǎng)絡(luò)圖中可以求出一條最短路徑，稱之為艦載機(jī)調(diào)運(yùn)候選路徑。

4.3艦載機(jī)碰撞檢測模型

這樣得到的候選路徑不一定是可行路徑，以艦載機(jī)F/A-18為例，其形狀機(jī)長大于機(jī)寬，導(dǎo)致在結(jié)點(diǎn)處轉(zhuǎn)彎時(shí)有可能與障礙物發(fā)生碰撞，因此需要在路徑結(jié)點(diǎn)處進(jìn)行艦載機(jī)碰撞檢測[13]。

進(jìn)行碰撞檢測需要在結(jié)點(diǎn)處進(jìn)行艦載機(jī)轉(zhuǎn)向計(jì)算。以艦載機(jī)外接矩形作為其碰撞檢測模型，假設(shè)艦載機(jī)長度為cf，寬度為kf，艦載機(jī)的轉(zhuǎn)向中心坐標(biāo)為p(x0,y0)，則艦載機(jī)的轉(zhuǎn)向半徑r為

(3)

圖9　艦載機(jī)轉(zhuǎn)向影響區(qū)

轉(zhuǎn)向影響區(qū)的計(jì)算方法為：艦載機(jī)以點(diǎn)p為圓心，以r為半徑，旋轉(zhuǎn)角度為θ。如圖9所示，深色區(qū)域即為轉(zhuǎn)向影響區(qū)。

通過計(jì)算轉(zhuǎn)向影響區(qū)與障礙物是否有重疊，即可判斷艦載機(jī)在結(jié)點(diǎn)處是否與障礙物發(fā)生碰撞。若檢測到碰撞，則在賦權(quán)網(wǎng)絡(luò)圖中刪除連接此結(jié)點(diǎn)的兩條線段或?qū)蓷l線段權(quán)值設(shè)置為無窮大，表示此路不可行，然后返回步驟3)重新對修改后的賦權(quán)網(wǎng)絡(luò)圖進(jìn)行候選路徑搜索。

5　仿真驗(yàn)證

以“尼米茲級”核動力航母為例，某一時(shí)刻艦載機(jī)在飛行甲板上的布列如圖10所示，其中位置S為被調(diào)運(yùn)艦載機(jī)起始位置，G為被調(diào)運(yùn)艦載機(jī)目標(biāo)位置。

圖11為對飛行甲板障礙物進(jìn)行緩沖區(qū)處理。在緩沖區(qū)邊緣取母點(diǎn)，然后作出Voronoi圖。為簡化計(jì)算，已將緩沖區(qū)合并處理，并取合并后的緩沖區(qū)母點(diǎn)坐標(biāo)進(jìn)行計(jì)算。圖12為使用Matlab進(jìn)行Voronoi圖規(guī)劃得到的路徑網(wǎng)絡(luò)圖，圖13中實(shí)線段為使用Dijkstra算法搜索得到的調(diào)運(yùn)候選路徑。

圖10　艦載機(jī)飛行甲板布列圖

圖11　飛行甲板障礙物緩沖區(qū)處理

圖12　飛行甲板Voronoi圖

圖13　艦載機(jī)調(diào)運(yùn)最短路徑

將候選路徑結(jié)點(diǎn)坐標(biāo)按照路徑順序取出，其坐標(biāo)和轉(zhuǎn)向角度如表1所示。

表1　路徑節(jié)點(diǎn)數(shù)據(jù)

然后采用作圖法在實(shí)體圖中將路徑結(jié)點(diǎn)處調(diào)運(yùn)影響區(qū)域標(biāo)出，若與障礙物有重疊，則此路不可行；否則，此路即為所求路徑。如圖14艦載機(jī)在調(diào)運(yùn)結(jié)點(diǎn)處與障礙物無重疊區(qū)域，表明此路可行。

仿真結(jié)果表明，該算法簡單合理，在路徑客觀存在的情況下，能在已知給定的環(huán)境中利用Voronoi圖法迅速規(guī)劃出路徑網(wǎng)絡(luò)圖，并由此求解得到艦載機(jī)調(diào)運(yùn)路徑。

6　結(jié)語

本文在對已知的飛行甲板環(huán)境和艦載機(jī)實(shí)體進(jìn)行建模的基礎(chǔ)上，研究了Voronoi圖法在艦載機(jī)調(diào)運(yùn)作業(yè)中的應(yīng)用，為飛行甲板艦載機(jī)調(diào)運(yùn)尋找一條從給定的起始點(diǎn)到目標(biāo)點(diǎn)的滿足無碰條件的最優(yōu)路徑，并進(jìn)行了仿真驗(yàn)證。結(jié)果表明，將Voronoi圖法應(yīng)用于航母艦載機(jī)調(diào)運(yùn)路徑規(guī)劃是可行的，該方法能夠有效提高艦載機(jī)的調(diào)運(yùn)效率，并且能夠?yàn)槠渌こ填I(lǐng)域的優(yōu)化問題提供借鑒。

圖14　路徑結(jié)點(diǎn)碰撞檢測

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

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

[3] 桂周，劉愛東.某型航母艦載機(jī)機(jī)庫內(nèi)調(diào)運(yùn)方法設(shè)計(jì)[J].計(jì)算機(jī)與現(xiàn)代化，2014(11)：110-112.

[4] 楊炳恒，韓峰，王海東等.艦載機(jī)機(jī)庫調(diào)運(yùn)作業(yè)路徑[J].艦船科學(xué)技術(shù)，2012，34(8)：141-143.

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

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

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

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

[9] 劉亞杰，翁輝，陳曉山.一種基于“矢柵結(jié)合”的機(jī)庫艦載機(jī)調(diào)運(yùn)作業(yè)環(huán)境建模方法[J].裝甲兵工程學(xué)院學(xué)報(bào)，2014，28(2)：75-78.

[10] 司維超，齊玉東，韓維.基于融合Dijkstra的凸殼算法的艦載機(jī)機(jī)庫調(diào)運(yùn)規(guī)劃[J].系統(tǒng)工程與電子技術(shù)，2015，37(3)：583-588.

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

[12] 張有會.關(guān)于一般圖形Voronoi圖的近似構(gòu)造法的研究[J].數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用，2002(3)：216-225.

[13] 張智，林圣琳，夏桂華等.艦載機(jī)甲板調(diào)運(yùn)過程避碰路徑規(guī)劃研究[J].哈爾濱工程大學(xué)學(xué)報(bào)，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日

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

TP391.7

10.3969/j.issn.1672-9730.2016.08.011