Path planning in expansive configuration spaces

We introduce the notion of expansiveness to characterize a family of robot configuration spaces whose connectivity can be effectively captured by a ro admap of randomly-sampled milestones. The analysis of expansive configurati on spaces has inspired us to develop a new randomized planning algorithm. T his new algorithm tries to sample only the portion of the configuration spa ce 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 only a single query is submitted for a given environment. Th e algorithm has been implemented and successfully applied to complex assemb ly maintainability problems from the automotive industry.