楊連花，常肖

(長安大學道路施工技術與裝備教育部重點實驗室，陜西西安 710064)

機器人空間路徑規(guī)劃的ACO算法特性分析

楊連花，常肖

(長安大學道路施工技術與裝備教育部重點實驗室，陜西西安 710064)

為進一步研究機器人的移動空間路徑規(guī)劃方法，分析蟻群算法的主要系數(shù)對路徑規(guī)劃的影響，根據(jù)蟻群優(yōu)化算法的主要特點，對機器人的移動空間信息采用柵格法進行全局描述。對蟻群優(yōu)化算法的主要系數(shù)如蟻群數(shù)量m和信息素蒸發(fā)系數(shù)ρ等進行選擇，以路徑長度和迭代次數(shù)為目標，仿真分析其對規(guī)劃路徑的長度和路徑規(guī)劃效率的影響，找到最佳匹配系數(shù)組。仿真結果表明：合理選擇算法系數(shù)能夠縮短機器人的移動空間路徑規(guī)劃長度,且能提高路徑規(guī)劃效率。

移動機器人；蟻群優(yōu)化算法；路徑規(guī)劃；影響系數(shù)

路徑規(guī)劃是對移動機器人(mobile robot，MR)進行研究的主要內(nèi)容之一，是指當工作空間中存在障礙物時，移動機器人能搜索到一條從給定起點到終點的工作路徑，使其在移動過程中可以安全、無碰撞地躲避所有障礙物，同時經(jīng)過的路徑最短，這是控制機器人工作的基礎[1]。當前，存在大量針對全局路徑規(guī)劃的算法，柵格、人工勢場等是其中幾種較為常見的算法。應用柵格法進行路徑規(guī)劃時，隨著空間的增大，計算所需的存儲空間急劇增大，導致決策速度降低[2]；而應用人工勢場法進行路徑規(guī)劃時，又極易出現(xiàn)局部最佳解和鎖死問題[3]。在智能控制算法迅速成熟的基礎上，逐漸出現(xiàn)了如免疫[4]、A*優(yōu)化[5]、蟻群優(yōu)化[6]、粒子群[7]、遺傳優(yōu)化[8]和人工魚群[9]等算法。

蟻群優(yōu)化(ant colony optimization，ACO)算法作為一種啟發(fā)式搜尋優(yōu)化工具，具備良好的算法結合兼容性、分布式精簡計算、健壯性好等優(yōu)勢。針對移動機器人的路徑規(guī)劃問題，本文采用ACO算法，計算并重點仿真分析螞蟻個數(shù)m和信息素蒸發(fā)系數(shù)ρ這兩個重要影響系數(shù)對規(guī)劃路徑結果和效率的影響。

1 機器人工作空間

1.1 路徑規(guī)劃選擇

在對移動機器人進行研究過程中，移動機器人的路徑規(guī)劃是非常重要的研究方向之一[10]。路徑規(guī)劃的目的是使機器人在整個移動過程中，能夠避開每個障礙物[11]。依照對空間信息的熟悉程度，該問題可以分為己知環(huán)境信息的全局路徑規(guī)劃和未知環(huán)境信息的局部路徑規(guī)劃[12]。根據(jù)已獲得的空間信息，全局規(guī)劃可以為移動機器人進行路徑規(guī)劃，并且獲得的空間信息精確度決定了路徑規(guī)劃的準確性[13]。全局規(guī)劃通常能夠得到最佳路徑，但必須提前獲取空間的精確信息，計算量龐大[14]。而局部規(guī)劃只需獲取機器人目前的局部空間信息，就能讓其具備優(yōu)良的規(guī)避特性[15]。僅僅根據(jù)局部空間信息進行路徑規(guī)劃，偶爾會出現(xiàn)局部極點，不能確保機器人順利移動至終點[16]。

本文中機器人對空間環(huán)境具備一定的熟悉程度，故采用全局路徑規(guī)劃對移動機器人的路徑規(guī)劃進行研究。

1.2 環(huán)境建模

假設機器人的工作空間為二維空間(記為RS)，在RS中的障礙物即為機床。當機器人行走時，障礙物為不發(fā)生變化的靜止物體，對移動機器人的工作環(huán)境進行模擬。按柵格法編號RS空間，機器人按柵格變換位置?？尚袞鸥駷闊o障礙物的柵格，不可行柵格為存在障礙物的柵格，所有的柵格組成了柵格集。柵格標識方法有編號法[17]和直角坐標法[18]，這里選擇編號標識法對機器人工作空間進行模擬。

