Incremental Map Generation (IMG)

Dawen Xie, Marco Morales, Roger Pearce, Shawna Thomas, Jyh Ming Lien, Nancy M. Amato

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAlgorithmic Foundation of Robotics VII - Selected Contributions of the Seventh International Workshop on the Algorithmic Foundations of Robotics
Number of pages16
StatePublished - 2008
Externally publishedYes
Event7th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2006 - New York, NY, United States
Duration: Jul 16 2006Jul 18 2006

Publication series

NameSpringer Tracts in Advanced Robotics
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X


Other7th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2006
Country/TerritoryUnited States
CityNew York, NY

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'Incremental Map Generation (IMG)'. Together they form a unique fingerprint.

Cite this