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

侯欣蕾+于蓮芝

摘要：針對(duì)蟻群算法進(jìn)行機(jī)器人路徑規(guī)劃時(shí)存在搜索空間大、效率低、容易陷入局部最優(yōu)解、易出現(xiàn)死鎖現(xiàn)象等問題，提出了一種改進(jìn)的蟻群算法。在蟻群算法基礎(chǔ)上，只對(duì)較優(yōu)螞蟻路徑進(jìn)行信息素濃度更新；針對(duì)U型障礙物，提出了螞蟻回退策略，以及一些仿真實(shí)驗(yàn)策略改進(jìn)。仿真結(jié)果表明：改進(jìn)后蟻群算法能快速搜索到最優(yōu)路徑，有效避免死鎖現(xiàn)象，與其它算法相比，具有良好的路徑尋優(yōu)能力與避障性能。

關(guān)鍵詞：移動(dòng)機(jī)器人；路徑規(guī)劃；改進(jìn)蟻群算法

DOIDOI：10.11907/rjdk.172054

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）012-0162-03

Abstract：When the ant colony algorithm（ACA） is used in mobile robot path planning， there are many problems such as large search space、inefficiency、easy to fail into locale optima、prove to deadlock and so on， an improved ant colony algorithm for robot path planning. At first， on the basic of ACA， phenomenon concentrations are updates only for the ant paths； Then the ant back off strategy is put forward for the U type obstacle； last some improvements in simulation experiments. Experiments proof： the improved ACA can fast search to optimal path and it can effectively avoided the deadlock phenomenon， compared with others algorithm， it has good route optimization ability and obstacle avoidance performance.

Key Words：mobile robot； path planning； an improved ant colony algorithm

0 引言

移動(dòng)機(jī)器人研究包括路徑規(guī)劃、導(dǎo)航定位、路徑跟蹤與運(yùn)動(dòng)控制等技術(shù)，其中路徑規(guī)劃是機(jī)器人研究領(lǐng)域基礎(chǔ)與核心。國(guó)內(nèi)外學(xué)者提出了柵格法、人工勢(shì)場(chǎng)法等路徑規(guī)劃方法[1-2]。柵格法一般用于機(jī)器人全局路徑規(guī)劃，但隨著機(jī)器人工作環(huán)境復(fù)雜程度不斷提高，柵格存儲(chǔ)空間需求也會(huì)增大，從而降低搜索效率。人工勢(shì)場(chǎng)法通常應(yīng)用于機(jī)器人局部路徑規(guī)劃，但也存在致命缺陷：局部極小點(diǎn)、目標(biāo)不可達(dá)。隨著神經(jīng)網(wǎng)絡(luò)、遺傳算法、模糊控制等智能算法的提出與發(fā)展，許多學(xué)者將人工智能算法應(yīng)用于路徑規(guī)劃，雖然可以提高求解速度，但存在算法復(fù)雜、搜索空間大等問題[3]。如何高效解決復(fù)雜環(huán)境下機(jī)器人路徑規(guī)劃問題依然是研究熱點(diǎn)。

受大自然中螞蟻覓食行為啟發(fā)，Marco Dorigo于1992年在博士論文中首次提出了蟻群算法。因?yàn)闄C(jī)器人路徑規(guī)劃類似螞蟻覓食行為，所以可使用蟻群算法進(jìn)行機(jī)器人路徑規(guī)劃。使用蟻群算法進(jìn)行路徑規(guī)劃，存在搜索時(shí)間長(zhǎng)、局部最優(yōu)解與死鎖現(xiàn)象[4]。因此，本文主要研究改進(jìn)蟻群算法在機(jī)器人路徑規(guī)劃中的應(yīng)用。

1 環(huán)境建模

機(jī)器人工作環(huán)境通過分形算法可以等效為二維平面的有限區(qū)域AS。鑒于AS可以為任意形狀，因此，在機(jī)器人環(huán)境建模時(shí)，需要在AS邊界向外補(bǔ)充障礙物柵格，使機(jī)器人工作環(huán)境補(bǔ)充為正方形或長(zhǎng)方形[5]。使用柵格法劃分機(jī)器人工作環(huán)境AS，劃分柵格分為3種：白色柵格、黑色柵格、混合柵格。如圖1所示，白色柵格表示自由柵格，黑色柵格與混合柵格表示障礙物柵格，機(jī)器人可在自由柵格之間移動(dòng)，且障礙物位置與大小均不發(fā)生改變。在建立的柵格空間上，按照從左到右，從上到下順序，依次為柵格標(biāo)號(hào)，記為數(shù)字1，2，3，…，n，每一個(gè)數(shù)字都代表一個(gè)柵格；以柵格空間左下方為坐標(biāo)原點(diǎn)，從左到右為X軸正方向，從下到上為Y軸正方向，柵格長(zhǎng)度為單位長(zhǎng)度，建立平面直角坐標(biāo)系XOY。柵格序號(hào)與柵格坐標(biāo)對(duì)應(yīng)關(guān)系如下：

