動(dòng)態(tài)環(huán)境下基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃研究

屈 鴻，黃利偉，柯 星

?

動(dòng)態(tài)環(huán)境下基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃研究

屈 鴻，黃利偉，柯 星

(電子科技大學(xué)計(jì)算智能實(shí)驗(yàn)室 成都 611731)

針對動(dòng)態(tài)復(fù)雜條件下的移動(dòng)機(jī)器人路徑規(guī)劃問題，根據(jù)全局靜態(tài)環(huán)境先驗(yàn)知識(shí)，提出一種改進(jìn)蟻群算法。在經(jīng)典蟻群算法的基礎(chǔ)上通過調(diào)整轉(zhuǎn)移概率，限定信息素強(qiáng)度的上下界，并引入相關(guān)策略解決死鎖問題，可以避免初期規(guī)劃的盲目性，增加解的多樣性，提高算法的全局搜索能力，進(jìn)一步減小算法早熟的可能性。在規(guī)劃過程中，根據(jù)動(dòng)態(tài)障礙物運(yùn)行方向的變化與否，提出了相應(yīng)的碰撞避免策略，并針對環(huán)境突發(fā)狀況引入Follow_wall行為進(jìn)行改進(jìn)。仿真實(shí)驗(yàn)證明，該算法優(yōu)于經(jīng)典蟻群算法，可有效地指導(dǎo)移動(dòng)機(jī)器人避免環(huán)境中的動(dòng)態(tài)障礙物，獲取無碰最優(yōu)或次優(yōu)路徑，并能更好地適應(yīng)環(huán)境的變化。

蟻群算法; 動(dòng)態(tài)復(fù)雜環(huán)境; 移動(dòng)機(jī)器人; 路徑規(guī)劃

在給定運(yùn)行空間中，移動(dòng)機(jī)器人路徑規(guī)劃的主要目標(biāo)是通過一定的算法尋求一條從起始位置到目標(biāo)位置的最優(yōu)或次優(yōu)無碰路徑。目前針對全局信息已知的靜態(tài)環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃的研究已經(jīng)很成熟。但是如何在有動(dòng)態(tài)障礙物的環(huán)境背景下進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃仍是一個(gè)難題。

1 環(huán)境描述

設(shè)二維平面上的矩形區(qū)域E為機(jī)器人的運(yùn)行環(huán)境空間。對機(jī)器人運(yùn)行環(huán)境空間的建模采用柵格法，且其中同時(shí)存在靜態(tài)和動(dòng)態(tài)障礙物。靜態(tài)障礙物可以是任意形狀，且數(shù)量有限；動(dòng)態(tài)障礙物為圓形且數(shù)量有限。若靜態(tài)障礙物只占據(jù)某個(gè)柵格的一部分，則將其視為完全占據(jù)此柵格。此外對移動(dòng)機(jī)器人運(yùn)行環(huán)境和移動(dòng)機(jī)器人本身做出以下假設(shè)：

2) 環(huán)境中靜態(tài)障礙物位置信息已知，并進(jìn)行“膨化”處理，以確保靜態(tài)障礙物邊界為安全區(qū)域。

3) 環(huán)境中動(dòng)態(tài)障礙物視為圓形，其直徑為單個(gè)柵格寬度(即為1)且其速度固定，但方向不定，不會(huì)和環(huán)境中的靜態(tài)障礙物及邊界發(fā)生碰撞。

4) 移動(dòng)機(jī)器人能夠通過傳感器感知有限范圍環(huán)境中動(dòng)態(tài)障礙物的運(yùn)行速度和方向。

5) 移動(dòng)機(jī)器人和動(dòng)態(tài)障礙物的可移動(dòng)方向如圖1所示。

6) 移動(dòng)機(jī)器人可在勻速運(yùn)動(dòng)與暫停兩種運(yùn)行狀態(tài)下任意轉(zhuǎn)換。

圖1 移動(dòng)機(jī)器人和動(dòng)態(tài)障礙物可移動(dòng)方向示意圖

2 經(jīng)典蟻群算法的改進(jìn)

蟻群算法[1]提出至今，國內(nèi)外學(xué)者對其進(jìn)行了大量的研究，并已被廣泛地應(yīng)用于解決旅行商問題[2]、路由問題[3]、工件排序問題[4]、車輛運(yùn)輸調(diào)度問題[5]、圖著色問題[6]、機(jī)器人路徑規(guī)劃問題[7-8]。

