This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via HighWire Citing Articles via Web of Science (1) Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by van den Berg, J. P. Articles by Overmars, M. H. Search for Related Content Social Bookmarking                         What's this?

Using Workspace Information as a Guide to Non-uniform Sampling in Probabilistic Roadmap Planners

Institute of Information and Computing Sciences, Utrecht University, the Netherlands, berg{at}cs.uu.nl

Mark H. Overmars

Institute of Information and Computing Sciences, Utrecht University, the Netherlands

The probabilistic roadmap (PRM) planner is a popular method for robot motion planning problems with many degrees of freedom. However, it has been shown that the method performs less well in situations where the robot has to pass through a narrow passage in the scene. This is mainly due to the uniformity of the sampling used in the planner; it places many samples in large open regions and too few in tight passages. Cell decomposition methods do not have this disadvantage, but are only applicable in low-dimensional configuration spaces. In this paper, a hybrid technique is presented that combines the strengths of both methods. It is based on a robot independent cell decomposition of the free workspace guiding the probabilistic sampling more toward the interesting regions in the configuration space. The regions of interest (narrow passages) are identified in the cell decomposition using a method we call watershed labeling. It is shown that this leads to improved performance on difficult planning problems in two- and three-dimensional workspaces.

Key Words: path planning • probabilistic roadmaps • narrow-passage problem

The International Journal of Robotics Research, Vol. 24, No. 12, 1055-1071 (2005)
DOI: 10.1177/0278364905060132


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?

This article has been cited by other articles:

				D. Hsu, J.-C. Latombe, and H. Kurniawati On the Probabilistic Foundations of Probabilistic Roadmap Planning The International Journal of Robotics Research, July 1, 2006; 25(7): 627 - 643. [Abstract] [PDF]