依次按照由左至右、由下至上的次序，把機器人移動空間用數(shù)字1,2,3,…,n標記，每個柵格用單個數(shù)字表示。通過將障礙物膨脹，使障礙物在占原有柵格的同時，再多占幾個柵格，但按單個柵格計算，從而避免機器人與障礙物發(fā)生碰撞。該標識方法能夠使真實情況和環(huán)境模型相符合，且簡單實用，在路徑規(guī)劃時使機器人移動暢通無阻。設置柵格序號集S={1,2,3,…，N}。由所述關系可知，g(0,0)的序號設置為1，g(1,0)的序號設置為2，直到g(X,Y)的序號設置為n。在不屬于同一柵格內(nèi)的前提下，規(guī)定起點、終點都為任意位置且都屬于S。

2 蟻群優(yōu)化算法

2.1 基本原理

基于蟻群的共同行為，搜尋路徑時能夠找到最佳結果的基本原理是:在蟻群通過的路徑上遺留信息素的方式，讓之后通過的蟻群分析信息素的強度以選取通道。當蟻群搜尋到從沒涉足的交叉口時，它將隨意選取通道通過且留下信息素，路徑距離跟遺留信息素的數(shù)量呈反比。過一段時間后，遺留在短距離路徑上的信息素將會連續(xù)累積，而遺留在相對長距離的路徑上的信息素就會漸漸蒸發(fā)甚至消失。通過這樣的方式，蟻群最終能夠搜尋到一條最佳路徑。蟻群工作示意圖如圖1所示。

a) 信息素設置 b)T=0時刻蟻群數(shù)目 c)T=1時刻蟻群數(shù)目圖1 蟻群工作工程圖

假設蟻穴的位置為A，食物源的位置為E，障礙物的位置為B、C、D、H。當蟻穴和食物源之間有障礙物時，蟻群能智能地從A通過C或H抵達E，或從E通過C或H抵達A，BCD長度為1，BHD長度為2，如圖1a)所示。從計算簡便的角度出發(fā)，假設在單個時間內(nèi)蟻群遺留下的信息素設置為1，且信息素殘留的時間也設置為1，設置A點與E點之間分別存在30只螞蟻。在開始時，路徑BC、BH、CD、HD上沒有留下信息素，在A與E之間的蟻群會隨意選取其通過的通道。根據(jù)統(tǒng)計學原理，蟻群選取路徑BC、BH、CD、HD幾率相等，如圖1b)所示。當歷時單個時間后，BCD遺留信息素增多，而BHD遺留信息素減少，如圖1c)所示。數(shù)量為20的蟻群由B、C和D點抵達E。隨著這種循環(huán)的繼續(xù)，蟻群認同BCD的幾率會提高，最后蟻群將絕對認同BCD路徑，進而搜尋到A和E之間的最短路徑。

圖2 ACO算法執(zhí)行流程圖

2.2 算法執(zhí)行步驟

算法的執(zhí)行流程如圖2所示。

步驟如下：

1)由0和1構成的矩陣代表機器人的柵格式移動空間信息，可通過柵格設置為0，障礙物柵格設置為1。可通過路徑節(jié)點設置初始化D={0,1,…，n-1}，假設信息啟發(fā)因子為α、蟻群數(shù)量為m、信息素蒸發(fā)系數(shù)為ρ、期望啟發(fā)因子為β、迭代次數(shù)為Nc。假設螞蟻k(k=1,2,…，m)目前所通過的柵格點禁忌表為Bk，將其初始化為Φ。把螞蟻放置于起點S，分別對起點S和終點E的柵格號進行選取。

2)根據(jù)狀態(tài)，單個螞蟻由i柵格行走至相鄰j柵格的概率[19]

3)螞蟻k每移動一次，把節(jié)點j添加至禁忌表Bk里，以修改Bk。

4)重復步驟2)～3)，直到?jīng)]有循環(huán)完畢的螞蟻移動至終點，計算每只螞蟻移動的路徑距離且進行存儲。

5)更新信息素

τij(t+1)=ρτij(t)+Δτij(t,t+1),

6)選取、輸出本次循環(huán)中的最佳路徑并存儲,否則重復步驟4)～5)。

3 ACO算法中模擬系數(shù)的選取

