基于元胞遺傳算法的多無人機(jī)編隊(duì)集結(jié)路徑規(guī)劃

，，， ，

(南京航空航天大學(xué)自動化學(xué)院，江蘇 南京 211106)

0 引言

近年來，無人機(jī)被廣泛應(yīng)用于各個領(lǐng)域，并扮演著越來越重要的作用。為了提高無人機(jī)執(zhí)行任務(wù)的效率，人們往往會采取多無人機(jī)協(xié)同編隊(duì)完成任務(wù)的方式，其前提條件之一便是多機(jī)集結(jié)路徑規(guī)劃[1]。

無人機(jī)航跡規(guī)劃需要滿足在自身動力學(xué)約束環(huán)境下，能夠規(guī)避威脅區(qū)，安全到達(dá)任務(wù)地點(diǎn)。目前常用的航跡規(guī)劃算法有A*算法、動態(tài)規(guī)劃算法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、群智能算法等[2]。而對于多機(jī)集結(jié)路徑規(guī)劃，除了需要滿足單機(jī)航跡規(guī)劃需求之外，還需要考慮多機(jī)到達(dá)時間的協(xié)同性以及多機(jī)之間的防碰撞[3-5]。

在此，提出了一種基于元胞遺傳算法的航跡規(guī)劃方法[6-9]，保證了全局搜索和局部尋優(yōu)之間的平衡，更好地保證了種群的多樣性。然后針對多機(jī)集結(jié)路徑規(guī)劃的要求，設(shè)計(jì)了時間協(xié)同和防碰撞策略。最后通過仿真，驗(yàn)證了該算法的有效性和穩(wěn)定性。

1 單機(jī)航跡規(guī)劃

1.1 航跡編碼

對于每一條航跡，都是由一個個航點(diǎn)組成，本文不考慮無人機(jī)飛行高度，將航跡規(guī)劃簡化為二維空間內(nèi)的路徑規(guī)劃，故所涉及到的速度和航程計(jì)算都是在二維空間內(nèi)的投影。記起始點(diǎn)坐標(biāo)為S(xs,ys)，終點(diǎn)坐標(biāo)為G(xg,yg)，中間n個航點(diǎn)的坐標(biāo)為Pi(xi,yi) (i=1, 2, 3, …,n)，則每一條航跡都可以表示為(S,P1,P2,P3, …,Pn,G)的航點(diǎn)序列，為了方便說明，S和G可分別表示為P0(x0,y0)和Pn+1(xn+1,yn+1)。

1.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于評價航跡的優(yōu)劣，航跡的適應(yīng)度越大，說明越滿足規(guī)劃要求。在規(guī)劃一條航跡時，需要盡可能避開威脅區(qū)域，同時為了使油耗最小，航跡應(yīng)盡可能短。此外，由于多機(jī)集結(jié)具有時間約束性，所規(guī)劃的航跡應(yīng)滿足速度約束條件。因此，選取威脅代價、航程代價和速度代價來表示適應(yīng)度函數(shù)。

1.2.1 威脅代價

假設(shè)二維空間內(nèi)有q個威脅點(diǎn)，各威脅點(diǎn)坐標(biāo)和威脅半徑分別為Wj=(xj,yj)，rj(j=1, 2, 3, …,q)。

(1)

圖1 威脅代價計(jì)算示意

dij為Wj到航線段PiPi+1最短距離，由此可以得出Wj到航線段PiPi+1的威脅代價值：

(2)

則航線段PiPi+1威脅代價值為：

(3)

記整條航跡的威脅代價值為S，則：

(4)

1.2.2 航程代價

在航跡規(guī)劃過程中，需要使油耗最小，因此整個航程也需要盡量小。對于每條航跡，計(jì)算航跡的總長度L，由此可以得出航程代價值：

(5)

1.2.3 速度代價

多無人機(jī)集結(jié)具有時間約束性，假設(shè)所有無人機(jī)都需要在T時間內(nèi)集結(jié)完畢，那么對于每架無人機(jī)，其飛行速度v應(yīng)滿足：

(6)

為了節(jié)省燃油以及應(yīng)對突發(fā)狀況，無人機(jī)應(yīng)盡量飛行在巡航速度vc，由此可以得出速度代價值V為：

V=v-vcvmin≤v≤vmax

(7)

綜上所述，可以得到航跡的總代價值C為：

C=ksS+klL+kvV

(8)

