Multilevel Incremental Roadmap Spanners for Reactive Motion Planning Generating robot motions from a precomputed graph has proven to be an effective approach to solving many motion planning problems. After their generation, roadmaps reduce complex motion planning problems to that of solving a graphbased shortest path. However, generating the graph can involve tradeoffs, such as how sparse or dense to make the graph. Sparse graphs may not provide enough options to navigate around a new obstacle or may result in grossly suboptimal motions. Dense graphs may take too long to search and result in an unresponsive robot. In this paper we present an algorithm that generates a graph with multiple sparse levelsxe2x80x93 the sparsest level can be searched quickly, while the densest level allows for asymptotically optimal motions. With the paired multilevel shortest path algorithm, after the robot computes an initial solution, it can then incrementally refine the shortestpath as time allows. We demonstrate the algorithms on an articulated robot with 8 degrees of freedom, having them compute an initial solution in a fraction of the time required for a full graph search, and subsequently, incrementally refine the solution to the optimal shortest path from the densest level of the graph.

LEGO: Leveraging Experience in Roadmap Generation for SamplingBased Planning We consider the problem of leveraging prior experience to generate roadmaps in samplingbased motion planning. A desirable roadmap is one that is sparse, allowing for fast search, with nodes spread out at key locations such that a low cost feasible path exists. An increasingly popular approach is to learn a distribution of nodes that would produce such a roadmap. Stateoftheart is to train a conditional variational autoencoder (CVAE) on the prior dataset with the shortest paths as target input. While this is quite effective on many problems, we show it can fail in the face of complex obstacle configurations or mismatch between training and testing. We present an algorithm LEGO that addresses these issues by training the CVAE with target samples that satisfy two important criteria. Firstly, these samples belong only to bottleneck regions along nearoptimal paths that are otherwise difficult tosample with a uniform sampler. Secondly, these samples are spread out across diverse regions to maximize the likelihood of a feasible path existing. We formally define these properties and prove performance guarantees for LEGO. We extensively evaluate LEGO on a range of planning problems, including robot arm planning, and report significant gains over heuristics as well as learned baselines.