劉 棟，童敏明，路紅蕊

(中國礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州 221008)

(*通信作者電子郵箱726770366@qq.com)

無人機多機協(xié)作探索煤礦災(zāi)變環(huán)境算法

劉 棟*，童敏明，路紅蕊

(中國礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州 221008)

(*通信作者電子郵箱726770366@qq.com)

針對目前煤礦災(zāi)變環(huán)境下救援機器人探索效率低的問題，提出了一種使用無人機多機協(xié)同探索煤礦災(zāi)變環(huán)境的改進型邊界探索算法。該算法在效用值邊界探索算法的基礎(chǔ)上增加了對無人機導(dǎo)航角度因素的考慮，同時引入分散度函數(shù)作為評判機制來構(gòu)建目標(biāo)函數(shù)，并使用蟻群算法對該目標(biāo)函數(shù)進行求解。最后利用Matlab軟件在柵格化地圖上進行了仿真實驗。實驗結(jié)果表明，和效用值邊界探索算法相比，改進型邊界探索算法減少了探測過程中的重復(fù)覆蓋和擁擠現(xiàn)象，縮短了探測時間，降低了約30%的能量消耗，提高了無人機多機系統(tǒng)的整體探索效率。

無人機多機；邊界探索；分散度函數(shù)；環(huán)境偵測；探索效率

0 引言

煤礦災(zāi)害事故發(fā)生后，快速有效地進行搶險救援是減少人員傷亡和財產(chǎn)損失的重要工作。由于災(zāi)后礦井環(huán)境未知，在災(zāi)害搶險救援的決策指揮中，關(guān)鍵是需要快速獲取災(zāi)后礦井的環(huán)境信息，采用無人機(Unmanned Aerial Vehicle, UAV)進入礦井進行環(huán)境偵測可以較好地解決這一問題[1]。環(huán)境偵測的無人機不僅可以探測災(zāi)后礦井的環(huán)境信息，如瓦斯、一氧化碳等有毒氣體，為救護隊伍的安全提供信息，還可搜尋被困或受傷礦工的信息。

單無人機在獲取和處理信息方面存在效率低、魯棒性差、環(huán)境偵測存在盲區(qū)等問題[2]。為了解決這個問題，本文擬研究多個無人機的協(xié)同探索方法。無人機多機(multiple Unmanned Aerial Vehicles, multi-UAV)協(xié)作探索按照控制結(jié)構(gòu)不同，主要可以分為兩大類[3]：一類是集中式協(xié)作探索；另一類是分布式協(xié)作探索。分布式協(xié)作探索的每個無人機都擁有獨立的控制器，使得系統(tǒng)具有較好的容錯性和魯棒性，所以本文將分布式協(xié)作方式運用于多無人機系統(tǒng)來探索礦井災(zāi)變環(huán)境。文獻[4]建立的機器人內(nèi)部傳感器的效率模型為減函數(shù)，機器人之間通過Voronoi圖的劃分來實現(xiàn)對未知環(huán)境的協(xié)作探索；文獻[5]提出一種基于分布式模型預(yù)測控制的多無人機協(xié)同探測策略，通過結(jié)合納什最優(yōu)和粒子群優(yōu)化算法，能大幅度降低算法迭代過程中的計算量；文獻[6]提出了基于效用值的協(xié)作探索算法。這些方法在一定程度上使移動機器人的擁擠問題得以解決，但總的來說上述方法考慮的因素都還不夠全面，在對環(huán)境的探測過程中會存在小區(qū)域遺漏和重復(fù)覆蓋問題，且探測時間和能耗都達不到理想要求。為此，本文提出一種新的改進型邊界探索算法(以下簡稱：改進型算法)，同時將距離和角度因素考慮進去，并引入分散機制，這樣可以使無人機之間更好地協(xié)作獲取災(zāi)后復(fù)雜礦井環(huán)境的信息，為安全救災(zāi)提供保障。