機(jī)器人路徑規(guī)劃過程中，為避免機(jī)器人與障礙物發(fā)生碰撞，對(duì)障礙物邊界進(jìn)行膨化處理，向外擴(kuò)展機(jī)器人最大長(zhǎng)度1/2，則機(jī)器人可以等效為質(zhì)點(diǎn)，其大小與尺寸忽略不計(jì)。上述方式劃分機(jī)器人工作空間能夠使環(huán)境模型與真實(shí)情況相符，使機(jī)器人路徑規(guī)劃暢通無阻。機(jī)器人路徑規(guī)劃起始位置與終止位置為任意柵格且都屬于AS（不在同一個(gè)柵格內(nèi)且不是障礙柵格）。

2.1.3 迭代循環(huán)

完成每輪信息素更新后，將全部螞蟻放到機(jī)器人路徑規(guī)劃起始點(diǎn)，重新開始新一輪路徑規(guī)劃，N次迭代完成后，從中選出一條最優(yōu)路徑。

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

對(duì)機(jī)器人進(jìn)行路徑規(guī)劃時(shí)，使用蟻群算法可規(guī)劃出一條從起始點(diǎn)到終止點(diǎn)安全、無碰撞的最優(yōu)路徑，但也存在搜索時(shí)間過長(zhǎng)、效率低、易出現(xiàn)死鎖等現(xiàn)象[4，8]。針對(duì)上述問題，本文對(duì)蟻群算法作出以下改進(jìn)，使機(jī)器人能夠在更短時(shí)間內(nèi)搜索出更短更平滑的路徑。

2.2.1 螞蟻回退策略

使用蟻群算法進(jìn)行機(jī)器人路徑規(guī)劃過程中，螞蟻k遇到U型障礙物時(shí)，容易陷入死鎖現(xiàn)象，導(dǎo)致蟻群算法停滯。一旦出現(xiàn)此類情況，假設(shè)此時(shí)定義螞蟻k死亡，就會(huì)影響到算法魯棒性與適應(yīng)度。因此，本文采用螞蟻回退策略來杜絕這類現(xiàn)象發(fā)生。螞蟻移動(dòng)過程中遇到U型障礙物時(shí)，首先判斷螞蟻是否落入陷阱，如果落入陷阱，則螞蟻回退到上一節(jié)點(diǎn)，同時(shí)將螞蟻所在節(jié)點(diǎn)從禁忌表中移除，按照狀態(tài)轉(zhuǎn)移概率公式繼續(xù)選擇下一轉(zhuǎn)移節(jié)點(diǎn)，然后判斷是否陷入陷阱，直至螞蟻回退到逃出陷阱為止。endprint

在蟻群算法中加入螞蟻回退策略可保證所有螞蟻都能順利完成路徑搜索，即使螞蟻遇到U型障礙物也不會(huì)死亡，進(jìn)一步保障了算法魯棒性與適應(yīng)度，提升算法性能。

2.2.2 較優(yōu)螞蟻路徑信息素更新

假設(shè)在每輪路徑搜索結(jié)束后，只對(duì)較優(yōu)螞蟻路徑進(jìn)行信息素更新，而其余路徑信息素則會(huì)因信息素?fù)]發(fā)逐漸降低，將增大路徑上信息素差異，使螞蟻在搜索路徑過程中更傾向于信息素濃度較大路徑，螞蟻能夠較快集中在較優(yōu)路徑鄰域，縮短算法求解時(shí)間，提高算法效率。

使用蟻群算法進(jìn)行路徑規(guī)劃時(shí)，由于路徑規(guī)劃起始位置與終止位置已知，且螞蟻同時(shí)從起始位置出發(fā)進(jìn)行路徑搜索，所以能夠在較短時(shí)間內(nèi)能找到終止位置的螞蟻就是較優(yōu)螞蟻，反之則為較差螞蟻。因此，在算法實(shí)現(xiàn)中，須找到前面幾只螞蟻的路徑，對(duì)其進(jìn)行信息素更新，加大較優(yōu)路徑與較差路徑信息素濃度差異，使螞蟻在選擇路徑時(shí)更加傾向于較優(yōu)路徑，大大地降低路徑搜索時(shí)間，提高機(jī)器人路徑規(guī)劃搜索效率。

