Development of Path Planning Algorithm Using Probabilistic Roadmap Based on Ant Colony Optimization | ||
| Engineering and Technology Journal | ||
| Article 7, Volume 38, 3A, March 2020, Pages 343-351 PDF (582.31 K) | ||
| DOI: 10.30684/etj.v38i3A.389 | ||
| Authors | ||
| Mohammed I. Abdulakareem* 1; Firas A. Raheem* 2 | ||
| 1Control and Systems Department, University of Technology, Baghdad, Iraq. | ||
| 2Control and Systems Department, University of Technology, Baghdad, Iraq | ||
| Abstract | ||
| In this paper, a unique combination among probabilistic roadmap, ant colony optimization, and third order B-spline curve has been proposed to solve path-planning problem in complex and very complex environments. This proposed method can be divided into three stages. First stage is to construct a random map depending on the environment complexity using probabilistic roadmap algorithm. This could be done by sampling N nodes randomly in complex and very complex static environments, then connecting these nodes together according to some criteria or conditions. The constructed roadmap contains huge number of possible random paths that may connect the start and the goal points together. Second stage includes finding path within the pre-constructed roadmap. Ant colony optimization is selected to find or to search the best path between start and goal points. Finally, the third stage uses B-spline curve to smooth and reduce total length of the found path in the previous stage where path’s length has been reduced by 1% in first environment and by 15% in second environment. The results of the proposed approach ensure feasible path between start and goal points in complex and very complex environment. In addition, the path is guaranteed to be shortest, smooth, continues and safe. | ||
| Keywords | ||
| path planning; Probabilistic Roadmap (PRM); Ant Colony Optimization; B-spline curve | ||
| References | ||
|
[1] F. A. Raheem, and U. I. Hameed, “Interactive heuristic D* path planning solution based on PSO for twolink robotic arm in dynamic environment,” World Journal of Engineering and Technology, Scientific Research Publishing, Vol. 7, No. 1, pp 80-81, February 2019. [2] S. H. Shwail, and A. Karim, “Probabilistic roadmap, A*, and GA for Proposed decoupled multi-robot path planning,” Iraq journal for applied physics, Vol. 10, No. 2, pp.3, June 2014. [3] N. B. Sariff, and N. B. Amin, “Ant colony system for robot path planning in global static environment,” 9th WSEAS international conference on System science and simulation in engineering, Japan, pp. 192, 2010. [4] F. A. Raheem, and A. A. Hussain, “Applying A* path planning algorithm based on modified C-space analysis,” Al-Khwarizmi Engineering Journal, Vol. 13, No. 4, pp. 125, 2017. [5] F. A. Raheem, and U. I. Hameed, “Path planning algorithm using D* heuristic method based on PSO in dynamic environment,” American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS), Vol. 49, No. 1, pp. 258, 2018. [6] Y. Gigras, and K. Gupta, “Metaheuristic algorithm for robotic path planning,” International Journal of Computer Applications, Vol. 85, No. 3, pp. 1, January 2014. [7] F. A. Raheem, and M. M. Bader, “Development of Modified path planning algorithm using artificial potential field (APF) based on PSO for factors optimization,” American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS), Vol. 37, No. 1, pp. 317, 2017. [8] L. E. Kavraki, P. Svestka, J. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Transaction on Robotics and Automation, Vol. 12, No. 4, pp. 566-570, August 1996. [9] V. Boor, M. H. Overman, and A. F. Stappen, “The gaussian sampling strategy for probabilistic roadmap planners,” IEEE International Conference on Robotics and Automation, Michigan, pp. 1018, 1999. [10] S. A. Wilmath, N. M. Amato, and P. F. Stiller, “MAPRM: a probabilistic roadmap planner with of the free space,” IEEE International Conference on Robotics and Automation, Michigan, pp. 1024, 1999. [11] R. Geraerts, and M. H. Overmars, “Sampling and node adding in probabilistic roadmap planners,” Robotics and Autonomous Systems, ELSEVIER, Vo. 54, No. 2, pp. 169, December 2005. [12] D. Hsu, G.S. Ante, and Z. Sun, “Hybrid PRM sampling with a cost-sensitive adaptive strategy,” IEEE International Conference on Robotics and Automation, Barcelona, pp. 3874, 2005. [13] Y. Zhang, N. Fattahi, and W. Li, “Probabilistic roadmap with self-learning for path planning of a mobile robot in a dynamic and unstructured environment,” IEEE International Conference on Mechatronics and Automation, Takamatsu, pp. 1074, 2013. [14] M. Brand, M. Masuda, and N. Wehner, X. Yu,’’ Ant colony optimization algorithm for robot path planning’’, International Conference on Computer Design and Applications ICCDA, China, pp.436-437, 2010. [15] M. Elbanhawi, M. Simic, and R. Jazar, “Continuous-curvature bounded trajectory planning using parametric splines,” Frontiers in artificial intelligence and applications, Vol. 262, pp.514, 2014. [16] M. Elbanhawi, M. Simic, and R. Jazar, Continuous path smoothing for car-like robots using B-spline curves,” Journal of Intelligent and Robotic Systems, Vol. 80, pp. 25-26, 2015. [17] C. Tai, S. Hu, and Q. Husang, “Approximate merging of B-spline curves via knot adjustment and constrained optimization,” Computer-Aided Design, Vol. 35, pp. 894, 2003 | ||
|
Statistics Article View: 297 PDF Download: 243 |
||