Design and performance analysis of global path planning techniques for autonomous mobile robots in grid environments
Ref: CISTER-TR-170308 Publication Date: 2017
Design and performance analysis of global path planning techniques for autonomous mobile robots in grid environmentsRef: CISTER-TR-170308 Publication Date: 2017
This paper presents the results of the two-year iroboapp research project which aims at devising path planning algorithms for large grid maps with much faster execution times while tolerating very small slacks with respect to the optimal path. We investigated both exact and heuristic methods. We contributed with the design, analysis, evaluation, implementation and experimentation of several algorithms for grid map path planning for both exact and heuristic methods. We also designed an innovative algorithm called RA∗ that has linear complexity with relaxed constraints, which provides near optimal solutions with an extremely reduced execution time as compared to A∗. We evaluated the performance of the different algorithms and we concluded that RA∗ is the best path planner as it provides a good trade-off among all the metrics, but we noticed that heuristic methods have good features that can be exploited to improve the solution of the relaxed exact method. This led us to design new hybrid algorithms that combine our RA∗ with heuristic methods which improve the solution quality of RA∗ at the cost of slightly higher execution time, while remaining much faster than A∗ for large scale problems. Finally, we demonstrate how to integrate the RA∗ algorithm in the Robot Operating System (ROS) as a global path planner and we show that it outperforms its default path planner with an execution time 38% faster on average.
To be published in International Journal of Advanced Robotic Systems, SAGE.