一種基于粒子群算法的移動機器人路徑規劃方法

摘 要：針對結構化環境中移動機器人路徑規劃問題，提出一種基于粒子群的路徑規劃算法。該算法利用適應度函數描述環境約束及路徑的距離信息，適應度函數通過神經網絡計算；由路徑節點構成粒子，通過混合粒子群算法進行尋優。最后，通過計算機仿真驗證了該算法是合理的，并且可應用于機器人的實時導航。

關鍵詞：路徑規劃；粒子群；適應度函數；神經網絡

中圖分類號：TP24文獻標志碼：A

文章編號：1001—3695(2007)03—0181—03

0 引言

移動機器人路徑規劃問題是機器人領域核心問題之一[1]，可定義為機器人在具有障礙物的工作空間中按照某種評價標準尋找一條安全無碰路徑。根據機器人對工作空間環境信息的已知程度，路徑規劃問題可被分為全局路徑規劃與局部路徑規劃。將移動機器人技術與RFID（Radio Frequency Iden￣tification，無線射頻識別是一種通過無線射頻方式進行非接觸式自動識別技術）技術相結合并應用于倉庫管理，可取代目前倉庫管理中普遍采用的人工貨物盤點方式，是對移動機器人應用領域的開拓。本文設計實現的路徑規劃算法，其應用目標為中國科學院自動化所自主開發的基于RFID的倉庫巡檢機器人。該倉庫巡檢機器人的工作環境為貨架位置固定的室內環境，其路徑規劃問題可抽象為結構化環境中的全局路徑規劃。

針對全局路徑規劃問題，國內外學者作了大量研究[2]，提出了許多算法，其中應用較多的有人工勢場法、可視圖法。人工勢場法的思想是將機器人看成處于一個虛擬力場中的“點”，規劃目標點對其具有吸引力而障礙物對其具有排斥力，兩種作用力的合力決定機器人運動方向。該方法具有計算量小、實時性好的特點，但由于陷阱區的存在可能導致規劃失敗。可視圖算法的思想是通過已知的障礙物幾何特征將工作空間中的可行區域映射為一個加權圖，然后利用圖搜索策略進行搜索。由于圖搜索算法的完備性，可視圖法能夠規劃出最短路徑，但同時也由于圖搜索算法的復雜性問題，該方法潛在具有組合爆炸的危險。

粒子群算法是Kennedy博士和Eberhart博士于1995年提出的一種集群進化算法[3]。該算法通過模擬鳥群的飛行行為而獲得多維尋優能力，同傳統的集群優化算法如遺傳算法相比，該算法具有實現簡單、收斂速度快的特點。文獻[4]采用Dijkstra算法從鏈接圖中獲得最短路徑，然后應用粒子群算法對該路徑進行二次優化，獲得了長度更短的可行路徑。該算法由于將粒子群算法應用于二次優化，并沒有完全發揮粒子群算法的全局尋優能力；另外由于采用了圖搜索算法，算法性能受鏈接圖節點數目的影響也比較大。針對倉庫巡檢機器人，本文提出一種更為簡單的基于粒子群算法的路徑規劃方法。其思想是：將路徑規劃問題抽象為對一個罰函數的優化問題，該罰函數通過神經網絡結構構造，其中包含環境中障礙物的約束及路徑的長度信息。將該罰函數作為粒子群算法中的適應度函數，而路徑中除去起點與終點外的路徑節點作為粒子，通過混合粒子群算法進行尋優。由于適應度函數中包含了環境約束信息及路徑長度信息，最后規劃結果為一條安全無碰且長度較短的路徑。針對移動機器人路徑規劃問題特點，提出一種合理的粒子編碼方法，通過該方法可在保證搜索空間維數較低的前提下使罰函數對路徑提供足夠安全的約束，最后通過仿真實驗數據驗證了算法的性能。

1 數學模型描述

倉庫巡檢機器人工作空間為有限二維平面，倉庫中的貨物可視為位置已知的凸多邊形（多為矩形）障礙物。將工作空間中障礙物按照機器人半徑尺寸膨脹，可將機器人等效為一個“點”，這樣可將路徑規劃問題等價為約束優化問題：

其中，M為路徑中的節點數目，N為機器人工作空間中的障礙物數目。C^j_i按照文獻[5]提出的三層神經網絡結構計算。具體計算過程可參閱第4章給出的計算示例。通過式（2）—（4）將移動機器人路徑規劃問題轉換為對式（2）的無約束優化問題。

2 粒子群優化算法及其在路徑規劃中的實現

2.1 粒子群算法

2.2 粒子群算法在路徑規劃中的實現

3 計算機仿真實驗

3.1 評價函數的計算示例

簡化問題而又不失一般性，本文算法仿真中障礙物約束如圖2所示，規劃起點位于坐標原點處，規劃終點位于（10，10）處，通過障礙物的邊界確定約束方程如式（10）、（11）所示：

則式（4）中的C_ij由圖2所示的神經網絡結構計算，計算公式為式（12）—（15）：

3.2 仿真結果

算法中，慣性權重ω按照式（16）計算：

分析圖4中的結果可知，該算法隨著迭代次數的增加，整體上將會獲得更優的規劃結果，但如圖中迭代最大次數為800時的規劃結果所示，有時算法會陷入局部最優。由于是對整條路徑進行碰撞評估，在粒子維數較低的情況下（仿真中為4）保證了規劃得到的路徑是安全的。圖5給出了相對復雜的環境下的規劃結果，表明該算法適合復雜環境下路徑規劃問題。

3.2 算法性能分析

本文通過固定粒子群規模、粒子維數及最大迭代次數，在同一臺計算機上測試算法的性能。通過逐漸增加機器人環境空間中的矩形障礙物的數目測試算法執行時間，每增加一個障礙物，仿真程序執行20次，計算程序平均執行時間，最后獲得算法性響應曲線，如圖6所示。從圖6可知當機器人環境空間中障礙物數目增多時，算法執行時間近似成比例增長，說明該算法在復雜環境中性能穩定。本文在粒子群規模及迭代次數不變的情況下，比較分別加入碰撞能量測試點以及單純增加粒子維數對算法性能的影響，圖7(a)側為加入50個碰撞能量測試點，迭代100次后的結果，算法執行時間為0.42s；圖7(b)為沒有加入碰撞能量測試點，但粒子維數增加50維，迭代100次后的結果，算法執行時間為2.25s。從圖7結果中可見加入碰撞能量測試點后保證了算法性能。

4 結束語

本文所提出的移動機器人路徑規劃算法是對粒子群算法在路徑規劃問題中應用的有益探索，該算法實現簡單，通過神經網絡結構構造粒子群算法中的適應度函數，同過對粒子合理編碼實現移動機器人路徑規劃。通過計算機仿真驗證，該算法可在規劃起始點與目標終點之間得到一條簡單的折線可行路徑，巡檢機器人采用該算法獲得的路徑非常便于位于路徑規劃模塊下層的運動控制模塊進行軌跡跟蹤，因此該算法適合倉庫巡檢機器人路徑規劃的需要。本文下一個研究目標是將移動機器人的導航系統與基于RFID倉庫管理軟件系統有機結合，為移動機器人在倉庫智能化管理方面的應用作出新的嘗試。

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