ks為威脅代價權(quán)重系數(shù)；kl為航程代價權(quán)重系數(shù)；kv為速度代價權(quán)重系數(shù)。使用f表示一個足夠大的數(shù)，則航跡的適應(yīng)度函數(shù)F可以表示為：

F=f-C

(9)

F值越大，說明規(guī)劃的航跡越符合要求。

1.3 種群初始化

在進(jìn)行遺傳操作之前，需要先初始化航跡種群。由于航跡是由一個個航點(diǎn)組成的，生成初始航跡也就是生成一系列的航點(diǎn)。采用端點(diǎn)啟發(fā)初始化的方法來生成初始航點(diǎn)，第i個航點(diǎn)Pi(xi,yi)為：

(10)

(11)

這樣便保證了單個航線段步長不小于起點(diǎn)到終點(diǎn)的最小航線段。

1.4 初始化元胞空間

假設(shè)初始種群規(guī)模即初始航跡條數(shù)為N，建立N=u×w的二維元胞空間，將初始種群隨機(jī)分布在元胞空間內(nèi)。采用Moore型鄰居結(jié)構(gòu)，元胞空間邊界采用周期型邊界，如圖2所示。在每一個(周期擴(kuò)展)九宮格內(nèi)，所有的“☆”都是“★”的鄰居，所有的遺傳操作都在鄰居之間進(jìn)行。

圖2 元胞空間結(jié)構(gòu)

1.5 遺傳操作

1.5.1 選擇

由于遺傳操作只在鄰居之間進(jìn)行，對于每一個中心元胞，只在它的鄰居元胞內(nèi)選擇個體遺傳到下一代。在此，使用輪盤賭的方式進(jìn)行個體選擇，對于每一個鄰居元胞內(nèi)的個體，分別計(jì)算其適應(yīng)度值Fi，則第i個元胞內(nèi)的個體被選中的概率psi為：

(12)

1.5.2 交叉

定義交叉概率pc，在[0,1]之間取隨機(jī)值pcr，若pcr≤pc，則進(jìn)行交叉操作。

交叉操作如圖3所示，進(jìn)行交叉操作時，對于中心元胞個體Qcen和被選中的鄰居元胞個體Qngb，除去初始點(diǎn)和終點(diǎn)，分別選擇第c個航點(diǎn)，將其和前一個航點(diǎn)斷開，將Qcen的c-1航點(diǎn)和Qngb的c航點(diǎn)相連，將Qngb的c-1航點(diǎn)和Qcen的c航點(diǎn)相連，分別計(jì)算新生成的2個航跡適應(yīng)度，選取適應(yīng)度大的進(jìn)入下一代，記為Qnew。

圖3 交叉操作

1.5.3 變異

定義變異概率pm，在[0, 1]之間取隨機(jī)值pmr，若pmr≤pm，則進(jìn)行變異操作。

(13)

取其中的最小值hm：

hm=min(h1,h2,h3,…,hq)

(14)

若hm>0，則說明Pe在威脅區(qū)外，保留個體Qnew無需變異，否則繼續(xù)進(jìn)行變異操作。

如圖4所示，假設(shè)hm對應(yīng)的威脅點(diǎn)為W，威脅半徑為r，變異之后產(chǎn)生新的航點(diǎn)Pe′(xe′,ye′)，則新航點(diǎn)坐標(biāo)為：

(15)

ke為取值在[1, 2]之間隨機(jī)增益系數(shù)，ω為隨機(jī)旋轉(zhuǎn)角度，使得變異具有隨機(jī)性。變異之后，Pe便跳到了距離Pe長度為ke|hm|的新航點(diǎn)Pe′上，由于變異具有隨機(jī)性，因此變異之后Pe′可能依舊在威脅區(qū)內(nèi)。

圖4 變異操作

在變異操作之后，更新Qnew為新的個體，仍然命名為Qnew，計(jì)算Qnew的適應(yīng)度Fnew，并與中心元胞個體Qcen的適應(yīng)度Fcen進(jìn)行比較，若Fnew>Fcen，則替換中心元胞個體為Qnew，否則放棄新個體。

1.6 算法終止條件

由于算法計(jì)算量大，一般很難在短時間內(nèi)找到全局最優(yōu)解，因此可以設(shè)置以下終止條件以節(jié)省計(jì)算時間：

a. 設(shè)置較為合適的適應(yīng)度標(biāo)準(zhǔn)F0，一旦新個體中有適應(yīng)度值不小于F0的出現(xiàn)，則終止尋優(yōu)，選擇該個體作為最終航跡。

