基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃

周敬東， 高偉周， 楊文廣， 戚得眾， 周天

(1.湖北工業(yè)大學(xué)機(jī)械工程學(xué)院， 武漢 430068； 2.湖北工業(yè)大學(xué)農(nóng)機(jī)工程研究設(shè)計(jì)院， 武漢 430068； 3.武漢沐沃霖科技發(fā)展有限公司， 武漢 430068)

隨著機(jī)器人技術(shù)的迅速發(fā)展，移動(dòng)機(jī)器人受到各領(lǐng)域廣泛的應(yīng)用。路徑規(guī)劃作為機(jī)器人行走的重要部分[1-2]。迄今為止，中外研究人員對(duì)移動(dòng)機(jī)器人的路徑規(guī)劃算法開展了大量的研究[3]，如遺傳算法[4]、神經(jīng)網(wǎng)絡(luò)算法[5]、粒子群算法[6]、蟻群算法[7]、A*算法[8]以及Dijkstrta算法[9]等各類算法。由于蟻群算法的魯棒性強(qiáng)和自組織性好，并且是一種并行算法，被廣泛應(yīng)用在機(jī)器人路徑規(guī)劃問(wèn)題[10]。

針對(duì)蟻群算法出現(xiàn)的收斂速度慢、易發(fā)生死鎖等不足，許多研究人員提出了大量的解決對(duì)策。袁福龍等[10]通過(guò)構(gòu)造數(shù)學(xué)模型、引入?yún)^(qū)域安全信息函數(shù)和轉(zhuǎn)角啟發(fā)信息函數(shù)等策略，采用“狼群分配策略”方法避免陷入局部最優(yōu)和加快最優(yōu)路徑的收斂，能夠有效避開靜態(tài)和動(dòng)態(tài)環(huán)境中的障礙物而迅速找到一條較平滑的最優(yōu)路徑。曹新亮等[11]通過(guò)在柵格地圖中劃出優(yōu)選區(qū)域?qū)Τ跏夹畔⑺貪舛炔町惢O(shè)置，盡管建立新的數(shù)學(xué)模型能有效地加快算法前期搜索的速度和減少了最優(yōu)迭代次數(shù)，但是算法建立復(fù)雜的數(shù)學(xué)模型以及選取比值節(jié)點(diǎn)會(huì)很大地增加了算法的運(yùn)算量和運(yùn)行時(shí)間。史恩秀等[12]針對(duì)蟻群算法中的啟發(fā)因子α等主要參數(shù)對(duì)路徑規(guī)劃效率的影響進(jìn)行了仿真實(shí)驗(yàn)分析，綜合考慮找到了改進(jìn)蟻群算法最佳匹配參數(shù)。牛龍輝等[13]通過(guò)引入自適應(yīng)信息素?fù)]發(fā)系數(shù)方法解決中尋優(yōu)能力不足和算法多樣性低等問(wèn)題，以加強(qiáng)全局尋優(yōu)能力，提高了算法多樣性。以上學(xué)者在蟻群算法理論方面做了研究改進(jìn)，對(duì)算法做了優(yōu)化，具有一定的適用性，但對(duì)機(jī)器人實(shí)際運(yùn)行效果研究較少，依然需要進(jìn)行優(yōu)化算法，提高改進(jìn)蟻群算法的實(shí)用性。

為了優(yōu)化路徑規(guī)劃，在已有的研究基礎(chǔ)上，提出一種新的蟻群算法，改變?cè)械某跏夹畔⑺胤峙浞绞綖殡A梯分配，融合A*算法作為路徑搜索的啟發(fā)式信息改進(jìn)啟發(fā)函數(shù)，加強(qiáng)最優(yōu)解對(duì)螞蟻的吸引力,設(shè)置蟻群回退策略，避免蟻群陷入“陷阱”后無(wú)法退回，引入螞蟻優(yōu)化排序，使算法路徑規(guī)劃更短、迭代次數(shù)更少的理想效果。通過(guò)MATLAB 軟件仿真和使用樹莓派六足機(jī)器人實(shí)驗(yàn)，期望改進(jìn)后的蟻群算法在路徑長(zhǎng)度、迭代次數(shù)和轉(zhuǎn)折點(diǎn)數(shù)等方面性能優(yōu)越于傳統(tǒng)蟻群算法。

