基于改進(jìn)多步長(zhǎng)蟻群算法的機(jī)器人路徑規(guī)劃

王明輝

(鹽城工學(xué)院信息工程學(xué)院，江蘇鹽城 224051)

0 前言

路徑規(guī)劃一直是移動(dòng)機(jī)器人領(lǐng)域的關(guān)鍵技術(shù)之一，指的是找出一條在特定環(huán)境中連接起點(diǎn)與終點(diǎn)的移動(dòng)機(jī)器人最佳路徑。路徑規(guī)劃問(wèn)題上具有代表性的傳統(tǒng)算法有A法、RRT法、人工勢(shì)場(chǎng)法、神經(jīng)網(wǎng)絡(luò)算法等。除此之外，還有大量仿生算法例如粒子群算法、遺傳算法、蟻群算法等。其中，蟻群算法的應(yīng)用最廣泛，主要是因?yàn)樗哂姓答伈呗浴?yōu)效果好等優(yōu)點(diǎn)。

蟻群算法最早是由DORIGO根據(jù)螞蟻搜尋食物行為設(shè)計(jì)提出的。蟻群算法具有優(yōu)勢(shì)，但也存在穩(wěn)定性差、易局部收斂等缺陷。因此國(guó)內(nèi)外學(xué)者針對(duì)蟻群算法的缺陷，提出了許多不同的改進(jìn)方案。文獻(xiàn)[9]針對(duì)傳統(tǒng)蟻群算法存在收斂性差、魯棒性不足等缺點(diǎn)，采用了一種多步長(zhǎng)蟻群算法，該模型可以根據(jù)周圍情況自由選擇步長(zhǎng)，并尋找出一條最短路徑，基于柵格環(huán)境選擇機(jī)器人的步長(zhǎng)，改進(jìn)信息素更新公式，同時(shí)對(duì)信息素加以限制，防止算法過(guò)早收斂。文獻(xiàn)[10]為改進(jìn)基本蟻群算法魯棒性不足的問(wèn)題，設(shè)計(jì)了一種自適應(yīng)蟻群算法，能夠依據(jù)算法中解的分布情況，動(dòng)態(tài)地更新調(diào)節(jié)信息素，同時(shí)在多步長(zhǎng)選擇模型中選取最佳步長(zhǎng)，提升算法全局搜索性能，仿真表明改進(jìn)的蟻群算法相可以更加準(zhǔn)確且迅速地尋找出最短路徑。

結(jié)合以上的研究成果及問(wèn)題，本文作者基于移動(dòng)機(jī)器人實(shí)際工作情景，提出一種改進(jìn)的多步長(zhǎng)蟻群算法。將移動(dòng)機(jī)器人運(yùn)行環(huán)境轉(zhuǎn)化為柵格環(huán)境，設(shè)計(jì)一種多步長(zhǎng)的選擇模型，改善基本蟻群算法中單步移動(dòng)模式的不足，從而縮短路徑距離。同時(shí)，針對(duì)移動(dòng)機(jī)器人實(shí)際運(yùn)行時(shí)可能出現(xiàn)坡度大的工況，在啟發(fā)函數(shù)中引入高度因素。另外，改進(jìn)算法中信息素更新模型，采用動(dòng)態(tài)揮發(fā)系數(shù)，以提升算法尋優(yōu)效率。

1 移動(dòng)機(jī)器人環(huán)境模型

移動(dòng)機(jī)器人路徑規(guī)劃中常見(jiàn)的建模方法主要有柵格地圖、MAKLINK圖、拓?fù)鋱D等。其中，柵格地圖維護(hù)簡(jiǎn)易且構(gòu)建簡(jiǎn)單，因此本文作者將柵格圖作為移動(dòng)機(jī)器人建模環(huán)境。柵格的粒徑由移動(dòng)機(jī)器人的規(guī)格決定，其大小必須可以容納移動(dòng)機(jī)器人自由運(yùn)行且保持柵格邊界與移動(dòng)機(jī)器人有一定的安全距離。在柵格地圖中黑色代表不可行空間，白色則代表自由通行區(qū)域。為保障移動(dòng)機(jī)器人的工作安全，規(guī)定移動(dòng)機(jī)器人工作時(shí)不能沿著障礙物邊緣及頂點(diǎn)行走。另外，如果障礙物不足一個(gè)柵格時(shí)，將它膨脹為一個(gè)柵格。

機(jī)器人柵格環(huán)境模型如圖1所示。假設(shè)柵格圖中柵格號(hào)按從下至上、從左到右依次遞增。柵格地圖規(guī)格為行列，柵格號(hào)為，柵格粒徑為1，則柵格中心坐標(biāo)可表示為

圖1 柵格模型

(1)

式中：、分別表示中心點(diǎn)的橫、縱坐標(biāo)；mod表示取余操作；int表示求整。

如果當(dāng)前位置坐標(biāo)為(,)，則柵格中障礙物及可行區(qū)域取值為

