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

朱顥東，孫 振，吳 迪，申 圳

(鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院 河南 鄭州 450002)

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

朱顥東，孫 振，吳 迪，申 圳

(鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院 河南 鄭州 450002)

針對(duì)蟻群算法應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃時(shí)存在易于陷入局部最優(yōu)解、收斂速度慢的問(wèn)題，提出了一種適用于靜態(tài)障礙環(huán)境下基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃方法。該方法改進(jìn)了節(jié)點(diǎn)間的狀態(tài)轉(zhuǎn)移規(guī)則，增加了得到最優(yōu)路徑的概率；自適應(yīng)調(diào)整啟發(fā)函數(shù)，提高了算法的搜索效率；基于狼群法則對(duì)信息素進(jìn)行更新，有效避免了算法陷入局部最優(yōu)解；動(dòng)態(tài)調(diào)整了衰減系數(shù)，在后期增加了螞蟻對(duì)最優(yōu)路徑的選擇概率，加快了算法的收斂速度。仿真實(shí)驗(yàn)表明，與其他算法在相同環(huán)境下比較，該改進(jìn)算法在路徑規(guī)劃結(jié)果相同的情況下具有較快的收斂速度；且改進(jìn)算法在不同復(fù)雜程度環(huán)境中均得到了最優(yōu)路徑，也表明了該算法的有效性和可靠性。該算法具有良好的尋優(yōu)能力，可以適用于不同復(fù)雜環(huán)境中的移動(dòng)機(jī)器人路徑規(guī)劃。

移動(dòng)機(jī)器人；蟻群算法；路徑規(guī)劃

0 引 言

移動(dòng)機(jī)器人路徑規(guī)劃是近年來(lái)機(jī)器人研究領(lǐng)域的重要分支和研究熱點(diǎn)之一。移動(dòng)機(jī)器人路徑規(guī)劃是指移動(dòng)機(jī)器人在有障礙物的環(huán)境中，找到一條從起始點(diǎn)到目的點(diǎn)最優(yōu)的無(wú)碰路徑[1-2]。路徑規(guī)劃問(wèn)題具有復(fù)雜性、多約束性和多目標(biāo)性等特點(diǎn)。傳統(tǒng)的路徑規(guī)劃算法有Dijkstra，A*算法等，Dijkstra是一種經(jīng)典的最短路徑搜索算法，它是一種貪心算法，雖然能很好地規(guī)劃出路徑，但是由于該算法是以起始點(diǎn)向外層層擴(kuò)展，直到搜索到目的節(jié)點(diǎn)為止，需要遍歷節(jié)點(diǎn)，計(jì)算復(fù)雜度高，效率比較低；A*算法是一種啟發(fā)式算法，它是通過(guò)估價(jià)函數(shù)來(lái)確定當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的距離和搜索方向，在復(fù)雜的環(huán)境中一個(gè)不理想的估計(jì)函數(shù)容易導(dǎo)致搜索不到路徑或者規(guī)劃路徑效果不理想。近年來(lái)，在移動(dòng)機(jī)器人路徑規(guī)劃方法中，國(guó)內(nèi)外專(zhuān)家學(xué)者提出了許多仿生智能優(yōu)化算法[3]，如：遺傳[4]、人工魚(yú)群[5]、蛙跳[6]、神經(jīng)網(wǎng)絡(luò)[7]以及蟻群[8]等算法。

