Homepage > Motion planning > List of publications > Paper

One of the fundamental tasks robots have to perform is planning their motions while avoiding collisions with obstacles in the environment. This is the central topic of the thesis. We restrict ourselves to motion planning for two- and three-dimensional rigid bodies and articulated robots moving in static and known virtual environments.

A Comparative Study of Probabilistic Roadmap Planners

Different sampling strategies used by the Probabilistic Roadmap Planner (PRM).

Different sampling strategies used by the Probabilistic Roadmap Planner (PRM).

Abstract

The probabilistic roadmap approach is a commonly used motion planning technique. A crucial ingredient of the approach is a sampling algorithm that samples the configuration space of the moving object for free configurations. Over the past decade many sampling techniques have been proposed. It is difficult to compare the different techniques because they were tested on different types of scenes, using different underlying libraries, implemented by different people on different machines. We compared twelve of such sampling techniques within a single environment on the same scenes. The results were surprising in the sense that techniques often performed differently than claimed by the designers. The study also showed how difficult it is to evaluate the quality of the techniques. The results should help users in deciding which technique is suitable for their situation.

References

  • Roland Geraerts and Mark H. Overmars. Sampling and Node Adding in Probabilistic Roadmap Planners. Robotics and Autonomous Systems (RAS), 54:165-173, 2006.

    pdf

  • Roland Geraerts and Mark H. Overmars. Sampling Techniques for Probabilistic Roadmap Planners. In Conference on Intelligent Autonomous Systems (IAS-8), pp. 600-609, 2004.

    pdf pptx

  • Roland Geraerts and Mark H. Overmars. A Comparative Study of Probabilistic Roadmap Planners. In Proc. Workshop on the Algorithmic Foundations of Robotics (WAFR'02), pp. 43-57, 2002.

    pdf pptx

A more elaborate version of this study can be found in Chapter 2 of my Ph.D. thesis.

The successor of this study can be found in our reachability analyses.

Some movies of the studied test scenes are showed on the motion planning software page.

Examples

The roadmap graph we get for the difficult hole test scene used in this paper. The left image shows the graph using halton sampling and the right image uses gaussian sampling.

Different roadmap graphs.

Different roadmap graphs.

These are the tested uniform sampling distributions. Each image shows a typical distribution of 500 samples.

Uniform sampling strategies: Random, Grid, Halton, Cell-based.

Uniform sampling strategies: Random, Grid, Halton, Cell-based.

These are the tested non-uniform sampling distributions. Each image shows a typical distribution of 500 samples.

Uniform sampling strategies: Gaussian, Obstacle-based, Obstacle-based*, Bridge, Medial axis, Nearest contact.

Non-uniform sampling strategies: Gaussian, Obstacle-based, Obstacle-based*, Bridge, Medial axis, Nearest contact.