(2)

2 基本蟻群算法

蟻群算法是為模擬蟻群尋找食物的行動(dòng)模式而設(shè)計(jì)的算法。蟻群在搜尋食物時(shí)會(huì)沿途分泌不等的信息素，而信息素的多少跟路徑距離有關(guān)。其他螞蟻則會(huì)根據(jù)路徑上信息素的濃度作出相應(yīng)決策，最終蟻群將逐步聚攏在最短路徑上。

在第次迭代中，螞蟻由節(jié)點(diǎn)轉(zhuǎn)移至節(jié)點(diǎn)的概率為

(3)

式中:表示螞蟻標(biāo)號(hào);、分別表示當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)；表示信息素濃度；表示啟發(fā)函數(shù)；、分別表示信息素和啟發(fā)式期望值；表示螞蟻可轉(zhuǎn)移節(jié)點(diǎn)的集合。其中：

,()=1(,)

(4)

式中：(,)表示節(jié)點(diǎn)與中心的距離。

在算法迭代過(guò)程中，信息素更新公式如下：

(5)

(6)

式中:為信息素?fù)]發(fā)因子;為信息素強(qiáng)度；為螞蟻?zhàn)哌^(guò)的總路程；為螞蟻總數(shù)；為螞蟻?zhàn)哌^(guò)節(jié)點(diǎn)的集合。

3 算法改進(jìn)方向

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

基本蟻群算法中，啟發(fā)函數(shù)只和路徑長(zhǎng)度有關(guān)，只能保證距離因素，無(wú)法適應(yīng)真實(shí)工作環(huán)境中高度不定的情形。因此對(duì)啟發(fā)函數(shù)作以下改進(jìn)：

(,)=1(,)+(,)

(7)

式中：表示高度因素，可表示為

(8)

式中:表示柵格高度矩陣;、指高度調(diào)節(jié)常數(shù)；max,、min,分別是相鄰柵格中與當(dāng)前柵格的最大高度差和最小高度差;0.001保證分式有意義。

3.2 改進(jìn)信息素更新機(jī)制

3.2.1 信息素增量

為更加真實(shí)地模擬機(jī)器人可能遇到的具有高度起伏的工作環(huán)境，加入高度啟發(fā)因素，因此對(duì)信息素增量公式進(jìn)行如下修正：

(9)

()=()+()

(10)

式中:()為路徑的綜合指標(biāo);()為路徑長(zhǎng)度；()為高度均方差。

3.2.2 揮發(fā)系數(shù)

基本蟻群揮發(fā)系數(shù)從始至終都是維持不變的，無(wú)法適應(yīng)實(shí)際環(huán)境。因此,為改進(jìn)算法的全局性，提出一種自適應(yīng)策略，在搜索前期增大，加快收斂，而在后期減小，增強(qiáng)算法全局性。具體公式如下：

(11)

式中:、都為常數(shù)；、分別為揮發(fā)系數(shù)最大、最小值。

3.3 多步長(zhǎng)選擇策略

基本蟻群算法中采用的是單步移動(dòng)模式，且轉(zhuǎn)移的方向只能為8個(gè)方向，如圖2所示。在傳統(tǒng)的單步長(zhǎng)移動(dòng)模式下路徑距離更長(zhǎng)，且轉(zhuǎn)折次數(shù)也更多。因此,本文作者采用多步長(zhǎng)移動(dòng)機(jī)制，此時(shí)螞蟻在移動(dòng)時(shí)不再局限于單步長(zhǎng)且方向可以任意選擇，縮短了路徑。具體方案：先利用改進(jìn)的蟻群算法搜尋出單步長(zhǎng)模式下最佳路徑，如圖3中的虛線所示，然后再次對(duì)此路徑進(jìn)行規(guī)劃，即將當(dāng)前柵格與下一柵格直接相連，判斷路徑上是否有障礙物，若沒(méi)有則繼續(xù)尋找下一個(gè)柵格，直至碰撞障礙區(qū)域。此時(shí)形成的柵格節(jié)點(diǎn)連線為最優(yōu)路徑，如圖3中實(shí)線所示。可知，多步長(zhǎng)選擇策略模式下路徑更短且轉(zhuǎn)折次數(shù)更少。

圖2 轉(zhuǎn)移方向 圖3 2種步長(zhǎng)模式下最佳路徑對(duì)比

3.4 改進(jìn)多步長(zhǎng)蟻群算法流程

改進(jìn)多步長(zhǎng)蟻群算法相應(yīng)的執(zhí)行流程如下：

(1)建立柵格地圖環(huán)境，設(shè)置算法參數(shù)初始值；

(2)設(shè)置起始及目標(biāo)位置，初始化信息素；

(3)采用多步長(zhǎng)移動(dòng)策略，根據(jù)公式(3)計(jì)算轉(zhuǎn)移概率，得到下一節(jié)點(diǎn)坐標(biāo)；