1992年，Marco Dorigo在博士論文中提出了蟻群算法，通過(guò)觀察螞蟻尋找食物源時(shí)發(fā)現(xiàn)路徑的行為而獲得啟發(fā)。傳統(tǒng)的蟻群算法主要是解決旅行商問(wèn)題(travelling salesman problem，TSP)，文獻(xiàn)[9]借鑒最大-最小蟻群系統(tǒng)的方法，限制了信息素的值域范圍，有效地避免了算法陷入局部最優(yōu)解問(wèn)題。文獻(xiàn)[10]構(gòu)建了權(quán)重可調(diào)的引力概率函數(shù)，并且把它作為啟發(fā)因子，有效地提高了算法的收斂速度。文獻(xiàn)[11]改進(jìn)了算法的信息素更新規(guī)則，并加入拐點(diǎn)作為評(píng)價(jià)路徑質(zhì)量的參數(shù)之一，提高了算法的效率。文獻(xiàn)[12] 分析了影響蟻群優(yōu)化中的關(guān)鍵參數(shù)，自適應(yīng)地設(shè)置了算法參數(shù)，調(diào)高了算法的精度和效率。文獻(xiàn)[13]提出了一種基于人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃方法，定義了一種新的引力函數(shù)，有效地提高了路徑規(guī)劃的性能。文獻(xiàn)[14]提出了自適應(yīng)調(diào)整啟發(fā)函數(shù)、路徑平滑策略，有效地提高了路徑的質(zhì)量。目前，不少算法在求解機(jī)器人全局路徑問(wèn)題中存在著局限性，遺傳算法由于運(yùn)算進(jìn)化代數(shù)眾多，規(guī)劃路徑時(shí)占用大量的存儲(chǔ)空間，導(dǎo)致運(yùn)算速度較慢。人工魚(yú)群算法雖然具有較快的收斂速度，但是很難得到精確的解，規(guī)劃出的路徑質(zhì)量不理想；混合蛙跳算法易于陷入局部最優(yōu)解，求解精度較低，而且收斂速度較慢，限制了該算法在路徑規(guī)劃領(lǐng)域的應(yīng)用；神經(jīng)網(wǎng)絡(luò)算法雖然具有較強(qiáng)的學(xué)習(xí)能力，但是當(dāng)機(jī)器人在復(fù)雜的環(huán)境中，很難用數(shù)學(xué)公式來(lái)描述。人工勢(shì)場(chǎng)法是以其數(shù)學(xué)計(jì)算上的簡(jiǎn)單明了而被廣泛應(yīng)用到路徑規(guī)劃中，但是，人工勢(shì)場(chǎng)法存在局部極小點(diǎn)和目標(biāo)不可達(dá)等問(wèn)題。而蟻群算法是一種模擬進(jìn)化算法，具有自組織性、較強(qiáng)的魯棒性、分布式計(jì)算、尋優(yōu)能力強(qiáng)、易于和其他算法相結(jié)合等優(yōu)點(diǎn)，非常適合應(yīng)用到移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題。

因此，論文提出利用改進(jìn)蟻群算法規(guī)劃移動(dòng)機(jī)器人路徑，并提出了動(dòng)態(tài)調(diào)整揮發(fā)系數(shù)、自適應(yīng)調(diào)整啟發(fā)函數(shù)等策略，能夠在不同復(fù)雜程度的環(huán)境中得到全局最優(yōu)路徑，提高了算法的搜索速率，并加快了算法的收斂速度，通過(guò)在Matlab軟件中仿真實(shí)驗(yàn)，表明了該算法是有效和可行的。

1 問(wèn)題描述與建模

機(jī)器人路徑規(guī)劃中重要的問(wèn)題之一是環(huán)境建模。建模就是根據(jù)已知機(jī)器人周?chē)沫h(huán)境信息，通過(guò)提取和分析，將現(xiàn)實(shí)中物理空間轉(zhuǎn)換為機(jī)器人可以理解的空間，通過(guò)建立良好的環(huán)境模型，有效地減少了路徑搜索過(guò)程中的麻煩。論文中主要用柵格法對(duì)機(jī)器人的二維環(huán)境進(jìn)行劃分，從左到右，從上到下對(duì)柵格進(jìn)行編號(hào)，論文中以10×10的柵格環(huán)境為例來(lái)說(shuō)明，如圖1所示。

圖1 柵格坐標(biāo)與序號(hào)關(guān)系Fig.1 Grid coordinate relates with serial number

