基于空間Agent的艦載機群調(diào)度路徑規(guī)劃

張鵬翼,黃百喬,崔博文

(1.中國船舶工業(yè)系統(tǒng)工程研究院，北京 100036；2.北京航空航天大學可靠性與系統(tǒng)工程學院，北京 100191)

艦載機的調(diào)度能力是艦載機出動與回收能力的重要基礎(chǔ)，但調(diào)度方案受到有限艦面空間的嚴重制約，但調(diào)度方案受到有限艦面空間的嚴重制約，必須進行合理調(diào)度路徑規(guī)劃，以減少艦載機群調(diào)度時間，提高機群調(diào)度效率[1-6]。

目前應(yīng)用較為廣泛的算法包括A*搜索算法[7-9]、引力搜索算法[10]、Dijkstra算法[11]、模擬退火算法[12]、遺傳算法[13]、粒子群優(yōu)化算法[14-15]、Multi-agent協(xié)同路徑規(guī)劃[16]，以及隨機生成樹等方法[17]。

一些研究將艦載機視為質(zhì)點，未考慮調(diào)度路徑的干涉問題，這導致路徑可執(zhí)行性下降。常見的解決方案是按圓形、多邊形等幾何形狀對實體和障礙物進行抽象，通過檢測距離實現(xiàn)碰撞檢測[18]。

Multi-Agent在群體路徑規(guī)劃方面已有很好的應(yīng)用，且Agent技術(shù)可支持對Agent外形尺寸的描述。為此，本文擬基于Multi-agent技術(shù)，考慮空間約束以及避障等需求，通過改進的A*算法研究艦載機群多機協(xié)同路徑的聯(lián)合規(guī)劃問題[4，19-20]。

1 機群路徑規(guī)劃過程

艦載機群的調(diào)度過程是艦載機在各個機務(wù)站位從規(guī)定位置或給定位置到達指定機務(wù)站位的過程。以起飛調(diào)度過程為例，其基本情況如圖1所示。

本文考慮一個包含N架次艦載機的機群編隊，可用起飛站位的數(shù)量為M(M

(1)

多機多點的調(diào)度環(huán)境下，調(diào)度過程需滿足一些約束條件，包括飛機調(diào)運最大速度v、飛機起飛位上的最長占用時間為TD、飛機調(diào)度中飛機的偏轉(zhuǎn)角的最大值Ψ。

同時，在機群調(diào)度的過程中，應(yīng)避免干涉，包括兩類：即飛機與固定障礙物的靜態(tài)干涉、兩架飛機同時移動時發(fā)生的動態(tài)干涉。為此給出飛機的最小安全距離d。

2 基于Multi-Agent的艦載機調(diào)度問題建模

2.1 空間環(huán)境Agent

2.1.1空間柵格模型

柵格法[21-22]是路徑規(guī)劃中常用的環(huán)境建模方法，本文借助柵格法對航母艦面環(huán)境進行建模。由于正六邊形柵格具有步間轉(zhuǎn)角適當、障礙物覆蓋能力強等優(yōu)點[23]，本文采用正六邊形柵格對空間環(huán)境進行分割，空間柵格模型如圖2所示。柵格數(shù)量為m×n個，每個柵格的編號分別用二維坐標(i,j)來表示，其中i表示行坐標、j表示列坐標。每個柵格可按兩種狀態(tài)進行初始化，0表示該柵格被占用、1表示該柵格未被占用。劃分的柵格覆蓋所有有效的艦面空間范圍。

在此基礎(chǔ)上，給出一種考慮安全碰撞距離的柵格尺寸的界定方式。調(diào)度過程中，飛機作為不規(guī)則形狀，可以簡化為一個包絡(luò)圓形，設(shè)半徑為R。已知飛機的安全碰撞距離為d，飛機的中心位置為Oi，則飛機與障礙物的距離應(yīng)滿足d(O1O2)>2R+d。柵格劃分規(guī)則為：(1)以O(shè)1，O2為圓心，以(R+d/2)為半徑對兩圓進行擴展，形成兩個相切圓；(2)分別作兩個圓的外接六邊形，單個柵格形狀為相切圓的外接六邊形。則可以計算出邊長為：

(2)

2.1.2空間Agent的基本屬性描述

將每個離散的柵格抽象為空間Agent，并對空間Agent的基本屬性進行如下描述。

1)空間Agent的位置

L={I/I=[x,y]T, 0≤x≤X, 0≤y≤Y}

(3)

式(3)中：X,Y分別表示整個空間行坐標與列坐標的最大值?？臻gAgent依據(jù)位置設(shè)定優(yōu)先級，假設(shè)跑道位置上的優(yōu)先級低。