圖3 空間路徑規(guī)劃

至今仍沒有嚴謹?shù)睦碚摶A來判定ACO算法中的最佳系數(shù)配置 ，最佳系數(shù)配置主要依賴于仿真結果的統(tǒng)計數(shù)據(jù)和經(jīng)驗值。針對ACO算法在模擬計算中存在的問題，研究α，β，ρ,m,Q等系數(shù)的最佳配置相當重要。研究如圖3所示環(huán)境下的路徑規(guī)劃，其中陰影柵格代表障礙物占用。

3.1 蟻群數(shù)量

在ACO算法中，隨著蟻群數(shù)量的增大，算法的穩(wěn)定性和蟻群的空間搜尋能力會隨之增加。但在實際應用中，隨著蟻群數(shù)量的增多，反而會減慢算法收斂速度，使搜尋過的路徑上的相關信息量受到影響，并使其變化趨于平均，從而使信息正反饋功能降低。相反，隨著蟻群數(shù)量的減少，在搜尋大規(guī)?？臻g的最佳路徑時，減少未搜尋路徑上的有關信息量，甚至使其完全消失，從而提高了ACO收斂速率，但降低了蟻群搜尋的隨機性，使路徑搜尋的全局性減弱，降低了ACO 的穩(wěn)定性。在本文中，設置蟻群優(yōu)化算法中，α=1，β=5，ρ=0.5,Q=100,在仿真分析時，選擇蟻群數(shù)量m分別為10、20、30、40、50、60、70、80、90、100、110、120、130、140、150、160、170、180、190、200，仿真結果如圖4所示。

由圖4可知，蟻群數(shù)量m基本按具備正分數(shù)指數(shù)的冪函數(shù)遞增規(guī)律來影響收斂迭代次數(shù)。隨著m的增加，ACO算法的穩(wěn)定性得到提高，但當m增加至臨界點之后，蟻群搜尋收斂速度降低，信息量波動趨于穩(wěn)定。同時也可得出，當蟻群數(shù)量為50時，搜尋迭代次數(shù)和路徑長度均為最小值。

a) 對路徑長度的影響 b) 對迭代次數(shù)的影響圖4 蟻群數(shù)量對ACO的影響

3.2 信息蒸發(fā)素系數(shù)

a) 對路徑長度的影響 b) 對迭代次數(shù)的影響圖5 信息素蒸發(fā)系數(shù)對ACO的作用

在ACO優(yōu)化時，蟻群具備記憶能力，隨著時間推移，蟻群遺留的信息漸漸蒸發(fā)。ACO算法中，蟻群對空間的搜尋能力及蟻群搜尋的收斂速度直接受到信息素蒸發(fā)系數(shù)ρ的影響。ρ過大，將大大增加二次搜尋路徑的概率，導致從未被蟻群搜尋過的路徑上的信息素蒸發(fā)甚至完全消失，使得蟻群的空間搜尋能力降低；相反，當ρ較小時，雖然蟻群對路徑的空間搜尋能力與隨機性有所提高，但卻降低了蟻群搜尋的收斂速度[7]。仿真分析時，設置m=100，α=1,β=5,Q=100,信息素蒸發(fā)系數(shù)ρ分別為0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9。計算結果如圖5 所示。

由圖5可知，當信息素蒸發(fā)系數(shù)ρ=0.6時，搜尋迭代次數(shù)和路徑長度均為最小值。

圖6 最佳路徑選擇結果

4 基于ACO算法路徑規(guī)劃仿真分析

本文通過設計并實現(xiàn)機器人的空間最佳規(guī)劃系統(tǒng)來探索ACO的有效性。基于Matlab 軟件仿真前提下，采用ACO優(yōu)化算法對機器人進行空間路徑規(guī)劃。仿真時，設序號1為空間信息的起始點柵格位置，序號400為終點柵格位置。設定m=50，Nc=100，α=1,β=5，ρ=0.6。仿真結果如圖6、 7所示。

圖7 仿真結果曲線

由圖6可見，蟻群可以搜尋到一條從起始點開始避開所有障礙物的空間最佳路徑，即在該環(huán)境下移動機器人可以搜尋到的最短路徑。由圖7可見，基于ACO算法的機器人空間搜尋模型在計算初期發(fā)生一定波動，但隨著時間的推移，計算所得的路徑長度越來越短，且在整體上呈收斂趨勢。在計算中后期，最佳路徑因隨機搜尋的數(shù)目降低而趨于穩(wěn)定。因信息素濃度的正反饋機制的存在，使得所搜尋的路徑在第31次算法迭代時收斂至最佳。