經(jīng)典蟻群算法中螞蟻通過向著信息素濃度較高的路徑移動(dòng)來尋找最優(yōu)路徑，這種正反饋機(jī)制可以加快收斂速度，但會(huì)導(dǎo)致蟻群多樣性減小，全局搜索能力減弱。此外在一些比較復(fù)雜的環(huán)境下，蟻群算法可能進(jìn)入死鎖狀態(tài)。為保證蟻群算法能夠收斂到全局最優(yōu)或近似最優(yōu)并解決死鎖問題，針對其存在的不足之處，本文做出以下的改進(jìn)。

1) 調(diào)整轉(zhuǎn)移概率

在經(jīng)典蟻群算法的轉(zhuǎn)移概率基礎(chǔ)上引入隨機(jī)選擇機(jī)制以增加解的多樣性。操作如下：設(shè)置隨機(jī)選擇參數(shù)，及隨機(jī)數(shù)。如果，查看當(dāng)前節(jié)點(diǎn)周圍所有節(jié)點(diǎn)的信息，排除有障礙物節(jié)點(diǎn)和已走節(jié)點(diǎn)后，隨機(jī)選取任意一個(gè)節(jié)點(diǎn)作為可行節(jié)點(diǎn)；如果，則需要計(jì)算轉(zhuǎn)移概率，然后根據(jù)轉(zhuǎn)移概率值來選擇下一個(gè)可行節(jié)點(diǎn)。新的可行節(jié)點(diǎn)選取為：

(2)

2) 信息素閾值限定

為進(jìn)一步提高算法的全局搜索能力，借鑒最大最小螞蟻系統(tǒng)(MMAS)，在算法每次迭代中，全局更新最優(yōu)路徑上的信息素時(shí)，對其進(jìn)行上下界限定。限定公式為：

3) 死鎖問題處理

當(dāng)環(huán)境條件較為復(fù)雜時(shí)，移動(dòng)機(jī)器人可能陷入死鎖狀態(tài)。如圖2所示，機(jī)器人運(yùn)行到時(shí)，無法向其周圍任意位置移動(dòng)，即陷入死鎖狀態(tài)。

圖2 移動(dòng)機(jī)器人進(jìn)入死鎖狀態(tài)

針對死鎖問題，文獻(xiàn)[9]采取“早期死亡”(early death)方法，該方法的主要思想為令處于死鎖狀態(tài)的螞蟻死亡，且不對其已走路徑的信息素進(jìn)行更新。但當(dāng)有較多螞蟻陷入死鎖狀態(tài)時(shí)，該方法不利于全局最優(yōu)解的搜索且會(huì)減小解的多樣性。對此，本文的解決方法如下：當(dāng)螞蟻陷入死鎖時(shí)，允許其回退一步，不令其死亡，然后更新禁忌表信息，并對死鎖邊上信息素進(jìn)行懲罰，在當(dāng)前路徑上螞蟻重新選擇移動(dòng)節(jié)點(diǎn)，如此即可避免其他螞蟻陷入死鎖。信息素懲罰函數(shù)為：

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

綜上所述，具體的改進(jìn)蟻群算法流程如下：

1) 對環(huán)境的建模采用柵格法，并初始化移動(dòng)機(jī)器人起始位置和目標(biāo)位置及相關(guān)參數(shù)。

3) 若螞蟻在搜索路徑時(shí)陷入死鎖狀態(tài)，則采取死鎖問題處理方法。若目標(biāo)點(diǎn)到達(dá)，則令，隨后轉(zhuǎn)到步驟2)，直到此次迭代過程中每一只螞蟻的搜索都已完成時(shí)結(jié)束，此時(shí)。

對應(yīng)的流程圖如圖3所示。

圖3 改進(jìn)蟻群算法流程圖

4 動(dòng)態(tài)環(huán)境避碰規(guī)劃策略

4.1 直線運(yùn)動(dòng)障礙物預(yù)測避碰

若環(huán)境中存在直線運(yùn)動(dòng)的障礙物，模擬滾動(dòng)窗口，預(yù)測移動(dòng)機(jī)器人與動(dòng)態(tài)障礙物在一個(gè)滾動(dòng)窗口周期內(nèi)的運(yùn)行軌跡，通過判斷它們是否相交來判斷碰撞是否發(fā)生，相應(yīng)的碰撞避免策略如下：

