Minimising Computational Complexity of the RRT Algorithm: A Practical Approach

Research output: Contribution to journalConference article in JournalResearchpeer-review

11 Citations (Scopus)
812 Downloads (Pure)

Abstract


Sampling based techniques for robot motion planning have become more widespread during the last decade. The algorithms however, still struggle with for example narrow passages in the configuration space and suffer from high number of necessary samples, especially in higher dimensions. A widely used method is Rapidly-exploring Random Trees (RRT's). One problem with this method is the nearest neighbour search time, which grows significantly when adding a large number of vertices. We propose an algorithm which decreases the computation time, such that more vertices can be added in the same amount of time to generate better trajectories. The algorithm is based on subdividing the configuration space into boxes, where only specific boxes needs to be searched to find the nearest neighbour. It is shown that the computational complexity is lowered from a theoretical point of view. The result is an algorithm that can provide better trajectories within a given time period, or alternatively compute trajectories faster. In simulation the algorithm is verified for a simple RRT implementation and in a more specific case where a robot has to plan a path through a human inhabited environment.
Original languageEnglish
JournalI E E E International Conference on Robotics and Automation. Proceedings
ISSN1050-4729
DOIs
Publication statusPublished - 2011

Fingerprint

Computational complexity
Trajectories
Robots
Motion planning
Sampling

Cite this

@inproceedings{98440dff586a4e83a11954d9eadb220a,
title = "Minimising Computational Complexity of the RRT Algorithm: A Practical Approach",
abstract = "Sampling based techniques for robot motion planning have become more widespread during the last decade. The algorithms however, still struggle with for example narrow passages in the configuration space and suffer from high number of necessary samples, especially in higher dimensions. A widely used method is Rapidly-exploring Random Trees (RRT's). One problem with this method is the nearest neighbour search time, which grows significantly when adding a large number of vertices. We propose an algorithm which decreases the computation time, such that more vertices can be added in the same amount of time to generate better trajectories. The algorithm is based on subdividing the configuration space into boxes, where only specific boxes needs to be searched to find the nearest neighbour. It is shown that the computational complexity is lowered from a theoretical point of view. The result is an algorithm that can provide better trajectories within a given time period, or alternatively compute trajectories faster. In simulation the algorithm is verified for a simple RRT implementation and in a more specific case where a robot has to plan a path through a human inhabited environment.",
author = "Mikael Svenstrup and Thomas Bak and Andersen, {Hans J{\o}rgen}",
year = "2011",
doi = "10.1109/ICRA.2011.5979540",
language = "English",
journal = "I E E E International Conference on Robotics and Automation",
issn = "2152-4092",
publisher = "IEEE Computer Society Press",

}

Minimising Computational Complexity of the RRT Algorithm : A Practical Approach. / Svenstrup, Mikael; Bak, Thomas; Andersen, Hans Jørgen.

In: I E E E International Conference on Robotics and Automation. Proceedings, 2011.

Research output: Contribution to journalConference article in JournalResearchpeer-review

TY - GEN

T1 - Minimising Computational Complexity of the RRT Algorithm

T2 - A Practical Approach

AU - Svenstrup, Mikael

AU - Bak, Thomas

AU - Andersen, Hans Jørgen

PY - 2011

Y1 - 2011

N2 - Sampling based techniques for robot motion planning have become more widespread during the last decade. The algorithms however, still struggle with for example narrow passages in the configuration space and suffer from high number of necessary samples, especially in higher dimensions. A widely used method is Rapidly-exploring Random Trees (RRT's). One problem with this method is the nearest neighbour search time, which grows significantly when adding a large number of vertices. We propose an algorithm which decreases the computation time, such that more vertices can be added in the same amount of time to generate better trajectories. The algorithm is based on subdividing the configuration space into boxes, where only specific boxes needs to be searched to find the nearest neighbour. It is shown that the computational complexity is lowered from a theoretical point of view. The result is an algorithm that can provide better trajectories within a given time period, or alternatively compute trajectories faster. In simulation the algorithm is verified for a simple RRT implementation and in a more specific case where a robot has to plan a path through a human inhabited environment.

AB - Sampling based techniques for robot motion planning have become more widespread during the last decade. The algorithms however, still struggle with for example narrow passages in the configuration space and suffer from high number of necessary samples, especially in higher dimensions. A widely used method is Rapidly-exploring Random Trees (RRT's). One problem with this method is the nearest neighbour search time, which grows significantly when adding a large number of vertices. We propose an algorithm which decreases the computation time, such that more vertices can be added in the same amount of time to generate better trajectories. The algorithm is based on subdividing the configuration space into boxes, where only specific boxes needs to be searched to find the nearest neighbour. It is shown that the computational complexity is lowered from a theoretical point of view. The result is an algorithm that can provide better trajectories within a given time period, or alternatively compute trajectories faster. In simulation the algorithm is verified for a simple RRT implementation and in a more specific case where a robot has to plan a path through a human inhabited environment.

U2 - 10.1109/ICRA.2011.5979540

DO - 10.1109/ICRA.2011.5979540

M3 - Conference article in Journal

JO - I E E E International Conference on Robotics and Automation

JF - I E E E International Conference on Robotics and Automation

SN - 2152-4092

ER -