2)空間Agent的狀態(tài)集

設(shè)置C={-1,0,1}三種狀態(tài)，-1表示固定占用空間，該空間的狀態(tài)為一直不可用；0表示臨時占用，并假設(shè)該空間在有限的時間t后可變?yōu)榭捎脿顟B(tài)；1表示該空間可用。

3)空間Agent的鄰居

每個柵格都至少與一個其他柵格相連接，定義空間Agent鄰居，Lk(xk,yk)表示某一空間Agent的位置，Lk+1(xk+i,yk+i)表示該空間Agent的鄰居坐標，則該空間Agent的鄰居集合為：

(4)

在整個機群的路徑規(guī)劃中，飛機所經(jīng)過的空間Agent連接關(guān)系構(gòu)成了飛機Agent移動的路徑。

2.2 飛機Agent

定義飛機Agent集Ω，且每個飛機Agent在任意空間中的狀態(tài)為：

p=〈A,θ,v〉

(5)

式(5)中：A表示飛機的位置，A應(yīng)滿足與某個空間Agent的位置重合；θ表示為當前位置距離目標位置偏角；v為考慮方向的飛機移動速度，其方向為η。

定義飛機Agent在某一k柵格時的狀態(tài)為pk={Ak,θk,vk}∈P，其中P為np維度的狀態(tài)空間；飛機Agent選擇空間Agent的控制函數(shù)為wk=g(v,ψ,d,ω)，wk體現(xiàn)了根據(jù)飛機Agent轉(zhuǎn)移時的速度、偏轉(zhuǎn)角、安全距離及目的角度等參數(shù)作為飛機Agent決策指標。飛機動態(tài)路徑規(guī)劃問題可以描述為以下狀態(tài)方程，即：

(6)

飛機Agent運動行為學狀態(tài)圖見圖3。飛機調(diào)度至目標位置的行為可用飛機Agent距離目標位置的偏離函數(shù)fgoal表示，fgoal越大越不利于靠近目標位置，fgoal可表示為：

fgoal(Ai)=α1θ(Ai)+α2φ(Ai)

(7)

式(7)中：θ(Ai)表示飛機Agent在位置Ai時距離目標位置G的角度；φ(Ai)表示該飛機Agent在位置Ai時的運動方向與飛機目的位置方向的偏差，且φ(Ai)=η(Ai)-ω；α1，α2表示飛機Agent的兩個偏移角度要素對其奔向目標的作用權(quán)重，且α1+α2=1。

圖3 飛機Agent運動行為學狀態(tài)圖

飛機在路徑規(guī)劃中存在的3種干涉情況：

飛機Agent在對下一個空間Agent進行搜索時，可實現(xiàn)障礙探測距離不小于(2R+d)，這樣可以保證飛機提前轉(zhuǎn)變移動方向，避免與障礙物相撞。

3 基于改進A*算法的艦載機Agent協(xié)同路徑搜索算法

3.1 代價函數(shù)

定義如下的機群單架飛機路徑規(guī)劃的代價函數(shù)f為：

f(Ai)=g(Ai)+fgoal(Ai)

(8)

式(8)中：g(Ai)是飛機Agent移動到Ai位置實際花費時間；fgoal(Ai)是飛機Agent距離目標位置偏離函數(shù)，可以將其作為飛機Agent搜索下一個空間Agent的啟發(fā)式函數(shù)。

飛機Agent與空間Agent的交互規(guī)則如下：

規(guī)則1：空間Agent選擇規(guī)則。

1)飛機Agent在接到任務(wù)后，需要從其當前所屬空間Agent的鄰居集合Neighbor(Ai)中選擇下一個路徑點，Ai表示飛機Agent當前位置；在控制函數(shù)wk=g(v,ψ,d,ω)的約束下，應(yīng)滿足:

(9)

θ(Ai)>90°時，表示飛機在目標位置的前方，因此應(yīng)設(shè)定α1占較大比重，且移動后方向為φ(Ai+1)=min{θ(Ai)，φ(Ai)+Ψ}，從而保證飛機Agent從正向移動至目標位置，提高規(guī)劃的成功率。

θ(Ai)≤90°，φ(Ai)≥90°時，表示飛機在向遠離目標位置的方向移動，因此，應(yīng)設(shè)定α2占大比重，且移動后的方向為φ(Ai+1)=min{θ(Ai)，φ(Ai)-Ψ}從而使得飛機能夠改變移動方向，向目標位置移動。