1 蟻群算法

1.1 基本蟻群算法

蟻群算法是由一種基于種群的啟發(fā)式隨機(jī)搜索算法[14]。蟻群在覓食的過(guò)程中，起點(diǎn)從蟻巢位置，食物位置為終點(diǎn)，通過(guò)多次搜索行走路徑，在已走的路徑上留下信息素[15]，避開障礙物選擇最佳路徑行走。蟻群覓食過(guò)程如圖1所示。

圖1 蟻群覓食過(guò)程Fig.1 Ant colony foraging process

1.2 改進(jìn)的蟻群算法

1.2.1 初始化信息素濃度的改變

傳統(tǒng)蟻群算法初始化信息素濃度是采取均勻分配在各個(gè)柵格的方式，這樣會(huì)降低螞蟻的搜索效率。蟻群在行走路徑的過(guò)程中，每只螞蟻是從起點(diǎn)出發(fā)搜索選擇最短路徑到達(dá)終點(diǎn)。為了避免蟻群在尋優(yōu)路徑中出現(xiàn)“原地不動(dòng)”現(xiàn)象，通過(guò)設(shè)置信息素軌跡量在[τmin,τmax]這個(gè)區(qū)間，合理安排路徑上的軌跡量，有利于避免初期盲目搜索的行為。故在設(shè)定信息素濃度矩陣Tau時(shí)，在起點(diǎn)與終點(diǎn)的最短路徑以及周圍路勁信息素值按照逐漸遞減方式設(shè)定。這樣可以有利于蟻群在初期對(duì)最優(yōu)路徑方向搜索，有效地提高了收斂速度。

1.2.2 啟發(fā)函數(shù)的改進(jìn)

傳統(tǒng)蟻群算法中啟發(fā)函數(shù)ηij(t)=1/dij(其中dij為柵格節(jié)點(diǎn)i,j之間的距離)表明螞蟻從節(jié)點(diǎn)i行走至柵格j的期望程度與節(jié)點(diǎn)之間的距離相關(guān)聯(lián)，在運(yùn)行過(guò)程中，出現(xiàn)迭代次數(shù)過(guò)少且無(wú)法找到最優(yōu)路徑，算法耗時(shí)比較長(zhǎng)，導(dǎo)致收斂速度較慢[16]。針對(duì)此缺陷對(duì)啟發(fā)函數(shù)進(jìn)行改進(jìn)，融合A*算法作為路徑搜索的啟發(fā)式信息，從而獲得較好的路徑。已知A*算法的評(píng)價(jià)函數(shù)表達(dá)式為

f(n)=g(n)+h(n)

(1)

式(1)中：f(n)為由起始點(diǎn)到達(dá)結(jié)束點(diǎn)的總代價(jià)值；g(n)為f(n)的前一部分代價(jià)，即起始點(diǎn)到當(dāng)前點(diǎn)的代價(jià)；h(n)為f(n)的后一部分代價(jià)，即當(dāng)前點(diǎn)到結(jié)束點(diǎn)的代價(jià)。

改進(jìn)后啟發(fā)算子ηij(t)為

(2)

改進(jìn)后的啟發(fā)函數(shù)提高了算法的有效性，提高了算法的尋優(yōu)能力，大大減少了算法收斂時(shí)間，使蟻群朝著最優(yōu)路徑方向快速搜索前進(jìn)。

1.2.3 蟻群回退策略的設(shè)置

為了避免蟻群在行走的過(guò)程中陷入H形、U形等障礙后沒(méi)有選擇的地步，采用螞蟻回退策略來(lái)應(yīng)對(duì)。通過(guò)加進(jìn)螞蟻回退策略，使螞蟻進(jìn)入“陷阱”后，有能力擺脫困境，發(fā)揮螞蟻的搜索作用，完成搜索任務(wù)。圖2為U形障礙物的柵格地圖，當(dāng)一只螞蟻到達(dá)N10位置時(shí),這只螞蟻無(wú)法前進(jìn)，此時(shí)被迫需要退回N7位置，同時(shí)要更新禁忌表記錄的螞蟻k當(dāng)前已走過(guò)的位tabuk中的數(shù)據(jù)，刪除N10位置信息，然后在選取合適路徑行走，假如這只螞蟻仍然無(wú)法前進(jìn)，則選擇繼續(xù)回退，這只螞蟻仍需從tabuk中刪除N7位置信息，螞蟻回退到N3位置，重新選擇前進(jìn)路徑。