圖1中，坐標(biāo)原點(diǎn)0在左下方，水平從左向右為x軸正方向，垂直從下到上為y軸正方向，柵格的大小由移動(dòng)機(jī)器人自身的大小和它運(yùn)動(dòng)步長(zhǎng)決定，為了簡(jiǎn)化計(jì)算路徑的長(zhǎng)度，一個(gè)柵格的邊長(zhǎng)為機(jī)器人的運(yùn)動(dòng)步長(zhǎng)，即一個(gè)單位長(zhǎng)度。序號(hào)與坐標(biāo)的對(duì)應(yīng)關(guān)系如下

(1)

(1)式中：Ni表示柵格的序號(hào)；N表示每一列的柵格數(shù)量；mod表示取余數(shù)；ceil表示向后取整數(shù)。

為了建立機(jī)器人可以理解的環(huán)境，根據(jù)環(huán)境地圖建立相應(yīng)的矩陣來(lái)表示每個(gè)柵格的狀態(tài)(可行柵格和障礙柵格)，在下面矩陣中，0代表可行柵格；1代表障礙柵格，每一個(gè)障礙可能占用一個(gè)或多個(gè)柵格，若障礙物占用不足一個(gè)柵格，視為占用一個(gè)完整柵格；機(jī)器人被視為一個(gè)點(diǎn)狀機(jī)器人；將障礙物以機(jī)器人半徑的大小進(jìn)行膨化，確保機(jī)器人可以安全地通過(guò)障礙物邊界。10×10的棚格環(huán)境可用矩陣表示為

(2)

2 基于改進(jìn)蟻群算法的路徑規(guī)化

研究表明螞蟻會(huì)在經(jīng)過(guò)的路徑上會(huì)留下信息素，并且可以在一定范圍內(nèi)感知信息素進(jìn)而引導(dǎo)自己的運(yùn)動(dòng)，因此，蟻群會(huì)表現(xiàn)出一種正反饋現(xiàn)象：越多的螞蟻經(jīng)過(guò)一條路徑，就會(huì)在這條路徑上釋放越多的信息素，后面的螞蟻選擇這條路徑的概率就越大，螞蟻之間就是通過(guò)這種信息素的交流來(lái)選擇路徑，進(jìn)而找到食物源[3]。蟻群算法具有局部尋優(yōu)能力強(qiáng)、自組織性等優(yōu)點(diǎn)，能很好地應(yīng)用到路徑規(guī)劃中，但傳統(tǒng)蟻群算法存在容易陷入局部最優(yōu)解、收斂速度慢等問(wèn)題，為了提高蟻群算法的搜索效率和路徑規(guī)劃質(zhì)量，論文對(duì)傳統(tǒng)蟻群算法做了以下改進(jìn)。

2.1 改進(jìn)節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移規(guī)則

螞蟻會(huì)根據(jù)啟發(fā)函數(shù)η和路徑上的信息素濃度τ來(lái)選擇下一步的可行節(jié)點(diǎn)，設(shè)定螞蟻的種群數(shù)量為m，假設(shè)當(dāng)前螞蟻k在節(jié)點(diǎn)i處，比較q和q0的大小，按照(3)式的概率進(jìn)行選擇下一步可行節(jié)點(diǎn)j。

(3)

(4)

2.2 自適應(yīng)調(diào)整啟發(fā)函數(shù)

在傳統(tǒng)的蟻群算法中，啟發(fā)函數(shù)η是2個(gè)節(jié)點(diǎn)之間距離的倒數(shù)。A*算法是一種啟發(fā)式算法，表示為f(n)=g(n)+h(n)，其中，g(n) 表示從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)；h(n) 表示當(dāng)前節(jié)點(diǎn)到目的節(jié)點(diǎn)的估計(jì)代價(jià)，在g值一定的情況下，h值越小，f值就越小，能保證最短路經(jīng)的搜索向著目標(biāo)點(diǎn)方向進(jìn)行。由啟發(fā)式A*算法獲得啟發(fā)，下一可行節(jié)點(diǎn)j和目標(biāo)點(diǎn)之間的距離可用于啟發(fā)函數(shù)ηij，即dij和djt被用于啟發(fā)函數(shù)上，即為

