Close this search box.

Sampling-Diagrams Automata: a Tool for Analyzing Path Quality in Tree Planners


Sampling-Diagrams Automata: a Tool for Analyzing Path Quality in Tree Planners
An illustration of the Promenade motion planning problem, a square obstacle within a square bounding-box. Two solution paths (solid / dashed lines) between \(q_1\) and \(q_2\) are shown, and represent “good” and “bad” solutions, respectively

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 by defining appropriate predicates, and pave the way to deeper understanding of hallmark planning algorithms.


  • Oren Nechushtan, Barak Raveh and Dan Halperin
    Sampling-Diagram Automata: A Tool for Analyzing Path Quality in Tree Planners
    Algorithmic Foundations of Robotics (WAFR) IX, 68/2011: 285-301, Springer Tracts in Advanced Robotics, 2011 [link][bibtex]
  • Supplementary On-line Proofs [pdf]


Oren Nechustan
Dan Halperin
Barak Raveh

Yair Oz - Webcreator


Skip to content