b. 設(shè)置最大進(jìn)化次數(shù)K，一旦進(jìn)化次數(shù)達(dá)到K次，則終止尋優(yōu)，選取其中適應(yīng)度值最大的個體作為最終航跡。

同時設(shè)置以上2個條件，可以得到相對滿足條件的“次優(yōu)解”。

1.7 航跡平滑處理

由于無人機(jī)飛行性能的約束，它的最小轉(zhuǎn)彎角必須大于某個閾值φm，由上述算法生成的最終航跡可能存在大量角度小于φm的尖角，不滿足無人機(jī)轉(zhuǎn)向要求，因此需要對這些尖角進(jìn)行平滑處理。

對于航跡上需要進(jìn)行平滑處理的航點(diǎn)Pi，若Pi-1和Pi+1的連線不經(jīng)過威脅區(qū)，如圖5a所示。則將Pi移至航線段的中點(diǎn)Pi′處。若Pi-1和Pi+1的連線經(jīng)過威脅區(qū)，如圖5b所示，則分別在PiPi-1和PiPi+1的1/M處取點(diǎn)Pi1和Pi2，連接Pi1Pi2，組成新的航跡。

圖5 航跡平滑處理

2 多機(jī)協(xié)同規(guī)劃

多機(jī)協(xié)同飛行主要需要考慮同時到達(dá)目標(biāo)點(diǎn)和飛行過程中的防碰撞。對于可以相互通信的無人機(jī)而言，只需相互之間實(shí)時匯報(bào)自己的狀態(tài)，再通過速度調(diào)整即可。對于通信無法正常建立的情況下，可由下文提出的策略進(jìn)行調(diào)整。

2.1 時間協(xié)同

多無人機(jī)編隊(duì)集結(jié)需要多架無人機(jī)在規(guī)定時間內(nèi)到達(dá)指定集結(jié)地點(diǎn)，最簡單的方法就是進(jìn)行速度控制。對于第k架無人機(jī)，其初始飛行速度vk0為：

(16)

Lk為第k架無人機(jī)的總航程，T為集結(jié)時間。由于無人機(jī)飛途中會有各種不確定性，無法保證全程都是按照設(shè)定速度飛行，由此提出了速度調(diào)整策略。

擴(kuò)展第k架無人機(jī)航跡的航點(diǎn)編碼Pki(xki,yki)，增加到達(dá)第i個航點(diǎn)的約定時間tki，其值為：

(17)

Lki為無人機(jī)飛到Pki時的總航程。這樣得到新的航點(diǎn)編碼Pki(xki,yki,tki)。無人機(jī)飛行到Pki時，根據(jù)已飛時間tk和飛到下一航點(diǎn)的約定時間tk(i+1)，可以確定下一階段的飛行速度vk：

(18)

通過不斷地對速度進(jìn)行微調(diào)，便可以基本保證在約定時間到達(dá)對應(yīng)航點(diǎn)，直至到達(dá)終點(diǎn)。

2.2 防碰撞策略

由于每架無人機(jī)都是單獨(dú)進(jìn)行航跡規(guī)劃，因此規(guī)劃出的航跡之間可能存在交叉或距離過近的情況，可能導(dǎo)致無人機(jī)之間發(fā)生碰撞，因此需要進(jìn)行無人機(jī)之間防碰撞設(shè)計(jì)。

本文是在簡化的二維空間內(nèi)進(jìn)行的航跡規(guī)劃，而無人機(jī)實(shí)際飛行在三維空間內(nèi)，因此，對于航跡有交叉或者距離小于安全距離Ds的無人機(jī)，可使其飛行在不同的高度層，每層之間相差至少1個安全距離。為了平衡燃油消耗，二維空間內(nèi)航程大的無人機(jī)應(yīng)飛行在較低的高度。這樣，即使航跡有交叉或距離過近，也不會發(fā)生碰撞事故。

3 仿真驗(yàn)證

為驗(yàn)證本算法的有效性，設(shè)計(jì)了仿真驗(yàn)證環(huán)節(jié)，約束條件如下所述：

a. 待集結(jié)的無人機(jī)為3架，分別為UAV1，UAV2和UAV3。

b. 各無人機(jī)的起點(diǎn)分別為S1(10, 10)，S2(20, 0)，S3(0, 30)，終點(diǎn)為G(100, 100)，單位為 km。

