Space-Filling Trees: A New Perspective on Incremental Search for Motion Planning
Venue
Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE (2011)
Publication Year
2011
Authors
James J. Kuffner, Steven M. LaValle
BibTeX
Abstract
This paper introduces space-filling trees and analyzes them in the context of
sampling-based motion planning. Space-filling trees are analogous to space-filling
curves, but have a branching, tree-like structure, and are defined by an
incremental process that results in a tree for which every point in the space has a
finite-length path that converges to it. In contrast to space-filling curves,
individual paths in the tree are short, allowing any part of the space to be
quickly reached from the root. We compare some basic constructions of space-filling
trees to Rapidly-exploring Random Trees (RRTs), which underlie a number of popular
algorithms used for sampling-based motion planning. We characterize several key
tree properties related to path quality and the overall efficiency of exploration
and conclude with a number of open mathematical questions.