(4)此輪迭代結(jié)束后，根據(jù)公式(9)—(11)更新算法中的信息素；

(5)判斷此次迭代是否結(jié)束，如果結(jié)束繼續(xù)執(zhí)行下一步驟，反之則返回步驟(3);

(6)判斷算法是否達(dá)到迭代次數(shù)最大值，若是則輸出最優(yōu)路徑，否則繼續(xù)下輪迭代。

4 實(shí)例仿真及分析

4.1 15×15環(huán)境仿真

基于MATLAB R2016b平臺(tái)進(jìn)行仿真實(shí)驗(yàn)。仿真時(shí)算法主要參數(shù)設(shè)置：最大迭代數(shù)為80，常數(shù)=5、=1，期望因子、分別為1和8。機(jī)器人的柵格環(huán)境規(guī)格為15×15，機(jī)器人起始點(diǎn)設(shè)為(0.5,0.5)、終點(diǎn)為(14.5,14.5)?；鞠伻核惴案倪M(jìn)多步長(zhǎng)蟻群算法的移動(dòng)機(jī)器人仿真路徑分別如圖4和圖5所示，圖中灰色越深表示環(huán)境高度越高。各指標(biāo)對(duì)比結(jié)果如表1所示。

圖4 基本蟻群算法仿真結(jié)果(15×15柵格)

圖5 改進(jìn)多步長(zhǎng)蟻群算法仿真結(jié)果(15×15柵格)

表1 2種算法結(jié)果對(duì)比(15×15柵格)

由圖4和圖5可看出：在有坡度的環(huán)境中，基本蟻群算法路徑長(zhǎng)、轉(zhuǎn)折次數(shù)多且無(wú)法避開高度高的區(qū)域，使得移動(dòng)機(jī)器人自身消耗過(guò)大，不利于移動(dòng)機(jī)器人實(shí)際工作；而改進(jìn)后的算法采用了多步長(zhǎng)策略，因此路徑轉(zhuǎn)折次數(shù)少且距離短，另外因?yàn)樵谀繕?biāo)函數(shù)中引入了高度因素，能夠繞開高區(qū)域，規(guī)劃出的路徑也更平坦。由表1可知：改進(jìn)多步長(zhǎng)蟻群算法的收斂速度遠(yuǎn)高于基本蟻群算法，同時(shí)容易看出其各項(xiàng)指標(biāo)均優(yōu)于基本蟻群算法，因此在實(shí)際環(huán)境中更有利于移動(dòng)機(jī)器人高效、安全地完成相應(yīng)工作。

4.2 20×20環(huán)境仿真

為進(jìn)一步驗(yàn)證文中算法的性能，在規(guī)格為20×20的柵格圖中與文獻(xiàn)[10]的改進(jìn)方法進(jìn)行仿真對(duì)比。各個(gè)參數(shù)設(shè)置與15×15的環(huán)境保持一致?；谖闹兴惴ǖ囊苿?dòng)機(jī)器人仿真結(jié)果如圖6所示，各指標(biāo)數(shù)據(jù)如表2所示。

圖6 改進(jìn)多步長(zhǎng)蟻群算法仿真結(jié)果(20×20柵格)

表2 2種算法結(jié)果對(duì)比(20×20柵格)

由表2可知:在更加復(fù)雜的環(huán)境中，采用文中算法的移動(dòng)機(jī)器人搜索出的路徑質(zhì)量依舊較高，無(wú)論是路徑長(zhǎng)度、轉(zhuǎn)折次數(shù)還是最大爬坡高度都優(yōu)于文獻(xiàn)[10]算法，且收斂效率更高，體現(xiàn)出了更強(qiáng)的環(huán)境適應(yīng)能力。

5 結(jié)論

采用蟻群算法規(guī)劃移動(dòng)機(jī)器人路徑時(shí)存在許多缺陷，因此本文作者設(shè)計(jì)了一種改進(jìn)的多步長(zhǎng)蟻群算法。一方面利用柵格地圖對(duì)機(jī)器人工作環(huán)境柵格化，同時(shí)采用一種多步長(zhǎng)的選擇模型，使得移動(dòng)機(jī)器人可根據(jù)環(huán)境自主選擇移動(dòng)方向，從而縮短路徑、減少轉(zhuǎn)折次數(shù)；另一方面，針對(duì)移動(dòng)機(jī)器人實(shí)際運(yùn)行時(shí)可能遭遇坡度變化大的環(huán)境，在啟發(fā)函數(shù)中引入高度因素。同時(shí)，改進(jìn)算法中信息素更新策略，采用動(dòng)態(tài)揮發(fā)系數(shù)，以提升算法尋優(yōu)效率。結(jié)果表明：所提算法具有更強(qiáng)的環(huán)境適應(yīng)能力，效率更高，對(duì)移動(dòng)機(jī)器人真實(shí)的運(yùn)行有積極意義。