c. 設(shè)置6個威脅區(qū)域，威脅中心和威脅半徑分別為：W1(15, 88)，r1=10；W2(23, 50),r2=15；W3(25, 15),r3=10；W4(57, 10),r4=10；W5(23, 50),r5=15；W6(55, 75),r6=20。

d. 無人機(jī)最小轉(zhuǎn)彎角φm=60°，最小速度vmin=40 km/h，最大速度vmax=200 km/h，巡航速度vc=140 km/h，安全距離Ds=80 m。

e. 集結(jié)時間T=60 min。

設(shè)置每條航跡的航點(diǎn)數(shù)為9，初始種群大小(即航跡數(shù))為40，分布在5×8的元胞空間內(nèi)，進(jìn)化代數(shù)為50。仿真結(jié)果如圖6所示。

圖6 三無人機(jī)協(xié)同航跡規(guī)劃

根據(jù)仿真數(shù)據(jù)，計(jì)算各無人機(jī)的初始速度分別為v10=137.69 km/h，v20=142.49 km/h,v10=141.84 km/h，基本接近巡航速度vc，滿足規(guī)劃要求，由此可以計(jì)算出無人機(jī)到達(dá)各航點(diǎn)的預(yù)定時間，部分航點(diǎn)數(shù)據(jù)如表1所示。

表1 部分航點(diǎn)數(shù)據(jù)

仿真結(jié)果表明，規(guī)劃出的航跡能很好地規(guī)避威脅區(qū)，并且滿足航程和速度約束。

4 結(jié)束語

采用元胞遺傳算法對多無人機(jī)協(xié)同編隊(duì)的集結(jié)路徑進(jìn)行了規(guī)劃，保證了全局搜索和局部尋優(yōu)之間的平衡，使得初始種群(航跡)能夠更好地保持其多樣性。針對多機(jī)協(xié)同航跡規(guī)劃的時間約束，在適應(yīng)度函數(shù)中加入了基于時間約束的速度代價，使得規(guī)劃出的航跡滿足無人機(jī)在較大的范圍內(nèi)實(shí)時調(diào)整速度的要求，以便各無人機(jī)能夠在突發(fā)狀況下依舊能夠準(zhǔn)時到達(dá)集結(jié)點(diǎn)。針對多機(jī)防碰撞問題，設(shè)計(jì)了基于高度差的規(guī)劃策略。最終仿真結(jié)果表明，規(guī)劃出的航跡滿足各項(xiàng)基本要求，算法搜索成功率高，具備良好的穩(wěn)定性。

[1] 樊瓊劍, 楊忠, 方挺, 等. 多無人機(jī)協(xié)同編隊(duì)飛行控制的研究現(xiàn)狀[J]. 航空學(xué)報(bào), 2009, 30(4): 683-691.

[2] 陳江濤, 王文光, 孫進(jìn)平. 基于改進(jìn)遺傳算法的無人機(jī)航跡規(guī)劃[J]. 計(jì)算機(jī)工程與應(yīng)用, 2016, 52(增刊1): 11-15.

[3] 倪良巧, 王道波, 蔣婉玥. 時間協(xié)同多無人機(jī)編隊(duì)航跡規(guī)劃[J]. 機(jī)械與電子, 2016, 34(2): 7-11.

[4] 周青, 張銳, 索曉杰, 等. 具有時間約束的無人機(jī)遺傳算法航跡規(guī)劃[J]. 航空計(jì)算技術(shù), 2016, 46(2): 93-96, 101.

[5] Cetin O, Yilmaz G. Real-time autonomous UAV formation flight with collision and obstacle avoidance in unknown environment[J]. Journal of Intelligent & Robotic Systems, 2016, 84(1/2/3/4): 1-19.

[6] 林志龍, 魯宇明. 元胞遺傳算法的多樣性研究[J].電子科技, 2015, 28(4): 9-12.

[7] Zhang Y, Wan X Y, Zheng X D,et al. Cellular genetic algorithm for multiobjective optimization based on orthogonal design[J]. Acta Electronica Sinica, 2016, 23(10): 4742-4746.

[8] Canyurt O E, Hajela P. Cellular genetic algorithm technique for the multicriterion design optimization[J]. Structural & Multidisciplinary Optimization, 2010, 40(1/2/3/4/5/6): 201-214.

[9] 張屹, 劉錚, 胡方軍, 等. 基于元胞遺傳算法的移動機(jī)器人路徑規(guī)劃[J]. 機(jī)床與液壓, 2014, 42(9): 17-20.