基于粒子群算法的移動機器人全局最優路徑規劃

摘要：以柵格法和粒子群算法為基礎，提出了一種新的機器人實時全局最優路徑規劃方法。該方法包括采用柵格法對環境進行建模和直接運用粒子群算法在環境模型中搜索全局最優路徑。在計算機上進行了仿真，仿真結果證明了該方法的可行性和有效性。

關鍵詞：移動機器人； 粒子群優化算法； 全局最優路徑規劃； 柵格法

中圖分類號：TP242;TP306.1文獻標志碼：A

文章編號：1001-3695(2007)11-0210-03

0引言

在移動機器人相關技術中，導航技術是其核心，而路徑規劃是導航研究中的一個重要環節和課題。路徑規劃是指移動機器人按照某一性能指標（如距離、時間、能量）搜索一條從起始狀態到目標狀態的最優或次優路徑[1]。對于環境信息已知的全局路徑規劃，目前已有許多解決方法，如人工勢場法[2]、可視圖法[3]以及由人工勢場演變而來的數值勢場法[4]等。近十年間，隨著人工智能研究不斷取得進展，許多智能算法也被用到移動機器人的路徑規劃中，包括模糊邏輯與增強學習算法[5]、神經網絡[6]、遺傳算法[4]以及蟻群算法[7]等。

粒子群優化算法是一種進化計算技術(evolutionary computation)[8，9]，由Kennedy和Eberhart發明。其源于對鳥群捕食的行為研究[8]。粒子群優化算法的基本思想是通過群體中個體之間的協作和信息共享來尋找最優解。

柵格法是對平面移動機器人運動路徑規劃的一個抽象模型，是目前研究最廣泛的路徑規劃方法之一。 柵格法由 M.B.Metea 首先提出[10]，用于解決分等級地形的自動化路徑規劃問題。對于柵格法模型的求解有許多研究方法，最經典的有K. Sugibara等人[11]提出的基于遺傳算法的規劃法。不過由于編碼長度隨著柵格數的增加而增大從而大大增加了計算的復雜度，使得該方法只能適用于柵格數不超過16×16的問題。針對這個缺點，李強等人[12]提出了基于四叉樹模型的遺傳算法規劃。該算法具有良好的全局搜索性能，但在搜索效率上較一般的搜索算法（如A* 算法）并無明顯的提高。孫樹棟等人[13]采用柵格欄編碼，縮短了染色體的長度，減少了遺傳算法求解時的計算量。但是，編碼的復雜度增加了，使得運算效率未能得到很好的提高。

本文用柵格法建立環境模型，以粒子群算法為基本演化算法，將粒子群算法直接運用到柵格法中，得到移動機器人全局最優路徑。

1空間建模

本文采用的空間建模方法是柵格法，以機器人自身的最寬尺寸為柵格的粒度。在離散化空間的同時，對障礙物的處理是這樣進行的：

a）不滿一個柵格時算一個柵格。

b）障礙物的空凹部分和這個障礙物算成一個整體障礙物，避免局部死區的出現，這叫做障礙物的合并。

c）地圖的邊界當成障礙物來處理。

考慮到移動機器人在二維平面上運動，忽略機器人的旋轉運動。運動空間中有障礙物Bi， i=1，2，3，…，n。路徑規劃就是尋找從A的初始位置S到目標位置T的避碰路徑。

圖1為一個實際的移動機器人工作環境實例。機器人本身的最大尺寸為20 cm，所以柵格粒度也為20 cm，整個工作環境長寬均為400 cm，共12個障礙物。按照上面所講的方法可以建立如圖2所示的空間模型。模型中的每一個柵格都與一個數組元素對應，有障礙物的黑色區域對應的值為1即障礙物區域；沒有障礙物的白色區域對應的值為0，是自由運動區域。

2粒子群算法

粒子群算法模擬鳥集群飛行覓食的行為，通過鳥之間的集體協作使群體達到目的。在PSO系統中，每個備選解被稱為一個粒子(particle)。粒子i在N維空間中的位置表示為矢量Xi＝(x1，x2，…，xN)；飛行速度表示為矢量Vi＝(v1，v2，…，vN)。每個粒子都有一個由目標函數決定的適應值 (fitness value)，并且知道自己到目前為止發現的最好位置(pbest)和現在的位置Xi，這個可以看做是粒子自己的飛行經驗。除此之外，每個粒子還知道到目前為止整個群體中所有粒子發現的最好位置(gbest) (gbest是pbest中的最好值)，這個可以看做是粒子同伴的經驗。粒子就是通過自己的經驗和同伴中最好的經驗來決定下一步的運動。

3基于粒子群算法的全局最優路徑搜索算法