1) 若移動(dòng)機(jī)器人與動(dòng)態(tài)障礙物無碰撞，則其按原始路徑移動(dòng)一個(gè)步長進(jìn)入下個(gè)滾動(dòng)窗口；

2) 若移動(dòng)機(jī)器人與動(dòng)態(tài)障礙物發(fā)生側(cè)面碰撞，則其在到達(dá)碰撞點(diǎn)之前停頓時(shí)間，隨后繼續(xù)按原始路徑行進(jìn)。的值為：

3) 若兩者發(fā)生正面碰撞，則重新規(guī)劃一條局部路徑。

①將滾動(dòng)窗口邊界與原始路徑的交點(diǎn)所在柵格設(shè)為局部子目標(biāo)。

②視碰撞處柵格為靜態(tài)障礙物，然后由當(dāng)前位置至局部子目標(biāo)點(diǎn)，利用改進(jìn)蟻群算法獲得無碰最優(yōu)局部路徑。

4) 再次根據(jù)相應(yīng)策略進(jìn)行預(yù)測避碰，此次將移動(dòng)機(jī)器人置于規(guī)劃好的局部路徑中。

但當(dāng)環(huán)境條件較為復(fù)雜時(shí)，“局部子目標(biāo)不可達(dá)”的現(xiàn)象可能會(huì)出現(xiàn)。如圖4所示，在位置處，機(jī)器人在當(dāng)前滾動(dòng)窗口內(nèi)探測到動(dòng)態(tài)障礙物的存在，且將在點(diǎn)處發(fā)生正面碰撞。若根據(jù)上述步驟進(jìn)行規(guī)劃，則無法規(guī)劃出局部路徑。

圖4 局部子目標(biāo)不可達(dá)

針對以上問題，本文采用如下方法：

1) 機(jī)器人不再規(guī)劃局部路徑，通過改進(jìn)蟻群算法將發(fā)生碰撞處柵格視為靜態(tài)障礙物獲得一條新的全局路徑。

2) 機(jī)器人將規(guī)劃出來的新的路徑作為原始路徑，并沿此路徑進(jìn)行局部路徑規(guī)劃。

4.2 運(yùn)行方向不定障礙物預(yù)測避碰

針對動(dòng)態(tài)障礙物運(yùn)行方向不確定的情況，文獻(xiàn)[10]中的策略(以下稱為策略一)是對動(dòng)態(tài)障礙物進(jìn)行膨化處理后，視整個(gè)膨化區(qū)域?yàn)殪o態(tài)障礙物，然后通過判斷移動(dòng)機(jī)器人的運(yùn)行軌跡是否與膨化區(qū)域相交來判斷碰撞是否存在，進(jìn)而進(jìn)行局部路徑規(guī)劃，但該做法具有很大的保守性。對此，本文提出一種新策略(以下稱為策略二)來避免移動(dòng)機(jī)器人與動(dòng)態(tài)障礙物發(fā)生碰撞，兩種策略的性能比較在仿真實(shí)驗(yàn)部分給出。

策略二的主要步驟如下：

1) 若預(yù)測到碰撞可能發(fā)生，則將時(shí)間分為等份，即，對應(yīng)時(shí)間內(nèi)移動(dòng)機(jī)器人的步長為。

4) 按照步驟3)規(guī)劃出的局部路徑，移動(dòng)機(jī)器人行進(jìn)并進(jìn)行預(yù)測避碰。

本文的策略能夠減小碰撞可能發(fā)生時(shí)的動(dòng)態(tài)障礙物的膨化區(qū)域，從而可以提供更好的規(guī)劃路徑，進(jìn)而對移動(dòng)機(jī)器人進(jìn)行有效的指導(dǎo)。兩種策略的對比分析在仿真實(shí)驗(yàn)部分給出。

4.3 局部滾動(dòng)預(yù)測避碰算法

結(jié)合上述碰撞避免策略和滾動(dòng)窗口原理，本文提出局部滾動(dòng)預(yù)測避碰算法，其主要步驟如下：

1) 相關(guān)參數(shù)初始化，主要有起始位置、目標(biāo)位置、機(jī)器人步長以及滾動(dòng)窗口半徑，并根據(jù)環(huán)境先驗(yàn)知識(shí)不考慮動(dòng)態(tài)障礙物，由改進(jìn)蟻群算法規(guī)劃全局路徑Gpath。