1 基于效用值的邊界探索算法

1.1 柵格化地圖

柵格是一個單位長度的正方形，又稱之為單元格。一幅二維地圖可以劃分為許多大小相同的柵格，其中：障礙物區(qū)域設(shè)置柵格占用值為1，用黑色表示；空閑區(qū)域設(shè)置柵格占用值為0，用白色表示；未知區(qū)域設(shè)置柵格占用值為0.5，用灰色表示。環(huán)境探測的二維地圖可以通過矩陣來描述，由于礦井災(zāi)變環(huán)境未知，地圖的矩陣初始值均設(shè)為0.5。無人機在偵測過程中，若傳感器檢測到未知區(qū)域的單元格，其值將會更新：1表示障礙物，0表示無障礙物。與未知區(qū)域單元格相鄰的自由柵格均屬邊界柵格，其占用值為0。本文把和邊界柵格的距離值小于d的部分均歸屬為邊界區(qū)域，該區(qū)域可表示為T={t|‖t-s‖≤d,s∈Sf}。其中：Sf為邊界柵格的集合；d為無人機的尺寸，其取值為一個單元格的大小。

1.2 基于效用值的邊界探索算法

基于效用值的邊界探索算法(以下簡稱：效用值算法)的探索目的是使效用值最大化，也就是為無人機指派飛行代價小、信息增益大的邊界。

假設(shè)無人機i移動到邊界j的代價是cij，那么效用值

uij=dj-cij

(1)

若信息增益dj越大，無人機飛行時的移動代價cij越小，則效用值uij就會越大?？梢詮乃袩o人機的效用值中尋找出最大的效用值，獲得具有最大效用值的組合：

〈i′,j′〉arg max{uij}

(2)

然后將邊界j′指派給無人機i′。更新其他邊界的信息增益及效用值，重復(fù)前面的最大化過程，使每一個無人機都被分配相應(yīng)的任務(wù)。

這種僅考慮距離與信息增益的效用值導(dǎo)航算法不能解決探測過程中的重復(fù)覆蓋問題[7-8]。該算法為得到最大的效用值，無人機偏向于飛行至相對開闊的邊界。在探索前期，無人機能夠獲得較大的信息增益；而探索后期，由于環(huán)境中的未知區(qū)域被分隔成了零散的小塊狀，無人機若要逐一地探索，就會造成重復(fù)覆蓋，致使探索效率降低。

2 改進型邊界探索算法

下面將對上述效用值算法進行改進，在保持該算法優(yōu)點的同時，達到既使無人機能迅速有序地在復(fù)雜的災(zāi)變環(huán)境中分散開來，又能減少重復(fù)覆蓋現(xiàn)象的目的。

若不計邊界寬度，則無人機向邊界移動的過程可用一條曲線來表示。設(shè)曲線兩端點處分別為A和B，則邊界在無人機坐標(biāo)系中可以表示為：

T={(r,θ)|r=r(θ),a≤θ≤b}

(3)

其中：端點A對應(yīng)角度a，端點B對應(yīng)角度b。

2.1 吸引度函數(shù)的構(gòu)建

2.1.1 距離吸引度函數(shù)

無人機以距離近的邊界為目標(biāo)來構(gòu)建距離吸引度函數(shù)，該函數(shù)表示如下：

(4)

式中:V0、r1、r2為常數(shù)。r1=Rmax，2Rmax≤r2≤4Rmax，Rmax表示無人機傳感器的檢測半徑。

如果邊界單元格與無人機目前位置間的連線存在障礙物，Vr的值將會變小，這意味著無人機飛行至該位置將會消耗更多的能量和時間。將距離較近的柵格視為目標(biāo)點，可使復(fù)雜環(huán)境下飛行的多個無人機快速分散開來。但無人機快速分散時，總會存在一些未知區(qū)域未被探測到。此時，無人機要繼續(xù)探測這些未知區(qū)域，必定會經(jīng)過之前檢測過的部分區(qū)域，從而導(dǎo)致重復(fù)覆蓋。

