一種新型蟻群隨機(jī)樹的機(jī)器人路徑規(guī)劃算法

白金柯，吳曉娜

(河南化工職業(yè)學(xué)院，河南 鄭州 450042)

Robot-path Planning Based on Ant Colony Optimization and Rapidly-exploring Random Tree

BAI Jinke，WU Xiaona

(Henan Vocational College of Chemical Technology，Zhengzhou 450042 China)

一種新型蟻群隨機(jī)樹的機(jī)器人路徑規(guī)劃算法

白金柯，吳曉娜

(河南化工職業(yè)學(xué)院，河南 鄭州 450042)

Robot-path Planning Based on Ant Colony Optimization and Rapidly-exploring Random Tree

BAI Jinke，WU Xiaona

(Henan Vocational College of Chemical Technology，Zhengzhou 450042 China)

摘要：為提高復(fù)雜環(huán)境下機(jī)器人的路徑規(guī)劃效率，提出了一種用蟻群算法來優(yōu)化隨機(jī)樹算法的新的全局路徑規(guī)劃算法。該算法有效地結(jié)合了蟻群和隨機(jī)樹算法的優(yōu)點(diǎn)，利用隨機(jī)樹算法的高效性快速收斂到一條可行路徑，將該路徑轉(zhuǎn)換為蟻群的初始信息素分布，可以減少蟻群算法初期迭代；然后利用蟻群算法的反饋性優(yōu)化路徑，求得最優(yōu)路徑。仿真實(shí)驗(yàn)表明，該蟻群隨機(jī)樹算法可以提高機(jī)器人路徑規(guī)劃的速度，并且在任何復(fù)雜環(huán)境下迅速規(guī)劃出最優(yōu)路徑。

關(guān)鍵詞：路徑規(guī)劃；隨機(jī)樹算法；高效完備性；蟻群算法；正反饋性

中圖分類號：TP302

文獻(xiàn)標(biāo)識碼：A

文章編號：1001-2257(2015)07-0073-04

收稿日期：2015-01-19

基金項目：河南省基礎(chǔ)與前沿技術(shù)研究計劃項目(142300410283)；河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項目(12B520063，14B520065)；河南省高等學(xué)校青年骨干教師資助計劃項目(2013GGJS-230)

作者簡介：白金柯(1984-)，男，河南鞏義人，助教，碩士研究生，研究方向?yàn)槿斯ぶ悄?、路徑?guī)劃。

Abstract：In order to improve robotic efficiency of path planning in a complex environment, this paper proposes a global path planning algorithm which makes use of ant colony optimization (ACO) to optimize rapidly-exploring random tree algorithm. The new algorithm effectively combines the strengths of the two algorithms, taking advantage of the high efficiency of the rapidly-exploring random algorithm to quickly converge a possible path, make it into a ACO initial distribution of pheromones, reduce the number of iterations and accelerate the convergence. At the same time, by using the positive feedback technology, the process of finding the optimum path is effectively improved. The simulation experiment shows that the algorithm increases the efficiency of robotic path planning greatly and can plan the best path in a complex environment quickly.

Key words：path planning; rapidly-exploring random tree; efficiency and completeness;ant colony optimization; positive feedback

0引言

路徑規(guī)劃是智能機(jī)器人研究領(lǐng)域的重要內(nèi)容。機(jī)器人路徑規(guī)劃的定義是，在含有障礙物的環(huán)境中，尋找一條合適的路徑使機(jī)器人能夠從任意起點(diǎn)運(yùn)動到終點(diǎn)，且在運(yùn)動過程中機(jī)器人應(yīng)不碰撞到障礙物，路徑最優(yōu)。全局路徑規(guī)劃主要是事先獲得環(huán)境信息，通過建立合適模型來搜索獲得全局最優(yōu)路徑[1]。目前常用的全局路徑規(guī)劃方法主要有：人工勢場法、柵格法和各種智能算法等[2-4]。人工勢場法算法簡單效率高，容易易于實(shí)現(xiàn)，且規(guī)劃的路徑較平滑，但是會出現(xiàn)遇到障礙物振蕩、局部極值點(diǎn)等問題；柵格法一般可以較快速求得最優(yōu)解，但是求解質(zhì)量受柵格大小設(shè)置的影響，同時當(dāng)搜索空間變大時占用的大量的存儲空間。近年來提出的智能算法如：蟻群算法、神經(jīng)網(wǎng)絡(luò)、遺傳算法等在路徑規(guī)劃領(lǐng)域廣泛應(yīng)用，這類算法都有優(yōu)點(diǎn)，但是都有一定局限性難以適應(yīng)路徑規(guī)劃的要求[5]。因此需要不斷尋找更新的算法，以適應(yīng)路徑規(guī)劃的更高需求。

