Publication detail

The RRT algorithms and a spatial index

GULINA, I. MATOUŠEK, R.

Czech title

RRT algoritmus a prostorový index

English title

The RRT algorithms and a spatial index

Type

conference paper

Language

en

Original abstract

The Rapidly-exploring Random Trees algorithm (RRT), based on incremental sampling, is a popular and powerful tool for motion planning problems. Although the RRT algorithm returns the solution relatively quickly, the computational cost of every new algorithm loop increases as the tree grows because of the nearest neighbor searching procedure. This paper solves this problem and improves the RRT performance using a spatial index. Through a series of simulation experiments we evaluate and compare the performance of RRT-based algorithms with and without a spatial index. We report on the results verifying the efficiency of the use of a spatial index

Czech abstract

Algoritmus RRT (Rapidly-exploring Random Trees) patatří k populárním algoritmům pro plánování cest. Přesto, že k výhodám tohoto algoritmu patří dobře definovatelná časová náročnost, řešení mnoha problémů znamená velký počet výpočetních běhů a tedy delší čas výpočtu. Článek popisuje přístup založený na tzv. prostorovém indexu (spatial index) s jehož využitím lze podstatně redukovat vliv velikosti vstupní nožiny uzlů na dobu výpočtu. V článku je prezentovaná empiricky uvedená asymptotická složitost výpočtu pro RRT bez a s využitim spatial indexování.

English abstract

The Rapidly-exploring Random Trees algorithm (RRT), based on incremental sampling, is a popular and powerful tool for motion planning problems. Although the RRT algorithm returns the solution relatively quickly, the computational cost of every new algorithm loop increases as the tree grows because of the nearest neighbor searching procedure. This paper solves this problem and improves the RRT performance using a spatial index. Through a series of simulation experiments we evaluate and compare the performance of RRT-based algorithms with and without a spatial index. We report on the results verifying the efficiency of the use of a spatial index

Keywords in Czech

plánování pohybu, RRT, prostorový index

Keywords in English

Motion planning, Rapidly-exploring random trees algorithm, spatial index

RIV year

2014

Released

25.06.2014

ISBN

978-80-214-4984-8

ISSN

1803-3814

Book

20th International Conference on Soft Computing, MENDEL 2014 (id 22122)

Volume

2014

Number

1

Edition number

1

Pages from–to

279–284

Pages count

6

BIBTEX


@inproceedings{BUT108987,
  author="Irina {Gulina} and Radomil {Matoušek},
  title="The RRT algorithms and a spatial index",
  booktitle="20th International Conference on Soft Computing, MENDEL 2014 (id 22122)",
  year="2014",
  volume="2014",
  number="1",
  month="June",
  pages="279--284",
  isbn="978-80-214-4984-8",
  issn="1803-3814"
}