TY - GEN
T1 - Space-filling trees
T2 - 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems: Celebrating 50 Years of Robotics, IROS'11
AU - Kuffner, James J.
AU - LaValle, Steven M.
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84455175508&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84455175508&partnerID=8YFLogxK
U2 - 10.1109/IROS.2011.6048346
DO - 10.1109/IROS.2011.6048346
M3 - Conference contribution
AN - SCOPUS:84455175508
SN - 9781612844541
T3 - IEEE International Conference on Intelligent Robots and Systems
SP - 2199
EP - 2206
BT - IROS'11 - 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems
Y2 - 25 September 2011 through 30 September 2011
ER -