(5)

(5)式中：dij是當(dāng)前節(jié)點(diǎn)i和可行節(jié)點(diǎn)j間的歐氏距離；djt是可行節(jié)點(diǎn)j和目的節(jié)點(diǎn)t間的歐式距離，把目的節(jié)點(diǎn)引用到啟發(fā)函數(shù)中，加強(qiáng)了路徑搜索的方向性，減少了算法的搜索空間，有效提高搜索的效率。但是過(guò)早的引入方向性啟發(fā)信息，使得初始的搜索空間太小從而導(dǎo)致算法容易陷入局部最優(yōu)解；在初始階段引進(jìn)起始節(jié)點(diǎn)S和當(dāng)前節(jié)點(diǎn)i之間的距離dsi，作為衡量搜索空間大小的標(biāo)準(zhǔn)，隨著后期擴(kuò)大搜索空間后，方向啟發(fā)信息將會(huì)被引進(jìn)。啟發(fā)函數(shù)為

(6)

(6)式中：dst是起始節(jié)點(diǎn)和目的節(jié)點(diǎn)的歐式距離；閥值ε是一個(gè)常數(shù)，由dst的長(zhǎng)度具體決定。

2.3 改進(jìn)信息素更新方式

在傳統(tǒng)的蟻群算法中，最差螞蟻的信息素經(jīng)過(guò)正反饋之后可能導(dǎo)致算法搜索陷入局部最優(yōu)解，為了避免這個(gè)問(wèn)題，論文借用狼群法則對(duì)信息素進(jìn)行更新，在一次循環(huán)中，找到經(jīng)過(guò)局部最優(yōu)的路徑和局部最差路徑的螞蟻，分別增加和減少釋放信息素濃度的量[3]，各條路徑按照(6)-(8)式進(jìn)行信息素濃度更新。

(7)

(8)

(9)

2.4 動(dòng)態(tài)調(diào)整衰減系數(shù)

在全局路徑規(guī)劃中信息素的衰減系數(shù)ρ起到重要作用，當(dāng)環(huán)境復(fù)雜時(shí)，一個(gè)比較大的衰減系數(shù)會(huì)增加信息素的正反饋，減少搜索空間以至于降低了找到最優(yōu)路徑的可能性；一個(gè)比較小的衰減系數(shù)會(huì)增加搜索時(shí)間。隨著時(shí)間和迭代次數(shù)的增加，傳統(tǒng)蟻群算法容易陷入局部最優(yōu)解，為了避免這個(gè)問(wèn)題，減少算法搜索時(shí)間并且能夠保證找到最優(yōu)路徑，論文提出動(dòng)態(tài)地設(shè)置衰減系數(shù)，表示為

(9)

3 算法流程

步驟1初始化參數(shù)。生成已知環(huán)境中的障礙物柵格地圖，設(shè)置柵格的序號(hào)。設(shè)定種群個(gè)數(shù)m，起始點(diǎn)S，目的點(diǎn)T，蟻群最大迭代次數(shù)Nmax，柵格的行數(shù)M和列數(shù)N，設(shè)置信息素的影響權(quán)值α和啟發(fā)式信息影響權(quán)值β。

步驟2所有螞蟻進(jìn)行路徑選擇。將m只螞蟻放到起始點(diǎn)，螞蟻k(k=1,2,3,…,m)從起始點(diǎn)S出發(fā)，并將起始點(diǎn)添加到禁忌表tabuk中，按照(3)式尋找下一個(gè)可行節(jié)點(diǎn)j，若j∈allowedk，選擇下一個(gè)柵格j，并將當(dāng)前節(jié)點(diǎn)j添加到禁忌表tabuk中。

