無人機(jī)巡檢礦區(qū)的路徑規(guī)劃策略

宣麗萍， 李 崢

(1.華南師范大學(xué) 數(shù)據(jù)科學(xué)與工程學(xué)院， 廣東 汕尾 516600； 2.黑龍江科技大學(xué) 電氣與控制工程學(xué)院， 哈爾濱 150022)

0 引 言

我國部分礦產(chǎn)資源儲藏量處于世界前列。豐富的礦產(chǎn)資源是強(qiáng)大的綜合國力的體現(xiàn)，但同時也給國家相關(guān)部門的監(jiān)督、管理帶來了不小的困難和挑戰(zhàn)。將無人機(jī)應(yīng)用到采礦領(lǐng)域是對該技術(shù)的一種新探索，也是對傳統(tǒng)礦區(qū)管理技術(shù)的革新[1-2]。無人機(jī)巡檢最早應(yīng)用與電力行業(yè)，劉壯等[3]詳細(xì)總結(jié)了近年來無人機(jī)輸電線路巡檢方面的研究，闡述了無人機(jī)高壓線路巡檢技術(shù)的應(yīng)用優(yōu)勢及其發(fā)展現(xiàn)狀。彭向陽等[4]提出了大型無人直升機(jī)電力巡檢技術(shù)研究、裝備研制和示范應(yīng)用方面的實(shí)用化目標(biāo)和策略。無人機(jī)電力巡檢技術(shù)為其在礦區(qū)的應(yīng)用提供了寶貴經(jīng)驗(yàn)。張力等[5]設(shè)計了一種基于超聲波測距的井下煤礦四旋翼巡檢無人機(jī)，能夠?qū)崟r獲取井下環(huán)境信息并通過無線網(wǎng)絡(luò)將采集到的數(shù)據(jù)和視頻信息實(shí)時回傳至控制臺。徐金鑫[6]對無人機(jī)露天礦區(qū)巡檢控制方式進(jìn)行了深入研究。綜上所述，無人機(jī)在煤礦應(yīng)用領(lǐng)域具有巨大的優(yōu)勢和潛能，筆者將根據(jù)某煤礦的建筑平面圖，對傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，設(shè)計出的礦區(qū)巡檢路徑規(guī)劃策略，通過仿真實(shí)驗(yàn)對比算法改進(jìn)前后巡檢性能的差異，驗(yàn)證改進(jìn)后算法的優(yōu)越性。

1 巡檢目標(biāo)路徑的規(guī)劃

1.1 巡檢目標(biāo)的確定

礦區(qū)位于安徽省境內(nèi)，該煤礦圍墻內(nèi)工業(yè)場地占地面積為27.775 km2，其中，礦井占地面積為19.135 km2。根據(jù)圖紙上標(biāo)注的建筑單位及其方位信息，共選擇了20個主要單位作為巡檢對象，將目標(biāo)單位質(zhì)點(diǎn)化，巡檢目標(biāo)方位與距離信息如圖1 所示。

圖1 巡檢目標(biāo)方位Fig. 1 Patrol target orientation

1.2 數(shù)學(xué)模型的建立

巡檢目標(biāo)方位圖確定后，需要為無人機(jī)設(shè)計一條巡視路線，從初始點(diǎn)出發(fā)，在多個點(diǎn)之間進(jìn)行無人機(jī)巡航，在規(guī)定時間內(nèi)返回出發(fā)點(diǎn)。根據(jù)上述要求需要找出合理的巡航路徑，使其在規(guī)定時間內(nèi)無人機(jī)巡航的點(diǎn)盡可能的多[7]。假設(shè)無人機(jī)可短時間垂直升空的充電四旋翼式飛行器，且對巡檢時間和巡檢速度等有限制。為在規(guī)定時間內(nèi)巡航多個地點(diǎn)，要求對其路徑進(jìn)行科學(xué)規(guī)劃達(dá)到目標(biāo)函數(shù)最優(yōu)，其數(shù)學(xué)模型為

(1)

(2)

