Probabilistic roadmap methods (PRMs) have been highly successful in
solving many high degree of freedom motion planning problems arising in diverse application domains such as traditional robotics, computer-aided design, and computational
biology and chemistry. One important practical issue with PRMs is that
they do not provide an automated mechanism to determine how large a roadmap is needed for a given problem. Instead, users typically determine this by trial and error and as a consequence often construct larger roadmaps than are needed. In this paper, we propose a new PRM-based framework called Incremental Map Generation (IMG) to address this problem. Our strategy is to break the map generation into several processes, each of which generates samples and connections, and to continue
adding the next increment of samples and connections to the evolving roadmap until it stops improving. In particular, the process continues until a set of evaluation criteria determine that the planning strategy is no longer effective at improving the roadmap. We propose some general evaluation criteria and show how to apply them to construct different types of roadmaps, e.g., roadmaps that coarsely or more finely
map the space. In addition, we show how IMG can be integrated with previously
proposed adaptive strategies for selecting sampling methods. We provide results illustrating the power of IMG.