晉一寧， 吳炎烜， 范寧軍

(北京理工大學(xué) 機電學(xué)院，北京 100081)

?

群無人機動態(tài)環(huán)境分布式持續(xù)覆蓋算法

晉一寧， 吳炎烜， 范寧軍

(北京理工大學(xué) 機電學(xué)院，北京 100081)

動態(tài)環(huán)境具有多變性和不確定性，為將動態(tài)環(huán)境的不確定性控制在一定范圍內(nèi)，需要群無人機對其進行持續(xù)覆蓋以便完成感知、監(jiān)視、偵察等任務(wù). 提出了一種考慮無人機飛行動力學(xué)約束的分布式協(xié)同覆蓋算法，無需先驗知識、無需事先進行路徑規(guī)劃. 各無人機獨立地根據(jù)局部感知和局部通信所獲信息進行在線覆蓋決策，使整個群無人機系統(tǒng)涌現(xiàn)出持續(xù)覆蓋行為. 提出的方法通信次數(shù)少，僅需鄰居無人機的位置信息進行合作，且對無人機的前飛航向沒有數(shù)量約束. 仿真結(jié)果表明，此分布式算法可實現(xiàn)群無人機對動態(tài)環(huán)境的持續(xù)覆蓋，算法性能穩(wěn)定，具有很好的靈活性和可擴展性.

群無人機；持續(xù)覆蓋； 分布式協(xié)同

無人機(unmanned aerial vehicle，UAV)通過裝載傳感器，可在戰(zhàn)場區(qū)域中執(zhí)行監(jiān)視、偵察、數(shù)據(jù)收集、目標(biāo)搜索等任務(wù)，無需考慮人員耐受性和傷亡. 而覆蓋戰(zhàn)場區(qū)域是進行上述任務(wù)的基礎(chǔ)和前提. 由于單架無人機覆蓋能力有限，通常需要一群無人機(swarm UAVs)相互協(xié)作地執(zhí)行覆蓋任務(wù).

現(xiàn)有的覆蓋研究多針對單次覆蓋問題，而面對復(fù)雜多變的戰(zhàn)場區(qū)域，單次覆蓋已不能滿足對信息獲取的需求，要對整個區(qū)域進行持續(xù)、重復(fù)的覆蓋，以便及時地更新戰(zhàn)場信息. 前人常用區(qū)域劃分法[1-6]來解決多無人機完全覆蓋問題，此為集中式控制策略，若有無人機損毀，則需重新進行區(qū)域劃分和分配. 且Nigam等[7]指出區(qū)域劃分法不適于無人機數(shù)量過多的情況，提出了一種反應(yīng)式協(xié)作策略，雖為分布式控制，但需全局通信來獲取所有無人機的位置. 彭輝等[8]提出一種分布式滾動優(yōu)化法，其信息交換量大、實時性差. 且滾動優(yōu)化法的計算量會隨無人機前飛航向的增多而呈指數(shù)性增長，所以文獻[9-10]等都假設(shè)無人機只有3個前進航向. 而群無人機系統(tǒng)是一類群機器人(swarm robotics)系統(tǒng)，由大量能力有限的無人機個體組成，個體需要在不知道全局信息的情況下，通過局部通信和交互合作完成復(fù)雜任務(wù). 所以群無人機系統(tǒng)需要采用基于局部信息的分布式合作法，且由于個體能力的限制，要盡量減少通信量和計算量.

目前，尚無關(guān)于群無人機僅通過局部通信實現(xiàn)對動態(tài)環(huán)境持續(xù)覆蓋的全分布式協(xié)作研究的公開資料. 本文提出一種適用于群無人機的分布式協(xié)作方法，核心思路是每個無人機獨立地存儲一個覆蓋決策圖，每個時刻僅利用自身傳感器采集到的信息和與鄰居無人機局部通信獲得的鄰居無人機位置信息來更新覆蓋決策圖，并根據(jù)圖進行在線覆蓋決策. 該方法通信次數(shù)少，不僅滿足飛行動力學(xué)約束，且對無人機的前進航向沒有數(shù)量約束.

1 持續(xù)覆蓋問題描述

本文以微小型固定翼無人機為研究平臺. 在群無人機系統(tǒng)中有n個無人機，用集合U={U1，U2，…，Un，n≥2}表示. 為方便研究覆蓋問題，對無人機作如下假設(shè)：

① 機載探測傳感器：設(shè)機載探測傳感器中心與無人機幾何中心重疊，采用簡化的圓盤探測模型來對機載傳感器建模，rsen為傳感器的探測半徑. 也就是說，只要目標(biāo)區(qū)域在傳感器探測范圍內(nèi)就被覆蓋.