步驟3判斷螞蟻是否到達(dá)目的點(diǎn)T。若螞蟻到達(dá)目的點(diǎn)T，則記錄螞蟻?zhàn)哌^(guò)的柵格序號(hào)和長(zhǎng)度，若沒(méi)有到達(dá)目的點(diǎn)T，則繼續(xù)搜索下一節(jié)點(diǎn)，直到找到目的點(diǎn)T為止。若某個(gè)螞蟻k陷入停滯，則剔除螞蟻k。如果本代中所有螞蟻都搜索完畢，轉(zhuǎn)到步驟4。

步驟4更新信息素。計(jì)算本代中所有螞蟻得到的可行路徑的長(zhǎng)度，找出本次循環(huán)中到達(dá)目的節(jié)點(diǎn)的局部最優(yōu)和最差螞蟻，按照(6)式對(duì)每個(gè)柵格進(jìn)行信息素更新。

步驟5判斷是否達(dá)到最大的迭代次數(shù)Nmax。若算法達(dá)到最大迭代次數(shù)，則輸出當(dāng)前群體中最短的路徑的長(zhǎng)度，否則，清空禁忌表tabuk，令N=N+1，轉(zhuǎn)到步驟2，繼續(xù)搜索，直到達(dá)到最大的迭代次數(shù)Nmax，算法結(jié)束，輸當(dāng)前群體中最短路徑的長(zhǎng)度。

4 算法仿真

使用Matlab軟件對(duì)改進(jìn)蟻群算法進(jìn)行了仿真實(shí)驗(yàn)，比較了仿真結(jié)果，并對(duì)仿真結(jié)果進(jìn)行了分析。

1)用論文提出的算法和文獻(xiàn)[11]所提出的算法進(jìn)行比較，在文獻(xiàn)[11]中的柵格環(huán)境(20×20)進(jìn)行仿真實(shí)驗(yàn)，設(shè)置相同的蟻群數(shù)量100，通過(guò)仿真實(shí)驗(yàn)，文獻(xiàn)[11]和本文改進(jìn)算法中路徑規(guī)劃圖分別如圖2、圖4所示，文獻(xiàn)[11]和本文算法迭代圖分別如圖3、圖5所示。

圖2 文獻(xiàn)[11]中最優(yōu)路徑規(guī)劃結(jié)果Fig.2 Result of optimal path planning in reference[11]

由于論文中將目標(biāo)節(jié)點(diǎn)引用到啟發(fā)函數(shù)，以加強(qiáng)算法搜索的方向性，減少了搜索空間，有效提高了算法的搜索效率；自適應(yīng)地調(diào)整了衰減系數(shù)，隨著迭代次數(shù)的增加衰減系數(shù)而增加，直到達(dá)到最大值，前期一個(gè)較小的衰減系數(shù)可以增加搜索空間，以便找到最優(yōu)解；后期一個(gè)較大的衰減系數(shù)增加了信息素的正反饋，使得在后期越來(lái)越多的螞蟻傾向于經(jīng)過(guò)最優(yōu)路徑，可以有效地避免算法陷入局部最優(yōu)解，同時(shí)使得算法更快的收斂于全局最優(yōu)解，提高了算法搜索效率和收斂速度。因此，從以上仿真結(jié)果可以看出，在相同的復(fù)雜程度(20×20)和相同障礙物情況下，論文提出的算法和文獻(xiàn)[11]中提出的算法規(guī)劃最優(yōu)路徑長(zhǎng)度相等，質(zhì)量(具有相同拐點(diǎn))相同，但是算法收斂速度略高于文獻(xiàn)[11]，表明本文提出的算法具有一定的優(yōu)越性。

圖3 文獻(xiàn)[11]中算法迭代曲線(xiàn)Fig.3 Iterative curve of algorithm in literature[11]

圖4 本文改進(jìn)蟻群算法最優(yōu)路徑規(guī)劃結(jié)果Fig.4 Result of optimal path planning based on improved algorithm in the paper

圖5 本文改進(jìn)蟻群算法迭代曲線(xiàn)Fig.5 Iterative curve of improved algorithm in the paper