蟻群算法(ACO)是一種仿生型智能算法[6-7]，主要通過螞蟻群體內(nèi)部的信息傳遞從而實(shí)現(xiàn)路徑優(yōu)化的目的，具有信息反饋、分布計算和啟發(fā)式搜索等特征。廣泛的應(yīng)用與路徑規(guī)劃問題，但普遍存在初期蟻群信息素匱乏，收斂速度慢的問題。

快速擴(kuò)展隨機(jī)樹(RRT)是目前廣泛應(yīng)用的基于采樣的單查詢運(yùn)動規(guī)劃方法[8]。該算法能夠快速地搜索整個環(huán)境，通過對環(huán)境中點(diǎn)隨機(jī)采樣，把搜索導(dǎo)向未搜索區(qū)域，從而搜素出一條從起點(diǎn)到終點(diǎn)的路徑。由于該算法隨機(jī)性，所以具有概率完備性。在有解的前提下，可保證算法獲得可行解。但隨機(jī)樹算法也存在重復(fù)性差，規(guī)劃出的路徑非最優(yōu)路徑等問題。

綜上，首先用隨機(jī)樹算法規(guī)劃出全局環(huán)境下一個可行路徑，作為蟻群算法初始信息素分布，再通過蟻群算法對路徑進(jìn)行優(yōu)化，有效提高算法收斂速度。大量仿真實(shí)驗(yàn)表明該方法效果十分滿意。

1蟻群隨機(jī)樹算法的路徑規(guī)劃

基于蟻群隨機(jī)樹路徑規(guī)劃算法的基本思想是結(jié)合隨機(jī)樹的快速收斂性和蟻群算法最優(yōu)的特點(diǎn)，快速找到一條最優(yōu)路徑。雖然隨機(jī)樹收斂速度非?？?，但是求得的路徑不一定是最優(yōu)路徑，同時，同一問題多次規(guī)劃可得到多個結(jié)果，可重復(fù)性差；蟻群算法能得到全局最優(yōu)路徑，但速度慢，效率低。本文先利用隨機(jī)樹算法生成一條路徑，然后將這條路徑用蟻群算法進(jìn)行優(yōu)化，該混合算法不僅提高蟻群算法效率，也增強(qiáng)了隨機(jī)樹算法的精度。通過仿真實(shí)驗(yàn)，該算法結(jié)果令人滿意。

1.1　初始化路徑

隨機(jī)樹算法是路徑規(guī)劃中常用的一種算法。每次路徑選擇是以搜索空間中當(dāng)前的點(diǎn)作為根節(jié)點(diǎn)，隨機(jī)向四周采樣，逐漸增加節(jié)點(diǎn)，生成一個隨機(jī)樹。當(dāng)隨機(jī)樹的節(jié)點(diǎn)中包含終點(diǎn)時，在隨機(jī)樹的節(jié)點(diǎn)中找到一條包含起點(diǎn)和終點(diǎn)的樹節(jié)點(diǎn)作為規(guī)劃路徑。

隨機(jī)樹構(gòu)建方法如圖1所示。圖中為一個擁有若干節(jié)點(diǎn)的隨機(jī)樹，x為T的節(jié)點(diǎn)，且Tk∈Cfree。同時定義xinit為初始位置，xgoal為目標(biāo)位置xgoal∈Cfree。令xrand表示在C空間中隨機(jī)選取的一個點(diǎn)，且xrand∈Cfree。

圖1　RRT的構(gòu)建過程

