顧海艷,陳 亮,王多點
1.江蘇警官學(xué)院 計算機信息與網(wǎng)絡(luò)安全系,南京 210031
2.陸軍工程大學(xué) 野戰(zhàn)工程學(xué)院,南京 210007
3.軍事交通學(xué)院 汽車士官學(xué)校,安徽 蚌埠 233011
4.陸軍研究院,北京 100089
近幾十年,有關(guān)多無人機技術(shù)的研究迅猛發(fā)展。其中,多無人機協(xié)同航跡規(guī)劃是無人機執(zhí)行任務(wù)的關(guān)鍵技術(shù)之一。多無人機協(xié)同航跡規(guī)劃研究無人機航跡之間的協(xié)同關(guān)系,包括空間協(xié)同和時間協(xié)同[1]??臻g協(xié)同即避碰問題,要求無人機能夠發(fā)現(xiàn)并消除碰撞沖突。時間協(xié)同,要求所有的無人機在執(zhí)行任務(wù)時滿足一定的時序約束或時間窗約束。
空間協(xié)同的方法主要有兩類:一類是幾何算法[2-3],通過分析成對無人機幾何空間的相對運動關(guān)系,提供被動式避碰策略。幾何法是解決碰撞問題最直觀的方法,然而幾何法只能有效消解成對無人機間的沖突,不適用于多無人機協(xié)同避碰。另一類是將避碰問題轉(zhuǎn)化為最小安全間隔約束條件下的航跡規(guī)劃問題進行求解。求解的算法主要有人工勢場法[4-5]、線性規(guī)劃法[6-7]和模型預(yù)測控制(Model Predictive Control,MPC)[8-9]等方法。其中,人工勢場法是集中式算法,只適用于固定障礙物的情況,并不適合分布式或動態(tài)障礙物的情況[10];線性規(guī)劃法也是集中式算法,并且隨著飛機數(shù)量的增加,計算量呈幾何指數(shù)上升;基于滾動優(yōu)化思想的MPC能夠顯式地考慮各種變量的約束,并滾動實施控制輸入,天然具有實時分布式控制的特點,因此該方法在無人機避碰問題中得到廣泛應(yīng)用[11-12]。文獻[13]采用模型預(yù)測控制方法將編隊重構(gòu)避碰問題轉(zhuǎn)化為滾動優(yōu)化問題,并采用微分進化方法求解。文獻[14]提出了一種改進的基于分布式的非線性MPC方法,設(shè)計的沖突消解算法不僅能夠計算每個無人機的控制量,并能確保無后續(xù)沖突。文獻[15]基于模型預(yù)測控制方法提出了一種實時機間避碰的多無人機協(xié)同航跡規(guī)劃方案。然而,以上研究僅考慮了無人機空間協(xié)同。
時序協(xié)同是時間協(xié)同的重點研究內(nèi)容,而同時到達則是時序協(xié)同中最具研究價值的方向之一。文獻[16-17]研究了基于協(xié)調(diào)變量和協(xié)調(diào)函數(shù)的多無人機協(xié)同航跡規(guī)劃算法,但該方法本質(zhì)上是集中控制方法,存在信息交互大、計算復(fù)雜和魯棒性差的缺點。文獻[18]基于一致性理論的分布式控制結(jié)構(gòu),設(shè)計了結(jié)合航跡規(guī)劃與軌跡控制的策略以實現(xiàn)多無人機同時到達的目的。文獻[19]針對復(fù)雜網(wǎng)絡(luò),提出了基于合作博弈的最優(yōu)一致算法解決多無人機在任務(wù)區(qū)域的集結(jié)問題。文獻[20]提出一種基于精英保持策略的分布式協(xié)同粒子群優(yōu)化算法解決多無人機編隊集結(jié)問題。然而,以上文獻僅考慮了時間協(xié)同。
綜合以上分析可見,雖然模型預(yù)測控制在無人機避碰問題中應(yīng)用廣泛,但同時實現(xiàn)空間協(xié)同和時間協(xié)同的方法卻鮮見于文獻。本文針對多無人機時空協(xié)同問題,提出了基于模型預(yù)測控制的無人機在線協(xié)同航跡規(guī)劃的方法。為了達到同時滿足多無人機空間協(xié)同和時間協(xié)同的目的,改進了碰撞沖突消解規(guī)則,設(shè)計了時間沖突消解規(guī)則,并采用優(yōu)先級的方法實現(xiàn)空間協(xié)同和時間協(xié)同的解耦。仿真實驗驗證了本文方法能夠有效實現(xiàn)多無人機時空協(xié)同。
假設(shè)某次任務(wù)中,要求NV(NV>1)架無人機對任務(wù)區(qū)內(nèi)NT(NT≥1)個目標發(fā)起攻擊。為使攻擊的發(fā)起具有突然性,要求無人機同時到達目標。同時,需要確保無人機在飛行過程中避免碰撞的發(fā)生。此外,規(guī)劃航跡還需要盡可能地降低能耗,以增加無人機執(zhí)行任務(wù)的有效時間。無人機具備以下三種基本能力:感知、通訊和計算能力。感知能力是指無人機可通過機載傳感器獲知當前自身狀態(tài)。通訊能力是指無人機間可實現(xiàn)全域通信,獲取彼此信息。計算能力是指無人機可規(guī)劃航跡。
基于MPC的多無人機分布式時空協(xié)同航跡規(guī)劃框架如圖1所示。該結(jié)構(gòu)運行于無人機平臺上,平臺由3個部分組成:MPC控制器、空間協(xié)同模塊和時間協(xié)同模塊。無人機在每一個通訊周期對外廣播自身預(yù)測的航跡信息和最早/最晚到達時間。同時,無人機接收其他無人機預(yù)測航跡信息和預(yù)測最早/最晚到達時間。無人機平臺的狀態(tài)由機載感應(yīng)設(shè)備獲取。無人機平臺在每一個采樣時刻基于接收的預(yù)測航跡信息、預(yù)測最早/最晚到達時間和自身狀態(tài),在線規(guī)劃航跡。
圖1 基于MPC多無人機分布式時空協(xié)同航跡規(guī)劃框架Fig.1 Structure of space-time cooperative path planning for multi-UAV based on MPC
MPC控制器根據(jù)本機和其他無人機狀態(tài)、目標信息和控制向量約束等輸入,對當前時刻的優(yōu)化問題進行求解,輸出控制時域內(nèi)的控制向量,并應(yīng)用控制向量的第一項對無人機進行控制操作。同時,無人機預(yù)測下一時刻的航跡和最早/最晚到達時間。
空間協(xié)同模塊負責(zé)發(fā)現(xiàn)、管理和消除碰撞沖突。該模塊按照功能屬性又分為3個子模塊[8]:沖突發(fā)現(xiàn)、沖突管理和沖突消解。沖突發(fā)現(xiàn)模塊接收其他無人機的預(yù)測航跡,并與自身MPC控制器輸出的本機預(yù)測航跡進行分析,生成預(yù)測沖突集合。沖突管理模塊根據(jù)無人機獲取的本機狀態(tài)和預(yù)測沖突集合,對預(yù)測沖突集內(nèi)的沖突進行管理和排序,并確定當前需要處理的沖突。沖突消解模塊利用建立的碰撞消解規(guī)則,生成包括航向角和飛行速度在內(nèi)的控制向量約束,并將其發(fā)送給MPC控制器。
時間協(xié)同模塊負責(zé)無人機間的時間協(xié)同。該模塊接收其他無人機預(yù)測的最早/最晚到達時間,結(jié)合無人機自身預(yù)測的最早/最晚到達時間,利用建立的時間沖突消解規(guī)則,生成飛行速度約束,并將其發(fā)送給MPC控制器。
MPC是一種在線優(yōu)化的控制策略。在每個采樣時刻,它根據(jù)當前狀態(tài)、參考信息和預(yù)測信息,通過求解一個優(yōu)化問題,得到一個控制序列,并將該控制序列的第一個控制量作用于被控制對象。在下一個采樣時刻,重復(fù)以上過程,從而形成閉環(huán)控制。MPC結(jié)構(gòu)如圖2所示[15]。
圖2 MPC原理圖Fig.2 MPC schematic diagram
由于每一架無人機具備獨立的感知、通信和計算能力,因此在時空協(xié)同過程中,無人機可分別規(guī)劃各自航跡,故采用分布式的結(jié)構(gòu)進行控制?;贛PC框架的無人機時空協(xié)同航跡規(guī)劃需要解決兩個關(guān)鍵問題:預(yù)測模型和滾動優(yōu)化。
2.2.1 運動模型
記無人機編隊集合V={i|i=1,2,…,NV},其中NV代表無人機的數(shù)目;并記Ui為第i架無人機。假設(shè)所有無人機均在水平面飛行,并將無人機視作平面內(nèi)的一個質(zhì)點。那么,其質(zhì)點運動模型可表示如下[15]:
其中,xi(t)=[xi(t),yi(t),φi(t)]T表示Ui的狀態(tài)向量,[xi(t),yi(t)]T∈R2表示Ui的位置,φi(t)∈[0,2π)表示Ui的航向角(以正北方向為零,逆時針方向正)。ui(t)=[vi(t),ωi(t)]T表示Ui的控制向量,vi(t)∈R表示Ui的速度,ωi(t)∈R表示Ui角速度。
對公式(1)進行離散化處理:設(shè)采樣周期為δ,在第k個采樣時刻,無人機的狀態(tài)量和控制量的離散值記為。在采樣時間周期內(nèi),和和,則無人機的離散化運動方程可表示為[15]:
以向量的形式重寫公式(2):
其中,yi(k+1)表示無人機輸出向量,矩陣Aik、Bik和Cik分別為:
2.2.2 模型預(yù)測
(1)狀態(tài)預(yù)測
假設(shè)不考慮干擾和測量噪聲對無人機的影響,控制時域和預(yù)測時域分別設(shè)置為Nc和Np,并且滿足Nc≤Np。由公式(2)和公式(3)可得到總的模型預(yù)測方程(公式(6))和輸出預(yù)測方程(公式(7))[15]:
其中,j=1,2,…,Np。當Nc<j≤Np,ui(k+j-1|k)=ui(k+Nc-1|k)。
(2)最早/最晚到達時間預(yù)測
假設(shè)在第k個采樣時刻,Ui距離目標的預(yù)測距離為Li(k)。Li(k)可按照下式估計:
2.2.3 滾動優(yōu)化
滾動優(yōu)化的關(guān)鍵是建立優(yōu)化問題模型。在時空協(xié)同過程中,規(guī)劃航跡除了滿足時空協(xié)同的要求外,還需要盡可能地降低無人機能耗,縮短飛行距離,以增加無人機執(zhí)行任務(wù)的有效時間。
(1)目標函數(shù)
在第k個采樣時刻,Ui到目標的距離可表示為:
在一個時間周期內(nèi),Ui最大飛行距離可表示為:,其中表示Ui最大飛行速度。由公式(6)可計算Ui新位置xi(k+Nc|k),新位置到目標的距離可表示為:
顯然,d2越小Ui越接近目標。對d2進行歸一化處理,得到如下目標函數(shù):
(2)約束條件
①無人機性能約束
②時空沖突消解控制約束
③空間協(xié)同距離約束
空間協(xié)同距離約束要求無人機在執(zhí)行任務(wù)的過程中,任意時刻任意2架無人機之間的距離必須大于安全距離ds。假設(shè)為Ui第k步預(yù)測的t時刻的自身位置,為Ui接收到鄰居Uj第k步預(yù)測的t時刻的位置,t∈(tk,tk+Npδ],則有距離約束:
④時間協(xié)同約束
本文研究同時到達約束,對于Ui,同時到達約束可表示為:
其中,O(Ui)表示與Ui同時到達目標的無人機的序號集合。ts為滿足同時到達目標要求的最大允許時間偏差。
空間協(xié)同模塊由沖突發(fā)現(xiàn)模塊、沖突管理模塊和沖突消解模塊三個子模塊組成。
2.3.1 沖突發(fā)現(xiàn)
沖突發(fā)現(xiàn)的目的是生成沖突集合,算法1給出了生成沖突集的過程。ds和de分別表示最小間隔距離(安全距離)和信息交互距離。第2~6行生成Ui的鄰居集合:對于Ui,在每個采樣時刻tk,當Ui與Uj之間的距離小于或等于de時,序號j加入到Ui的鄰居集合Vi(tk)。第7~14行生成沖突集合:對于Ui,如果Ui與Uj(j∈Vi(tk))在預(yù)測航跡上的距離小于或等于ds,表示存在一個潛在沖突。潛在沖突是一個二元組,由入侵無人機序號和沖突時間共同組成。
算法1生成Ui的沖突集
Input:最小間隔距離ds;交互距離de;無人機序號集合V;離散化采樣時間間隔δ;預(yù)測時域Np
Output:沖突集Ci(tk)
2.3.2 沖突管理
在預(yù)測時域內(nèi),當前無人機可能與多架無人機存在碰撞沖突。為了保證沖突處理的一致性,采用多碰撞優(yōu)先級排序思想[8]對沖突進行管理。算法2實現(xiàn)了該過程。第2、3行,對沖突集Ci(tk)按照沖突發(fā)生時間升序排序。第4行,沖突集Ci(tk)中第一個元素作為待處理沖突,并標記待處理沖突的入侵無人機序號。第6~14行,按照速度大小和無人機編號的先后關(guān)系確定Ui與Up之間的leader-follower關(guān)系。
算法2確定leader無人機和follower無人機
Input:沖突集Ci(tk),無人機速度v
Output:leadi和followeri
2.3.3 沖突消解
按照無人機的航向關(guān)系,沖突可分為兩種:相向沖突和同向沖突。相向沖突是指2架無人機相向而行發(fā)生的沖突,如圖3所示。同向沖突是指2架無人機同向飛行,后面的無人機由于速度較快,迫近前面的無人機,從而產(chǎn)生的沖突,如圖4所示。
圖4 同向沖突Fig.4 Chasing collision conflict diagram
為了消解兩架無人機之間的沖突,文獻[8]提出了航向規(guī)則和速度規(guī)則。然而,文獻[8]僅提出了相向沖突的消解規(guī)則,沒有給出同向沖突的消解規(guī)則。當使用文獻[8]中規(guī)則解決同向沖突時,規(guī)則不能發(fā)揮有效作用,甚至可能導(dǎo)致碰撞的發(fā)生。本文在實驗中,將用實例進一步說明此種情況。針對以上存在的問題,補充了以下同向沖突消解規(guī)則。設(shè)φL和φF分別代表leader和follower的航向角,0≤φL<2π,0≤φF<2π。Δφ表示leader的航向到follower航向的順時針角度,0≤Δφ<2π。
對于相向沖突:
(1)當0≤Δφ≤π,增加φL和φF;
(2)當π<Δφ<2π,減小φL和φF。
對于同向沖突:
(1)當0≤Δφ≤π,減小φL,增加φF;
(2)當π<Δφ<2π,增加φL,減小φF。
ΔφF和ΔφL分別表示leader無人機和follower無人機的航向角控制增量。圖5和圖6分別圖解了相向沖突和同向沖突的航向角規(guī)則。圖中的虛線箭頭表示發(fā)生沖突的leader無人機和follower無人機的初始航向,實線表示按照沖突消解規(guī)則調(diào)整后的航向。
圖5 消解相向沖突的航向規(guī)則Fig.5 Heading rules for opposite conflict
圖6 消解同向沖突的航向規(guī)則Fig.6 Heading rules for chasing conflict
速度規(guī)則:增加leader無人機的速度,減小follower無人機的速度。
記無人機編隊中需要滿足同時到達目標約束的無人機的集合為O。記,TL=。其中,和表示Ui預(yù)計最早和最晚到達目標時間。取TA=(TE+TL)2,TA表示集合O中的無人機期望到達時間。那么Ui在tk時刻的期望飛行速度為:。Li(k)為公式(8)計算得到的預(yù)測距離。那么,可建立以下時間沖突消解規(guī)則:
由于空間協(xié)同和時間協(xié)同都需要調(diào)整無人機的控制向量,兩個問題耦合在一起,相互影響,不方便處理??紤]到無人機飛行過程中避碰的重要性和偶發(fā)性,提出優(yōu)先級的方法對空間協(xié)同和時間協(xié)同進行解耦。規(guī)定空間協(xié)同的優(yōu)先級高于時間協(xié)同優(yōu)先級,也就是說,無人機在需要同時處理空間協(xié)同和時間協(xié)同時,優(yōu)先處理空間協(xié)同,直到不存在潛在碰撞時,再處理時間協(xié)同。
綜合以上分析,給出基于DMPC思想的無人機時空協(xié)同航跡規(guī)劃流程圖,如圖7。
圖7 多無人機時空協(xié)同航跡規(guī)劃流程圖Fig.7 Structure of space-time cooperative path planningfor multi-UAV
在采樣時刻tk,Ui通過信息交互獲取其他無人機預(yù)測信息,通過機內(nèi)傳感器獲取當前狀態(tài)信息xi(tk),判斷當前是否需要進行空間協(xié)同。若需要,利用空間協(xié)同單元確定Ui控制量(角速度和飛行速度)約束。若不需要,接著判斷是否需要進行時間協(xié)同。若需要,利用時間協(xié)同單元確定Ui控制量(飛行速度)約束。然后,將xi(tk)、控制量約束、Ui的性能約束輸入到MPC控制器,MPC調(diào)用DDECS算法[21]求解優(yōu)化問題,生成Ui的控制序列ui(tk)。接著,對Ui應(yīng)用ui(tk)中的第一項。更新狀態(tài)信息xi(tk+1),并基于xi(tk+1)和ui(tk),對未來的航跡和最早/最晚到達時間進行預(yù)測。最后,將預(yù)測的航跡和預(yù)測的最早/最晚到達時間發(fā)送給其他無人機。重復(fù)以上過程,直至任務(wù)結(jié)束。
假設(shè)任務(wù)空域范圍為50 km×50 km,無人機的最小速度為200 m/s,最大速度為300 m/s,最大角速度為10(°)/s,沖突發(fā)現(xiàn)距離de=8 km,安全飛行半徑為ds=2 km,預(yù)測時域為20 s。無人機航跡規(guī)劃的采樣時間間隔δ=1 s。攻擊發(fā)起距離設(shè)置1 km。最大允許時間偏差ts=5 s。DDECS算法的種群規(guī)模設(shè)置為20,最大函數(shù)評價次數(shù)設(shè)置為2 000,其他參數(shù)參考文獻[21]。仿真實驗環(huán)境:Intel Core i7-7500U 2.70 GHz、8 GB內(nèi)存和64 bit Microsoft Windows 10。為了驗證本文方法的有效性,選擇3個無人機航跡規(guī)劃場景進行仿真實驗。
本文采用無人機航向角的變化角度進行編碼[22]。如圖8所示,每個基因位上的αi(i=1,2,…,n)表示單位時長無人機航向角的變化值,因此采用實數(shù)編碼方式。無人機以恒定的速度V飛行,按照規(guī)劃的航向角完成機動,形成航跡S。具體來說,假設(shè)點是航跡S的起點,此時無人機的航向角為θ0。第一個基因位α1表示在單位時間Δt內(nèi),無人機的航向角改變了α1。那么無人機飛行Δt時長后的位置可以按照下式近似計算:
重復(fù)以上過程,可得到航跡上各點的坐標位置。
圖8 編碼方式示意圖Fig.8 Schematic diagram of coding
2架無人機相向飛行,無人機的初始條件和仿真參數(shù)見表1。實驗中,MPC單次循環(huán)最大耗時336 ms,平均耗時199 ms,可以滿足δ=1 s條件下實時性要求。時空協(xié)同航跡規(guī)劃仿真結(jié)果如圖9(a)所示。
表1 實驗1的初始條件和參數(shù)Table 1 Initial conditions and simulation parametersof experiment 1
依據(jù)初始條件,檢測到潛在沖突(無人機1、2,11 s)。2架無人機按照航向角規(guī)則和速度規(guī)則,迅速調(diào)整航向角和飛行速度。圖9(c)和9(d)展示了航向角和飛行速度的變化情況。圖9(b)展示了2架無人機飛行過程中的相對距離??梢钥闯觯涸诘?6 s,2架無人機距離最小,相距2.26 km,滿足空間協(xié)同的要求。2架無人機到達目標的時間均為107 s,時間差距小于5 s,滿足時間協(xié)同的要求。而文獻[8]規(guī)劃得到的到達目標的時間分別是106和125,時間差距為19 s,大于5 s,不滿足時間協(xié)同的要求。
圖9 2架無人機(相向沖突)航跡規(guī)劃仿真結(jié)果Fig.9 Path planning simulation results of 2 UAVs(opposite conflict)
2架無人機向同一方向飛行,無人機的初始條件和仿真參數(shù)見表2。實驗中,MPC的單次循環(huán)最大耗時179 ms,平均耗時151 ms,可以滿足δ=1 s條件下實時性要求。時空協(xié)同航跡規(guī)劃仿真結(jié)果如圖10(a)所示。
依據(jù)初始條件,檢測到潛在沖突(無人機1、2,3 s)。2架無人機按照航向角規(guī)則和速度規(guī)則,調(diào)整航向角和速度。圖10(c)和10(d)展示了航向角和飛行速度的變化情況。圖10(b)展示了2架無人機飛行過程中的相對距離。可以看出:在第47 s,2架無人機距離最小,相距2.30 km,滿足空間協(xié)同的要求。2架無人機到達目標的時間均為70 s,時間差距小于5 s,滿足時間協(xié)同的要求。
表2 實驗2的初始條件和參數(shù)Table 2 Initial conditions and simulation parameters of experiment 2
本問題中的沖突屬于同向沖突,若采用文獻[8]中的方法,2架無人機將會相伴飛行,無法消解沖突(如圖11所示)。并且在第11 s,無人機間的距離為1.97 km,將會發(fā)生碰撞。
4架無人機同時執(zhí)行任務(wù),無人機的初始條件和仿真參數(shù)見表3。實驗中,MPC單次循環(huán)最大耗時692 ms,平均耗時為530 ms,滿足δ=1 s條件下實時性要求。時空協(xié)同航跡規(guī)劃仿真結(jié)果如圖12(a)所示。
圖10 2架無人機(同向沖突)航跡規(guī)劃仿真結(jié)果Fig.10 Path Planning simulation results of 2 UAVs(chasing conflict)
圖11 采用文獻[8]沖突消解規(guī)則的仿真結(jié)果Fig.11 Simulation results with conflict resolution rules in Ref[8]
表3 實驗3的初始條件和參數(shù)Table 3 Initial conditions and simulation parameters of experiment 3
依據(jù)初始的條件,檢測到潛在沖突(無人機3、4,19 s)、(無人機1、2,26 s)和(無人機1、4,45 s)共3組。運用規(guī)則,調(diào)整航向角和速度。圖12(c)和圖12(d)展示了航向角和飛行速度的變化情況。圖12(b)展示任意2架無人機的相對距離。可以看出:在第42 s,無人機1與無人機2間距離最小,距離2.33 km,滿足空間協(xié)同的要求。4架無人機到達目標的時間均為136 s,最大時間差距小于5 s,滿足時間協(xié)同的要求。文獻[8]規(guī)劃得到的到達時間分別為T1=134 s,T2=167 s,T3=162 s和T4=176 s,最大時間差距42 s,遠大于5 s,不滿足時間協(xié)同的要求。
本文提出了一種基于DMPC的同時處理空間協(xié)同和時間協(xié)同的在線航跡規(guī)劃問題的方法。設(shè)計了由MPC控制器、空間協(xié)同模塊和時間協(xié)同模塊組成的多無人機分布式時空協(xié)同航跡規(guī)劃框架結(jié)構(gòu)。該算法的優(yōu)點主要有三點:(1)通過對空間協(xié)同問題和同時到達問題設(shè)定不同的優(yōu)先級,實現(xiàn)兩種問題的解耦,從而可同時處理避碰問題和同時到達問題;(2)分析了以往航向規(guī)則的不足,提出了同向沖突的解決規(guī)則;(3)設(shè)計了時間沖突消解規(guī)則。最后,通過實驗驗證了本文提出的算法的有效性。未來,一方面將研究通信時延和時變通信拓撲條件下的多無人機協(xié)同航跡規(guī)劃;另一方面,將研究多個優(yōu)化目標的多無人機協(xié)同航跡規(guī)劃問題。
圖12 4架無人機時空協(xié)同航跡規(guī)劃仿真結(jié)果Fig.12 Path planningsimulation results of 4 UAVs