Google Research

Space-Filling Trees: A New Perspective on Incremental Search for Motion Planning

  • James J. Kuffner
  • Steven M. LaValle
Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE (2011)


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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work