由于隨機(jī)樹具有較好的完備性，包含了所有可能的路徑，但隨機(jī)樹采用隨機(jī)采樣生成，同一任務(wù)多次規(guī)劃會產(chǎn)生多個的結(jié)果，這樣機(jī)器人執(zhí)行同一任務(wù)的重復(fù)性就比較差。同時由于隨機(jī)樹的路徑點(diǎn)由隨機(jī)采樣生成，所規(guī)劃出的路徑并不一定是最優(yōu)路徑。

如圖2所示。圖中的路徑為從起點(diǎn)S到終點(diǎn)G的隨機(jī)樹路徑規(guī)劃，實(shí)線和虛線分別是隨機(jī)樹算法兩次規(guī)劃的路徑PRRT?？梢钥闯鲭S機(jī)樹算法可以找到可行的路徑但是每次規(guī)劃出不同結(jié)果，并不能確定最優(yōu)路徑。因此，采用蟻群算法對路徑進(jìn)行修正，搜索出一條真正有效的全局最優(yōu)路徑。

圖2　RRT算法路徑規(guī)劃

1.2　信息素的構(gòu)建

采用隨機(jī)樹算法進(jìn)行兩次路徑規(guī)劃，將兩次規(guī)劃的路徑轉(zhuǎn)化為蟻群算法的最初信息素分布。由于這些路徑只是相對最優(yōu)路徑，因此，使蟻群在一定范圍內(nèi)進(jìn)行搜索，對路徑進(jìn)行優(yōu)化，最終確定出最優(yōu)的路徑。

首先根據(jù)環(huán)境信息得到蟻群信息素的初始值τi，j(0)，然后將隨機(jī)樹得到的最優(yōu)路徑轉(zhuǎn)換為信息素的初始值Δτi，j，接著對初始信息素的進(jìn)行二次分布，新的信息素量為τi，j，按照式(1)計算。

τi，j=τi，j(0)+Δτi，j

(1)

這樣蟻群有了最初的信息素，蟻群將按照式(1)進(jìn)行路徑選擇。

1.3　基于蟻群算法最優(yōu)路徑規(guī)劃

(2)

螞蟻k(k為任意螞蟻)在運(yùn)動過程中，會根據(jù)當(dāng)前路徑上的信息素的量決定其下一步的移動，假設(shè)在某時刻t，螞蟻k要從任意位置點(diǎn)i向j移動，其下一移動位置的定義為：

(3)

假設(shè)隨時間推移，信息素逐漸地?fù)]發(fā)。用ρ表示單位時間內(nèi)信息素?fù)]發(fā)后的剩余度。假定在經(jīng)過h個時刻后，蟻群完成一輪路徑規(guī)劃。此時，將所有路徑上信息素的量按式(4)調(diào)整規(guī)則進(jìn)行重新設(shè)置。

(4)

上述蟻群隨機(jī)樹算法主要步驟為：

a.根據(jù)環(huán)境信息和隨機(jī)樹得到的初始路徑得到蟻群初始路徑。

b.設(shè)置蟻群數(shù)目和循環(huán)次數(shù)。根據(jù)式(1)分布路徑信息素初始值。

c.啟動蟻群，所有螞蟻根據(jù)蟻群移動規(guī)則式(2)選擇路徑點(diǎn)，進(jìn)行路徑規(guī)劃。

d.重復(fù)步驟c，直至到達(dá)設(shè)定循環(huán)時間或者所有螞蟻到達(dá)終點(diǎn)。

e.計算出每只螞蟻的所走的路徑長度L，求解出最優(yōu)路徑。

f.根據(jù)式(5)對蟻群在各條路徑上的信息素進(jìn)行更新。

g.若蟻群循環(huán)達(dá)到規(guī)定次數(shù)或全部收縮在一條路徑上，結(jié)束循環(huán)。否則轉(zhuǎn)到步聚c，繼續(xù)循環(huán)。

h.輸出本次循環(huán)最優(yōu)路徑。

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