本文要研究的問題可以描述為：由n個無人機組成的群無人機進入目標(biāo)區(qū)域后，在各無人機有限的續(xù)航時間ttotal內(nèi)，持續(xù)地對目標(biāo)區(qū)域進行覆蓋，無人機僅知道目標(biāo)區(qū)域的地理位置信息和邊界信息. 設(shè)計一種滿足無人機動力學(xué)約束的群無人機分布式覆蓋協(xié)作方法，使目標(biāo)區(qū)域內(nèi)不能留有任何一塊區(qū)域長時間未被覆蓋，即使目標(biāo)區(qū)域內(nèi)所有柵格的兩次被覆蓋時間間隔最短，可以表示為

(1)

式中tij為目標(biāo)區(qū)域內(nèi)任意柵格G(i，j)(1≤i≤M，1≤j≤N)從上一次被覆蓋到當(dāng)前時刻所經(jīng)過的時間.

2 持續(xù)覆蓋策略

為便于各無人機記錄和傳遞目標(biāo)區(qū)域的覆蓋信息、實現(xiàn)合作，采用離散信息圖的形式對各類所需信息進行建模. 每個圖的數(shù)據(jù)結(jié)構(gòu)都是一個與柵格數(shù)量對應(yīng)的M×N的矩陣.

2.1 區(qū)域價值圖

區(qū)域價值圖Q(t)代表覆蓋該區(qū)域的收益. 無人機在飛行途中建立并更新一種信息素圖χ(t)，以此記錄自己覆蓋過的地方. 信息素濃度越高的區(qū)域，代表無人機覆蓋的次數(shù)越多，其存在的不確定性越低，覆蓋該區(qū)域的收益也越低. 對于無人機Uk，信息素圖中柵格G(i，j)的信息素值更新如下式所示

(2)

式中：ξkij為信息素增益值；η為信息素衰減因子；Γ(pk(t))為 無人機Uk在位置pk(t)時機載傳感器對目標(biāo)區(qū)域的覆蓋域.

當(dāng)無人機Uk有通信鄰居無人機時，可以與鄰居無人機交換各自存儲的信息素圖，再結(jié)合自己的信息素圖按下式進行更新.

(3)

然后再根據(jù)式(4)用信息素值計算區(qū)域價值圖Q(t).

(4)

2.2 分散航向圖

根據(jù)虛擬力理論[8]，假設(shè)當(dāng)無人機質(zhì)心之間的距離小于等于rrep時，無人機之間會產(chǎn)生大小相同、方向相反的虛擬排斥力F. 定義Uk的排斥鄰居無人機的集合為

(5)

式中rrep為排斥力產(chǎn)生距離，rrep≥2vΔt. 為了簡化計算，此處設(shè)虛擬排斥力F的值為固定的單位斥力.

t時刻，無人機Uk的優(yōu)選航向角φkpref(t)的更新原則為

(6)

分散航向圖H(t)記錄的是t時刻，無人機從當(dāng)前位置飛向某個柵格G(i，j)中心點的航向角與優(yōu)選航向角的契合度以及最大轉(zhuǎn)彎角的約束信息. 于是，本文設(shè)計了一個分段函數(shù)作為分散航向值計算函數(shù)為

(7)

分散航向圖的建立目的是使群無人機分散開來覆蓋更廣的區(qū)域，并避免短期內(nèi)的重復(fù)覆蓋，可同時實現(xiàn)一定程度的避碰，但若完全實現(xiàn)避踫，還需進一步研究.

2.3 任務(wù)傾向性圖

當(dāng)有多個無人機飛向同一目的地時，在集中式控制方法中，將離目的地最近的無人機分配去執(zhí)行相應(yīng)的覆蓋任務(wù)會得到更高的效費比. 換個角度來看，上述任務(wù)分配可以轉(zhuǎn)化為無人機傾向于覆蓋離自己更近的柵格. 因此，本文提出一種基于距離的間接任務(wù)分配方式，設(shè)計一個基于距離的任務(wù)傾向性圖D(t). 對于無人機Uk，任務(wù)傾向性值的計算方法為

(8)

式中：dk→ij(t)為t時刻無人機Uk從當(dāng)前位置飛向柵格G(i，j)的距離；dmax為覆蓋區(qū)域?qū)蔷€的長度.

2.4 覆蓋決策圖

用一個M×N的矩陣C(t)表示無人機的覆蓋決策圖，決策圖里的每個數(shù)值代表無人機飛向每個柵格的概率. 對于無人機Uk，柵格G(i，j)的覆蓋決策變量的計算方法如下

(9)

