Path planning in expansive configuration spaces

TLDR

The paper introduces expansiveness as a property of robot configuration spaces that allows their connectivity to be captured by a roadmap of randomly sampled milestones. The authors propose a randomized planning algorithm that samples only the query‑relevant portion of the configuration space, avoiding the cost of precomputing a full roadmap. The resulting algorithm, inspired by expansive configuration spaces, efficiently handles single‑query problems and has been successfully applied to complex automotive assembly maintainability tasks.

Abstract

We introduce the notion of expansiveness to characterize a family of robot configuration spaces whose connectivity can be effectively captured by a roadmap of randomly-sampled milestones. The analysis of expansive configuration spaces has inspired us to develop a new randomized planning algorithm. This algorithm tries to sample only the portion of the configuration space that is relevant to the current query, avoiding the cost of precomputing a roadmap for the entire configuration space. Thus, it is well-suited for problems where a single query is submitted for a given environment. The algorithm has been implemented and successfully applied to complex assembly maintainability problems from the automotive industry.