基于融合Dijkstra的凸殼算法的艦載機(jī)機(jī)庫調(diào)運(yùn)規(guī)劃

司維超,齊玉東,韓 維

(1.海軍航空工程學(xué)院兵器科學(xué)與技術(shù)系,山東煙臺(tái)264001; 2.海軍航空工程學(xué)院飛行器工程系,山東煙臺(tái)264001)

基于融合Dijkstra的凸殼算法的艦載機(jī)機(jī)庫調(diào)運(yùn)規(guī)劃

司維超1,齊玉東1,韓 維2

(1.海軍航空工程學(xué)院兵器科學(xué)與技術(shù)系,山東煙臺(tái)264001; 2.海軍航空工程學(xué)院飛行器工程系,山東煙臺(tái)264001)

為解決艦載機(jī)在特殊的機(jī)庫環(huán)境中調(diào)運(yùn)路徑規(guī)劃問題,提出了一種融合Dijkstra方法的凸殼算法。首先,建立了飛機(jī)機(jī)庫調(diào)運(yùn)的數(shù)學(xué)模型以及相關(guān)基礎(chǔ)模型,為算法應(yīng)用提供基礎(chǔ)。其次,給出了利用凸殼算法進(jìn)行路徑規(guī)劃的執(zhí)行機(jī)制,并利用其建立了飛機(jī)調(diào)運(yùn)可行路徑有向圖。然后,利用Dijkstra方法對(duì)該可行路徑有向圖進(jìn)行最短路徑求解,最終給出最優(yōu)路徑。最后,將該方法應(yīng)用于庫茲涅佐夫號(hào)航母飛機(jī)機(jī)庫調(diào)運(yùn)。結(jié)果表明,該方法原理正確,且能夠較好地給出最優(yōu)路徑。

飛機(jī)調(diào)運(yùn);路徑規(guī)劃;Dijkstra;凸殼算法;最優(yōu)路徑

0 引 言

航空母艦在當(dāng)今世界作用越來越重要,其絕大多數(shù)作戰(zhàn)使命都需要并且只能由飛機(jī)來承擔(dān)和完成。通過對(duì)飛機(jī)進(jìn)行有效的保障,可以大大提高航空母艦的作戰(zhàn)能力[1]。飛機(jī)保障過程中的一個(gè)重要方面是對(duì)其在機(jī)庫甲板上進(jìn)行有序地移動(dòng)[2]。鑒于機(jī)庫甲板面積較小,為了保證安全,必須進(jìn)行合理規(guī)劃[3]。

隨著現(xiàn)代戰(zhàn)爭(zhēng)的節(jié)奏加快,航母作用日益突出,而提高其艦載機(jī)調(diào)運(yùn)效率顯得尤為重要[4]。在滿足安全約束條件下,根據(jù)機(jī)庫特殊情況,動(dòng)態(tài)給出艦載機(jī)移動(dòng)路線需要進(jìn)一步研究。

國外針對(duì)飛機(jī)的調(diào)運(yùn)主要依靠人工指揮[5]。此種方法不可避免會(huì)導(dǎo)致效率低下及出現(xiàn)錯(cuò)誤。另外,我國尚未具備成熟的飛機(jī)機(jī)庫調(diào)運(yùn)經(jīng)驗(yàn),亟待進(jìn)行研究。為此本文通過對(duì)飛機(jī)機(jī)庫調(diào)運(yùn)問題進(jìn)行建模,并利用融合Dijkstra方法[6]的凸殼算法[78]對(duì)艦載機(jī)機(jī)庫調(diào)運(yùn)問題進(jìn)行求解,提高了效率和準(zhǔn)確性。

1 飛機(jī)機(jī)庫調(diào)運(yùn)路徑規(guī)劃問題建模

飛機(jī)在機(jī)庫中調(diào)運(yùn)路徑規(guī)劃問題可以看為在滿足約束條件下的最短路求解問題[9]。由于機(jī)庫的環(huán)境相對(duì)艦面來說更狹小,所以在調(diào)運(yùn)飛機(jī)時(shí)要滿足的約束條件也更多更嚴(yán)格[10]。數(shù)學(xué)模型建立如下:

目標(biāo)函數(shù)

約束條件