式中：0,N+1——出發(fā)點(diǎn)和返回點(diǎn)(同一個點(diǎn)，方便模型計算)；

V——N個目標(biāo)點(diǎn)的集合；

V0——目標(biāo)和0點(diǎn)集合；

VN+1——無人機(jī)和N+1點(diǎn)的集合；

dij——i到j(luò)的距離；

Ti——到達(dá)i的時間；

xij——0或1變量，表示是否存在；

v——無人機(jī)飛行速度；

T——最大巡航時間。

由式(1)可知，其表示希望在規(guī)定時間內(nèi)盡可能的巡視更多的目標(biāo)地點(diǎn)。式(2)為約束條件，其表示使用一架無人機(jī)進(jìn)行巡檢，每個點(diǎn)最多被巡航一次，保證流量守恒，同時，巡檢必須在規(guī)定時間內(nèi)完成巡航任務(wù)等約束。

1.3 改進(jìn)型蟻群算法的礦區(qū)巡檢路徑規(guī)劃

針對傳統(tǒng)蟻群算法易造成局部最優(yōu)和計算時間長的不足[8-11]，在算法改進(jìn)時調(diào)整思路，不要求所有螞蟻都找到最佳路徑，只要一只螞蟻找到最優(yōu)路徑即可，同時，對信息素的權(quán)衡標(biāo)準(zhǔn)進(jìn)行調(diào)整，借助輪盤賭算法，通過該方法及時調(diào)整不同巡檢目標(biāo)之間的轉(zhuǎn)換狀態(tài)，當(dāng)某個目標(biāo)適應(yīng)值越高，就說明該目標(biāo)地點(diǎn)被選中的可能性越大，最后進(jìn)行較優(yōu)路徑結(jié)點(diǎn)交叉操作，當(dāng)陷入局部最優(yōu)時，通過來自不同目標(biāo)地的路徑進(jìn)行交叉操作來更新路徑，提高搜索效率。

利用蟻群算法進(jìn)行路徑規(guī)劃時，構(gòu)建合理的路徑供螞蟻選擇，當(dāng)t=0時，所有路線上均含有同等濃度的信息素。螞蟻由目標(biāo)地i移動到目標(biāo)地j的概率為

(3)

式中：τij——i、j連線上的信息素量；

Ak——螞蟻下一步可去城市的集合；

i、j——起點(diǎn)和終點(diǎn)；

在具體運(yùn)算時，假設(shè)某個路線被選定，立即重新計算信息素的分布情況，第一次巡檢時將設(shè)定一個初始濃度，當(dāng)一條路線巡檢過之后，信息素濃度就會相應(yīng)上升或下降，經(jīng)反復(fù)迭代計算之后，所有目標(biāo)點(diǎn)的濃度值均處在合理區(qū)間。初始濃度超出一定的閾值，線路更新時極易出現(xiàn)“早熟”現(xiàn)象，最快搜索到的線路有可能并不是最短的，反復(fù)搜索又會使時間增加。每次迭代后，所產(chǎn)生的信息素計算方法為

(4)

式中，ρ——自適應(yīng)調(diào)整系數(shù)。

傳統(tǒng)蟻群算法的實(shí)現(xiàn)往往容易受多種外界環(huán)境變化的干擾，引入自適應(yīng)調(diào)整系數(shù)ρ優(yōu)化傳統(tǒng)蟻群算法，處理傳統(tǒng)算法在實(shí)現(xiàn)時存在的收斂慢、容易產(chǎn)生局部循環(huán)等問題。自適應(yīng)調(diào)整公式為

(5)

式中，C——隨機(jī)常數(shù)。

同時，在算法改進(jìn)中引入輪盤賭算法，即將輪盤算子更新方法加入到蟻群信息素轉(zhuǎn)移函數(shù)中，可以提高函數(shù)收斂速度，計算方法為

(6)

式中：q——任一只螞蟻經(jīng)第k個目標(biāo)至第k+1個目標(biāo)中間所有的連接線的數(shù)量， 即集合i、j子區(qū)間的個數(shù)；

