Sampling-based robot path planning algorithms assessment and improvement

Sampling-based planning algorithms (typically the RRT* family) represent one of the most popular path finding approaches that basically grow a tree or graph structure incrementally through various sampling techniques and try to connect the vertices with collision-free edges. To assure the completeness of exploration and the path optimality, the samples distribute uniformly over the entire space, which can often limit the sample efficiency and leads to slow convergence, making the algorithms practically less efficient in cluttered environments. In this article, we propose a novel sampling technique that leverages the sample information to predict the topological layout of the space and concentrate the sampling in plausible passages to boost the sample efficiency. Samples failing the collision detection are reused to interpret the obstacle distribution through dynamically constructed Voronoi graphs which will guide the subsequent sampling to be focused near the inferred homotopy classes. We build extended planning paradigms implementing the our method against popular RRT* variants (namely BIT*, Infomred RRT*, Smart-RRT*) to demonstrate the effectiveness of the proposed technique in accelerating the convergence speed while pursuing the completeness and optimality. The experiments and analyses justify that our method can effectively exploit the sampled information to improve the promising sample ratio and generally yields faster convergence in terms of shorter planning time and better solution cost compared to the others, especially when subject to difficult-to-sample homotopy classes.Master of Science (Communications Engineering