2.1.2 角度吸引度函數(shù)

為使無人機在分散過程中快速又有序地移動，增加了角度吸引度函數(shù)[9]。從A點沿著邊界逆時針方向繞過Δθ大小的角度。若繞過的夾角超過邊界終點B，則B為錨點。選擇錨點的目的是為了使邊界能夠完全被覆蓋到。若Δθ太大，目標(biāo)點距邊界的起始位置過遠，會導(dǎo)致部分邊界不能被傳感器檢測出來；若Δθ太小，目標(biāo)點距邊界起始位置過近，傳感器的覆蓋范圍將會存在與障礙物相交的部分，導(dǎo)致某些區(qū)域?qū)o法被探測到。通過實驗我們發(fā)現(xiàn)，當(dāng)Δθ的值處于45°～60°范圍時，能夠體現(xiàn)出較好的效果。

(5)

(6)

式中：K為常數(shù)；前一項Vk表示在同一邊界之內(nèi)運算，后一項為不同邊界之間的運算。

將以上距離和角度因素綜合在一起，則總的吸引度評價函數(shù)可描述為：

V(t)=β×Vr+(1-β)×(Vθ+Vk)

(7)

式中β為權(quán)重因子，一般令β=0.5。

2.2 分散度函數(shù)

分散度函數(shù)可以對無人機之間的相互位置進行估計[10]，引入分散度函數(shù)，使無人機之間存在一定的相互排斥，避免多個無人機出現(xiàn)相互擁擠的情況。如果一塊區(qū)域沒有無人機，那么分散度值比較高；若分散度值過小，說明該區(qū)域太擁擠，無人機之間需適當(dāng)避讓。

邊界區(qū)域T全部單元格的初始分散度值設(shè)置為U(t)=U0。若無人機在邊界柵格t′位置處，鄰近柵格的分散度值則會變小，無人機相互間的排斥作用越大，此時其他無人機應(yīng)該選擇避讓。單元格t處分散度函數(shù)的值更新為如下式(8)：

Unew(t)=Uold(t)-α×(1-‖t-t′‖/Rmax)

(8)

式中α=(0.2～0.8)U0。當(dāng)‖t-t′‖>Rmax，無需更新分散度值。根據(jù)分散度值的大小，可以指示該區(qū)域無人機的飛行航跡，從而有效避免無人機出現(xiàn)擁擠。

2.3 算法流程

綜合考慮上述分析的吸引度與分散度因素對無人機飛行航跡的影響，可將目標(biāo)函數(shù)描述為如下表達式：

L=∑V+γ×U

(9)

其中γ為參數(shù)，用來調(diào)節(jié)無人機之間的分散程度。求出目標(biāo)函數(shù)L的最大值，便可得到有效指示無人機探測未知礦井環(huán)境的最佳方案。這是一個組合優(yōu)化問題，本文使用了蟻群算法[11-12]對該問題求解。

設(shè)排列Π表示所有可能的無人機任務(wù)分配方案的集合,其元素π(i)表示將目標(biāo)點ti指派給無人機i。算法流程如下：

1)確定邊界柵格的集合T。

2)初始化Lmax，令其為0；計算出邊界柵格對無人機的吸引度V。

3)對分散度函數(shù)進行初始化U(t)=U0，L0=0。

4)按照排列Π為無人機i分配柵格π(i)，更新目標(biāo)函數(shù)如下：

Li=Li-1+V(i,π(i))+γ×U(π(i))

(10)

5)更新分散度函數(shù)U(t′)。

6)若分配未結(jié)束，重復(fù)4)、5)步。

7)若L>Lmax，則Lmax=L，最佳任務(wù)分配方案的排列Πbest=Π。

8)繼續(xù)進行迭代運算，直至找到無人機的最佳任務(wù)分配方案。

