基于改進蟻群算法的移動機器人路徑規(guī)劃研究

王志中

（重慶建筑工程職業(yè)學(xué)院，重慶 400072）

1 引言

隨著機器人人工智能的不斷提高，機器人能夠更加自覺、高效地為人類服務(wù)。機器人作為多個學(xué)科領(lǐng)域的集合體，其可以為代替人類勞動[1]，將人類從反復(fù)的體力勞動中解放出來，如室內(nèi)清潔機器人、機械臂；也可以完成人類無法進行或難以進行的工作，如擦窗機器人、月球車等。機器人路徑規(guī)劃問題是機器人導(dǎo)航研究的重點，是對機器人導(dǎo)航需要解決的首要問題[2]。因此尋求一條路徑最短、收斂最快、能夠避開障礙的最優(yōu)路徑，對解決機器人導(dǎo)航問題具有重要意義。按照對機器人工作環(huán)境信息的掌握程度，機器人路徑規(guī)劃可以分為全局路徑規(guī)劃和局部路徑規(guī)劃[3]。全局路徑規(guī)劃是機器人工作環(huán)境已知，當(dāng)前的全局路徑規(guī)劃方法有柵格解耦法[4]、拓撲圖法[5]、可視圖[6]等。局部路徑規(guī)劃是指機器人工作環(huán)境未知，是一種邊探測工作環(huán)境邊進行路徑規(guī)劃的問題，局部路徑規(guī)劃方法有人工勢場法[7]、模糊邏輯算法[7]、遺傳算法[8]等。這些方法在全局或局部路徑規(guī)劃中都取得了很好的效果，當(dāng)前使用智能算法的群智能特性尋找機器人避障的最優(yōu)路徑稱為機器人研究的熱點問題。介紹了柵格環(huán)境建模方法，將工作環(huán)境轉(zhuǎn)化為機器人可以識別的數(shù)學(xué)模型，分析了蟻群算法原理，對路徑搜索策略和路徑選擇策略提出了改進方法，并提出了信息素揮發(fā)系數(shù)的自適應(yīng)調(diào)整方法，改進算法與傳統(tǒng)算法相比，具有更快的收斂速度、更集中于最優(yōu)路徑、更優(yōu)的最優(yōu)解。

2 柵格法原理

研究的是全局路徑規(guī)劃問題，機器人路徑規(guī)劃問題可以分為兩部分，一是工作環(huán)境建模，二是路徑規(guī)劃方法。環(huán)境建模就是將機器人工作區(qū)域轉(zhuǎn)化為機器人可以識別的數(shù)學(xué)模型，在全局路徑規(guī)劃中最常用的環(huán)境建模方法為柵格法。柵格法就是在機器人工作環(huán)境上建立二維直角坐標(biāo)系，而后按照障礙物和機器人尺寸確定柵格大小，以固定尺寸的柵格分割工作環(huán)境，此時根據(jù)柵格區(qū)域的障礙物情況，可以將柵格分為三類，一是障礙物柵格，二是可行駛區(qū)域柵格，三是半障礙物柵格，為了使機器人能夠識別工作環(huán)境，將第一類和第三類柵格全部歸為障礙物柵格，對此類柵格賦值為1，對可行駛柵格賦值為0，這樣機器人就可以根據(jù)柵格的屬性值區(qū)分障礙物和可行駛區(qū)域。所有柵格的邊長定義為1。柵格的標(biāo)識具有兩種方法，一是使用直角坐標(biāo)法（x，y），二是序號法，按照X、Y軸正方向進行編號，兩種方法可以相互轉(zhuǎn)換。選用相對簡單的序號法對柵格進行標(biāo)識，如圖1所示。圖中黑色部分為障礙物柵格，白色部分為可行駛柵格。

3 蟻群算法原理

3.1 旅行商問題

為了方便對蟻群算法進行分析，首先給出旅行商問題（也叫TSP問題）。旅行商問題是指給定m個城市及任意兩城市之間的距離，要求找到一條經(jīng)過任何城市一次、且只經(jīng)過一次的最短路徑。將m個城市分別表示為p1，p2，…，pm，城市pi和pi+1之間的路徑長度記為d（pi，pi+1），則旅行商問題的數(shù)學(xué)模型可以描述為：

3.2 蟻群算法分析

以旅行商問題為背景，對蟻群算法進行分析。假設(shè)在初始時刻，任意兩城市i、j之間的信息素相同，記為τij（0），且兩城市之間距離記為dij。將n只螞蟻隨機放置在起點城市，螞蟻k下一步要轉(zhuǎn)移的城市按照隨機比例規(guī)則[9]進行選擇，概率公式為：

