司維超,齊玉東,韓 維

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

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

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

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

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

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

0 引 言

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

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

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

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

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

目標函數(shù)

約束條件

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

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

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

2.1 環(huán)境建模

(1)機庫模型的建立

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

圖1 機庫模型

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

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

圖2 飛機凸多邊形模型

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

圖3 飛機凸殼模型

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

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

圖4 障礙物位姿模型

令A模型中任意一頂點坐標為(x,y),則對應新的坐標計算過程為

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

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

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

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

圖5 碰撞檢測示意圖

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

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

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

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

圖6 求交示意圖

(3)針對障礙物每條邊分別進行上述比較,使得最后可以給出一個交點集合(無重復,且因為為凸多邊形所以最多有兩個交點,記為(a,b1)和(a,b2))。

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

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

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

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

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

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

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

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

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

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

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

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

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

③分別計算Up Points的上凸包和DownPoints的下凸包。

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

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

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

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

圖8 初始凸包圖

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

具體如下:

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

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

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

利用線段連接上下新凸包各個頂點,如圖9中虛線所示。

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

圖10 最終可行路徑有向圖

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

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

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

Dijkstra方法的具體步驟如下:

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

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

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

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

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

3 實例仿真

將上述求解過程實際應用于求解庫茲涅佐夫號航母機庫飛機的調(diào)運。

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

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

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

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

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

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

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

圖15 平均計算時間

4 結(jié) 論

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

[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. (段萍萍,聶宏.航母運動對飛機著艦攔阻性能的影響分析[J].南昌航空大學學報(自然科學版),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].湖南科技大學學報(自然科學版),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普及出版社,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.(鄭昌文,嚴平,丁明躍,等.飛行器航跡規(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.(楊毅,劉亞辰.一種基于凸殼的智能服務機器人路徑規(guī)劃算法[J].北京理工大學學報,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].河南理工大學學報, 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-),男,講師,博士,主要研究方向為艦載機技術(shù)研究及應用。E-mail:sxwxc1984@163.com

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

韓 維(1970-),男,教授,博士,主要研究方向為艦載機技術(shù)研究及應用。

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)絡優(yōu)先出版日期:2014-09-28。

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