基于改進(jìn)蟻群算法的移動機(jī)器人火災(zāi)救援路徑規(guī)劃方法

昝新宇，張鐵峰, 苑津莎

(華北電力大學(xué)電氣與電子工程學(xué)院，保定 071003)

近年來，中國每年發(fā)生數(shù)萬起火災(zāi)事故[1-2]，嚴(yán)重影響著人們正常的生產(chǎn)生活。隨著機(jī)器人技術(shù)的迅速發(fā)展，機(jī)器人因其智能、高效等優(yōu)點(diǎn)受到各行各業(yè)的青睞，因此移動機(jī)器人參與火災(zāi)救援已成為未來發(fā)展趨勢。為此，探究移動機(jī)器人在火災(zāi)救援中如何快速到達(dá)待救援點(diǎn)執(zhí)行救援任務(wù)，具有十分重要的研究意義。

關(guān)于火災(zāi)救援路徑規(guī)劃的問題，李珊珊等[3]針對多起點(diǎn)、多終點(diǎn)的大型火災(zāi)救援路線，設(shè)計(jì)了一種組合優(yōu)化路徑規(guī)劃方法，可以計(jì)算出安全、快速的救援路徑，提高了火災(zāi)救援的效率；劉軍[4]采用蟻群算法與遺傳算法結(jié)合方式，改善了超市火災(zāi)環(huán)境下消防員滅火救援路徑；張?zhí)K英等[5]提出一種改進(jìn)蟻群算法，優(yōu)化了大型綜合建筑火災(zāi)疏散路徑;張麗杰等[6]針對復(fù)雜建筑火災(zāi)中的人員疏散路徑優(yōu)化策略問題，構(gòu)建了一種以最短時(shí)間、最小風(fēng)險(xiǎn)水平和最大疏散容量為目標(biāo)的路徑優(yōu)化模型，并結(jié)合自適應(yīng)果蠅算法對模型求解。

在移動機(jī)器人路徑規(guī)劃方面，Luo等[7]為解決蟻群算法搜索效率低、收斂速度慢等問題，提出一種優(yōu)化蟻群算法，并通過實(shí)驗(yàn)仿真驗(yàn)證了該算法能夠提高移動機(jī)器人路徑規(guī)劃效率；王蘇彧等[8]提出了一種基于自適應(yīng)導(dǎo)向的優(yōu)化蟻群算法，通過優(yōu)化算法的收斂速度和尋優(yōu)能力，進(jìn)而提高了移動機(jī)器人自主規(guī)劃路徑的能力；Ranaweera等[9]提出了一種粒子群優(yōu)化算法來尋找消防救援機(jī)器人的最短路徑，并通過模擬實(shí)驗(yàn)驗(yàn)證了改進(jìn)算法的效率遠(yuǎn)高于傳統(tǒng)算法；李理等[10]提出了一種多啟發(fā)因素改進(jìn)蟻群算法，該算法計(jì)算出的路徑在路徑長度、轉(zhuǎn)彎次數(shù)以及坡度平滑性三因素綜合性能上具有較大的提高，進(jìn)而增強(qiáng)了移動機(jī)器的環(huán)境適應(yīng)能力。

當(dāng)前，中外學(xué)者針對移動機(jī)器人火災(zāi)救援路徑規(guī)劃問題的研究較少，而且在已有方法中只考慮了距離因素，沒有考慮影響路徑選擇的其他因素。對此，現(xiàn)考慮多因素針對移動機(jī)器人火災(zāi)救援路徑規(guī)劃的影響，提出一種基于改進(jìn)蟻群算法的移動機(jī)器人火災(zāi)救援路徑方法。方法考慮多因素分配各路徑上的信息素，指導(dǎo)螞蟻尋找最優(yōu)路徑。通過動態(tài)調(diào)整信息素和啟發(fā)式函數(shù)影響因子，以期提升算法的搜索能力與收斂速度。

1 環(huán)境描述