為驗(yàn)證算法的效果，用Matlab軟件進(jìn)行大量仿真實(shí)驗(yàn)。蟻群參數(shù)的設(shè)置為：蟻群數(shù)目Na=40，最大循環(huán)次數(shù)Ma=60，距離信息的重要程度β=2，信息素的重要程度參數(shù)α=1，信息素的揮發(fā)速度ρ=0.3，常數(shù)Q=100。仿真結(jié)果如圖3、圖4所示，其中仿真環(huán)境大小為30 m×30 m。圖3是本文算法在簡單下的搜索的最優(yōu)路徑；圖4是在復(fù)雜環(huán)境下搜索的最優(yōu)路徑。圖3的仿真結(jié)果給出了一個平滑的路徑適合機(jī)器人行走。圖4的仿真結(jié)果表明，只要存在通路，該算法就能迅速規(guī)劃出較優(yōu)路徑。通過多種環(huán)境仿真實(shí)驗(yàn)，結(jié)果表明，不論環(huán)境如何復(fù)雜，本算法都能收斂于全局最優(yōu)路徑。

圖3　環(huán)境1仿真結(jié)果

圖4　環(huán)境2仿真結(jié)果

參考文獻(xiàn)本文提出的蟻群隨機(jī)樹算法和[7]的蟻群算法，在Matlab中進(jìn)行90次仿真的比較，結(jié)果如表1所示。雖然本文混合算法的復(fù)雜性較隨機(jī)樹和蟻群算法高，但由于根據(jù)隨機(jī)樹算法的結(jié)果作為蟻群算法的初始信息素，大大提高蟻群算法效率和隨機(jī)樹算法的準(zhǔn)確度，所以所得結(jié)果的有效性和效率均高于蟻群算法和隨機(jī)樹算法。通過多次仿真，該算法在復(fù)雜環(huán)境下的路徑規(guī)劃，收斂速度快并且收斂路徑均全局最優(yōu)。

表1與蟻群算法的比較

仿真條件蟻群算法本文算法最優(yōu)路徑步數(shù)最優(yōu)解耗時/s最優(yōu)路徑步數(shù)最優(yōu)解耗時/s環(huán)境172.12.3155.81.41環(huán)境283.42.865.61.6

3結(jié)束語

針對機(jī)器人全局路徑規(guī)劃問題，提出了蟻群隨機(jī)樹相結(jié)合的新算法，該算法大大提高蟻群算法的收斂速度，在規(guī)劃速度上和效果上均優(yōu)于蟻群算法。仿真結(jié)果表明，該算法在機(jī)器人路徑規(guī)劃中的效果好具有實(shí)用性。

[1]李磊, 葉濤，譚民，等.移動機(jī)器人技術(shù)研究現(xiàn)狀與未來[J]. 機(jī)器人, 2002, 24(5): 475-480.

[2]Cai Wenbin，Zhu Qingbao，Hu Jun．Path planning based on biphasic ant colony algorithm and fuzzy control in dynamic environment [C]//2010 2nd International Conference on Intelligent Human-Machine Systems and Cybernetics．Hangzhou：Ⅱ E Press，2010：333-336．

[3]Keron Y,Borenstein J. Potential field methods and their inherent limitations for mobile robot navigation [C] // Proceedings of the IEEE International Conference on Robotics and Automation.Piscata way, NJ, USA: IEEE, 1991: 1398-1404.

[4]秦元慶, 孫德寶，李寧，等. 基于粒子群算法的移動機(jī)器人路徑規(guī)劃[J]. 機(jī)器人, 2004, 26(3): 222-225.

[5]吳憲祥, 郭寶龍，王娟.基于粒子群三次樣條優(yōu)化的移動機(jī)器人路徑規(guī)劃算法[J]. 機(jī)器人, 2009, 31(6): 556-561.

[6]Dorigo M, Caro G D. The modified swarm optimization metaheuristic [M] //Come D, Mdorigo, Glover F, Editors. New Ideas in Optimization. Mc London, UK: Graw Hill, 1999: 11-32.

[7]Bonabeau E, Dorigo M, Theraulaz G. Swarm intelligence: from natural to artificial systems [M].New York: Oxford University Press, 1999.

[8]Lavalle S M, Kuffner J. Rapidly exploring random trees:progress and prospects [C] //Proceedings of the International Workshop on Algorithmic Foundations of Robotics. Hanover, USA, 2000: 45-59.