式中,F為調(diào)運(yùn)所要達(dá)到的目標(biāo)效果,即在滿足約束條件下,盡可能縮短飛機(jī)在機(jī)庫內(nèi)的行走路徑,從而縮短飛機(jī)出庫時(shí)間;S為飛機(jī)沿某條機(jī)庫行走路徑的距離;Ai為第i條艦載機(jī)行走路線,aij為第i條行走路線中的第j個(gè)中間路徑節(jié)點(diǎn),規(guī)定其位于機(jī)庫坐標(biāo)平面內(nèi)的坐標(biāo)為(xij,yij);n為路徑節(jié)點(diǎn)的個(gè)數(shù);a0為路徑的起始點(diǎn);an為路徑的終點(diǎn); Dz表示當(dāng)前狀態(tài)下機(jī)庫中所有的障礙物區(qū)域的集合;Qleft表示機(jī)庫右側(cè)邊界所表示的X軸值;Qright表示機(jī)庫左側(cè)邊界所表示的X軸值;Qtop表示機(jī)庫上側(cè)邊界所表示的Y軸值;Qbottom表示機(jī)庫下側(cè)邊界所表示的Y軸值;dsafe表示最小安全間隔,即不與機(jī)庫四周發(fā)生碰撞的最小間距;lij為飛機(jī)第i條路徑的第j個(gè)移動(dòng)路徑段的長度;Lmax為所要求的起點(diǎn)和終點(diǎn)之間最大不能超過的路徑總長度[11]。

由上述可知,式(2)表明了飛機(jī)移動(dòng)的起點(diǎn)和目的地。式(3)表示所規(guī)劃的飛機(jī)行走路線不能與障礙物發(fā)生碰撞。式(4)表示所規(guī)劃出的最終路徑中相鄰兩個(gè)節(jié)點(diǎn)的連線不能與任何障礙物相交。式(5)和(6)表示飛機(jī)路徑節(jié)點(diǎn)不能與機(jī)庫四周墻壁發(fā)生碰撞。式(7)表示所規(guī)劃的飛機(jī)行走路線的距離必須具有上限約束。

2 基于融合Dijkstra的凸殼算法的最短路徑規(guī)劃

2.1 環(huán)境建模

(1)機(jī)庫模型的建立

本部分主要對(duì)飛機(jī)調(diào)運(yùn)所需的機(jī)庫環(huán)境進(jìn)行建模,給出整個(gè)大環(huán)境。此處可以近似將機(jī)庫看作為一個(gè)矩形區(qū)域。例如針對(duì)庫茲涅佐夫號(hào)航母機(jī)庫矩形區(qū)域如圖1所示。

圖1 機(jī)庫模型

(2)飛機(jī)實(shí)體模型和障礙物凸殼模型建立

為了簡化問題,用包圍飛機(jī)最大邊界的簡單凸多邊形來表示艦載機(jī),如圖2所示,圖中,Ga、Gb和Gc為按照比例縮放時(shí)的相關(guān)尺寸。

圖2 飛機(jī)凸多邊形模型

為了能夠?qū)⑦\(yùn)動(dòng)實(shí)體簡化為一個(gè)質(zhì)點(diǎn),方便凸殼算法的執(zhí)行,在規(guī)劃路徑時(shí),首先需要將障礙物凸多邊形進(jìn)行擴(kuò)充,建立障礙物凸殼多邊形[12],如圖3所示,圖中各參數(shù)可以通過測(cè)量給出。

圖3 飛機(jī)凸殼模型

(3)建立艦載機(jī)位姿模型

針對(duì)每一個(gè)障礙物凸殼模型,當(dāng)確定其狀態(tài)(位置、朝向等)時(shí)需要用到二維平面變換。具體如圖4所示。

圖4 障礙物位姿模型

令A(yù)模型中任意一頂點(diǎn)坐標(biāo)為(x,y),則對(duì)應(yīng)新的坐標(biāo)計(jì)算過程為

(4)碰撞檢測(cè)模型的建立

此處需要對(duì)路徑節(jié)點(diǎn)進(jìn)行碰撞檢測(cè),主要是判斷所規(guī)劃出移動(dòng)路徑上的節(jié)點(diǎn)是否位于其他障礙物內(nèi)部,即是否發(fā)生碰撞[1314]。具體步驟如下:

步驟1 明確當(dāng)前機(jī)庫中各個(gè)障礙物狀態(tài)及路徑節(jié)點(diǎn)坐標(biāo)M(a,b),進(jìn)行初步判斷。依據(jù)為通過判斷該障礙物的最左側(cè)點(diǎn)和最右側(cè)點(diǎn)是否位于X=a直線兩側(cè),由此可以減少參與點(diǎn)碰撞檢測(cè)的障礙物數(shù)量。

步驟2 對(duì)篩選出來的障礙物與點(diǎn)M(a,b)進(jìn)行最終點(diǎn)碰撞檢測(cè)。以某個(gè)障礙物模型A為例,示意圖如圖5所示。

圖5 碰撞檢測(cè)示意圖

(1)分別比較A的每一條邊與直線X=a的關(guān)系,看是否有交點(diǎn)。令某邊的端點(diǎn)為(xi,yi)和(xj,yj),則判斷依據(jù)如下:

①(max(xi,xj)≥a)and(min(xi,xj)＜a)表明X=a直線穿過該邊或其右端點(diǎn);

②(max(xi,xj)＞a)and(min(xi,xj)≤a)表明X=a直線穿過該邊或其左側(cè)端點(diǎn)。

(2)計(jì)算交點(diǎn)。據(jù)比例公式(a-xi)/(xj-xi)=(yib1)/(yi-yj),可以得出b1=yi-(a-xi)(yi-yj)/(xjxi),則所求交點(diǎn)為(a,b1),示意圖如圖6所示。

圖6 求交示意圖

(3)針對(duì)障礙物每條邊分別進(jìn)行上述比較,使得最后可以給出一個(gè)交點(diǎn)集合(無重復(fù),且因?yàn)闉橥苟噙呅嗡宰疃嘤袃蓚€(gè)交點(diǎn),記為(a,b1)和(a,b2))。

(4)進(jìn)行最終的檢測(cè):若min(b1,b2)＜y＜max(b1,b2),表明M點(diǎn)介于兩交點(diǎn)之間,另據(jù)凸多邊形的性質(zhì)可知,M點(diǎn)必位于障礙物內(nèi)部,也即此時(shí)會(huì)出現(xiàn)碰撞現(xiàn)象;否則不發(fā)生。

2.2 基于凸殼算法的可行路徑有向圖建模

(1)初始化機(jī)庫布局環(huán)境,明確運(yùn)動(dòng)實(shí)體及調(diào)運(yùn)目的地,建立障礙物凸殼模型。

根據(jù)飛機(jī)位姿模型確定機(jī)庫環(huán)境。假設(shè)有12架飛機(jī)(以Z1-Z12表示),令Z1作為運(yùn)動(dòng)實(shí)體(簡化為一質(zhì)點(diǎn)),位置D作為調(diào)運(yùn)目的地,并對(duì)障礙物執(zhí)行凸殼擴(kuò)充,如圖7所示。

圖7 假設(shè)的機(jī)庫局部凸殼環(huán)境模型

圖7中,四周虛線表示機(jī)庫墻壁進(jìn)行凸殼內(nèi)擴(kuò)后的界限。運(yùn)動(dòng)實(shí)體Z1的運(yùn)動(dòng)軌跡不能與障礙物凸殼模型及四周虛線框有碰撞,即其間隔必須大于等于最小安全距離。

(2)執(zhí)行凸殼算法,尋求可行路徑有向圖。

凸殼算法主要是基于兩點(diǎn)之間線段距離最短的思想。首先,建立起點(diǎn)和終點(diǎn)的連線,如果該連線不與任何障礙物凸殼模型相交,則其即為待規(guī)劃的最優(yōu)路徑;否則,連線穿過障礙物凸殼模型,則該連線將障礙物分為上下兩部分,此時(shí)可以將路徑規(guī)劃問題轉(zhuǎn)換為求解障礙物上下兩部分頂點(diǎn)集的凸包問題,從而可以得到上下兩條最優(yōu)路徑(假如存在的話)。其次,對(duì)當(dāng)前規(guī)劃出路徑上相鄰兩個(gè)節(jié)點(diǎn)間的路徑段重復(fù)執(zhí)行以上的路徑規(guī)劃,直至所有路徑段均不與障礙物發(fā)生碰撞。最后,按照所記錄的無碰撞路徑節(jié)點(diǎn)建立路徑有向圖。

