一種新型蟻群隨機樹的機器人路徑規劃算法

白金柯，吳曉娜

(河南化工職業學院，河南 鄭州 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)

一種新型蟻群隨機樹的機器人路徑規劃算法

白金柯，吳曉娜

(河南化工職業學院，河南 鄭州 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)

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

關鍵詞：路徑規劃；隨機樹算法；高效完備性；蟻群算法；正反饋性

中圖分類號：TP302

文獻標識碼：A

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

收稿日期：2015-01-19

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

作者簡介：白金柯(1984-)，男，河南鞏義人，助教，碩士研究生，研究方向為人工智能、路徑規劃。

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引言

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

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

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

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

1蟻群隨機樹算法的路徑規劃

基于蟻群隨機樹路徑規劃算法的基本思想是結合隨機樹的快速收斂性和蟻群算法最優的特點，快速找到一條最優路徑。雖然隨機樹收斂速度非常快，但是求得的路徑不一定是最優路徑，同時，同一問題多次規劃可得到多個結果，可重復性差；蟻群算法能得到全局最優路徑，但速度慢，效率低。本文先利用隨機樹算法生成一條路徑，然后將這條路徑用蟻群算法進行優化，該混合算法不僅提高蟻群算法效率，也增強了隨機樹算法的精度。通過仿真實驗，該算法結果令人滿意。

1.1　初始化路徑

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

隨機樹構建方法如圖1所示。圖中為一個擁有若干節點的隨機樹，x為T的節點，且Tk∈Cfree。同時定義xinit為初始位置，xgoal為目標位置xgoal∈Cfree。令xrand表示在C空間中隨機選取的一個點，且xrand∈Cfree。

圖1　RRT的構建過程

由于隨機樹具有較好的完備性，包含了所有可能的路徑，但隨機樹采用隨機采樣生成，同一任務多次規劃會產生多個的結果，這樣機器人執行同一任務的重復性就比較差。同時由于隨機樹的路徑點由隨機采樣生成，所規劃出的路徑并不一定是最優路徑。

如圖2所示。圖中的路徑為從起點S到終點G的隨機樹路徑規劃，實線和虛線分別是隨機樹算法兩次規劃的路徑PRRT。可以看出隨機樹算法可以找到可行的路徑但是每次規劃出不同結果，并不能確定最優路徑。因此，采用蟻群算法對路徑進行修正，搜索出一條真正有效的全局最優路徑。

圖2　RRT算法路徑規劃

1.2　信息素的構建

采用隨機樹算法進行兩次路徑規劃，將兩次規劃的路徑轉化為蟻群算法的最初信息素分布。由于這些路徑只是相對最優路徑，因此，使蟻群在一定范圍內進行搜索，對路徑進行優化，最終確定出最優的路徑。

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

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

(1)

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

1.3　基于蟻群算法最優路徑規劃

(2)

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

(3)

假設隨時間推移，信息素逐漸地揮發。用ρ表示單位時間內信息素揮發后的剩余度。假定在經過h個時刻后，蟻群完成一輪路徑規劃。此時，將所有路徑上信息素的量按式(4)調整規則進行重新設置。

(4)

上述蟻群隨機樹算法主要步驟為：

a.根據環境信息和隨機樹得到的初始路徑得到蟻群初始路徑。

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

c.啟動蟻群，所有螞蟻根據蟻群移動規則式(2)選擇路徑點，進行路徑規劃。

d.重復步驟c，直至到達設定循環時間或者所有螞蟻到達終點。

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

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

g.若蟻群循環達到規定次數或全部收縮在一條路徑上，結束循環。否則轉到步聚c，繼續循環。

h.輸出本次循環最優路徑。

2仿真實驗

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

圖3　環境1仿真結果

圖4　環境2仿真結果

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

表1與蟻群算法的比較

仿真條件蟻群算法本文算法最優路徑步數最優解耗時/s最優路徑步數最優解耗時/s環境172.12.3155.81.41環境283.42.865.61.6

3結束語

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

[1]李磊, 葉濤，譚民，等.移動機器人技術研究現狀與未來[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]. 機器人, 2004, 26(3): 222-225.

[5]吳憲祥, 郭寶龍，王娟.基于粒子群三次樣條優化的移動機器人路徑規劃算法[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.