2)在不同復(fù)雜程度的靜態(tài)環(huán)境中仿真實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)分別設(shè)置為種群數(shù)量m=50，最大迭代次數(shù)為100，ρmin=0.1，ρmax=0.5，α=1.1，β=7。實(shí)驗(yàn)結(jié)果如下。

①在10×10柵格環(huán)境中進(jìn)行仿真試驗(yàn)，路徑規(guī)劃結(jié)果如圖6所示，路徑長(zhǎng)度為13.90，算法迭代如圖7所示。

圖6 10×10柵格環(huán)境中路徑規(guī)劃結(jié)果Fig.6 Result of path planning in the 10×10 environment

圖7 10×10柵格環(huán)境中改進(jìn)算法迭代曲線(xiàn)Fig.7 Iterative curve of improved algorithm in the 10×10 environment

②在20×20的柵格環(huán)境進(jìn)行仿真試驗(yàn)，路徑規(guī)劃結(jié)果如圖8所示，路徑長(zhǎng)度為29.21，算法迭代如圖9所示。

圖8 20×20柵格中環(huán)境路徑規(guī)劃結(jié)果Fig.8 Result of path planning in the 20×20 environment

圖9 20×20柵格環(huán)境中改進(jìn)算法迭代曲線(xiàn)Fig.9 Iterative curve of improved algorithm in the 20×20 environment

③在30×30的柵格環(huán)境進(jìn)行仿真試驗(yàn)，路徑規(guī)劃結(jié)果如圖10所示，路徑長(zhǎng)度為43.36，算法迭代如圖11所示。

圖10 30×30柵格環(huán)境中路徑規(guī)劃結(jié)果Fig.10 Result of path planning in the 30×30 environment

通過(guò)在不同的靜態(tài)柵格環(huán)境(從簡(jiǎn)單到復(fù)雜的柵格環(huán)境)中進(jìn)行多個(gè)仿真試驗(yàn)，表明算法不僅在簡(jiǎn)單的環(huán)境中可以規(guī)劃出最優(yōu)路徑，而且在復(fù)雜的環(huán)境中也可以規(guī)劃出最優(yōu)路徑，并且算法迭代次數(shù)較少，收斂速度較快，即該算法在路徑規(guī)劃中適用于不同復(fù)雜程度的環(huán)境，具有可行性和有效性。

圖11 30×30柵格環(huán)境中改進(jìn)算法迭代曲線(xiàn)Fig.11 Iterative curve of improved algorithm in the 30×30 environment

5 結(jié)束語(yǔ)

傳統(tǒng)蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題中存在收斂速度慢、易陷入局部最優(yōu)解、路徑效果不理想等問(wèn)題。針對(duì)這些問(wèn)題，論文對(duì)節(jié)點(diǎn)間的狀態(tài)轉(zhuǎn)移規(guī)則、啟發(fā)函數(shù)的自適應(yīng)調(diào)整、信息素更新方式、衰減系數(shù)的動(dòng)態(tài)調(diào)整進(jìn)行改進(jìn)，通過(guò)在相同的環(huán)境中和文獻(xiàn)[11]中的算法比較，在得到路徑質(zhì)量相同的情況下，論文提出的算法可以通過(guò)較少的迭代次數(shù)找到最優(yōu)路徑和較快的收斂速度；通過(guò)在不同復(fù)雜程度的環(huán)境中進(jìn)行多個(gè)仿真實(shí)驗(yàn)，該算法都能規(guī)劃出理想的路徑，表明了該算法的可行性和有效性。通過(guò)對(duì)比試驗(yàn)和試驗(yàn)仿真，表明了論文提出的算法具有一定的優(yōu)越性。論文中主要是針對(duì)移動(dòng)機(jī)器人在靜態(tài)環(huán)境中全局路徑規(guī)劃，沒(méi)有考慮到存在有限個(gè)動(dòng)態(tài)障礙物的情況，這也是論文的不足之處及后續(xù)的研究重點(diǎn)。