2) 機(jī)器人按全局路徑以滾動(dòng)窗口方式行進(jìn)，刷新當(dāng)前所在滾動(dòng)窗口內(nèi)的環(huán)境信息，判斷其是否到達(dá)目標(biāo)點(diǎn)，若到達(dá)，則算法終止。

3) 在滾動(dòng)窗口內(nèi)進(jìn)行碰撞檢測，若無碰撞，機(jī)器人按原始路徑移動(dòng)一個(gè)步長，轉(zhuǎn)步驟2)。

4) 根據(jù)碰撞避免策略，規(guī)劃局部路徑Lpath，機(jī)器人沿此路徑行進(jìn)，轉(zhuǎn)步驟2)。

首先由改進(jìn)蟻群算法規(guī)劃出一條全局路徑，然后根據(jù)實(shí)時(shí)的局部環(huán)境信息，將預(yù)測避碰策略用于滾動(dòng)窗口內(nèi)，進(jìn)行局部滾動(dòng)預(yù)測避碰。由此避免與所有動(dòng)態(tài)障礙物碰撞，隨滾動(dòng)窗口逐步推進(jìn)目標(biāo)點(diǎn)，最終獲取無碰最優(yōu)或次優(yōu)路徑。

5 仿真實(shí)驗(yàn)

5.1 改進(jìn)蟻群算法性能比較

本文的實(shí)驗(yàn)對比了改進(jìn)蟻群算法和經(jīng)典蟻群算法并驗(yàn)證了其對死鎖問題的處理。蟻群算法相關(guān)參數(shù)如表1所示，經(jīng)典蟻群算法無懲罰系數(shù)設(shè)置，實(shí)驗(yàn)環(huán)境為VC++6.0。圖5為兩種蟻群算法規(guī)劃出的全局路徑。圖6為運(yùn)行過程中兩種蟻群算法在最短路徑長度和收斂速度兩方面性能的比較。兩種算法分別運(yùn)行100次后，各指標(biāo)的統(tǒng)計(jì)結(jié)果如表2所示。

表1 改進(jìn)蟻群算法相關(guān)參數(shù)設(shè)置

圖5 經(jīng)典蟻群算法與改進(jìn)蟻群算法路徑規(guī)劃結(jié)果

表2 經(jīng)典蟻群算法與改進(jìn)蟻群算法性能比較

由改進(jìn)蟻群算法獲取的全局無碰最優(yōu)路徑如圖5中實(shí)線所示，而由經(jīng)典蟻群算法獲取的全局無碰最優(yōu)路徑為圖5中的虛線路徑。

圖6中數(shù)據(jù)顯示出改進(jìn)蟻群算法的收斂速度比經(jīng)典蟻群算法要快，而且這兩種算法所獲取的最短路徑長度前者優(yōu)于后者。

由表2得出，改進(jìn)蟻群算法與經(jīng)典蟻群算法相比，其最短路徑長度、最優(yōu)解比例以及平均耗時(shí)都有一定的提升。在改進(jìn)蟻群算法條件下，沒有螞蟻進(jìn)入死鎖狀態(tài)且所有螞蟻都獲得了最優(yōu)路徑，這一點(diǎn)可以從最優(yōu)解比例為100%得出。同時(shí)說明改進(jìn)蟻群算法可以有效避免死鎖問題。由以上實(shí)驗(yàn)數(shù)據(jù)得出，相比于經(jīng)典蟻群算法，改進(jìn)蟻群算法可以加快收斂速度，時(shí)間性能也有所提升，并且能有效地避免局部最優(yōu)和死鎖問題。

圖6 經(jīng)典蟻群算法與改進(jìn)蟻群算法收斂速度和最短路徑長度比較

5.2 動(dòng)態(tài)環(huán)境下改進(jìn)蟻群算法的可行性

本文的仿真實(shí)驗(yàn)驗(yàn)證了環(huán)境空間中存在動(dòng)態(tài)障礙物時(shí)，由本文提出的改進(jìn)蟻群算法所規(guī)劃出路徑的可行性。

