Homepage of Roland Geraerts

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 Small Roadmaps for Solving Motion Planning Problems

Small roadmap for a large 3D environment.

Abstract

In robot motion planning, many algorithms have been proposed that create a roadmap from which a path for a moving object can be extracted. These algorithms generally do not give guarantees on the quality of the roadmap, i.e. they do not promise that a path will always be found in the roadmap if one exists in the world. Furthermore, such roadmaps often become very large which can cause memory problems and high query times.

We present a new efficient algorithm that creates small roadmaps for two- and three-dimensional problems. The algorithm ensures that a path is always found (if one exists) at a given resolution. These claims are verified on a broad range of environments. The results also give insight in the structure of covering roadmaps.

References

Roland Geraerts and Mark H. Overmars. Creating Small Graphs for Solving Motion Planning Problems. In IEEE International Conference on Methods and Models in Automation and Robotics (MMAR'05) , pp. 531-536, 2005.