5 結論

1)針對機器人路徑規(guī)劃問題，采用柵格法對空間環(huán)境進行全局空間信息描述，并基于蟻群優(yōu)化的路徑規(guī)劃方法對機器人進行路徑規(guī)劃。結果證明該方法不僅實現(xiàn)簡單，而且具備良好的算法結合兼容性，可用于解決環(huán)境已知情況下的機器人路徑規(guī)劃問題。

2)通過仿真分析ACO算法的螞蟻數(shù)量、信息素蒸發(fā)系數(shù)這2個重要系數(shù)對規(guī)劃路徑效率及路徑規(guī)劃結果的影響，結果表明蟻群數(shù)量基本按具備正分數(shù)指數(shù)的冪函數(shù)遞增規(guī)律來影響迭代次數(shù)。隨著蟻群數(shù)量的增長，ACO的穩(wěn)定性提高。但當m增長到臨界點后，則蟻群搜尋收斂速率減慢，信息量波動趨于穩(wěn)定。確定m=50時，規(guī)劃結果最優(yōu)；當信息素蒸發(fā)系數(shù)增加時，會使已搜尋過的路徑被二次計算的概率增大，導致沒有被搜尋到的路徑上的信息素減少甚至完全蒸發(fā)，從而使ACO的全局搜尋能力降低。當信息素蒸發(fā)系數(shù)減小時，雖然能夠提高ACO的整體搜尋能力和隨機性，但卻減小了ACO的收斂速度。最終確定ρ=0.6時，規(guī)劃結果最優(yōu)。

[1]劉玲.基于智能計算的移動機器人路徑規(guī)劃方法研究[D].長沙:湖南大學,2007. LIU Ling.Research on path planning for mobile robot based on intelligent computing[D].Changsha: Hunan University,2007.

[2]史恩秀,陳敏敏,李俊,等.基于蟻群算法的移動機器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機械學報,2014,45(6):53-57. SHI Enxiu,CHEN Minmin,LI Jun,et al.Research on global path planning for mobile robot based on ant colony algorithm[J].Journal of Agricultural Machinery,2014,45(6):53-57.

[3]于振中,閆繼宏,趙杰,等.改進人工勢場法的移動機器人路徑規(guī)劃[J].哈爾濱工業(yè)大學學報,2011,43(1):50-55. YU Zhenzhong,YAN Jihong,ZHAO Jie,et al.Improved artificial potential field method of path planning for mobile robot[J].Journal of Harbin Institute of Technology,2011,43(1):50-55.

[4]葉兆莉,袁明新,程帥,等.移動機器人的一種煙花爆炸式新免疫規(guī)劃算法[J].計算機仿真,2013,30(3):323-326,375. YE Zhaoli,YUAN Mingxin,CHENG Shuai,et al.New fireworks explosive immune planning algorithm for mobile robots[J].Computer Simulation,2013,30(3):323-326,375.

[5]王殿君.基于改進A*算法的室內(nèi)移動機器人路徑規(guī)劃[J].清華大學學報(自然科學版),2012,52(8):1085-1089. WANG Dianjun.Indoor mobile-robot path planning based on an improved A*algorithm[J].Journal of Tsinghua University (Science and Technology),2012,52(8):1085-1089.

[6]張志協(xié),曹陽.基于改進型蟻群算法的最佳路徑問題求解[J].計算機系統(tǒng)應用,2012,38(10):76-80. ZHANG Zhixie,CAO Yang.Optimal path problem solving based on improved ant colony algorithm[J].Computer System Application,2012,38(10):76-80.

[7]李擎,徐銀梅,張德政,等.基于粒子群算法的移動機器人全局路徑規(guī)劃策略[J].北京科技大學學報,2010,32(3):397-402. LI Qing,XU Yinmei,ZHANG Dezheng,et al.Global path planning method for mobile robots based on the particle swarm algorithm[J].Journal of University of Science and Technology Beijing,2010,32(3):397-402.

[8]石鐵峰.改進遺傳算法在移動機器人路徑規(guī)劃中的應用[J].計算機仿真,2011,28(4):193-195,303. SHI Tiefeng.Research on path planning for mobile robot based on improved genetic algorithm[J].Computer Simulation,2011,28(4):193-195,303.