在已經建立的空間模型中，利用粒子群算法直接找出一條最優路徑。粒子群算法中的每一個粒子都是一個解，也就是一條路徑，粒子群算法從眾多的解中尋找一個最優解。每一個粒子的代價函數是粒子所代表的

路徑長度，在這里具體指的是每一個粒子所跨過的格數。把每一個粒子設置為一個一維數組，數組的元素為20個，如果有n個粒子，那么粒子數組可以用一個n×20的二維數組表示。一個粒子所表的整個路徑由在環境數組中的20個元素組成，這20個元素就是模型空間的20個點，再按照一定的規則換算成一條路徑。換算成連續的路徑后，再計算整條路徑所經過的柵格數，所經過的柵格數目即這個粒子的適應值。適應值越小，路徑越短，粒子越優。如果粒子p的元素p[i]的值為k，則在環境數組中所表示的點為Circum[i][k]。粒子的有效性是指粒子中任意兩個相鄰的元素之間在第i與i+1行、列在p[i]與p[i+1]之間的矩形區域能自由連通，中間不能有障礙物，連通的路線不能迂回。圖3所表示的是幾種有效和無效的實例。

3．1粒子適應值的計算及如何轉換成完整的路徑

對于每一個有效的粒子都對應著一條路徑，其關鍵部分是如何將粒子所代表的在柵格中的20個點連成一條完整的路徑。從粒子的有效性可以看出，粒子兩個相鄰的元素之間至少有一條通道，使得機器人能從柵格的一個點成功地到達另一個點。在該算法中，機器人可以在一定的條件下沿著斜格走，條件是與之都相鄰的兩個柵格的值均為0。沿斜格走時，適應值算一個格子數，可知走斜格可以使粒子的適應值變小，路徑變短。圖4所表示的是粒子能走斜格和不能走斜格時不同的適應值。假設粒子中第i和i+1兩個相鄰元素的適應值表示為fit(i，i+1)，那么整個粒子的適應值可用下式計算：

5結束語

本文以柵格法為環境建模方法，直接將粒子群算法運用到全局最優路徑規劃中，簡單明了，容易實現。其基本分為兩步：a)以機器人自身最大寬度作為柵格粒度，采用柵格法對環境進行建模，得出環境數組Circum[ ][ ]；b)直接運用粒子群算法在環境中搜索全局最優路徑。計算機仿真證明該方法不僅可以找到全局最優路徑，而且算法過程簡單，容易實現，完全可以用于機器人全局最優路徑規劃，不失為機器人路徑規劃方面的一個新方法。

參考文獻:

[1]歐青立，何克忠.室外智能移動機器人的發展及其相關技術研究 [J].機器人，2000，22(6):519-526.

[2]GE S S， CUI Y J. New potential functions for mobile robot path planning[J]. IEEE Transactions on Robotics and Automation， 2000，16(5):615-620.

[3]李磊，葉濤，譚民.移動機器人技術研究現狀與未來[J]. 機器人， 2002，24(5):475-480.

[4]龔進峰，彭商賢.數字勢場和遺傳算法的機器人路徑規劃的方法[J].天津大學學報，2002，35(4):525-529.

[5]YUNG N H C， CANG Ye. An intelligent mobile vehicle navigator based on fuzzy logic and reinforcement learning[J]. IEEE Transactions on Systems， Man， and Cybernetics， 1999，29(2):314-321.

[6]LEBEDEV D. Neural network model for robot path planning in dynamically changing environment[J]. Modeling and Analysis of Information Systems，2001，18(1):12－18.

[7]董玉成，陳義華. 基于螞蟻算法的移動機器人路徑規劃[J].重慶大學學報，2003，26(3):49-51.

[8]KENNEDY J， EBERHART R C. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. Piscataway， NJ: IEEEService Center， 1995:1942-1948.

[9]EBERHART R，KENNEDY J．A new optimizer using particle swarm theory[C]//Proc of the 6th International Symposium on Micro Machine and Human，Science．1995:39-43.

[10]METEA M B. Route planning for intelligent autonomous land vehicles using hierarchical terrain representation[C]//Proc of IEEE Int Conf on Robotics and Automation.1987:1947-1952.

[11]SUGIBARA K， SMITH J. Genetic algorithms for adaptive motion planning of an autonomous mobiles robotics[C]//Proc of IEEE Trans SMS.[S.l.]: MIT，1997:138-143.

[12]李強，林良明，顏國正.基于進化的移動機器人路徑規劃方法[C]//Proc of the 3rd World Congress on Intelligent Control and Autonation，Hefei:[s.n.]，2000:1206-1209.

[13]孫樹棟，曲彥賓.遺傳算法在機器人路徑規劃中的應用研究[J].西北工業大學學報，1998，16(1):79-83.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”