式中：τij（t）—在t時刻，從i城市到j(luò)城市路徑上的信息素濃度；α—信息啟發(fā)因子；ηij=1/dij—兩城市之間距離對螞蟻選擇的影響；β—期望啟發(fā)因子；allowedk—螞蟻k下一步允許到達的城市集合，在此集合中包含螞蟻k尚未到達的所有城市的集合，這種設(shè)置是為了保證所有城市均經(jīng)歷，且只經(jīng)歷一次。α值的大小代表信息素濃度對螞蟻運動的影響大小，其值越大，表明螞蟻越傾向于走其它螞蟻走過的路徑；β值的大小代表能見度對螞蟻運動的影響大小，其值越大，路徑的選擇越接近于貪心規(guī)則[10]。

按照上述規(guī)則，當(dāng)經(jīng)過m個時刻后，n只螞蟻均完成一次全城市遍歷，計算每只螞蟻的路徑長度，并保存所有路徑中的最短路徑，然后進行信息素更新。信息素的更新包括兩部分，一是各路徑上信息素的揮發(fā)，二是螞蟻在所經(jīng)過路徑留下的信息素。記Δτij（t）為所有螞蟻在城市i、j路徑上單位長度軌跡的信息素，則所有螞蟻完成一次遍歷后的信息素更新公式為：

式中：ρ—信息素的揮發(fā)系數(shù)；Δτkij（t）—螞蟻 k 在城市 i、j路徑上留下的信息素濃度；Q—螞蟻攜帶的信息素強度；Lk—螞蟻k完成城市遍歷的路徑長度。

由式（5）可以看出，螞蟻k在城市i、j路徑上留下的信息素濃度與其路徑的優(yōu)化層度有關(guān)，路徑越短，則留下的信息素濃度越高，否則信息素濃度就低。

4 改進的蟻群算法

4.1 路徑搜索策略的改進

算法的起始時刻各路徑上的信息素量均為0，信息素濃度的差異要在一段時間后才能表現(xiàn)出來，因此在蟻群算法起始的一段時間內(nèi)，信息素對蟻群的引導(dǎo)作用不存在，使得算法路徑搜索時間過長，為了提高可行解的搜索效率，提出了螞蟻相遇策略、螞蟻回退策略。螞蟻相遇策略。在傳統(tǒng)蟻群算法中，n只螞蟻隨機放置在起點，而后各自自由地進行路徑搜索，算法搜索效率低、搜索速度慢。為了提高蟻群算法的搜索效率，將n只螞蟻平均分成兩組，記為A組和B組，指定A組從起始點到目標(biāo)點進行路徑搜索，B組從目標(biāo)點到起始點進行路徑搜索，A組螞蟻相當(dāng)于尋找食物過程，B組螞蟻相當(dāng)于將食物運回蟻巢過程。對螞蟻k賦屬性值directionk，directionk=0表示螞蟻屬于A組；directionk=1表示螞蟻屬于B組，directionk值在搜索到最優(yōu)路徑后進行更新。當(dāng)A組和B組的螞蟻相遇時，將兩組螞蟻的路徑連線就得到了一條可行路徑，尤其對于復(fù)雜工作環(huán)境，此方法可以極大地提高搜索效率。螞蟻k1、k2的相遇定義為當(dāng)滿足d（p1，p2）≤ 2 時，兩只螞蟻相遇，此時的路徑長度為：L=L（k1）+L（k2） （6）

式中：L（k1）、L（k2）—相遇的螞蟻中兩方向各自的最短路徑。

圖1 柵格標(biāo)識法Fig.1 Marking Method of Grid

圖2 U形陷阱示意圖Fig.2 U-shaped Trap

螞蟻回退策略。記螞蟻k在ti時刻的可行節(jié)點集合為gatheri，隨著算法的進行，一些螞蟻可能會進入U形陷阱，使自身的可行柵格集合為空集，此時螞蟻陷入死鎖，如圖2所示。此類現(xiàn)象嚴(yán)重影響算法的適應(yīng)度和魯棒性。

4.2 路徑選擇策略的改進

