在室內環境中使用ALC-PSO演算法與危險度指標改良RRT路徑規劃

Using ALC-PSO Algorithm to Improve RRT Path Planning in Indoor Environments with Danger Degree

姜俊甫(Jyun-Fu Jiang)

指導教授 ： 鍾鴻源

國立中央大學/資訊電機學院/電機工程學系/碩士(2014年)

摘要

在移動式機器人中，要如何在有障礙物的環境中，規劃出一條合適的無障礙物的路徑，讓移動機器人能從起始點移動到達目標點且確保路徑是最短的，是一個很重要議題。
本文提出一種最佳路徑規劃方法於移動機器人，利用改良式粒子群演算法也就是老齡化領導者與挑戰者粒子群演算法(ALC-PSO)來模擬快速搜尋隨機樹(RRT)，與過去傳統粒子群演算法用於路徑規劃方法有所不同，在本文是藉由樹枝生長的方式來增加延伸點，在我們比較之後，選擇最好的延伸點加到粒子之中，而這是基於使用ALC-PSO演算法的基礎下產生的創新路徑規劃演算法。
這個方法克服了粒子群演算法容易陷入區域最佳點應用於機器人路徑規劃方面上的缺點，而且因為基本的RRT演算法在每次規劃路徑上是不穩定的，所以本文利用模擬RRT演算法的方式來改良ALC-PSO演算法應用在路徑規劃上，且加入了危險度地圖的概念來避開障礙物，經過模擬結果，我們可以證明這個改良創新演算法可以使結果穩定在室內環境中而且比RRT演算法更好，同時也確保規劃路徑會是最短的。

關鍵字

老齡化領導者與挑戰者粒子群演算法 ； 危險度指標 ； 快速搜尋隨機樹 ； 路徑規劃 ； 移動機器人

並列摘要

Path planning is an important issue in mobile robotics. In an environment with obstacles, path planning is to find a suitable collision-free path for a mobile robot to move from a start location to a target location along the shortest path.
This paper proposes an optimal path planning algorithm for mobile robots based on Particle Swam Optimization with an Aging Leader and Challengers (ALC-PSO) to imitate Rapidly-exploring Random Tree (RRT), traditional Particle Swam Optimization (PSO) for path planning is different, In this paper, we propose a branches-grow method based on the ALC-PSO algorithm, and add extend point to particles after we compare.
This method overcomes the drawback for particle swam optimization is easy to fall into local optimization in robotic path planning. Because the basic Rapidly-exploring Random Tree (RRT) path planning is unstable for every time, so this paper improved algorithm of ALC-PSO to imitate RRT in path planning, and add Danger Degree Map to avoid obstacles. From the results of simulations, we show that this algorithm can improve the stability of RRT path planning in static environment, and ensures that the path is almost optimal.

並列關鍵字

ALC-PSO ； Danger Degree ； Rapidly-exploring Random Tree ； Path Planning ； Mobile Robots

參考文獻

[38] F. Ye and C. Y. Chen, “Alternative KPSO-Clustering Algorithm,” Tamkang Journal of Science and Engineering, Vol. 8, No. 2, pp. 165-174, 2005.

[3] X. Ye, Y. L. and H. Hon, “Design of intelligent mobile vehicle system and its global optimal path planning,” IEEE International Conference on Industrial Technology, No.1-5, 2008.

[4] A. T. Klesh, P. T. Kabamba and A.R. Girard, “Optimal Path planning for uncertain exploration,” American Control Conference, No.2421-2426, 2009.

[6] K. Sugihara and J. Smith, “Genetic Algorithms for Adaptive Motion Planning of an Autonomous Mobile Robot,” in Proceedings of IEEE international Symposium on Computational Intelligence in Robotics and Automation, pp. 138-143, 1997.

[7] I. Ashiru, C. Czarnecki, and T. Routen, “Characteristics of a Genetic Based Approach to Path Planning for Mobile Robots,” J. Network and Computer Applications, Vol. 19, pp. 149-169, 1996.