fij——第i個和第j個子區(qū)間解的適應(yīng)度；

采用式(6)設(shè)定初始值C，自適應(yīng)調(diào)整揮發(fā)系數(shù)ρ。改進(jìn)型蟻群算法的礦區(qū)巡檢路徑規(guī)劃具體算法步驟分為9步。

步驟1初始化螞蟻參數(shù)M，文中設(shè)置為50只螞蟻，新建一個50×n的矩陣作為禁忌表，其中，n為巡航點(diǎn)的個數(shù)，n=20，將起始禁忌表設(shè)為空集，在禁忌表中的第i行第j列的數(shù)據(jù)為o則表示第i只螞蟻訪問的第j個點(diǎn)為o。

步驟2生成初始解，文中設(shè)計生成種群規(guī)模為50的初始解，鑒于文中數(shù)據(jù)特點(diǎn)，一共有20個巡視點(diǎn)，首先生成一個50×20的矩陣，且每行的第一個數(shù)據(jù)為設(shè)定的出發(fā)點(diǎn)，在生成初始解時第一個解設(shè)置為從1到20的順序巡視路線(除了出發(fā)點(diǎn)之外的19個點(diǎn)順序排列)，第二條路徑是從20到1的逆序巡視路線，其他的48條初始解通過將20個點(diǎn)隨機(jī)排序生成，進(jìn)行下一步操作。

步驟3構(gòu)造可行解，首先將出發(fā)點(diǎn)加入第k行第1列的禁忌表中，初始k為1。

步驟4采用式(6)通過信息素濃度大小使用輪盤賭機(jī)制，根據(jù)信息素濃度大小作為各個點(diǎn)的權(quán)重判斷各個節(jié)點(diǎn)被選擇的概率，按照新狀態(tài)轉(zhuǎn)移概率選擇下一個節(jié)點(diǎn)加入禁忌表，加入禁忌表中的點(diǎn)為下一個巡航位置。

步驟5根據(jù)式(2)判斷無人機(jī)是否能夠在規(guī)定時間返回出發(fā)點(diǎn)，從而確定螞蟻周游是否結(jié)束，若周游結(jié)束，無人機(jī)無法在規(guī)定時間內(nèi)返回出發(fā)點(diǎn)，則將剛選擇的點(diǎn)踢出路徑，并在路徑中加上初始點(diǎn)用來表示無人機(jī)返回出發(fā)點(diǎn)，該螞蟻的行駛路徑設(shè)計完成，螞蟻k=k+1表示為下一只螞蟻設(shè)計路徑，并返回步驟5，否則返回到步驟4繼續(xù)搜索下一個點(diǎn)進(jìn)行巡航。

步驟6判斷螞蟻k是否等于M+1，即判斷是否所有螞蟻都設(shè)計了路徑，是則進(jìn)行下一步驟，否則返回到步驟3。

步驟7根據(jù)式(1)計算在規(guī)定時間內(nèi)巡航的點(diǎn)的個數(shù)，計算禁忌表中每行非零的個數(shù)再減去1，并對其排序，然后根據(jù)式(4)、(5)對選出的50條路徑的巡航線路進(jìn)行信息素更新，未被選中的路徑也會更新信息素，未被選中的路徑信息素會逐步揮發(fā)，被選中的路徑次數(shù)信息素濃度增加越大，因此，下次被選中的概率也越大。

步驟8將本輪迭代的最優(yōu)解跟當(dāng)前最優(yōu)解進(jìn)行對比，若巡邏點(diǎn)更多，則更新最優(yōu)解；若巡邏點(diǎn)數(shù)量相同，則比較巡邏時間，巡邏時間較少的為優(yōu)。

步驟9判斷是否滿足結(jié)束條件，迭代次數(shù)是否達(dá)到限制，文中設(shè)置迭代次數(shù)400次；或者在規(guī)定迭代次數(shù)內(nèi)最優(yōu)解未發(fā)生變化，是則結(jié)束輸出結(jié)果，否則進(jìn)行較優(yōu)路徑節(jié)點(diǎn)交叉操作，然后判斷是否滿足結(jié)束條件，是則輸出結(jié)果，否則返回到步驟1，進(jìn)行下一輪迭代， 直至循環(huán)結(jié)束。具體算法流程如圖2所示。