θ(Ai)≤90°，φ(Ai)≤90°時，表明飛機Agent正在向目標位置移動，可設(shè)置α1，α2均衡比重，且移動后的方向為φ(Ai+1)=min{θ(Ai)，φ(Ai)-Ψ}，保障飛機平穩(wěn)向目標移動。

在飛機Agent的單次規(guī)劃距離2R+d內(nèi)，飛機可以到達所有Selected(Ai)中的位置。假設(shè)飛機Agent從當前位置到Selected(Ai)中每個空間Agent所經(jīng)歷的時間T(φ,θ)是φ,θ的函數(shù)，可表示為：

(10)

由于它對飛機Agent移動時間產(chǎn)生影響，fgoal是影響飛機Agent選擇空間Agent的另一要素，因此，定義：

ming(Ai+1)+fgoal(Ai+1)

(11)

式(11)是飛機Agent選擇下一個空間Agent的依據(jù)，其中g(shù)(Ai+1)=g(Ai)+T(φ,θ)，fgoal(Ai+1)是飛機Agent在Selected(Ai)中每個空間Agent上距離目標位置G的偏差函數(shù)。

代價函數(shù)的值相等時，應(yīng)遵循先入為主的優(yōu)先原則以及空間Agent的優(yōu)先級順序。

規(guī)則2：空間Agent沖突解決規(guī)則。

3.2 算法的執(zhí)行過程

基于兩類Agent的飛機路徑規(guī)劃規(guī)則，給出機群基于A*算法的啟發(fā)式路徑規(guī)劃算法的執(zhí)行過程如圖4所示。

圖4 機群路徑搜索算法執(zhí)行過程

本方法將Agent之間的協(xié)商過程融入到路徑A*算法的實現(xiàn)過程中，可有效地解決機群多機同時調(diào)度的碰撞問題。

4 仿真案例

假設(shè)航母艦面的飛行甲板為斜直兩段式甲板，尺寸約為330 m×80 m，艦載機的尺寸為20 m×15 m(展翼狀態(tài))，如圖1所示。以艦載機作戰(zhàn)的典型任務(wù)模式連續(xù)出擊為例。假設(shè)機群某波次任務(wù)需出動10架次飛機，這些飛機需要從初始停放位置調(diào)度到彈射起飛的準備位，并要求機群調(diào)度過程為并行作業(yè)。

每個飛機初始位置、飛機朝向、目標位置等相關(guān)參數(shù)如表1所示，表1中包含了每架飛機的調(diào)度開始時間和目標位置信息。設(shè)飛機調(diào)度過程最大轉(zhuǎn)角度為60°，最高速度為1.5 m/s，最小安全距離為2 m，飛機起飛位上的準備時間為服從N-(1.8,0.52)的正態(tài)分布，定義起飛任務(wù)開始的時刻為0時刻。

表1 機群飛機相關(guān)參數(shù)

以A3和A4飛機調(diào)度過程對機群路徑規(guī)劃進行說明，其中的避碰實現(xiàn)過程如圖5所示。在第191 s時，A3調(diào)用空間Agent選擇模塊，并根據(jù)算法選擇了位置(745,171)的空間Agent，并發(fā)現(xiàn)該點已經(jīng)被A4飛機臨時占用，因此A3選擇了等待策略，直到A4釋放了該點之后，才完成了移動。飛機A3和飛機A4的路徑節(jié)點分別為:

A3:(690,76)-(745,171)-(800,226)-(910,226)-

(1 020,226)-(1 130,226)-(1 240,226);

A4：(415,171)-(525,171)-(635,171)-

(855,171)-(965,171)-(1 075,171)-

(1 185,171)

圖5 機群動態(tài)避障的過程

全部機群路徑規(guī)劃結(jié)果如表2所示。

表2 機群路徑規(guī)劃結(jié)果

在本次仿真中，從第一架飛機開始到最后一架飛機完成起飛所花費的總時間為658 s，這一結(jié)果說明本文所構(gòu)建的模型是合理可行的。

5 結(jié)論

1)在機群路徑規(guī)劃的研究中，要考慮艦載機的空間特征對機群調(diào)度的影響。

2)利用正六邊形對機群調(diào)運的空間環(huán)境進行柵格建模，并確定空間環(huán)境Agent和飛機Agent。

3)考慮機群調(diào)度中的碰撞問題，引入等待策略和繞行策略對機群路徑規(guī)劃的影響，并利用改進A*算法對飛機Agent 的調(diào)度路徑進行規(guī)劃，實現(xiàn)了機群調(diào)度的全局最優(yōu)。

本文中的研究仍需要進一步深化，例如可以對艦面環(huán)境進行更精確的建模，從而實現(xiàn)路徑規(guī)劃的更優(yōu)性研究。