群無(wú)人機(jī)動(dòng)態(tài)環(huán)境分布式持續(xù)覆蓋算法

晉一寧， 吳炎烜， 范寧軍

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

?

群無(wú)人機(jī)動(dòng)態(tài)環(huán)境分布式持續(xù)覆蓋算法

晉一寧， 吳炎烜， 范寧軍

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

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

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

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

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

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

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

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

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

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

(1)

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

2 持續(xù)覆蓋策略

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

2.1 區(qū)域價(jià)值圖

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

(2)

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

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

(3)

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

(4)

2.2 分散航向圖

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

(5)

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

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

(6)

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

(7)

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

2.3 任務(wù)傾向性圖

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

(8)

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

2.4 覆蓋決策圖

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

(9)

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

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

(10)

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

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

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

(11)

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

(12)

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

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

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

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

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

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

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

表1 群無(wú)人機(jī)通信次數(shù)

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

4 結(jié) 論

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

[1] 薛頌東，曾建潮.群機(jī)器人研究綜述[J].模式識(shí)別與人工智能，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] 唐勝景，宋祥，郭杰，等.基于遺傳算法的無(wú)人機(jī)模糊-積分控制器設(shè)計(jì)[J].北京理工大學(xué)學(xué)報(bào)，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路徑的無(wú)人機(jī)避障規(guī)劃算法[J].北京理工大學(xué)學(xué)報(bào)，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ù)測(cè)控制的多無(wú)人機(jī)協(xié)同區(qū)域覆蓋[J].航空學(xué)報(bào)，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] 吳文超，黃長(zhǎng)強(qiáng)，宋磊.不確定環(huán)境下的多無(wú)人機(jī)協(xié)同搜索航路規(guī)劃[J].兵工學(xué)報(bào)，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ǔ)研究基金資助項(xiàng)目(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