圖2 改進(jìn)型蟻群算法流程Fig. 2 Improved ant colony algorithm

2 仿真與結(jié)果分析

四旋翼無人機(jī)巡航速度為20 km/h，巡航時間未定。文中分別設(shè)定巡航5、7、10 min，對比改進(jìn)型蟻群算法和傳統(tǒng)蟻群算法的結(jié)果，分析算法的優(yōu)越性。當(dāng)巡檢時間為5 min，出發(fā)點(diǎn)為1號位置時，通過改進(jìn)后蟻群算法和傳統(tǒng)蟻群算法得出結(jié)果如圖3所示。從圖3可知，改進(jìn)后蟻群算法所獲得的結(jié)果明顯較傳統(tǒng)蟻群算法的巡航路徑更加簡潔，巡檢路線未出現(xiàn)交叉，從數(shù)據(jù)可以看出，在規(guī)定時間內(nèi)改進(jìn)型蟻群算法巡視了18個目標(biāo)地，傳統(tǒng)蟻群算法巡視目標(biāo)地個數(shù)為17個，改進(jìn)后算法性能更優(yōu)越。

當(dāng)巡檢時間為7 min，結(jié)果如圖4所示。從圖4可知，改進(jìn)型蟻群算法獲得結(jié)果能巡視20個目標(biāo)地，但傳統(tǒng)蟻群算法只能巡視19個目標(biāo)地，同時，改進(jìn)后算法巡視總長度為2 077 m，而未改進(jìn)時算法的結(jié)果巡視總長度為2 079 m，可以看出，改進(jìn)型蟻群算法所求結(jié)果更加精確。

圖3 5 min巡檢路線Fig. 3 5 min inspection route

圖4 7 min巡檢路線Fig. 4 7 min inspection route

當(dāng)巡檢時間增加到10 min時，四旋翼無人機(jī)已經(jīng)能做到巡檢完所有地點(diǎn)并返回出發(fā)點(diǎn)，因此，此時比較的就是哪一種巡檢策略能更短的時間內(nèi)巡視完所有的目標(biāo)地，具體結(jié)果如圖5所示。

圖5 10 min巡檢路線Fig. 5 10 min inspection route

從圖5可知，兩種算法都能設(shè)計出合理路線將所有目標(biāo)地巡檢一遍，但是改進(jìn)型蟻群算法飛行距離為2 108 m，而傳統(tǒng)蟻群算法的路徑需要飛行2 178 m。

3 結(jié) 論

(1) 當(dāng)巡檢時間為5 min，初始位置均為信號樓時，改進(jìn)后蟻群算法所獲得的巡檢路線圖明顯較傳統(tǒng)蟻群算法更加簡潔，且算法改進(jìn)后巡檢路線未出現(xiàn)交叉，仿真表明，在規(guī)定時間內(nèi)改進(jìn)型蟻群算法比改進(jìn)前多巡檢1個目標(biāo)地，綜合對比改進(jìn)后算法性能更優(yōu)越。

(2) 當(dāng)巡檢時間為7 min，初始位置均為信號樓時，在規(guī)定時間內(nèi)改進(jìn)型蟻群算法比改進(jìn)前多巡檢1個目標(biāo)地，同時，改進(jìn)后算法巡視總長度比改進(jìn)前少2 m，改進(jìn)型蟻群算法所求結(jié)果更加精確。當(dāng)巡檢時間為10 min，初始位置均為信號樓時兩種算法都能設(shè)計出合理路線將所有目標(biāo)地有巡檢一遍，但是改進(jìn)型蟻群算法飛行距離為2 108 m，而傳統(tǒng)蟻群算法的路徑需要飛行2 178 m,改進(jìn)型蟻群算法飛行距離更短。