無人機多機協作探索煤礦災變環境算法

劉 棟，童敏明，路紅蕊

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

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

無人機多機協作探索煤礦災變環境算法

劉 棟*，童敏明，路紅蕊

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

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

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

無人機多機；邊界探索；分散度函數；環境偵測；探索效率

0 引言

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

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

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

1.1 柵格化地圖

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

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

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

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

uij=dj-cij

(1)

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

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

(2)

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

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

2 改進型邊界探索算法

下面將對上述效用值算法進行改進，在保持該算法優點的同時，達到既使無人機能迅速有序地在復雜的災變環境中分散開來，又能減少重復覆蓋現象的目的。

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

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

(3)

其中：端點A對應角度a，端點B對應角度b。

2.1 吸引度函數的構建

2.1.1 距離吸引度函數

無人機以距離近的邊界為目標來構建距離吸引度函數，該函數表示如下：

(4)

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

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

2.1.2 角度吸引度函數

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

(5)

(6)

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

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

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

(7)

式中β為權重因子，一般令β=0.5。

2.2 分散度函數

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

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

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

(8)

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

2.3 算法流程

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

L=∑V+γ×U

(9)

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

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

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

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

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

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

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

(10)

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

6)若分配未結束，重復4)、5)步。

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

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

3 仿真實驗與分析

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

3.1 仿真結果

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

3.2 實驗結果分析

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

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

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

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

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

(11)

(12)

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

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

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

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

4 結語

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

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

References)

[1] 田子建,高學浩,張夢霞.基于改進人工勢場的礦井導航裝置路徑規劃[J].煤炭學報,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] 高云園,郭云飛,韋巍.協作多機器人用于未知環境完全探測和地圖構建[J].儀器儀表學報,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] 張民強,宋建梅,薛瑞彬.通信距離受限下多無人機分布式協同搜索[J].系統工程理論與實踐,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] 彭輝,沈林成,朱華勇.基于分布式模型預測控制的多UAV協同區域搜索[J]. 航空學報,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] 陳海,何開鋒,錢煒祺.多無人機協同覆蓋路徑規劃[J].航空學報,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] 胡中華.基于智能優化算法的無人機航跡規劃若干關鍵技術研究[D].南京：南京航空航天大學,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] 王芳.基于量子蟻群算法的多無人機協同航跡規劃研究[D].哈爾濱：哈爾濱工業大學,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] 楊華江.求解未知環境下多無人機任務自組織的蟻群算法研究[D].長沙：國防科學技術大學,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] 孫小雷,齊乃明,董程,等.無人機任務分配與航跡規劃協同控制方法[J].系統工程與電子術,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。

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

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

1001- 9081(2017)08- 2401- 04

10.11772/j.issn.1001- 9081.2017.08.2401