Space-filling trees: A new perspective on incremental search for motion planning

James J. Kuffner, Steven M. LaValle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationIROS'11 - 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems
Subtitle of host publicationCelebrating 50 Years of Robotics
Pages2199-2206
Number of pages8
DOIs
StatePublished - 2011
Event2011 IEEE/RSJ International Conference on Intelligent Robots and Systems: Celebrating 50 Years of Robotics, IROS'11 - San Francisco, CA, United States
Duration: Sep 25 2011Sep 30 2011

Publication series

NameIEEE International Conference on Intelligent Robots and Systems

Other

Other2011 IEEE/RSJ International Conference on Intelligent Robots and Systems: Celebrating 50 Years of Robotics, IROS'11
Country/TerritoryUnited States
CitySan Francisco, CA
Period9/25/119/30/11

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Computer Vision and Pattern Recognition
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Space-filling trees: A new perspective on incremental search for motion planning'. Together they form a unique fingerprint.

Cite this