3 仿真實驗與分析

本文使用Matlab搭建仿真環(huán)境，建立的柵格地圖大小為60×72。比較β=1和β=0.5兩種情況下無人機多機協(xié)作探索的性能表現(xiàn)。當(dāng)β=1時，表示效用值算法；β=0.5時，表示改進型算法。假設(shè)無人機的傳感器探測范圍為Rmax=10，其他參數(shù)設(shè)為：Δθ=π/4，V0=200，K=20/π，U0=80，α=0.5U0，γ=1。無人機的初始位置設(shè)為地圖中央，無人機的尺寸可以視為一個質(zhì)點，且無人機之間的相互位置預(yù)先已知，在任務(wù)執(zhí)行過程中能夠保持通信。本文用3架無人機(分別編號為1、2、3)來模擬礦井災(zāi)變環(huán)境下無人機對未知環(huán)境的探測情況。

3.1 仿真結(jié)果

基于效用值算法和改進型邊界探索算法的導(dǎo)航軌跡圖分別如圖1和圖2所示，將3架無人機的初始位置均設(shè)置在地圖中央。在初始位置處時，各無人機均只能檢測到傳感器所能探測的有限范圍。

3.2 實驗結(jié)果分析

效用值算法和改進型算法的時間與覆蓋率的關(guān)系對比如圖3所示，其中覆蓋率用來描述已探測區(qū)域的面積與地圖整個面積之比。從圖3可看出：兩種算法在前期的探測進度差別不大；但在后期，同樣的覆蓋率，效用值邊界探索算法所需的時間明顯長于改進型算法，其原因在于效用值邊界探索算法后期出現(xiàn)了重復(fù)覆蓋現(xiàn)象，這與上述仿真實驗探測分析吻合。同時，對全部地圖的偵測，改進型算法所花費的時間明顯少于效用值算法，證明了重復(fù)覆蓋將會降低探索效率。

能量消耗與覆蓋率關(guān)系對比如圖4所示。其中，無人機向正向方向飛行需耗費10個單位的能量，向?qū)欠较蝻w行需耗費14個單位的能量[13]，拐彎45°、90°、135°、180°分別耗費4、6、8、10個單位的能量。通過圖4可以看出，改進型算法所消耗的能量相對效用值算法降低了約30%，這是由于探索后期效用值算法中出現(xiàn)的無人機路徑重復(fù)覆蓋會導(dǎo)致更多的能量消耗。

圖1 效用值邊界探索算法仿真結(jié)果Fig. 1 Simulation results of boundary exploration algorithm of utility value

圖2 改進型算法仿真結(jié)果Fig. 2 Simulation results of improved algorithm

圖5是兩種算法飛行距離方差對比。無人機飛行距離的方差可反映出任務(wù)分配是否合理[14]。飛行距離方差可通過以下公式計算：

(11)

(12)

式中:n是無人機的個數(shù)，本文取n=3；si表示第i個無人機飛行的距離。各無人機飛行的距離相差越大，方差就越大，這意味著算法對多無人機系統(tǒng)任務(wù)分配不合理。從圖5可以看出，在探測中、后期，效用值算法中各無人機之間的飛行距離存在很大差異。中期存在的較大方差是圖1(d)中3號無人機飛行至下方較寬邊界所致，后期則是由無人機之間的任務(wù)分配不合理、無人機的探索路線出現(xiàn)了較大的重復(fù)覆蓋所致。在整個探測過程中改進型邊界探索算法不存在很大的方差，說明各無人機之間的任務(wù)分配相對合理。在本文中，由于構(gòu)建的地圖較大，且方差是3個無人機飛行距離偏差的平方和，所以，方差在10 000以內(nèi)屬于正?，F(xiàn)象。

圖3 時間與覆蓋率的關(guān)系對比Fig. 3 Relationship comparison of time and coverage

圖4 能量消耗與覆蓋率的關(guān)系對比Fig. 4 Relationship comparison of energy consumption and coverage

