Sparse tree heuristics for RRT∗ family motion planners

Olzhas Adiyatov, Kazbek Sultanov, Olzhas Zhumabek, Huseyin Atakan Varol

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Sampling-based approaches constitute the state-of-The-Art for robot motion planning. Collision checking and nearest neighbor search are the major performance bottlenecks of these methods. For an environment with fixed number of obstacles, collision checking for a new candidate state is a constant time operation, whereas nearest neighbor search usually degrades during the runtime of the algorithm. Multiple variants of the single-query probabilistically optimal RRT∗ algorithm were introduced to tackle these issues. In this work, we present heuristics to augmented RRT∗ such that it finds the initial solution faster and converges to the optimal solution with less number of nodes. Instead of checking collision for every new node candidate, we consider only samples which are maximum step size away from the nearest neighbor or are near obstacles. With our augmented node concept, we embed nearby obstacle information to the nodes either as a binary variable (RRT K) or with a higher resolution quadrant based representation (RRT Q). Extensive benchmark batteries conducted on 2D and 3D problems with geometric constraints show the efficacy of our approach.

Original languageEnglish
Title of host publication2017 IEEE International Conference on Advanced Intelligent Mechatronics, AIM 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1447-1452
Number of pages6
ISBN (Electronic)9781509059980
DOIs
Publication statusPublished - Aug 21 2017
Event2017 IEEE International Conference on Advanced Intelligent Mechatronics, AIM 2017 - Munich, Germany
Duration: Jul 3 2017Jul 7 2017

Conference

Conference2017 IEEE International Conference on Advanced Intelligent Mechatronics, AIM 2017
CountryGermany
CityMunich
Period7/3/177/7/17

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Computer Science Applications
  • Software

Fingerprint Dive into the research topics of 'Sparse tree heuristics for RRT∗ family motion planners'. Together they form a unique fingerprint.

  • Cite this

    Adiyatov, O., Sultanov, K., Zhumabek, O., & Varol, H. A. (2017). Sparse tree heuristics for RRT∗ family motion planners. In 2017 IEEE International Conference on Advanced Intelligent Mechatronics, AIM 2017 (pp. 1447-1452). [8014222] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/AIM.2017.8014222