[1] 李成兵,郭瑞雪,李敏.改進(jìn)蟻群算法在旅行商問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2014,34(S1):131-132. LI Chengbing, GUO Ruixue,LI Min. Application of improved ant colony algorithm in travelling salesman problem[J]. Journal of Computer Applications,2014, 34(S1):131-132.

[2] 張琦,馬家辰,謝偉,等. 基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版,2013,34(11):1521-1524. ZHANG Qi, MA Jiachen, XIE Wei, et al. Improved Ant Colony Algorithm-Based Path Planning for Mobile Robot[J]. Journal of Northeastern University: Natural Science, 2013, 34(11):1521-1524.

[3] RAJA P, PUGAZHENTHI S. Optimal path planning of mobile robots: A review [J]. International Journal of Physical Sciences,2012,7(9): 1314-1320.

[4] 潘桂彬,潘豐,劉國(guó)棟.基于改進(jìn)混合蛙跳算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)應(yīng)用,2014,34(10)：2850-2853. PAN Guifeng, PAN Feng, LIU Guodong. Path planning for mobile robots based on improved shuffled frog leaping algorithm[J]. Journal of Computer Applications, 2014,34(10)：2850-2853.

[5] 段俊花,李孝安. 基于改進(jìn)遺傳算法的機(jī)器人路徑規(guī)劃[J]. 微電子學(xué)與計(jì)算機(jī),2005,22(1):70-72. DUAN Junhua, LI Xianan. Robot Path Planning Based on Improved Genetic Algorithm[J]. Microelectronics & Computer,2005, 22(1):70-72.

[6] 聶黎明,周永權(quán). 基于人工魚(yú)群算法的 機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(32):48-50. NIE Liming, ZHOU Yongquan. Path planning of robot based on artificial fish-swarm algorithm[J].Computer Engineering and Applications, 2008,44(32):48-50.

[7] 王愛(ài)民,史慶國(guó),呂晨亮.機(jī)器人路徑規(guī)劃的神經(jīng)網(wǎng)絡(luò)算法及優(yōu)化[J].河北工業(yè)大學(xué)學(xué)報(bào).1999,28(6):13-16. WANG Aimin, SHI Qingguo, LV Chenliang. Path Planning and Optimizing Algorithm of Robot Based on Neural Network[J]. Journal of Hebei University of Technology. 1999,28(6):13-16.

[8] 柳長(zhǎng)安, 鄢小虎, 劉春陽(yáng),等，基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法[J].電子學(xué)報(bào),2011,39(5)：1220-1223. LIU Changan,YAN Xiaohu,LIU Chunyang, et al. Dynamic Path Planning for Mobile Robot Based on Improved Ant Colony Optimization Algorithm[J]. Acta Electronica Sinica, 2011,39(5)：1220-1223.

[9] 張毅,高永琪,牛興江. 一種改進(jìn)蟻群優(yōu)化算法的仿真研究[J].武漢理工大學(xué)報(bào):交通科學(xué)與工程版,2013,37(6)：1330-1332. ZHANG Yi, GAO Yongqi, NIU Xingjiang. Simulation Research with an Improved Ant Colony Algotithm[J]. Journal of Wuhan University of Technology: Transportation Science & Engineering, 2013,37(6)：1330-1332.

[10] 孫純哲,桂貴生,韓東,等. 基于蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究與應(yīng)用[J].合肥工業(yè)大學(xué):自然科學(xué)版,2006,29(10):1208-1211. SUN Guizhe, GUI Guisheng, HAN Dong, et al. Algorithm for mobile robot path planning based on the ant colony algorithm and its application[J].Journal of Hefei University of Technology: Natural Science Edition, 2006,29(10):1208-1211.

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

WANG Xiaofeng, HU Wei, FANG Wuyi,et al. Research on path planning of robot based on improved ant colony algorithm[J].Computer Engineering and Applications, 2014, 50(18)：63-66.

[12] 劉道華, 熊炎, 李為華,等. 蟻群參數(shù)自適應(yīng)調(diào)整的優(yōu)化設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用研究,2011,28(3):905-908. LIU Daohua, XIONG Yan, LI Weihua, et al. Ant Colony optimization with self-adaptive parameter adjusting[J].Application Research of Computers, 2011,28(3):905-908.