[9]周利坤,劉宏昭.自適應人工魚群算法在清罐移動機器人路徑規(guī)劃中的應用[J].機械科學與技術,2012,31(7):1085-1089. ZHOU Likun,LIU Hongzhao.An adaptive artificial fish school algorithm for path planning of mobile tank-clearing robot[J].Mechanical Science and Technology,2012,31(7):1085-1089.

[10]BRADEN E Stenning,TIMOTHY D Barfoot.Path planning with variable-fidelity terrain assessment[J].Robotics and Autonomous Systems,2012,60(9):1135-1148.

[11]游維.一種未知動態(tài)環(huán)境下移動機器人路徑規(guī)劃研究[D].湘潭:湘潭大學,2009. YOU Wei.An unknown dynamic environment for mobile robot path planning research[D].Xiangtan :Xiangtan University,2009.

[12]張曉.全方位移動平臺的設計以及定位和路徑規(guī)劃[D].北京:北京工業(yè)大學,2013. ZHANG Xiao.Design and positioning and path planning of the mobile platform[D].Beijing :Beijing University of Technology,2013.

[13]張鵬飛.自主移動機器人路徑規(guī)劃與運動控制的研究與實現(xiàn)[D].西安:西安理工大學,2008 ZHANG Pengfei.Research and implementation of path planning and motion control of autonomous mobile robot[D].Xi′an :Xi′an University of technology,2008.

[14]邸建華.用于水下機器人路徑規(guī)劃的優(yōu)化算法研究[D].哈爾濱:哈爾濱工程大學,2009. DI Jianhua.Optimization algorithm for path planning of underwater robot[D].Harbin: Harbin Engineering University,2009.

[15]黎田.基于改進蟻群算法的移動機器人路徑規(guī)劃[D].西安:西安科技大學,2011. LI Tian.Research of path planning for mobile robots based on improved ant colony algorithm[D].Xi′an: Xi′an University of Science and Technology,2011.

[16]王麗.移動機器人路徑規(guī)劃方法研究[D].西安:西北工業(yè)大學,2007. WANG Li.Research on path planning method of mobile robot[D].Xi′an: Northwestern Polytechnical University,2007.

[17]夏梁盛,嚴衛(wèi)生.基于柵格法的移動機器人運動規(guī)劃研究[J].計算機仿真,2012,12(29):229-233. XIA Liangsheng,YAN Weisheng.Study on mobile robot motion planning based on grid method[J].Computer Simulation,2012,12(29):229-233.

[18]楊杰,賀利樂,李榮麗,等.基于改進勢場柵格法的移動機器人路徑規(guī)劃[J].煤礦機械.2012,33(8):74-76. YANG Jie,HE Lile,Li Rongli ,et al.Based on the improved potential field grid method for path planning of mobile robot[J].Coal Mine Machinery,2012,33 (8): 74-76.

[19]徐進.基于蟻群算法的移動機器人路徑規(guī)劃算法研究[D].北京:北京化工大學,2009. XU Jin.Research on path planning algorithm of mobile robot based on ant colony algorithm[D].Beijing: Beijing University of Chemical Technology,2009.

(責任編輯：郎偉鋒)

ACO Algorithm Characteristic Analysis of Robot′s Space Path Planning

YANGLianhua,CHANGXiao

(KeyLaboratoryofRoadConstructionTechnologyandEquipment,MinistryofEducation,Chang′anUniversity,Xi′an710064,China.)

In order to further research the path planning method of robot′s mobile space and analyze the influence of main coefficients of ant colony algorithm on path planning,the mobile spatial information of the robot is described by the grid method according to the main characteristics of ant colony optimization algorithm.With the path length and the number of iterations as the goal,the key parameters such as the number of ant colony and information pheromone evaporation coefficients of the ant colony optimization algorithm are selected to simulate and analyze their influence on the length and efficiency of the path planning to get the best array of path.The simulation results show that the reasonable selection of algorithm parameters can achieve the short path planning length of the robot′s mobile space and the high path planning efficiency.

mobile robot; ant colony optimization algorithm; path planning; influence parameter

2016-05-26

楊連花(1991—)，女，河南原陽人，碩士研究生，主要研究方向為機械設計及理論，E-mail：1245201067@qq.com.

10.3969/j.issn.1672-0032.2016.04.013

TP242.6

A

1672-0032(2016)04-0081-06