①建立起點(diǎn)Z1和終點(diǎn)D之間的有向線段Z1D,確定線段Z1D所穿越的障礙物。

由圖7可知,有向線段Z1D直接穿過障礙物Z6和Z7,但是由于障礙物Z5與Z6有交集,在計(jì)算凸包時(shí)必須把Z5算入線段Z1D間接穿過的障礙物,故最終被穿越的障礙物集合為R={Z5,Z6,Z7}。

②以線段Z1D為分界線,將R中障礙物分為上下兩部分,并對(duì)各自的頂點(diǎn)集合排序。

判斷障礙物集合R中各障礙物頂點(diǎn)屬于“上半部分”或者“下半部分”的依據(jù)為:假設(shè)經(jīng)過Z1點(diǎn)和D點(diǎn)直線方程為f(x,y)=ax+by+c,且待判斷的某頂點(diǎn)坐標(biāo)為(xi,yi),則f(xi,yi)=(axi+byi+c)≥0,表示該頂點(diǎn)位于線段Z1D上部;f(xi,yi)=(axi+byi+c)＜0,表示該頂點(diǎn)位于線段Z1D下部。

由圖7可知,點(diǎn)ui(i=1,2,…,16)屬于上部;點(diǎn)di(i= 1,2)屬于下部。分別對(duì)兩頂點(diǎn)集按照“先按X坐標(biāo)升序,當(dāng)X坐標(biāo)相同時(shí),再按Y坐標(biāo)升序”的原則進(jìn)行排序,結(jié)果為:上部頂點(diǎn)集Up Points={Z1,u1,u2,u3,u4,u5,u6,u7,u8,u9,u10,u11,u12,u13,u14,u15,u16,D};下部頂點(diǎn)集Down-Points={Z1,d1,d2,D}。

③分別計(jì)算Up Points的上凸包和DownPoints的下凸包。

所謂凸包是指頂點(diǎn)集中凸點(diǎn)的集合。在進(jìn)行凸包搜索時(shí),需要判斷相鄰3個(gè)頂點(diǎn)的排列順序(順時(shí)針或逆時(shí)針)。這里采用矢量叉積的方式進(jìn)行判斷,具體如下:

點(diǎn)P0、P1、P2按照順時(shí)針的順序排列,則P1點(diǎn)為上凸包點(diǎn),依據(jù)為(P2-P0)×(P1-P0)＜0;點(diǎn)P0、P1、P2按照逆時(shí)針的順序排列,則P1點(diǎn)為下凸包點(diǎn),依據(jù)為(P2-P0) ×(P1-P0)＞0;點(diǎn)P0、P1、P2共線,P1點(diǎn)不為凸包點(diǎn),依據(jù)為(P2-P0)×(P1-P0)=0。

針對(duì)圖7所示情況,對(duì)其頂點(diǎn)集Up Points按照順時(shí)針判斷方式求其上凸包頂點(diǎn);對(duì)其頂點(diǎn)集Down Points按照逆時(shí)針判斷方式求其下凸包頂點(diǎn)。結(jié)果為:上凸包點(diǎn)集Up-Bulgy Points={Z1,u1,u4,u6,u9,u11,u13,u15,D};下凸包點(diǎn)集DownBulgy Points={Z1,d1,d2,D}。

④依次連接上凸包及下凸包中各頂點(diǎn),并進(jìn)行初步優(yōu)化。將上下凸包各個(gè)頂點(diǎn)連接起來,如圖8中虛線所示。

圖8 初始凸包圖

此時(shí)得到兩條初始規(guī)劃路徑UpRoute(Z1,D)和DownRoute(Z1,D)。但是,由圖8可以看出,這兩條路徑并不是完全滿足要求的,例如上凸包中的點(diǎn)u4位于障礙物Z5內(nèi)部等。為此需要對(duì)UpRoute(Z1,D)和DownRoute(Z1, D)分別進(jìn)行碰撞檢測(cè)。

具體如下:

步驟1 對(duì)上下凸包執(zhí)行碰撞檢測(cè),去除不合格點(diǎn)。經(jīng)檢測(cè)可知,此處上凸包中的點(diǎn)u4與障礙物Z5發(fā)生碰撞,所以將其進(jìn)行排除。點(diǎn)u9雖然不位于障礙物內(nèi)部,但是線段u6u9穿越障礙物,所以將其進(jìn)行排除。

上凸包點(diǎn)集Up Bulgy Points={Z1,u1,u6,u11,u13,u15, D};下凸包點(diǎn)集Down Bulgy Points={Z1,d1,d2,D}。

步驟2 對(duì)新的上下凸包點(diǎn)集執(zhí)行優(yōu)化操作,去除冗余點(diǎn)。由于飛機(jī)在機(jī)庫中調(diào)運(yùn)時(shí),應(yīng)該盡量避免頻繁轉(zhuǎn)向。為此對(duì)上下凸包分別進(jìn)行檢查可知,上凸包中點(diǎn)u13是多余的,可以刪掉。此時(shí)新的上下凸包點(diǎn)集為:上凸包點(diǎn)集Up-Bulgy Points={Z1,u1,u6,u11,u15,D};下凸包點(diǎn)集Down-Bulgy Points={Z1,d1,d2,D}。

利用線段連接上下新凸包各個(gè)頂點(diǎn),如圖9中虛線所示。

圖9 優(yōu)化后凸包圖

圖10 最終可行路徑有向圖

2.3 基于Dij kstra方法的最短路徑求解

利用凸殼算法最終可以得出可行路徑有向圖,其復(fù)雜情況完全取決于參與凸殼運(yùn)算的障礙物的數(shù)量,且不同的起點(diǎn)和終點(diǎn)其可行路徑有向圖也互不相同。為了能夠覆蓋所有可能情況,此處將所有的可行路徑有向圖求最優(yōu)路徑問題統(tǒng)一看為賦權(quán)有向圖求最短路問題,從而可以利用統(tǒng)一的算法進(jìn)行求解。目前對(duì)于所有非負(fù)權(quán)有向圖求最短路最好的方法是Dijkstra方法[15],為此本文采用該算法求解飛機(jī)機(jī)庫調(diào)運(yùn)可行路徑有向圖的最短路徑。對(duì)圖10所示的可行路徑有向圖進(jìn)行簡化提取,如圖11所示。其中的權(quán)值取兩點(diǎn)間距離。

圖11 簡化后賦權(quán)可行路徑有向圖

Dijkstra方法的具體步驟如下:

步驟1 初始化。給定賦權(quán)有向圖D=(V,A)。用P, T分別表示某個(gè)點(diǎn)的P標(biāo)號(hào)、T標(biāo)號(hào),Si表示第i步時(shí),具P標(biāo)號(hào)點(diǎn)的集合。為了在求出從vs到各點(diǎn)的距離的同時(shí),也求出從vs到各點(diǎn)的最短路,給每個(gè)點(diǎn)v以一個(gè)λ值,算法終止時(shí),如果λ(v)=m,表示在從vs到v的最短路上,v的前一個(gè)點(diǎn)是vm;如果λ(v)=M,則表示D中不含從vs到v的路;λ(v)=0表示v=vs。

初始i=0時(shí),令S0={vs},P(vs)=0,λ(vs)=0;對(duì)每一個(gè)v≠vs,令T(v)=+∞,λ(v)=M,k=s。

步驟2 如果Si=V,算法終止,這時(shí),對(duì)每個(gè)v∈Si, d(vs,v)=P(v);否則轉(zhuǎn)入步驟3。

步驟3 考查每個(gè)使(vk,vj)∈A且vj?Si的點(diǎn)vj。如果T(vj)＞P(vk)+ωkj,則把T(vj)修改為P(vk)+ωkj,把λ(vj)修改為k;否則轉(zhuǎn)入步驟4。

對(duì)圖11所示的可行路徑有向圖執(zhí)行進(jìn)行Dijkstra求解可知,從Z1到D的最短路為(Z1,d1,d2,u22,D),長度為23.9。

3 實(shí)例仿真

