Customizing PRM roadmaps at query time

In this paper, we propose a new approach for building and querying probabilistic roadmaps. In the roadmap construction stage, we build coarse roadmaps by performing only an approximate validation of the roadmap nodes and/or edges. In the query stage, the roadmap is validated and refined only in the area of interest for the query, and moreover; is customized in accordance with any specified query preferences. This approach, which postpones some of the validation checks (e.g., collision check) to the query phase, yields more efficient solutions to many problems. An important benefit of our approach is that it gives one the ability to customize the same roadmap in accordance with multiple, variable, query preferences. For example, our approach enables one to find a path which maintains a particular clearance, or makes at most some specified number of sharp turns. Our preliminary results on problems drawn from diverse application domains show that this new approach dramatically improves performance, and show s remarkable flexibility when adapting to different query requirements.