圖5 飛行距離方差對比Fig. 5 Comparison of flight distance variance

4 結(jié)語

本文提出使用多無人機協(xié)作探索煤礦災(zāi)變環(huán)境，對無人機多機系統(tǒng)使用改進型算法解決了探測過程中小塊未知區(qū)域的遺漏問題，減少了探測過程中的重復(fù)覆蓋和擁擠現(xiàn)象。相比效用值算法，改進后的算法縮短了探測時間，降低了能量的消耗，且各無人機間的任務(wù)分配更為合理，提高了礦井災(zāi)變環(huán)境下未知區(qū)域的探測效率。

雖然改進后的算法提高了探測效率，但是還存在一定的不足，很多現(xiàn)實的客觀因素沒有考慮進去，如各傳感器產(chǎn)生的噪聲誤差、無人機之間數(shù)據(jù)交換丟包誤差、外界環(huán)境導(dǎo)致的非線性誤差都會對實驗有一定的影響，如何將這些誤差融入算法中進行濾波與補償會在以后的工作中進行重點研究。

References)

[1] 田子建,高學(xué)浩,張夢霞.基于改進人工勢場的礦井導(dǎo)航裝置路徑規(guī)劃[J].煤炭學(xué)報,2016,41(S2):589-597. (TIAN Z J, GAO X H, ZHANG M X. Path planning based on the improved artificial potential field of coalmine dynamic target navigation [J]. Journal of China Coal Society, 2016, 41(S2): 589-597.)

[2] 高云園,郭云飛,韋巍.協(xié)作多機器人用于未知環(huán)境完全探測和地圖構(gòu)建[J].儀器儀表學(xué)報,2007,28(7):1259-1264. (GAO Y Y, GUO Y F, WEI W. Coordinated multi-robots for complete exploration and map-building in unknown environment [J]. Chinese Journal of Scientific Instrument, 2007, 28(7): 1259-1264)

[3] 張民強,宋建梅,薛瑞彬.通信距離受限下多無人機分布式協(xié)同搜索[J].系統(tǒng)工程理論與實踐,2015,35(11):2980-2986. (ZHANG M Q, SONG J M, XUE R B. Multiple UAVs cooperative search under limited communication range [J]. Systems Engineering — Theory & Practice, 2015, 35(11):2980-2986)

[4] GURUPRASAD K R, GHOSE D. Multi-Agent search strategy based on centroidal Voronoi configuration [C]// ICRA 2010： Proceedings of the IEEE International Conference on Robotics and Automation. Piscataway, NJ: IEEE, 2010:3550-3555.

[5] 彭輝,沈林成,朱華勇.基于分布式模型預(yù)測控制的多UAV協(xié)同區(qū)域搜索[J]. 航空學(xué)報,2010,31(3):593-601. (PENG H, SHEN L C, ZHU H Y. Multiple UAV cooperative area search based on distributed model predictive control [J]. Acta Aeronautica et Astronautica Sinica, 2010, 31(3): 593-601.)

[6] STACHNISS C. Coordinated multi-robot exploration [J]. IEEE Transactions on Robotics, 2009, 21(3): 376-386.

[7] YAMAUCHI B. Frontier-based exploration using multiple robot [C] // AGENTS ’98: Proceedings of the 2nd International Conference on Autonomous Agents. New York: ACM, 1998: 47-53.

