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.

Creating High-quality Roadmaps for Motion Planning in Virtual Environments

Creating high-clearance paths, short paths, and short minimum-clearance paths.

Techniques that improve the path clearance of a roadmap graph.


Our goal is to create roadmaps that are particularly suited for motion planning in virtual environments. We use our Reachability Roadmap Method to compute an initial, resolution complete roadmap. In addition, this roadmap is small which keeps query times and memory consumption low. However, for use in virtual environments, there are additional criteria that must be satisfied. In particular, we require that the roadmap contains useful cycles. These provide short paths and alternative routes which allow for variation in the routes a moving object can take. We will show how to incorporate such cycles. In addition, we provide high-clearance paths by retracting the edges of the roadmap to the medial axis. Since all operations are performed in a preprocessing phase, high-quality paths can be extracted in real-time as is required in interactive applications.


  • Roland Geraerts and Mark H. Overmars. Creating High-quality Roadmaps for Motion Planning in Virtual Environments. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'06), pp. 4355-4361, 2006.

    pdf pptx

Some results

Retracted roadmaps.

Retracted roadmaps.