Sampling-based robot path planning algorithms assessment and improvement

• Main Author: Liu, Xinyu
• Other Authors: Hu, Guoqiang
• Format: Thesis-Master by Coursework
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Engineering::Electrical and electronic engineering
• Online Access: https://hdl.handle.net/10356/150299
• Institution: Nanyang Technological University

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.