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

Fingerprint

Motion planning
Robots
Sampling
Nearest neighbor search

ASJC Scopus subject areas

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

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

Sparse tree heuristics for RRT∗ family motion planners. / Adiyatov, Olzhas; Sultanov, Kazbek; Zhumabek, Olzhas; Varol, Huseyin Atakan.

2017 IEEE International Conference on Advanced Intelligent Mechatronics, AIM 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 1447-1452 8014222.

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

Adiyatov, O, Sultanov, K, Zhumabek, O & Varol, HA 2017, Sparse tree heuristics for RRT∗ family motion planners. in 2017 IEEE International Conference on Advanced Intelligent Mechatronics, AIM 2017., 8014222, Institute of Electrical and Electronics Engineers Inc., pp. 1447-1452, 2017 IEEE International Conference on Advanced Intelligent Mechatronics, AIM 2017, Munich, Germany, 7/3/17. https://doi.org/10.1109/AIM.2017.8014222
Adiyatov O, Sultanov K, Zhumabek O, Varol HA. Sparse tree heuristics for RRT∗ family motion planners. In 2017 IEEE International Conference on Advanced Intelligent Mechatronics, AIM 2017. Institute of Electrical and Electronics Engineers Inc. 2017. p. 1447-1452. 8014222 https://doi.org/10.1109/AIM.2017.8014222
Adiyatov, Olzhas ; Sultanov, Kazbek ; Zhumabek, Olzhas ; Varol, Huseyin Atakan. / Sparse tree heuristics for RRT∗ family motion planners. 2017 IEEE International Conference on Advanced Intelligent Mechatronics, AIM 2017. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 1447-1452
@inproceedings{32c5157cf8a74615bfd2bc37299cc330,
title = "Sparse tree heuristics for RRT∗ family motion planners",
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.",
author = "Olzhas Adiyatov and Kazbek Sultanov and Olzhas Zhumabek and Varol, {Huseyin Atakan}",
year = "2017",
month = "8",
day = "21",
doi = "10.1109/AIM.2017.8014222",
language = "English",
pages = "1447--1452",
booktitle = "2017 IEEE International Conference on Advanced Intelligent Mechatronics, AIM 2017",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
address = "United States",

}

TY - GEN

T1 - Sparse tree heuristics for RRT∗ family motion planners

AU - Adiyatov, Olzhas

AU - Sultanov, Kazbek

AU - Zhumabek, Olzhas

AU - Varol, Huseyin Atakan

PY - 2017/8/21

Y1 - 2017/8/21

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85028750922&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028750922&partnerID=8YFLogxK

U2 - 10.1109/AIM.2017.8014222

DO - 10.1109/AIM.2017.8014222

M3 - Conference contribution

AN - SCOPUS:85028750922

SP - 1447

EP - 1452

BT - 2017 IEEE International Conference on Advanced Intelligent Mechatronics, AIM 2017

PB - Institute of Electrical and Electronics Engineers Inc.

ER -