將上述求解過程實(shí)際應(yīng)用于求解庫茲涅佐夫號(hào)航母機(jī)庫飛機(jī)的調(diào)運(yùn)。

(1)確定機(jī)庫初始調(diào)運(yùn)環(huán)境,以及運(yùn)動(dòng)實(shí)體和目的地。假設(shè)庫茲涅佐夫號(hào)航母的某種機(jī)庫布局如圖12所示,且需要將飛機(jī)S調(diào)運(yùn)至升降機(jī)D。

圖12 實(shí)例之機(jī)庫局部布局環(huán)境圖

(2)建立機(jī)庫障礙物凸殼環(huán)境模型,如圖13所示。

圖13 實(shí)例之機(jī)庫凸殼環(huán)境模型

(3)執(zhí)行融合Dijkstra方法的凸殼算法,求最優(yōu)路徑。

圖14中粗折線為所規(guī)劃的最優(yōu)路徑,與實(shí)際最優(yōu)路徑基本吻合,這表明本文所提的方法是可行的。對(duì)不同情況下的飛機(jī)分別進(jìn)行路徑規(guī)劃,都能夠得到較好的結(jié)果。由此可知,本文所述方法可較好地對(duì)飛機(jī)機(jī)庫調(diào)運(yùn)問題進(jìn)行求解,所得結(jié)果基本符合實(shí)際要求。另外,算法執(zhí)行的復(fù)雜程度主要取決于參與運(yùn)算的障礙物數(shù)量,而與路徑長度關(guān)系不大,為此在不同數(shù)量障礙物下對(duì)算法分別執(zhí)行50次獨(dú)立路徑規(guī)劃運(yùn)算,提取規(guī)劃時(shí)間的統(tǒng)計(jì)結(jié)果如圖15所示。由圖15可知,當(dāng)有6個(gè)障礙物參與運(yùn)算時(shí),所需計(jì)算時(shí)間平均為28 s,所以計(jì)算效率基本符合實(shí)際要求。

圖14 實(shí)例之最優(yōu)調(diào)運(yùn)路徑

圖15 平均計(jì)算時(shí)間

4 結(jié) 論

將飛機(jī)機(jī)庫調(diào)運(yùn)問題轉(zhuǎn)化為在滿足特殊約束條件下的最短路徑求解問題,提出了一種融合Dijkstra方法的凸殼算法,并對(duì)最短路進(jìn)行規(guī)劃,克服了以往靠人工引導(dǎo)的缺陷。通過將該方法實(shí)際應(yīng)用于庫茲涅佐夫號(hào)航母飛機(jī)機(jī)庫調(diào)運(yùn),結(jié)果表明,該方法原理正確,且所得結(jié)果符合實(shí)際。

[1]Han W,Wang Q G.Conspectus of aircraft carrier and carrier plane[M].Yantai:Naval Aeronautical and Astronautical University Press,2009:37-41.

[2]Duan PP,Nie H.Effect of carrier movement on aircraft’s landing and arresting performance[J].Journal of Nanchang Hangkong University(Natural Sciences),2012,26(1):53-60. (段萍萍,聶宏.航母運(yùn)動(dòng)對(duì)飛機(jī)著艦攔阻性能的影響分析[J].南昌航空大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,26(1):53-60.)

[3]Fu Y G,Ding M Y,Zhou C P.Phase angle-encoded and quantum-behaved particle swarm optimization applied to three-dimensional route planning for UAV[J].IEEE Trans.on Systems, Man and Cybernetics-Part A:Systems and Humans,2012,42 (2):511-526.

[4]Authority of the Chief of Naval Operations.CV Flight/Hangar Deck NATOPS Manual[R].Washington,D C:Authority of the Chief of Naval Operations 2001.

[5]Johnston J S.A feasibility study of a persistent monitoring system for the flight deck of U.S[D].USA:Navy Aircraft Carriers Department of the Air Force Air University,2009.

[6]Deng Y,Chen Y,Zhang Y,et al.Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment[J].Applied Soft Computing,2012,12(3):1231-1237.

[7]Liu R,Fang B,Tang Y Y.A fast convex hull algorithm with maximum inscribed circle affine transformation[J].Neurocomputing,2012,77(1):212-221.

