Piecewise linear regressions for approximating distance metrics
This addresses the computational bottleneck in robot motion planning, particularly for multi-robot systems, though it appears incremental as it builds on existing approximation techniques.
This paper tackles the problem of efficiently computing distances in robot configuration spaces by developing a data structure that uses piecewise linear regressions to approximate distance metrics, achieving extremely fast query times compared to traditional graph search methods like Probabilistic Roadmaps. The approach also extends to multi-robot motion planning heuristics and enables remote computation for resource-constrained robots.
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.