蟻群回退策略的設(shè)置，使螞蟻在前進(jìn)搜索過(guò)程中擺脫“陷阱”困境，充分發(fā)揮每只螞蟻的搜索作用，大大增強(qiáng)了算法的健壯性以及蟻群對(duì)環(huán)境的適應(yīng)能力。

黑色陰影柵格為障礙物；帶數(shù)字柵格為螞蟻可通行區(qū)域(無(wú)障礙)， 其中數(shù)字表示位置順序，如“1”表示N1圖2 U形障礙物的柵Fig.2 Grid map of U-shaped obstacle

1.2.4 優(yōu)化排序的引入

為了加快蟻群找到最優(yōu)解速度，在每次蟻群完成行走路徑后，標(biāo)記信息素最優(yōu)解[17]。每只螞蟻完成路徑搜索后，螞蟻行走的路徑長(zhǎng)度不同。在修改信息素路徑前，按照螞蟻的長(zhǎng)度由短到長(zhǎng)進(jìn)行排序L1≤L2≤…≤Lm，每只螞蟻釋放的信息素量和排名相乘。已知在每次循環(huán)中，只有排名前h-1位的螞蟻和精英螞蟻才允許在行走路徑上釋放信息素[18]。已知的最優(yōu)路徑給以最強(qiáng)的反饋，和系數(shù)h相乘，排名第k位的螞蟻則乘系數(shù)h-k。則信息素表達(dá)式為

(3)

(4)

(5)

式(5)中：Lbs為已知最優(yōu)路徑Tbs的長(zhǎng)度。

2 算法運(yùn)行流程

2.1 環(huán)境建模

環(huán)境建模有柵格地圖法和數(shù)字序列法等方法，使用柵格法建立移動(dòng)機(jī)器人的環(huán)境模型[19]。柵格法采用“0”“1”表示柵格地圖中有無(wú)障礙，0表示此處無(wú)障礙物，機(jī)器人可以自由通過(guò)，1表示此處有障礙，機(jī)器人無(wú)法通過(guò)。設(shè)置移動(dòng)機(jī)器人的移動(dòng)范圍為20×20大小的柵格方形，單位長(zhǎng)度為1，如圖3所示。

S為起始點(diǎn)；E為目標(biāo)點(diǎn)圖3 20×20柵格地圖Fig.3 20×20 grid map

機(jī)器人前進(jìn)必須占用柵格，考慮到移動(dòng)機(jī)器人在真實(shí)環(huán)境下會(huì)有很多方向可供選擇，為了簡(jiǎn)化移動(dòng)方向，規(guī)定機(jī)器人停在每個(gè)活動(dòng)區(qū)域的中心點(diǎn)為準(zhǔn)，每一步移動(dòng)可供參考的方向只有8種，分別為左前、左后、右前、右后4個(gè)斜方向和前后左右4個(gè)直行方向。機(jī)器人的移動(dòng)方向，如圖4所示。

圖4 機(jī)器人移動(dòng)方向Fig.4 Direction of robot movement

2.2 算法執(zhí)行步驟

蟻群算法應(yīng)用于機(jī)器人路徑規(guī)劃時(shí)主要由初始化、解構(gòu)建和信息素更新三部分組成[15,20-21]。參數(shù)初始化主要對(duì)時(shí)間、循環(huán)次數(shù)、信息素、迭代次數(shù)等參數(shù)設(shè)置初始值。螞蟻根據(jù)狀態(tài)轉(zhuǎn)移概率公式計(jì)算出的概率選擇元素j并前進(jìn)，最終完成搜索路徑到達(dá)目標(biāo)點(diǎn)[21]。通過(guò)不斷修改禁忌表指針和更新每條路徑上的信息量方法，找到一條最優(yōu)行走路徑。蟻群算法的執(zhí)行步驟流程圖，如圖5所示。

圖5 蟻群算法的執(zhí)行步驟流程圖Fig.5 Flow chart of the execution steps of ant colony algorithm