仿真實(shí)驗(yàn)中，環(huán)境運(yùn)行區(qū)域被劃分為100′80的柵格，移動(dòng)機(jī)器人起始位置坐標(biāo)為，目標(biāo)位置坐標(biāo)為，步長為，感知半徑為。此外，環(huán)境中存在4個(gè)動(dòng)態(tài)障礙物、、和，其中和做直線運(yùn)動(dòng)，和運(yùn)動(dòng)方向不確定，且每經(jīng)過一個(gè)柵格后，移動(dòng)方向隨機(jī)變化。動(dòng)態(tài)障礙物移動(dòng)步長為2。機(jī)器人運(yùn)行環(huán)境如圖7所示，實(shí)驗(yàn)環(huán)境為VC++6.0。

首先由改進(jìn)蟻群算法根據(jù)靜態(tài)全局環(huán)境的先驗(yàn)信息且不考慮動(dòng)態(tài)障礙物的情況下，規(guī)劃出一條全局最優(yōu)路徑，然后移動(dòng)機(jī)器人按此路徑行進(jìn)并進(jìn)行預(yù)測避碰。規(guī)劃的全局路徑如圖7中虛線所示。

圖7 移動(dòng)機(jī)器人環(huán)境空間及全局最優(yōu)路徑

在2時(shí)刻，機(jī)器人到達(dá)位置。在當(dāng)前滾動(dòng)窗口內(nèi)檢測到直線運(yùn)動(dòng)的動(dòng)態(tài)障礙物。根據(jù)“直線運(yùn)動(dòng)障礙物預(yù)測避碰”方法，得出移動(dòng)機(jī)器人與動(dòng)態(tài)障礙物將在位置發(fā)生側(cè)碰。機(jī)器人通過在位置處停留時(shí)間，此過程如圖8b所示，如此則可避免與動(dòng)態(tài)障礙物碰撞。

a. 動(dòng)態(tài)障礙物方向不確定且無碰撞

b. 動(dòng)態(tài)障礙物直線運(yùn)動(dòng)且發(fā)生側(cè)碰

c. 動(dòng)態(tài)障礙物直線運(yùn)動(dòng)且發(fā)生正碰

d. 動(dòng)態(tài)障礙物方向不確定且發(fā)生碰撞

e. 初始路徑有障礙物停留

由實(shí)驗(yàn)結(jié)果得，本文的避碰策略優(yōu)于文獻(xiàn)[10]中的策略。如圖8d所示，當(dāng)檢測到碰撞有可能發(fā)生時(shí)，策略一對動(dòng)態(tài)障礙物進(jìn)行膨化處理。此做法保守性很大，將大部分的可行區(qū)域都膨化成為了靜態(tài)障礙物。另外，這也常常引起在某些情況下，存在移動(dòng)機(jī)器人無法規(guī)劃出可行路徑或者規(guī)劃出來的路徑較長的問題。在檢測到可能存在碰撞時(shí)，本文的策略二只對動(dòng)態(tài)障礙物進(jìn)行膨化處理，并減小移動(dòng)機(jī)器人的步長，通過減小相應(yīng)的膨化區(qū)域，從而進(jìn)一步檢測碰撞是否發(fā)生。策略二的做法，可增加機(jī)器人的可行區(qū)域，從而能夠更高效地指導(dǎo)其進(jìn)行路徑規(guī)劃。

圖9中所示路徑即為本文所提改進(jìn)蟻群算法指導(dǎo)移動(dòng)機(jī)器人所獲得的無碰最優(yōu)路徑。

圖9 移動(dòng)機(jī)器人最終的全局無碰路徑

6 結(jié) 論

本文研究了動(dòng)態(tài)復(fù)雜環(huán)境下，基于環(huán)境先驗(yàn)知識(shí)的單移動(dòng)機(jī)器人路徑規(guī)劃問題，利用改進(jìn)蟻群算法獲取全局路徑，并結(jié)合滾動(dòng)窗口原理進(jìn)行局部滾動(dòng)預(yù)測避碰，最終獲取無碰最優(yōu)路徑。本文考慮了動(dòng)態(tài)障礙物直線運(yùn)動(dòng)和運(yùn)動(dòng)方向不確定的情況，給出了相應(yīng)的碰撞避免策略，并針對不能適應(yīng)環(huán)境變化的缺陷，加入Follow_wall行為。仿真實(shí)驗(yàn)證明了本文算法的有效性，但是針對動(dòng)態(tài)復(fù)雜情況下多移動(dòng)機(jī)器人的路徑規(guī)劃問題，還有待于進(jìn)一步的學(xué)習(xí)和研究。

