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

楊連花，常肖

(長(zhǎng)安大學(xué)道路施工技術(shù)與裝備教育部重點(diǎn)實(shí)驗(yàn)室，陜西西安 710064)

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

楊連花，常肖

(長(zhǎng)安大學(xué)道路施工技術(shù)與裝備教育部重點(diǎn)實(shí)驗(yàn)室，陜西西安 710064)

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

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

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

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

1 機(jī)器人工作空間

1.1 路徑規(guī)劃選擇

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

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

1.2 環(huán)境建模

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

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

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

2.1 基本原理

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

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

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

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

2.2 算法執(zhí)行步驟

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

步驟如下：

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

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

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

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

5)更新信息素

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

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

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

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

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

3.1 蟻群數(shù)量

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

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

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

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

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

在ACO優(yōu)化時(shí)，蟻群具備記憶能力，隨著時(shí)間推移，蟻群遺留的信息漸漸蒸發(fā)。ACO算法中，蟻群對(duì)空間的搜尋能力及蟻群搜尋的收斂速度直接受到信息素蒸發(fā)系數(shù)ρ的影響。ρ過(guò)大，將大大增加二次搜尋路徑的概率，導(dǎo)致從未被蟻群搜尋過(guò)的路徑上的信息素蒸發(fā)甚至完全消失，使得蟻群的空間搜尋能力降低；相反，當(dāng)ρ較小時(shí)，雖然蟻群對(duì)路徑的空間搜尋能力與隨機(jī)性有所提高，但卻降低了蟻群搜尋的收斂速度[7]。仿真分析時(shí)，設(shè)置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。計(jì)算結(jié)果如圖5 所示。

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

圖6 最佳路徑選擇結(jié)果

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

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

圖7 仿真結(jié)果曲線

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

5 結(jié)論

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

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

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

[2]史恩秀,陳敏敏,李俊,等.基于蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào),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]于振中,閆繼宏,趙杰,等.改進(jìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),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]葉兆莉,袁明新,程帥,等.移動(dòng)機(jī)器人的一種煙花爆炸式新免疫規(guī)劃算法[J].計(jì)算機(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]王殿君.基于改進(jìn)A*算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),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é),曹陽(yáng).基于改進(jìn)型蟻群算法的最佳路徑問(wèn)題求解[J].計(jì)算機(jī)系統(tǒng)應(yī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]李擎,徐銀梅,張德政,等.基于粒子群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃策略[J].北京科技大學(xué)學(xué)報(bào),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]石鐵峰.改進(jìn)遺傳算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(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]周利坤,劉宏昭.自適應(yīng)人工魚(yú)群算法在清罐移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[J].機(jī)械科學(xué)與技術(shù),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]游維.一種未知?jiǎng)討B(tài)環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃研究[D].湘潭:湘潭大學(xué),2009. YOU Wei.An unknown dynamic environment for mobile robot path planning research[D].Xiangtan :Xiangtan University,2009.

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

[13]張鵬飛.自主移動(dòng)機(jī)器人路徑規(guī)劃與運(yùn)動(dòng)控制的研究與實(shí)現(xiàn)[D].西安:西安理工大學(xué),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]邸建華.用于水下機(jī)器人路徑規(guī)劃的優(yōu)化算法研究[D].哈爾濱:哈爾濱工程大學(xué),2009. DI Jianhua.Optimization algorithm for path planning of underwater robot[D].Harbin: Harbin Engineering University,2009.

[15]黎田.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[D].西安:西安科技大學(xué),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]王麗.移動(dòng)機(jī)器人路徑規(guī)劃方法研究[D].西安:西北工業(yè)大學(xué),2007. WANG Li.Research on path planning method of mobile robot[D].Xi′an: Northwestern Polytechnical University,2007.

[17]夏梁盛,嚴(yán)衛(wèi)生.基于柵格法的移動(dòng)機(jī)器人運(yùn)動(dòng)規(guī)劃研究[J].計(jì)算機(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]楊杰,賀利樂(lè),李榮麗,等.基于改進(jìn)勢(shì)場(chǎng)柵格法的移動(dòng)機(jī)器人路徑規(guī)劃[J].煤礦機(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]徐進(jìn).基于蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃算法研究[D].北京:北京化工大學(xué),2009. XU Jin.Research on path planning algorithm of mobile robot based on ant colony algorithm[D].Beijing: Beijing University of Chemical Technology,2009.

(責(zé)任編輯：郎偉鋒)

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—)，女，河南原陽(yáng)人，碩士研究生，主要研究方向?yàn)闄C(jī)械設(shè)計(jì)及理論，E-mail：1245201067@qq.com.

10.3969/j.issn.1672-0032.2016.04.013

TP242.6

A

1672-0032(2016)04-0081-06