[8]Brun C,Dufourd J F,Magaud N.Designing and proving correct a convex hull algorithm with hypermaps in Coq[J].Computational Geometry,2012,45(8):436-457.

[9]Hu Y M,Liu W M.Multi-constrained shortest path model and soving[J].Journal of Hunan University of Science&Technology(Natural Science Edition),2010,25(1):87 90.(胡耀民,劉偉銘.多約束最短路模型與求解[J].湖南科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,25(1):87-90.)

[10]Sun S N.Modern aircraft carrier[M].Shanghai:Shanghai Popular Science Press,2000:1-50.(孫詩南.現(xiàn)代航空母艦[M].上海:上?？茖W(xué)普及出版社,2000:1 50.)

[11]Zheng C W,Yan P,Ding M Y,et al.Route planning for air vehicles[M].Beijing:National Defense Industry Press,2008: 70-79.(鄭昌文,嚴(yán)平,丁明躍,等.飛行器航跡規(guī)劃[M].北京:國防工業(yè)出版社,2008:70-79.)

[12]Yang Y,Liu Y C.A path planning algorithm based on convex hull for autonomous service robot[J].Transaction of Beijing Institute of Technology,2011,31(1):54-58.(楊毅,劉亞辰.一種基于凸殼的智能服務(wù)機(jī)器人路徑規(guī)劃算法[J].北京理工大學(xué)學(xué)報(bào),2011,31(1):54-58.)

[13]Prete J,Mitchell J S B.Safe routing of multiple aircraft flows in the presence of time-varying weather data[C]∥Proc.of the AIAA Guidance,Navigation,and Control Conference,2004: 1-21.

[14]Dieguez A R,Sanz R,Lopez J.Deliberative on-line local path planning for autonomous mobile robots[J].Journal of Intelligent and Robotic Systems,2003,37(1):12-19.

[15]Xiong D G,Hu Y W.A matrix method of solving shortest path using Dijkstra algorithm[J].Journal of Henan Polytechnic University,2011,30(5):608-612.(熊德國,胡勇文.用Dijkstra算法求解最短路的矩陣方法[J].河南理工大學(xué)學(xué)報(bào), 2011,30(5):608- 612.)

Carrier plane transportation in hangar based on convex hull algorithm combined with Dijkstra

SI Wei-chao1,QI Yu-dong1,HAN Wei2
(1.Department of Ordnance Science and Technology,Naval Aeronautical and Astronautical University,Yantai 264001,China;2.Department of Airborne Vehicle Engineering, Naval Aeronautical and Astronautical University,Yantai 264001,China)

In order to solve the carrier plane moving route planning problem in special hangar environment, a new convex hull algorithm combined with Dijkstra is proposed.Firstly,the mathematic model of the carrier plane moving problem and correlative basic models are established,which supply foundation for the using of the algorithm.Secondly,the executive mechanism of using the convex hull algorithm to plan routes is provided, which is used to establish the carrier plane moving route directed graph.Then the best route could be found by using Dijkstra to operate on the directed graph.Finally,the method is used to solve the carrier plane moving route planning problem in hangar of the Kuznetsov aircraft carrier.Simulation results indicate that the principle of the method is correct and it performs well for getting the best route.

carrier plane moving;route planning;Dijkstra;convex hull algorithm;best route

TP 202

A

10.3969/j.issn.1001-506X.2015.03.17

司維超(1984-),男,講師,博士,主要研究方向?yàn)榕炤d機(jī)技術(shù)研究及應(yīng)用。E-mail:sxwxc1984@163.com

齊玉東(1974-),男,教授,博士,主要研究方向?yàn)橹笓]控制及優(yōu)化。E-mail:LuckydevilSI@163.com

韓 維(1970-),男,教授,博士,主要研究方向?yàn)榕炤d機(jī)技術(shù)研究及應(yīng)用。

E-mail:Luckydevilhan@163.com

網(wǎng)址:www.sys-ele.com

1001-506X(2015)03-0583-06

2014-03-24;

2014-07-24;網(wǎng)絡(luò)優(yōu)先出版日期:2014-09-28。

網(wǎng)絡(luò)優(yōu)先出版地址:http://w ww.cnki.net/kcms/detail/11.2422.TN.20140928.1716.019.html