張鵬翼,黃百喬,崔博文

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

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

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

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

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

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

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

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

(1)

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

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

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

2.1 空間環(huán)境Agent

2.1.1空間柵格模型

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

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

(2)

2.1.2空間Agent的基本屬性描述

將每個(gè)離散的柵格抽象為空間Agent，并對(duì)空間Agent的基本屬性進(jìn)行如下描述。

1)空間Agent的位置

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

(3)

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

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

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

3)空間Agent的鄰居

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

(4)

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

2.2 飛機(jī)Agent

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

p=〈A,θ,v〉

(5)

式(5)中：A表示飛機(jī)的位置，A應(yīng)滿足與某個(gè)空間Agent的位置重合；θ表示為當(dāng)前位置距離目標(biāo)位置偏角；v為考慮方向的飛機(jī)移動(dòng)速度，其方向?yàn)棣恰?/p>

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

(6)

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

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

(7)

式(7)中：θ(Ai)表示飛機(jī)Agent在位置Ai時(shí)距離目標(biāo)位置G的角度；φ(Ai)表示該飛機(jī)Agent在位置Ai時(shí)的運(yùn)動(dòng)方向與飛機(jī)目的位置方向的偏差，且φ(Ai)=η(Ai)-ω；α1，α2表示飛機(jī)Agent的兩個(gè)偏移角度要素對(duì)其奔向目標(biāo)的作用權(quán)重，且α1+α2=1。

圖3 飛機(jī)Agent運(yùn)動(dòng)行為學(xué)狀態(tài)圖

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

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

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

3.1 代價(jià)函數(shù)

定義如下的機(jī)群?jiǎn)渭茱w機(jī)路徑規(guī)劃的代價(jià)函數(shù)f為：

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

(8)

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

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

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

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

(9)

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

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

θ(Ai)≤90°，φ(Ai)≤90°時(shí)，表明飛機(jī)Agent正在向目標(biāo)位置移動(dòng)，可設(shè)置α1，α2均衡比重，且移動(dòng)后的方向?yàn)棣?Ai+1)=min{θ(Ai)，φ(Ai)-Ψ}，保障飛機(jī)平穩(wěn)向目標(biāo)移動(dòng)。

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

(10)

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

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

(11)

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

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

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

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

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

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

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

4 仿真案例

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

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

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

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

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 機(jī)群動(dòng)態(tài)避障的過程

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

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

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

5 結(jié)論

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

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

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

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