2.2.3 仿真策略改進(jìn)

使用改進(jìn)后蟻群算法進(jìn)行機(jī)器人路徑規(guī)劃，采取以下策略：

（1）限制螞蟻下一步柵格選擇范圍。路徑搜索過程中，螞蟻移動(dòng)到當(dāng)前柵格時(shí)，下一步可選擇柵格只能是與當(dāng)前柵格相鄰且沒有訪問過的無障礙物柵格。

（2）使用“輪盤賭”方法選擇下一柵格。通過“輪盤賭”方法結(jié)合狀態(tài)轉(zhuǎn)移概率公式，增大螞蟻選擇隨機(jī)性，提高螞蟻全局搜索能力，可有效防止算法過早收斂。

（3）校正搜索成功的螞蟻路徑。螞蟻在柵格之間移動(dòng)可能會(huì)走彎曲路徑，通過對(duì)彎曲路徑的處理，可以進(jìn)一步縮短搜索路徑總長(zhǎng)度，使搜索路徑達(dá)到最優(yōu)。

2.3 改進(jìn)后蟻群算法流程

改進(jìn)后蟻群算法流程如圖2所示。

3 實(shí)驗(yàn)結(jié)果

將機(jī)器人工作空間劃分為20×20柵格，起始位置為（1，1），終止位置為（20，20）。算法參數(shù)設(shè)置：螞蟻數(shù)目m=50；迭代次數(shù)N=100；信息素?fù)]發(fā)系數(shù)=0.3。

本文使用改進(jìn)蟻群算法進(jìn)行路徑規(guī)劃，搜索得到最優(yōu)路徑如圖3所示，最短路徑收斂速度如圖4所示。

本文比較了A*算法、蟻群算法、改進(jìn)蟻群算法性能，結(jié)果如表1所示。

由表1可知，改進(jìn)蟻群算法可快速搜索到最優(yōu)路徑，有效避免死鎖現(xiàn)象，具有良好路徑尋優(yōu)能力與避障性能。

4 結(jié)語

本文針對(duì)機(jī)器人路徑規(guī)劃中存在問題，改進(jìn)了蟻群算法，只對(duì)路徑較優(yōu)螞蟻進(jìn)行信息素更新，大量減少信息素更新計(jì)算量，在一定程度上提高算法收斂速度；校正搜索成功的螞蟻路徑，拉直螞蟻在相鄰柵格之間多走的彎曲路徑，縮短搜索路徑長(zhǎng)度；處理U型障礙物，提出了螞蟻回退策略，避免陷入局部最優(yōu)解與死鎖現(xiàn)象。大量仿真實(shí)驗(yàn)證明，改進(jìn)后蟻群算法能夠快速搜索到最優(yōu)路徑，有效避免死鎖現(xiàn)象，與其它算法相比，具有良好路徑尋優(yōu)能力與避障性能。

參考文獻(xiàn)：

[1] 歐陽鑫玉，楊曙光.基于勢(shì)場(chǎng)柵格法的移動(dòng)機(jī)器人避障路徑規(guī)劃[J].控制工程，2014（1）：134-137.

[2] 溫素芳，郭光耀.基于改進(jìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015（10）：226-230.

[3] 朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010（7）：4-10.

[4] 周明秀，程科，汪正霞.動(dòng)態(tài)路徑規(guī)劃中的改進(jìn)蟻群算法[J].計(jì)算機(jī)科學(xué)，2013（1）：320-322.

[5] 羅榮貴，屠大維.柵格法視覺傳感集成及機(jī)器人實(shí)時(shí)避障[J].計(jì)算機(jī)工程與應(yīng)用，2011（24）：237-239.

[6] 萬曉鳳，胡偉，方武義，等.基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃研究[J].計(jì)算機(jī)工程與應(yīng)用，2014（18）：63-66.

[7] 康冰，王曦輝，劉富.基于改進(jìn)蟻群算法的搜索機(jī)器人路徑規(guī)劃[J].吉林大學(xué)學(xué)報(bào)，2014（4）：167-173.

[8] XIONG W， WEI P.A kind of ant colony algorithm for function optimization[C].Proceeding of the 1st International Conference on Machine Learning and Cybernetics，2002：552-555.

（責(zé)任編輯：何 麗）endprint