螞蟻對路徑的選擇與路徑上信息素的濃度有很大關(guān)系，路徑的選擇與信息素的釋放是一種正反饋機制，也就是說路徑上的信息素濃度越高則此路徑越容易被選擇，而此路徑越容易被選擇則殘留在此路徑上的信息素也就越多。這種正反饋機制是蟻群算法群智能性的核心，但是同時從算法的開始階段就限制了路徑選擇的多樣性。為了使蟻群在算法的初始階段能夠?qū)尚薪饪臻g進行大范圍搜索，增加解的多樣性，對螞蟻的信息素感應(yīng)設(shè)定閾值h0，當(dāng)信息素濃度h＜h0時，螞蟻感應(yīng)不到信息素，此時信息素對螞蟻的導(dǎo)引作用也就不存在，此時蟻群可以對可行路徑進行大范圍搜索；當(dāng)算法進行到一定階段，路徑上信息素積累到一定程度即h≥h0時，信息素對算法的導(dǎo)引作用開始體現(xiàn)。也就是說，此時螞蟻從i城市到j(luò)城市選擇概率公式為：

4.3 揮發(fā)系數(shù)自適應(yīng)調(diào)整

信息素揮發(fā)系數(shù)ρ對算法性能影響很大，若信息素揮發(fā)系數(shù)過大，則蟻群對螞蟻引導(dǎo)作用過小，蟻群的群體智能性無法顯示出來；若信息素揮發(fā)系數(shù)過小，此時蟻群對螞蟻的引導(dǎo)作用過強，使蟻群的搜索能力降低，可行解的搜索范圍減小。因此提出了自適應(yīng)的揮發(fā)系數(shù)調(diào)整方法，在算法的前期，揮發(fā)系數(shù)較低，減小螞蟻之間的互相引導(dǎo)，增加螞蟻的搜索范圍，提高搜索效率；在算法后期，揮發(fā)系數(shù)較大，增加蟻群的群智能性，使算法快速收斂到最優(yōu)解?；谝陨戏治?，提出的揮發(fā)系數(shù)自適應(yīng)調(diào)整方案為：

式中：ρmin—揮發(fā)系數(shù)ρ可以取到的最小值，揮發(fā)系數(shù)ρ初值為1。由式（8）可以看出，隨著算法的進行，揮發(fā)系數(shù)不斷減小，直至達到最小值。

4.4 基于改進遺傳算法的機器人路徑規(guī)劃步驟

通過以上分析，基于改進遺傳算法的機器人路徑規(guī)劃步驟具體為：Step1：參數(shù)初始化。需要初始化的參數(shù)包括種群個數(shù)n、最大迭代次數(shù)Kmax、信息啟發(fā)因子α、期望啟發(fā)因子β等、信息素感應(yīng)閾值h0；Step2：將n/2只螞蟻分別放置在起點和終點進行路徑規(guī)劃，按照式（8）對揮發(fā)系數(shù)自適應(yīng)調(diào)整，按照式（7）進行路徑選擇，直至兩組蟻群相遇；Step3：按照式（6）選擇最短路徑，并記錄最優(yōu)路徑，按照式（3）、式（4）、式（5）進行信息素更新；Step4：判斷算法循環(huán)次數(shù)是否達到上限，若是則輸出最優(yōu)路徑，否則將螞蟻重新分組后返回Step2。

5 仿真實驗

機器人的工作環(huán)境建模為（20×20）的柵格，傳統(tǒng)蟻群算法和改進蟻群算法的蟻群規(guī)模均設(shè)置為30，算法的最大迭代次數(shù)設(shè)置為300。傳統(tǒng)算法和改進算法最小路徑長度隨算法迭代次數(shù)的變化曲線，如圖3所示。由圖3可以得出兩點結(jié)論：（1）改進算法相比于傳統(tǒng)算法的收斂速度快很多，這是因為改進算法提出了信息素揮發(fā)因子，使算法在后期能夠快速收斂至最優(yōu)解；再者對式（5）進行了重新定義，保留了種群對最優(yōu)路徑的記憶能力，促進了算法的快速收斂；再就是使用了螞蟻相遇策略，蟻群能夠相向同時進行路徑搜索，提高了搜索效率。（2）改進算法最終的收斂值明顯優(yōu)于傳統(tǒng)算法，這是因為改進算法提出了自適應(yīng)信息素揮發(fā)因子和設(shè)置了信息素感應(yīng)閾值，使算法在前期能夠大范圍地對解空間進行搜索，使得改進算法搜索到的最優(yōu)解優(yōu)于傳統(tǒng)算法。

圖3 最短路徑長度變化曲線Fig.3 Length Changing Curve of Shortest Path

如圖4所示，一次路徑規(guī)劃中全部螞蟻的規(guī)劃結(jié)果，從圖中可以看出，改進算法中螞蟻的規(guī)劃路徑非常集中，集中在最優(yōu)路徑附近，而傳統(tǒng)算法的路徑相對分散，沒有很好的集中在最優(yōu)路徑附近。這說明改進算法的蟻群在進行路徑搜索時，目標(biāo)比較明確，減少了算法在路徑搜索時的盲目性。這是因為對式（5）進行重新定義，保留了蟻群對最優(yōu)路徑的“記憶”能力，使蟻群在路徑搜索時目標(biāo)明確，規(guī)劃出的路徑集中在最優(yōu)路徑附近。