環(huán)境模型的構(gòu)建對于移動機(jī)器人路徑規(guī)劃至關(guān)重要，通過部署在建筑物內(nèi)的無線傳感設(shè)備獲取環(huán)境信息，然后根據(jù)柵格法[11]建立環(huán)境模型。通過MATLAB仿真，仿真結(jié)果如圖1所示。

綠色圓點(diǎn)為移動機(jī)器人的起始位置，紅色圓點(diǎn)為待救援位置；黑色柵格表示障礙物，白色柵格表示自由空間；紅色柵格表示火源中心，黃色柵格表示火源周圍蔓延區(qū)域；綠色深淺表示坡度大小，顏色越深表示坡度越大

針對移動機(jī)器人在火災(zāi)救援過程中對于安全性方面的要求非常高，規(guī)劃出的路徑盡量遠(yuǎn)離障礙物、火源以及蔓延區(qū)域，即使頂點(diǎn)也要避免觸碰。因此規(guī)定每個(gè)柵格中心為節(jié)點(diǎn)，螞蟻的運(yùn)動軌跡可以理解為從當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)轉(zhuǎn)移的累積過程。同時(shí)為了避免移動機(jī)器人在轉(zhuǎn)彎過程中發(fā)生碰撞，只有目標(biāo)柵格和轉(zhuǎn)角處柵格均為自由柵格時(shí)，才能向該目標(biāo)節(jié)點(diǎn)轉(zhuǎn)移，如圖2所示。

圖2 轉(zhuǎn)彎示意圖

2 傳統(tǒng)蟻群算法

蟻群算法是Dorigo提出的一種模擬螞蟻種群覓食行為的智能仿生算法[12]。該算法具有并行計(jì)算、正反饋、魯棒性強(qiáng)等優(yōu)點(diǎn)，因此許多學(xué)者將蟻群算法用于路徑規(guī)劃，并取得較好的效果。信息素模型和啟發(fā)式函數(shù)的構(gòu)建是蟻群算法優(yōu)劣的關(guān)鍵因素[13]。信息素是蟻群發(fā)出的指引信息并隨著時(shí)間揮發(fā)，路徑上的信息素濃度越高，越能指導(dǎo)螞蟻沿該路徑前進(jìn)；啟發(fā)式函數(shù)則相當(dāng)于螞蟻根據(jù)自身所處環(huán)境進(jìn)行判斷的依據(jù)。

螞蟻在搜索過程中根據(jù)轉(zhuǎn)移概率選擇下一步前進(jìn)方向，轉(zhuǎn)移概率為

(1)

(2)

每只螞蟻在使用信息素的同時(shí)也會分泌信息素，并且會隨著迭代次數(shù)的增加，信息素會在路徑上積累，同時(shí)也會揮發(fā)減少。傳統(tǒng)蟻群算法的信息素更新模型為

τi,j(t+1)=(1-ρ)τi,j(t)+ρΔτi,j(t)

(3)

(4)

式中：ρ為信息素?fù)]發(fā)度；Δτi,j(t)為第t次迭代中信息素在節(jié)點(diǎn)i至節(jié)點(diǎn)j上的增量；Q為信息素常數(shù)；Lk為第k只螞蟻從起點(diǎn)至終點(diǎn)走過的路徑長度。

3 改進(jìn)蟻群算法

3.1 多因素啟發(fā)式函數(shù)

傳統(tǒng)蟻群算法的啟發(fā)式信息與當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)的距離成反比，這促使螞蟻選擇距離短的路徑。但是，在實(shí)際環(huán)境中決定路徑優(yōu)劣的因素不止距離一種，還有路徑的曲折程度、顛簸程度等因素。移動機(jī)器人在火災(zāi)救援中多轉(zhuǎn)彎一次可能會浪費(fèi)大量的寶貴救援時(shí)間，顛簸程度較大的路況不僅會影響移動機(jī)器人的速度，可能還會損壞機(jī)器設(shè)備。因此，規(guī)劃一條綜合指標(biāo)最好的路線對于移動機(jī)器人參與火災(zāi)救援至關(guān)重要。為此，針對影響路徑優(yōu)劣的多因素引入多因素啟發(fā)式函數(shù)，來計(jì)算轉(zhuǎn)移概率，并同時(shí)引入阻尼系數(shù)，加快算法后期的收斂速度，即

