Premium
Result Verification of RRT‐based Single‐Query Path Planning through Interval Analysis
Author(s) -
Grimm Cornelius
Publication year - 2008
Publication title -
pamm
Language(s) - English
Resource type - Journals
ISSN - 1617-7061
DOI - 10.1002/pamm.200810971
Subject(s) - interval (graph theory) , interval arithmetic , reliability (semiconductor) , motion planning , computation , computer science , path (computing) , critical path method , field (mathematics) , mathematical optimization , algorithm , mathematics , artificial intelligence , engineering , mathematical analysis , power (physics) , physics , pure mathematics , robot , bounded function , programming language , systems engineering , combinatorics , quantum mechanics
Single–query path planning is still an open research field. A very promising approach is the use of Rapidly–exploring Random Trees (RRTs). In this approach two RRTs are constructed, one starting from the initial configuration and one from the goal configuration. In comparison with other approaches, this methodology is very efficient in high–dimensional configuration spaces. However, a naive implementation of this approach results in reliability problems: For the construction of an RRT, only discrete configurations are tested for feasibility, while continuous transitions between configurations are not. Furthermore, numerical computations are performed in a floating point arithmetic without accounting for round–off errors. In this work an advanced algorithm will be presented that incorporates interval analysis to eliminate these problems and yield reliable results. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)