圖4 所有螞蟻的規(guī)劃結(jié)果Fig.4 Planning Path of Every Ant

6 結(jié)論

通過以上分析，可以得到以下結(jié)論：（1）螞蟻相遇策略使蟻群同時相向搜索，加快了算法的搜索速度；（2）螞蟻回退策略可以避免螞蟻陷入U形陷阱，增加了算法魯棒性和適應(yīng)性；（3）通過設(shè)置信息素敏感閾值，增加了算法前期的大范圍搜索能力；（4）對信息素殘留公式的重新定義，保留了算法對最優(yōu)解的“記憶”能力，使蟻群搜索目標(biāo)明確，規(guī)劃出的路徑集中在最優(yōu)路徑周圍；（5）信息素揮發(fā)系數(shù)的自適應(yīng)調(diào)整兼顧了算法前期的大范圍搜索和后期的快速收斂；（6）與傳統(tǒng)算法相比，改進遺傳算法具有更快的收斂速度和更好的最優(yōu)解。

［1］譚民，王碩.機器人技術(shù)研究進展［J］.自動化學(xué)報，2013，39（7）：963-972.（Tan Min，Wang Shuo.Research progress on robotics［J］.Acta Autom Atica Sinca，2013，39（7）：963-972.）

［2］栗紅生，劉瑩.復(fù)雜路徑下機器人路徑規(guī)劃優(yōu)化方法仿真［J］.計算機仿真，2014，31（1）：407-411.（Li Hong-sheng，Liu Ying.Robot path planning under complicated path simulation optimization method［J］.Computer Simulation，2014，31（1）：407-411.）

［3］Fakoor M，Kosari A，Jafarzadeh M.Humanoid robot path planning with fuzzy markov decision processes［J］.Journal of Applied Research&Technology，2016，14（5）：300-310.

［4］柴寅，唐秋華，鄧明星.機器人路徑規(guī)劃的柵格模型構(gòu)建與蟻群算法求解［J］.機械設(shè)計與制造，2016（4）：178-181.（Chai Geng，Tang Qiu-hua，Deng Ming-xing.Grid model and ant colony aligorithm for robot path planning［J］.Machinery Design&Manufacture，2016（4）：178-181.）

［5］李明磊，趙杰，李戈.面向方形節(jié)點拓撲地圖下的移動機器人路徑規(guī)劃算法研究［J］.機械與電子，2015（10）：67-70.（Li Ming-lei，Zhao Jie，Li Wen.Research on pathh panning algorithm for mobile robot based on square nades in topological map［J］.Machinery&Electronics，2015（10）：67-70.）

［6］陳超，唐堅，靳祖光.一種基于可視圖法導(dǎo)盲機器人路徑規(guī)劃的研究［J］.機械科學(xué)與技術(shù)，2014，33（4）：490-495.（Chen Chao，Tang Jian，Zhan Zu-guang.A path planning algorithm for seeing eye robots based on V-Graph［J］.Mechanical Science and Technology for Aerospace Engineering，2014，33（4）：490-495.）

［7］盧路秋.基于模糊人工勢場法的多移動機器人路徑規(guī)劃研究［D］.天津：天津工業(yè)大學(xué)，2016.（Lu Lu-qiu.Based on the fuzzy artificial potential field method of multi mobile robot path planning research［D］.Tianjing：Tianjin University of Technology，2016.）

［8］李剛，魚佳欣，郭道通.基于改進遺傳算法的機器人路徑規(guī)劃與仿真［J］.計算技術(shù)與自動化，2015（2）：24-27.（Li Gang，Yu Jia-xin，Guo Dao-tong.Robot path planning based on improved genetic algorithm and simulation，2015（2）：24-27.）

［9］喬茹，章小兵，趙光興.基于改進蟻群算法的移動機器人全局路徑規(guī)劃［J］.安徽工業(yè)大學(xué)學(xué)報：自科版，2009，26（1）：77-80.（Qiao Ru，Zhan Xiao-bing，Zhao Guang-xing.Global path planning of mobile robot based on improved ant colony algorithm［J］.J.of Anhui University of Technology，2009，26（1）：77-80.）

［10］Zhang K，Yuan C M，Gao X S.A greedy algorithm for feedrate planning of CNC machines along curved tool paths with confined jerk［J］.Robotics and Computer-Integrated Manufacturing，2012，28（4）：472-483.