Please use this identifier to cite or link to this item:
Title: Sampling-based robot path planning algorithms assessment and improvement
Authors: Liu, Xinyu
Keywords: Engineering::Electrical and electronic engineering
Issue Date: 2021
Publisher: Nanyang Technological University
Source: Liu, X. (2021). Sampling-based robot path planning algorithms assessment and improvement. Master's thesis, Nanyang Technological University, Singapore.
Abstract: 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.
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:EEE Theses

Files in This Item:
File Description SizeFormat 
  Restricted Access
1.31 MBAdobe PDFView/Open

Page view(s)

Updated on May 17, 2022


Updated on May 17, 2022

Google ScholarTM


Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.