(6)

式(6)中：Jk={1,2,…,n}-tabuk為螞蟻k在下一步可以選擇的位置集合，其中tabuk為禁忌表記錄的螞蟻k當(dāng)前已走過(guò)的位置；ηij為一個(gè)啟發(fā)因子，表示螞蟻從位置i轉(zhuǎn)移到位置j的期望程度；α為信息素的相對(duì)重要程度；β為期望啟發(fā)因子的相對(duì)重要程度；τij為柵格節(jié)點(diǎn)i,j之間的信息素濃度；τis為位置點(diǎn)i到初始點(diǎn)的信息素濃度；ηis為位置點(diǎn)i到初始點(diǎn)的啟發(fā)函數(shù)。

在所有螞蟻完成一次從起點(diǎn)到終點(diǎn)后，各路徑信息素開始更新，信息素更新公式為[18]

τij(t+n)=(1-ρ)τij(t)+Δτij

(7)

式(7)中：ρ為路徑上信息素的蒸發(fā)系數(shù)，0<ρ<1；1-ρ為信息素的持久性系數(shù)；Δτij為本次迭代中邊ij上信息素的增量。

Δτij可表示為[18]

(8)

(9)

式(9)中：Q為正常數(shù)；Lk為第k只螞蟻在本次迭代中所走過(guò)路徑的長(zhǎng)度。

3 仿真與評(píng)價(jià)

為了驗(yàn)證算法優(yōu)化后的效果，在MATLAB 2016a上對(duì)改進(jìn)蟻群算法進(jìn)行多次仿真，與傳統(tǒng)蟻群算法作對(duì)比分析。利用已建成20x20的柵格地圖運(yùn)行程序，設(shè)定機(jī)器人初始坐標(biāo)為(0.5，19.5)，終點(diǎn)坐標(biāo)為(19.5，0.5)。程序仿真參數(shù)設(shè)置如表1所示。

圖6、圖7分別為在傳統(tǒng)蟻群算法和改進(jìn)蟻群算法仿真的路徑軌跡和迭代次數(shù)結(jié)果。

由圖6可知，傳統(tǒng)蟻群算法在初期無(wú)法確定搜索方向，盲目性大，迭代次數(shù)高達(dá)40次以上，最短路徑長(zhǎng)度為32.5。

由圖7可知，改進(jìn)蟻群算法的搜索效率較高，迭代次數(shù)少于40次，最短路徑長(zhǎng)度只有29.2。分析表2數(shù)據(jù)可知：所提的改進(jìn)蟻群算法在多方面評(píng)價(jià)參數(shù)優(yōu)于傳統(tǒng)蟻群算法。

表1 參數(shù)設(shè)置

圖6 傳統(tǒng)蟻群算法Fig.6 Traditional ant colony algorithm

為驗(yàn)證所提出的改進(jìn)算法的先進(jìn)性和有效性，通過(guò)創(chuàng)建帶有不同的障礙物柵格環(huán)境(20×20)，進(jìn)行多次仿真驗(yàn)證。表3為隨機(jī)選取6組在不同的障礙物柵格地圖環(huán)境對(duì)兩類蟻群算法仿真的結(jié)果。

通過(guò)對(duì)6組帶有不同的障礙物環(huán)境仿真結(jié)果分析可以得出，改進(jìn)蟻群算法的迭代次數(shù)平均減少了30.24%，規(guī)劃出的路徑平均縮短了9.03%，運(yùn)行時(shí)間平均減少了16.19%。仿真結(jié)果表明，改進(jìn)蟻群算法的路徑規(guī)劃長(zhǎng)度與傳統(tǒng)蟻群算法相比更短，迭代效率更高效，尤其在大尺寸地圖和障礙物多的情況下。

圖7 改進(jìn)蟻群算法Fig.7 Improved ant colony algorithm

表2 蟻群算法改進(jìn)前后仿真結(jié)果對(duì)比

表3 兩類蟻群算法仿真結(jié)果

4 實(shí)驗(yàn)