(5)

(6)

式中：φ(i,j,q)為距離因素，即當(dāng)前節(jié)點(diǎn)的各個(gè)相鄰節(jié)點(diǎn)至目標(biāo)節(jié)點(diǎn)的歐式距離的倒數(shù)；φi,j(t)為曲折程度，即當(dāng)前轉(zhuǎn)向若與上次轉(zhuǎn)向相同，則其值就較大，反之則較?。沪?i,j)為顛簸程度，即當(dāng)前節(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)的高度差的倒數(shù)；ζ為阻尼系數(shù)；tmax為最大迭代次數(shù)。

3.2 改進(jìn)信息素更新規(guī)則

信息素更新主要模擬自然界中螞蟻信息素隨時(shí)間的積累和揮發(fā)過程。將最大-最小蟻群系統(tǒng)(MMAS)的基本模型與多因素啟發(fā)式函數(shù)相結(jié)合，對信息素更新規(guī)則進(jìn)行改進(jìn)。

每當(dāng)一只螞蟻到達(dá)終點(diǎn)時(shí)，信息素根據(jù)式(7)、式(8)進(jìn)行局部更新。所有螞蟻完成一次迭代后，所有螞蟻行走的過程中，會存在綜合指標(biāo)最小的路徑，全局信息素只對其更新，從而增加當(dāng)前綜合性最優(yōu)路徑對后續(xù)蟻群尋優(yōu)的影響，如式(9)所示。

(7)

Sk(t)=xLk(t)+yFk(t)+zTk(t)

(8)

(9)

式中：Sk(t)為第k只螞蟻在第t次迭代中所走路徑的綜合指標(biāo)；Smin(t)為第t次迭代中最小的綜合指標(biāo)；Lk(t)為路徑長度；Fk(t)為螞蟻訪問過節(jié)點(diǎn)的高度均方差；Tk(t)為轉(zhuǎn)彎次數(shù)；x、y、z分別為路徑長度、顛簸程度以及曲折程度的相對重要性，可以根據(jù)實(shí)際需要進(jìn)行調(diào)節(jié)。為了防止算法停滯，將信息素限制在[τmin,τmax]范圍內(nèi)，如式(10)所示。

(10)

式(10)中：τmin、τmax分別為信息素的最小值和最大值，取值可以根據(jù)實(shí)際的場景進(jìn)行設(shè)計(jì)。

3.3 動態(tài)調(diào)整信息素和啟發(fā)式函數(shù)影響因子

信息素影響因子反映了信息素在蟻群搜索中的相對重要性[14]，其值過大或過小，都會導(dǎo)致蟻群算法找不到最優(yōu)解。啟發(fā)式函數(shù)影響因子反映了蟻群尋找最優(yōu)解過程中先驗(yàn)性的相對重要程度[15]，其值增大，加速算法的收斂，但同時(shí)會減小算法的隨機(jī)性；減小時(shí)，則相反。

因此信息素和啟發(fā)式函數(shù)影響因子對于蟻群算法至關(guān)重要，為了提升算法收斂速度和搜索能力，提出了一種動態(tài)調(diào)整信息素和啟發(fā)式函數(shù)影響因子的方法。算法初期，針對信息素分布差別較小，螞蟻的搜索過程可能混亂，這時(shí)啟發(fā)式函數(shù)在蟻群搜索中起主要引導(dǎo)作用，螞蟻更多地依據(jù)自身環(huán)境選擇前進(jìn)方向；隨著信息素不斷地更新，信息素的分布差別變得明顯，此時(shí)信息素和啟發(fā)式函數(shù)共同引導(dǎo)蟻群尋優(yōu)過程，螞蟻在選擇下一節(jié)點(diǎn)時(shí)，需要同時(shí)考慮自身環(huán)境和前面螞蟻留下的信息素。如式(11)、式(12)所示。