[13] YIN L ,YIN Y X , LIN C J. A new potential field method for mobile robot path planning in the dynamic environments[J]. Asian Journal of Control,2009,11(2): 214-225.

[14] WANG Y T，LI J J. A route planning optimization model based on improved ant colony algorithm[C]//IEEE.2009 Eigth IEEE/ACIS International Conference on Computer and Information Science. ShangHai:IEEE Press, 2009: 82- 86.

朱顥東(1980-),男,河南虞城人,副教授,博士,碩士生導(dǎo)師,主要研究方向?yàn)橹悄苄畔⑻幚?、?jì)算智能。E-Mail:zhuhaodong80@163.com。

孫 振(1989-),男,河南新鄉(xiāng)人,在讀碩士研究生,主要研究方向?yàn)橹悄苄畔⑻幚?、模式識(shí)別。

吳 迪(1990-),男,河南南陽(yáng)人,在讀碩士研究生,主要研究方向?yàn)橹悄苄畔⑻幚怼D像處理。

申 圳(1989-),男,河南唐河人,在讀碩士研究生,主要研究方向?yàn)閳D像處理、模式識(shí)別。

(編輯：劉 勇)

Path planning for mobile robot based on improved ant colony algorithm

ZHU Haodong, SUN Zhen, WU Di, SHEN Zhen

(School of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, P.R. China)

In order to solve the problem that the ant colony algorithm was used in path planning for mobile robot, and is easily falls into local optimum and has a slow convergence speed, the paper proposes a method that the improved ant colony algorithm was used in path planning for mobile robot in the static environment. The method improves the transition rule of node state to increase the probability of searching optimal path. An adaptive heuristic function improves the searching efficiency of the algorithm. Updating the pheromone avoids falling into local optimum based on the assignment rule of wolves. Dynamical adjustment of the decay parameter increases the probability of choosing the optimal path by ants at a later stage, thus accelerating the convergence speed. The simulation results show that the improved algorithm has faster convergence speed under the condition of the same result of path planning when compared to other algorithm in the same environment. The improved algorithm obtains the optimal path in the environments of different complexity levels and it shows the efficiency and feasibility of the improved algorithm, which has good optimization ability and can be applied to path planning for mobile robot in the environments of different complexity levels.

mobile robot; ant colony algorithm; path planning

10.3979/j.issn.1673-825X.2016.06.017

2015-06-18

2016-03-10

朱顥東 zhuhaodong80@163.com

國(guó)家自然科學(xué)基金(61201447);河南省高等學(xué)校青年骨干教師資助計(jì)劃項(xiàng)目(2014GGJS-084);河南省科技創(chuàng)新杰出人才計(jì)劃項(xiàng)目(134200510025);河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目 (13A520367);鄭州輕工業(yè)學(xué)院校級(jí)青年骨干教師培養(yǎng)對(duì)象資助計(jì)劃項(xiàng)目(XGGJS02);鄭州輕工業(yè)學(xué)院博士科研基金(2010BSJJ038);鄭州輕工業(yè)學(xué)院研究生科技創(chuàng)新基金

Foundation Items：The National Natural Science Foundation of China (61201447);The Youth Backbone Teachers Funding Planning Project of Colleges and Universities in Henan Province of China(2014GGJS-084);The Technology Innovation Outstanding Talents Plan Project of Henan Province of China(134200510025);The Science and Technology Research Key Project of Education Department of Henan Province of China (13A520367);The Youth Backbone Teachers Training Targets Funded Project of Zhengzhou University of Light Industry of Henan Province of China(XGGJS02);The Ph.D.Research Funded Project of Zhengzhou University of Light Industry of Henan Province of China (2010BSJJ038) ;The Science and Technology Innovation Fund Project of Postgraduate of Zhengzhou University of Light Industry

TP301

A

1673-825X(2016)06-0849-07