[8] 陳海,何開鋒,錢煒祺.多無人機協(xié)同覆蓋路徑規(guī)劃[J].航空學(xué)報,2016,37(3):928-935. (CHEN H, HE K F, QIAN W Q. Cooperative coverage path planning for multiple UAVs [J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(3): 928-935.)

[9] 胡中華.基于智能優(yōu)化算法的無人機航跡規(guī)劃若干關(guān)鍵技術(shù)研究[D].南京：南京航空航天大學(xué),2011:21-23. (HU Z H. Research on some key techniques of UAV path planning based on intelligent optimization algorithm [D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2011: 21-23.)[10] 王芳.基于量子蟻群算法的多無人機協(xié)同航跡規(guī)劃研究[D].哈爾濱：哈爾濱工業(yè)大學(xué),2015:57-59. (WANG F. Collaborative path planning of UAVs based on quantum ant colony algorithm [D]. Harbin: Harbin Institute of Technology, 2015: 57-59.)

[11] STüTZLE T, DORIGO M. ACO Algorithms for the Quadratic Assignment Problem [M]. Maidenhead, UK: McGraw-Hill Ltd., 1999: 5-18.

[12] 楊華江.求解未知環(huán)境下多無人機任務(wù)自組織的蟻群算法研究[D].長沙：國防科學(xué)技術(shù)大學(xué),2007:33-37. (YANG H J. Research on ant colony algorithm for self-organization of UAVs’ mission in unknown environment [D]. Changsha: National University of Defense Technology, 2007: 33-37.)

[13] MEI Y, LU Y-H, LEE C S G, et al. Energy-efficient mobile robot exploration [C]// ICRA 2006: Proceedings of the 2006 IEEE International Conference on Robotics and Automation. Piscataway, NJ: IEEE, 2006: 505-511.

[14] 孫小雷,齊乃明,董程,等.無人機任務(wù)分配與航跡規(guī)劃協(xié)同控制方法[J].系統(tǒng)工程與電子術(shù),2015,37(12):2772-2776. (SUN X L, QI N M, DONG C, et al. Cooperative control algorithm of task assignment and path planning for multiple UAVs [J]. Systems Engineering and Electronics, 2015, 37(12): 2772-2776.)

This work is partially supported by “the 13th Five-Year Plan” National Key Research and Development Program of China (2016YFC0801808).

LIUDong, born in 1991, M. S. candidate. Her research interests include artificial intelligence, signal processing.

TONGMinming, born in 1956, Ph. D., professor. His research interests include artificial intelligence, data analysis and processing, image processing.

LUHongrui, born in 1991, M. S. candidate. Her research interests include artificial intelligence, image processing.

Algorithmforexploringcoalminedisasterenvironmentbymulti-UAVcooperation

LIU Dong*, TONG Minming, LU Hongrui

(SchoolofInformationandControlEngineering,ChinaUniversityofMiningandTechnology,XuzhouJiangsu221008,China)

Focusing on the low efficiency of the rescue robot in the coal mine disaster environment, a new improved boundary exploration algorithm based on multiple Unmanned Aerial Vehicles (multi-UAV) was proposed. Based on the utility value boundary exploration algorithm, the flight angle parameter of UAV was considered, and the distribution function was introduced as a judgment mechanism to construct the objective function. Finally, the ant colony algorithm was used to solve the objective function. Simulation experiments were carried out on a rasterized map with Matlab software. The simulation results show that the improved boundary exploration algorithm can reduce the phenomenon of repeated coverage and crowding, shorten the detection time, meanwhile the energy required by UAV is reduced by about 30%, thus improving the overall exploration efficiency of multi-UAV system.

multiple Unmanned Aerial Vehicle (multi-UAV); boundary exploration; distribution function; environment detection; exploration efficiency

TP242.6

A

2017- 02- 20;

2017- 04- 05。

“十三五”國家重點研發(fā)計劃項目(2016YFC0801808)。

劉棟(1991—)，女，湖南岳陽人，碩士研究生，主要研究方向：人工智能、信號處理； 童敏明 (1956—)，男，浙江龍游人，教授，博士，主要研究方向：人工智能、數(shù)據(jù)分析與處理、圖像處理； 路紅蕊 (1991—)，女，河南濮陽人，碩士研究生，主要研究方向：人工智能、圖像處理。

1001- 9081(2017)08- 2401- 04

10.11772/j.issn.1001- 9081.2017.08.2401