  This paper presents a data structure that summarizes distances between
configurations across a robot configuration space, using a binary space
partition whose cells contain parameters used for a locally linear
approximation of the distance function. Querying the data structure is
extremely fast, particularly when compared to the graph search required for
querying Probabilistic Roadmaps, and memory requirements are promising. The
paper explores the use of the data structure constructed for a single robot to
provide a heuristic for challenging multi-robot motion planning problems.
Potential applications also include the use of remote computation to analyze
the space of robot motions, which then might be transmitted on-demand to robots
with fewer computational resources.