為了驗(yàn)證改進(jìn)的蟻群算法仿真結(jié)果的正確性以及體現(xiàn)改進(jìn)算法在實(shí)際應(yīng)用中的實(shí)用性和有效性，采用樹莓派(SpiderPi)六足機(jī)器人為研究對(duì)象[20]。為了有效地對(duì)作業(yè)環(huán)境進(jìn)行全局把控，本次實(shí)驗(yàn)采用人工拍攝的方式提前將機(jī)器人的行走環(huán)境采集，達(dá)到全局監(jiān)控的效果。樹莓派(SpiderPi)六足機(jī)器人，如圖8所示。

實(shí)驗(yàn)環(huán)境如圖9所示，實(shí)驗(yàn)場(chǎng)地為3 m×3 m的方形環(huán)境地圖。在實(shí)驗(yàn)環(huán)境內(nèi)，六足機(jī)器人處于起始位置，有各種障礙物分布，從起點(diǎn)爬行到終點(diǎn)。實(shí)驗(yàn)環(huán)境處理后為邊長(zhǎng)為15 cm、大小為20×20的柵格模型環(huán)境，如圖10所示。

設(shè)定六足機(jī)器人的起始位置為(0.5，19.5),終點(diǎn)位置為(19.5，0.5)。把改進(jìn)后的蟻群算法和傳統(tǒng)蟻群算法分別應(yīng)用在六足機(jī)器人的開發(fā)板中，讓機(jī)器人自主尋找路徑行走。在兩種蟻群算下行走的路徑軌跡如圖11、圖12所示。

圖8 SpiderPi六足機(jī)器人Fig.8 SpiderPi hexapod robot

圖9 實(shí)驗(yàn)環(huán)境Fig.9 Lab environment

由表4可知，通過(guò)將兩類算法燒進(jìn)六足機(jī)器人控制板中，改進(jìn)蟻群算法程序在路徑長(zhǎng)度、迭代次數(shù)和轉(zhuǎn)彎次數(shù)等方面性能優(yōu)于傳統(tǒng)蟻群算法，證明了改進(jìn)蟻群算法的優(yōu)化效果，提高了算法的魯棒性和尋優(yōu)能力。

圖10 處理后的環(huán)境Fig.10 Environment after treatment

圖11 改進(jìn)蟻群算法應(yīng)用Fig.11 Improved ant colony algorithm application

圖12 傳統(tǒng)蟻群算法應(yīng)用Fig.12 Traditional ant colony algorithm application

表4 兩類算法的對(duì)比

5 結(jié)論

針對(duì)傳統(tǒng)蟻群算法在路徑規(guī)劃中表現(xiàn)出的收斂速度慢、初始化信息素少、全局規(guī)劃能力弱等缺點(diǎn)，提出了一種改進(jìn)蟻群算法。得出如下結(jié)論。

(1)通過(guò)采用初始化信息素濃度的改變、啟發(fā)函數(shù)的改進(jìn)、蟻群回退策略的設(shè)置、引入優(yōu)化排序?qū)鹘y(tǒng)蟻群算法改進(jìn)，有利于提高蟻群對(duì)最優(yōu)路徑搜索效率，加快收斂速度。

(2)通過(guò)對(duì)改進(jìn)的蟻群算法仿真與分析得出了改進(jìn)的蟻群算法優(yōu)化的效果優(yōu)于傳統(tǒng)蟻群算法，尤其是在大尺寸地圖和障礙物多的情況下。

(3)通過(guò)對(duì)改進(jìn)的蟻群算法應(yīng)用在六足機(jī)器人中得到改進(jìn)蟻群算法在路徑長(zhǎng)度、迭代次數(shù)和轉(zhuǎn)彎點(diǎn)等方面性能優(yōu)于傳統(tǒng)蟻群算法，證明了改進(jìn)蟻群算法的優(yōu)化效果，提高了算法的魯棒性和尋優(yōu)能力。

所提的改進(jìn)蟻群算法在傳統(tǒng)蟻群算法的基礎(chǔ)上針對(duì)初始化信息素濃度、蟻群回退策略等方面進(jìn)行了優(yōu)化，但在動(dòng)態(tài)調(diào)整信息素?fù)]發(fā)因子方面沒(méi)有深入考慮，在未來(lái)的算法優(yōu)化中，可以引入更加智能化算法，使移動(dòng)機(jī)器人的路徑規(guī)劃更有效。