Paper Info
Title
Sampling-Diagram Automata: A Tool for Analyzing Path Quality in Tree Planners.
Abstract
Sampling-based motion planners are a central tool for solving motion-planning problems in a variety of domains, but the theoretical understanding of their behavior remains limited, in particular with respect to the quality of the paths they generate (in terms of path length, clearance, etc.). In this paper we prove, for a simple family of obstacle settings, that the popular dual-tree planner Bi-RRT may produce low-quality paths that are arbitrarily worse than optimal with modest but significant probability, and overlook higher-quality paths even when such paths are easy to produce. At the core of our analysis are probabilistic automata designed to reach an accepting state when a path of significantly low quality has been generated. Complementary experiments suggest that our theoretical bounds are conservative and could be further improved. To the best of our knowledge, this is the first work to study the attainability of high-quality paths that occupy a significant (non-negligible) portion of the space of all paths. The formalism presented in this work can be generalized to other algorithms and other motion-planning problems by defining appropriate predicates, and pave the way to deeper understanding of hallmark planning algorithms.
Year
DOI
Venue
2010
10.1007/978-3-642-17452-0_17
ALGORITHMIC FOUNDATIONS OF ROBOTICS IX
Field
DocType
Volume
Obstacle,Path length,Computer science,Automaton,Planner,Theoretical computer science,Diagram,Sampling (statistics),Formalism (philosophy),Probabilistic automaton
Conference
68
ISSN
Citations 
PageRank 
1610-7438
12
1.05
References 
Authors
16
3
Name
Order
Citations
PageRank
Oren Nechushtan1614.52
Barak Raveh2836.66
Dan Halperin31291105.20