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

，，， ，

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

0 引言

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

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

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

1 單機航跡規(guī)劃

1.1 航跡編碼

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

1.2 適應度函數(shù)

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

1.2.1 威脅代價

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

(1)

圖1 威脅代價計算示意

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

(2)

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

(3)

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

(4)

1.2.2 航程代價

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

(5)

1.2.3 速度代價

多無人機集結具有時間約束性，假設所有無人機都需要在T時間內集結完畢，那么對于每架無人機，其飛行速度v應滿足：

(6)

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

V=v-vcvmin≤v≤vmax

(7)

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

C=ksS+klL+kvV

(8)

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

F=f-C

(9)

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

1.3 種群初始化

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

(10)

(11)

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

1.4 初始化元胞空間

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

圖2 元胞空間結構

1.5 遺傳操作

1.5.1 選擇

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

(12)

1.5.2 交叉

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

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

圖3 交叉操作

1.5.3 變異

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

(13)

取其中的最小值hm：

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

(14)

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

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

(15)

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

圖4 變異操作

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

1.6 算法終止條件

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

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

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

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

1.7 航跡平滑處理

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

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

圖5 航跡平滑處理

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

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

2.1 時間協(xié)同

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

(16)

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

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

(17)

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

(18)

通過不斷地對速度進行微調，便可以基本保證在約定時間到達對應航點，直至到達終點。

2.2 防碰撞策略

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

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

3 仿真驗證

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

a. 待集結的無人機為3架，分別為UAV1，UAV2和UAV3。

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

c. 設置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. 無人機最小轉彎角φm=60°，最小速度vmin=40 km/h，最大速度vmax=200 km/h，巡航速度vc=140 km/h，安全距離Ds=80 m。

e. 集結時間T=60 min。

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

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

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

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

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

4 結束語

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

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

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

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

[4] 周青, 張銳, 索曉杰, 等. 具有時間約束的無人機遺傳算法航跡規(guī)劃[J]. 航空計算技術, 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] 張屹, 劉錚, 胡方軍, 等. 基于元胞遺傳算法的移動機器人路徑規(guī)劃[J]. 機床與液壓, 2014, 42(9): 17-20.