Automatic motion planning has applications ranging from traditional robotics to computer-aided design to computational biology and chemistry. Probabilistic roadmap methods (PRMs) have been highly successful in solving
many of these high degree of freedom problems. One important practical issue with PRMs is they do not provide an automated mechanism to determine what size roadmap to construct. Instead, users typically determine an appropriate roadmap size by trial and error and often construct larger maps than needed or build several maps before obtaining one that meets their needs. 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 independent processes, each of which generates samples and connections independently. IMG proceeds by adding these collections of samples and connections to an existing roadmap until it satisfies some specified evaluation criteria. We propose some general evaluation criteria and show how they can be used to construct diferent types of roadmaps, e.g., roadmaps that coarsely or more finely map the space. In addition to addressing the roadmap size question, the fact that each roadmap increment is independently and deterministically seeded has several other benefits such as supporting roadmap reproducibility, the adaptive selection of sampling methods in different roadmap increments, and parallelization. We provide results illustrating the power of IMG.