(11)

(12)

式中：α為信息素影響因子；β為啟發(fā)式函數(shù)影響因子；ζ為一個(gè)百分比常數(shù)；A、B、C、D、E為正整數(shù)，可隨環(huán)境不同改變?nèi)≈怠?/p>

3.4 改進(jìn)算法流程

步驟1地圖障礙物、火源等位置信息以及參數(shù)初始化。其中螞蟻數(shù)量m=50，最大迭代次數(shù)tmax=100，信息素強(qiáng)度Q=100，其他的參數(shù)作為變量根據(jù)實(shí)驗(yàn)環(huán)境進(jìn)行設(shè)置。

步驟2設(shè)置起始坐標(biāo)與終點(diǎn)坐標(biāo)。

步驟3禁忌表初始化。

步驟4確定信息素和啟發(fā)式函數(shù)影響因子。根據(jù)式(11)和式(12)分別計(jì)算信息素和啟發(fā)式函數(shù)影響因子。

步驟5路徑選擇。由式(3)和式(5)分別計(jì)算信息素與多因素啟發(fā)式函數(shù)，然后由式(1)計(jì)算螞蟻每個(gè)前進(jìn)方向的概率，最后利用輪盤賭決定螞蟻下一個(gè)轉(zhuǎn)移節(jié)點(diǎn)。

步驟6更新禁忌表。

步驟7判斷當(dāng)前螞蟻是否到達(dá)終點(diǎn)坐標(biāo)位置，若是，繼續(xù)執(zhí)行算法；否則，返回步驟5。

步驟8由式(8)計(jì)算螞蟻?zhàn)哌^路徑的綜合指標(biāo)，由式(7)進(jìn)行信息素局部更新。

步驟9判斷是否所有螞蟻完成搜索，若是，繼續(xù)執(zhí)行算法；否則，增加螞蟻數(shù)量，即m=m+1，然后返回步驟3。

步驟10更新全局信息素。需要找到本次迭代中綜合指標(biāo)最佳的路徑，并根據(jù)式(9)進(jìn)行全局信息素更新。

步驟11判斷迭代次數(shù)是否達(dá)到最大迭代次數(shù)，若是，比較各迭代次數(shù)中綜合指標(biāo)最佳的路徑，輸出最優(yōu)路徑，結(jié)束算法；否則，增加迭代次數(shù)，即t=t+1,m=1，然后返回步驟3。

改進(jìn)的算法流程如圖3所示。

圖3 改進(jìn)算法流程

4 實(shí)驗(yàn)仿真與分析

使用MATLAB R2019a仿真軟件對算法進(jìn)行仿真，模擬移動機(jī)器人在火災(zāi)救援中規(guī)避障礙物和火源及蔓延區(qū)域的路徑規(guī)劃過程。設(shè)定30 m×30 m的區(qū)域內(nèi)均勻分布傳感設(shè)備，時(shí)刻監(jiān)視火源及蔓延區(qū)域情況；移動機(jī)器人的起始坐標(biāo)為(0.5,0.5)m，待救援位置即終點(diǎn)坐標(biāo)為(29.5,29.5)m。初始環(huán)境如圖1所示。根據(jù)經(jīng)驗(yàn)和實(shí)驗(yàn)仿真對比進(jìn)行參數(shù)取值，算法的參數(shù)配置如表1所示。

表1 改進(jìn)蟻群算法的參數(shù)配置

將改進(jìn)蟻群算法、文獻(xiàn)[10]算法和傳統(tǒng)蟻群算法在相同的環(huán)境模型中進(jìn)行實(shí)驗(yàn)仿真。3種不同算法計(jì)算出最佳救援路線如圖4所示。