式中：ωq為區(qū)域價值權(quán)重；ωh為分散航向權(quán)重；ωd為任務(wù)傾向性權(quán)重.

在群無人機執(zhí)行區(qū)域覆蓋任務(wù)時，每個決策時刻，各無人機都根據(jù)局部感知和局部通信所得信息更新自身的覆蓋決策圖C(t)，再采用貪婪策略，直接選擇決策變量值最大的柵格作為下一步覆蓋的目標(biāo)柵格. 對于無人機Uk有

(10)

式中Gk(x，y)為覆蓋決策值最高的柵格.

3 仿真結(jié)果與比較

本文用Matlab來驗證提出的分布式協(xié)作算法用于執(zhí)行持續(xù)覆蓋任務(wù)的有效性. 算法性能以目標(biāo)區(qū)域中每個時刻所有柵格最大未覆蓋時長tMET、整個覆蓋過程中的最大未覆蓋時長tTMET、整個覆蓋過程中的平均未覆蓋時長tAMET作為評價指標(biāo)，根據(jù)式(11)進行計算.

(11)

式中T(t)為未覆蓋時長全局監(jiān)測圖. 對于柵格G(i，j)，其計算方法如下，

(12)

式中Γ(P(t))為 群無人機的機載探測傳感器對目標(biāo)區(qū)域的覆蓋域.

第1組仿真，分別對群無人機中有5，10，15個無人機的情況進行了仿真，所得結(jié)果如圖1所示. 圖中折線表示目標(biāo)區(qū)域中tMET隨時間的變化，橫線表示平均未覆蓋時長tAMET，五角星為整個覆蓋過程中的最大未覆蓋時長tTMET.

由圖1可以看出，目標(biāo)區(qū)域中tMET上升到一定的值后總會下降，表明群無人機通過協(xié)作完成了對目標(biāo)區(qū)域的持續(xù)、無盲區(qū)覆蓋，并保證覆蓋區(qū)域中不會有長期未被覆蓋的點. 另外，目標(biāo)區(qū)域內(nèi)工作的無人機個數(shù)越多，tAMET越小，表明各點被覆蓋的頻率越高.

圖2展示了圖1中n=10的群無人機在t=[0 min，3 min]時段的航跡. 圖下方的箭頭所指處為各無人機的初始位置，箭頭指向為初始航向，虛線框為需要覆蓋的目標(biāo)區(qū)域. 從圖2中各無人機的飛行航跡可看出，引入無人機最大轉(zhuǎn)彎角約束后，無人機的覆蓋航跡平滑、在轉(zhuǎn)彎時無突變尖銳的拐角，所有航跡都物理可飛.

第2組仿真，分別針對不同的群無人機規(guī)模進行了50次仿真，每次仿真中，各無人機的初始位置與航向都是隨機的，仿真的統(tǒng)計結(jié)果如圖3所示.

由圖3可以看出，雖然初始位置與初始航向隨機化，但不論群無人機規(guī)模大小，tAMET和tTMET都在有限的范圍內(nèi)波動，表明本文提出的覆蓋控制算法性能穩(wěn)定. 另外，無人機個數(shù)越多，未覆蓋時長波動越小，充分證明了所提算法能有效地協(xié)同大規(guī)模的群無人機進行持續(xù)覆蓋.

另外，統(tǒng)計了上述仿真中無人機之間的通信次數(shù)如表1所示.

表1 群無人機通信次數(shù)

從表1可以看出，由于本文所提算法采用的是間歇式局部通信，因此通信量遠少于需要全局通信的算法.

4 結(jié) 論

提出了一種將未覆蓋時長和飛行動力學(xué)約束結(jié)合考慮的分布式協(xié)作方法，使群無人機實現(xiàn)了對動態(tài)目標(biāo)區(qū)域的持續(xù)不間斷覆蓋. 此算法不需要先驗知識，無需無人機事先進行路徑規(guī)劃，也不需要進行全局通信，只需要無人機進行局部感知和與鄰居無人機進行局部通信，只用交換鄰居無人機的位置信息，通信次數(shù)少，算法簡單，可實現(xiàn)在線決策. 并且，由于算法是全分布式的，無人機可以自由地加入或退出覆蓋任務(wù)而不影響整個系統(tǒng)的運行，也能實現(xiàn)不同速度無人機之間的協(xié)作，因此具有良好的可擴展性和靈活性. 通過仿真表明此算法性能穩(wěn)定，在一定的無人機數(shù)量下，可以將各柵格的未覆蓋時長控制在一定的范圍內(nèi)，使目標(biāo)區(qū)域中不存在長期未被覆蓋的點. 而且此算法能有效地協(xié)同大規(guī)模的群無人機進行持續(xù)覆蓋.

