DefinePK

Abstract

Path planning is one of the most vital aspects in robotics. Since the last few decades, it importance has been increasing due to the growing effort on the development of autonomous robots. Cell decomposition (CD), voronoi diagram (VD), probability roadmap (PRM) and visibility graph (VG) are among the earliest, most established and most popular methods in path planning. They have been used in many robotics path planning applications especially for autonomous systems. Before designing a path planning method, the three criteria i.e., path length, computational complexity and completeness have to be taken into account. This paper compares the performance of the above-mentioned path planning methods in terms of computation time and path length. For the sake of fair and conclusive finding, simulation is performed in three type of environments i.e., slightly cluttered, normally cluttered and highly cluttered. The finding shows that the visibility graph consistently produces relatively the shortest path while the voronoi diagram the longest. Shortest path is favorable for robots as the robots will consume less power/fuel and have an increased life cycle. However, the visibility graph is computationally intractable as in runs in polynomial time with respect to the number of obstacles. In contrast, PRM consumes the least time in planning a collision-free path. The finding of this paper could be used as a guideline about the performance in terms of path length and computation time for those who are interested in path planning using these four methods.