藍(lán)色實(shí)線為傳統(tǒng)蟻群算法的規(guī)劃路線；黑色虛線為文獻(xiàn)[10]算法計(jì)算出的最佳路徑；紅色實(shí)線為本文算法規(guī)劃的最佳路徑

為了驗(yàn)證改進(jìn)算法的優(yōu)越性，進(jìn)行了多次實(shí)驗(yàn)仿真，如圖5和表2所示。通過比較3個(gè)算法的實(shí)驗(yàn)結(jié)果，在路徑長度、路徑高度均方差以及轉(zhuǎn)彎次數(shù)3個(gè)指標(biāo)上本文算法均小于傳統(tǒng)蟻群算法和文獻(xiàn)[10]算法，比較3個(gè)算法的綜合指標(biāo)可以看出，本文算法計(jì)算出的路徑在多因素上明顯優(yōu)于文獻(xiàn)[10]算法和傳統(tǒng)蟻群算法。并且本文算法較大地提高了算法的收斂速度，降低了穩(wěn)定迭代次數(shù)，提升了算法的搜索能力，使螞蟻初始尋路就能找到綜合指標(biāo)較好的路徑。在算法穩(wěn)定性方面，本文算法多次實(shí)驗(yàn)計(jì)算出的最優(yōu)路徑中的各項(xiàng)指標(biāo)波動較小，明顯優(yōu)于文獻(xiàn)[10]算法和傳統(tǒng)蟻群算法。

表2 本文算法、文獻(xiàn)[10]算法及傳統(tǒng)蟻群算法的結(jié)果對比

連續(xù)10次實(shí)驗(yàn)中不同算法平均運(yùn)行時(shí)間如表3所示，雖然本文算法運(yùn)行時(shí)間稍長于傳統(tǒng)算法，但迭代穩(wěn)定時(shí)間明顯小于傳統(tǒng)蟻群算法和文獻(xiàn)[10]算法。由此可見，本文算法的執(zhí)行效率顯然優(yōu)于傳統(tǒng)蟻群算法和文獻(xiàn)[10]算法，可以幫助移動機(jī)器人快速找到一條多因素綜合性最優(yōu)的路徑。

表3 連續(xù)10次實(shí)驗(yàn)中不同算法平均運(yùn)行時(shí)間

可見，本文算法在多因素綜合性能上有了較大提升，并且具有較好的全局搜索能力和收斂速度。因此，該方法可以使移動機(jī)器人有效避開障礙物和火源區(qū)域，找到一條安全、快速的救援路線，大大提高了火災(zāi)救援的效率。

5 結(jié)論

針對移動機(jī)器人在火災(zāi)救援中路徑規(guī)劃的多種影響因素，提出了一種基于改進(jìn)蟻群算法的路徑規(guī)劃方法。

(1)改進(jìn)蟻群算法通過引入多啟發(fā)式函數(shù)和改進(jìn)全局信息素更新策略，更好地引導(dǎo)蟻群向綜合性最優(yōu)的路徑靠近。

(2)通過對信息素和啟發(fā)式函數(shù)影響因子動態(tài)調(diào)整，提升了算法的搜索能力和收斂速度。

(3)通過實(shí)驗(yàn)仿真驗(yàn)證和3種方法的對比分析，驗(yàn)證了本文算法能夠滿足移動機(jī)器人救援路徑規(guī)劃快速決策的需要，較好地提高了火災(zāi)救援的效率。

改進(jìn)算法在傳統(tǒng)蟻群算法基礎(chǔ)上針對啟發(fā)式函數(shù)和信息素更新方式等方面進(jìn)行了優(yōu)化，沒有考慮初始信息素差別分布，在今后的研究中，可以利用神經(jīng)網(wǎng)絡(luò)對其進(jìn)行優(yōu)化，使路徑規(guī)劃方法更加高效、智能。