Analysis of RRT, PRM and voronoi path planning algorithms to solve a modular maze using a two-DOF platform

Abstract

This paper analyzes three path planning techniques to solve a ball-maze system with a two-degree-of-freedom platform. The system’s objective focuses on the ball traveling a path from an initial point to a final point (defined by the user) in the maze. The RRT algorithms (Rapidly Exploring Random Trees), PRM (Probabilistic Roadmap), and Voronoi diagrams were implemented using the A* search algorithm. The system architecture consists of four subsystems called mechanical, vision, planning, and control. The main contribution of this work is the evaluation of the algorithms on a physical system and a complete results analysis (graphical and analytical). The experimental tests were performed based on analyzing four different maze configurations, the run time, and path length metrics. In this context, 20 algorithm executions were developed for each configuration, then the meantime and mean length and their 95% confidence intervals were determined. The main results show that the RRT algorithm presents a more significant variation in its data, the longest path length, and the best performance in terms of run time. Moreover, the PRM algorithm generates the path with the shortest length but has the worst performance concerning run time. Finally, the Voronoi diagrams’ technique takes less time to execute, has less variation in its data, and presents the smoothest and equidistant path between the maze walls. © 2022, Universidad de Tarapaca.