[1] 薛頌東，曾建潮.群機器人研究綜述[J].模式識別與人工智能，2008，21(2):177-185.

Xue Songdong， Zeng Jianxhao. Swarm robotics: a survey[J]. Pattern Recognition and Artificial Intelligence， 2008，21(2):177-185. (in Chinese)

[2] Sahin E， Winfield Alan F T. Special issue on swarm robotics[J]. Swarm Intelligence， 2008，2(2-4):69-72.

[3] Sivakumar A， Tan C K Y. UAV swarm coordination using cooperative control for establishing a wireless communications backbone[C]∥Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems. Toronto, Canada, 2010:1157-1164.

[4] Mohsen Mehdizade. A decomposition strategy for optimal coverage of an area of interest using heterogeneous team of UAVs[D]. Quebec， Canada: Concordia University， 2012:77-100.

[5] 唐勝景，宋祥，郭杰，等.基于遺傳算法的無人機模糊-積分控制器設(shè)計[J].北京理工大學(xué)學(xué)報，2013，33(12)：1274-1278.

Tang Shengjing, Song Xiang, Guo Jie, et al. Fuzzy-integration controller design of UAV based on genetic algrithm[J]. Transactions of Beijing Institute of Technology, 2013,33(12):1274-1278. (in Chinese)

[6] 關(guān)震宇，楊東曉，李杰，等.基于Dubins路徑的無人機避障規(guī)劃算法[J].北京理工大學(xué)學(xué)報，2014，34(6)：570-575.

Guan Zhenyu, Yang Dongxiao, Li Jie, et al. Obstacle avoidance planning algrithm for UAV based on Dubins path[J]. Transactions of Beijing Institute of Technology, 2014,34(6):570-575. (in Chinese)

[7] Nigam N， Kroo I. Control and design of multiple unmanned air vehicles for a persistent surveillance task[J]. AIAA， 2009(1852):1-19.

[8] 彭輝，沈林成，朱華勇.基于分布式模型預(yù)測控制的多無人機協(xié)同區(qū)域覆蓋[J].航空學(xué)報，2010，31(3):593-601.

Peng Hui， Shen Lincheng， Zhu Huayong. Multiple UAV cooperative area search based on distributed model predictive control[J]. Acta Aeronautica Et Astronautica Sinica， 2010，31(3):593-601. (in Chinese)

[9] 吳文超，黃長強，宋磊.不確定環(huán)境下的多無人機協(xié)同搜索航路規(guī)劃[J].兵工學(xué)報，2011，32(11):1337-1342.

Wu Wenchao， Huang Changqiang， Song Lei. Cooperative search and path planning of multi-unmanned air vehicles in uncertain environment[J]. Acta Armamentarii， 2011，32(11):1337-1342. (in Chinese)

[10] Spears D， Kerr W， Spears W. Physics-based robot swarms for coverage problems[J]. International Journal on Intelligent Control and Systems， 2006，11:24-40.

(責(zé)任編輯：劉雨)

Distributed Cooperative Control of Swarm UAVs for Dynamic Environment Persistent Coverage

JIN Yi-ning， WU Yan-xuan， FAN Ning-jun

(School of Mechatronical Engineering， Beijing Institute of Technology， Beijing 100081， China)

In order to control the uncertainty of dynamic environment into a certain scope, it is necessary for swarm UAVs to continuously cover the environment so as to achieve some perception, watch and spy task. A distributed collaborative coverage method was proposed based on the kinematic constraints of UAV, doing without prior knowledge and advanced path planning. Each UAV made its coverage decision online only based on the information gotten from the real-time local sensing and the local communications, making the swarm UAVs have persistent coverage ability. The information needed to be exchanged was very little, and only position information needed to be exchanged within local inter-UAV communication, which made the algorithm simpler and more practical. The simulation results show that, the distributed collaborative coverage method can adapt swarm UAVs for persistent coverage to dynamic environment, the performance of the algorithm is stable, flexible and scalable.

swarm UAVs; persistent coverage; distributed cooperation

2014-11-15

北京理工大學(xué)基礎(chǔ)研究基金資助項目(20120242009)

晉一寧(1986—)，女，博士生，E-mail:yn.jin@foxmail.com；吳炎烜(1981—)，男，博士，講師，E-mail:alexwyx@bit.edu.cn.

范寧軍(1949—)，男，博士，教授，E-mail:ningjunfan@bit.edu.cn.

V 279; TP 18

A

1001-0645(2016)06-0588-05

10.15918/j.tbit1001-0645.2016.06.007