[1] DORIGO M, MANIEZZO V, COLORNI A. Ant system: Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics. Part B: Cybernetics, 1996, 26(1): 29-41.

[2] BAI J, YANG G K, CHEN Y W, et al. A model induced max-min ant colony optimization for asymmetric traveling salesman problem[J]. Applied Soft Computing, 2013, 13(3): 1365-1375.

[3] 任敬安, 涂亞慶. 基于蟻群優(yōu)化的Ad hoc網(wǎng)絡(luò)路由協(xié)議實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程, 2012, 38(11): 114-118

REN Jing-an, TU Ya-qing. Implementation of Ad hoc network routing protocol based on ant colony optimization[J]. Computer Engineering, 2012, 38(11): 114-118.

[4] 王欣盛, 馬良. 工件排序的改進(jìn)蟻群算法優(yōu)化[J]. 上海理工大學(xué)學(xué)報(bào), 2011, 33(4): 362-366

WANG Xin-sheng, MA Liang. Improved ant colony optimization for scheduling problem[J]. Journal of University of Shanghai for Science and Technology, 2011, 33(4): 362-366

[5] ZENG Y, LIU D, HOU X. Complex vehicle scheduling optimization problem based on improved ant colony algorithm[C]//Proceedings of the 2012 International Conference on Information Technology and Software Engineering. Berlin: Springer, 2013: 805-812.

[6] CONSOLI P, COLLERA A, PAVONE M. Swarm intelligence heuristics for graph coloring problem[C]//IEEE Congress on Evolutionary Computation. [S.l.]: IEEE, 2013: 1909-1916.

[7] DENG X, ZHANG L, LUO L. An improved ant colony optimization applied in robot path planning problem[J]. Journal of Computers, 2013, 8(3): 585-593.

[8] TANG B W, ZHU Z X, FANG Q, et al. Path planning and replanning for intelligent robot based on improved ant colony algorithm[J]. Applied Mechanics and Materials, 2013, 390: 495-499.

[9] DONG S W, HUA F Y. Path planning of mobile robot in dynamic environments[C]//2nd International Conference on Intelligent Control and Information Processing (ICICIP). [S.l.]: IEEE, 2011, 2: 691-696.

[10] 王一可.基于滾動(dòng)窗口的多機(jī)器人協(xié)調(diào)路徑規(guī)劃算法研究[D]. 上海: 上海交通大學(xué), 2004.

WANG Yi-ke. A study of multi-robot cooperative path planning based on rolling windows[D]. Shanghai: Shanghai Jiaotong University, 2004.

編 輯 黃 莘

Research of Improved Ant Colony Based Robot Path Planning Under Dynamic Environment

QU Hong, HUANG Li-wei, and KE Xing

(Computing Intelligence Lab, University of Electronic Science and Technology of China Chengdu 611731)

This paper presents an improved ant colony algorithm for mobile robot path planning under dynamic complex conditions based on prior knowledge of global static environment. On the basis of conventional ant colony algorithm, by adjusting the transition probability, limiting the bounds of pheromone, and introducing relevant strategy to solve the deadlock problem, the improved ant colony algorithm not only can avoid the blindness of early planning and increase the diversity of solutions, but also can improve global search capability of the algorithm, and further reduce the possibility of algorithm prematurity as well. During the planning process, according to the direction changes of the dynamic obstacles, corresponding collision avoidance strategies are put forward. The Follw_wall behavior is introduced for unexpected situations in the environment. Simulation results show that the proposed algorithm is superior to conventional ant colony algorithm. It can effectively guide the mobile robot to avoid dynamic obstacles. Thus obtains a collision free optimal or suboptimal path, which adapts to the changes of the environment more effectively.

ant colony algorithm; dynamic complex environment; mobile robot; path planning

TP312

A

10.3969/j.issn.1001-0548.2015.02.017

2014-03-20;

2014-05-30

國家自然科學(xué)基金(61273308)；中央高?；究蒲袠I(yè)務(wù)費(fèi)(ZYGX2012J068)

屈鴻(1977-)，男，博士，副教授，主要從事機(jī)器學(xué)習(xí)、計(jì)算智能等方面的研究.