A Comparative Study of Probabilistic Roadmap Planners

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 Overmars. A Comparative Study of Probabilistic Roadmap Planners.
In Proc. Workshop on the Algorithmic Foundations of Robotics (WAFR'02), 2002, pp. 43-57.
Full text: [pdf] Presentation: [ppt]

Roland Geraerts and Mark Overmars. Sampling Techniques for Probabilistic Roadmap Planners.
In Conference on Intelligent Autonomous Systems (IAS-8), 2004, pp. 600-609.
Full text: [pdf] Presentation: [ppt]

Roland Geraerts and Mark Overmars. Sampling and Node Adding in Probabilistic Roadmap Planners.
Journal of Robotics and Autonomous Systems (RAS), 54:165-173, 2006.
Full text: [pdf]
Sampling methods

Software
The (Windows) framework can be downloaded here [2.16MB]. The zip file also contains all test environments and robots. Commercial usage is not allowed. On the SAMPLE homepage, you can find more information about the scenes and file formats.

Follow-up research
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 here: reachability analysis.

Movies of the studied test scenes
Here you see some computed (and smoothed) paths in our test scenes (i.e. rooms, corridor, clutter, hole, house, respectively).

Rooms: In this scene there are three rooms with lots of space and with narrow doors between them. So the density of obstacles is rather non-uniform. The table must move through the two narrow doors to the other room. The table is rather complex because it has four cylindrical legs, leading to more time-consuming collision checking. Corridor: This is the most simple scene. An L-shaped object must translate and rotate through a winding corridor to the other end. Some obstacles force rotation of the object. We expect that all methods can solve this problem very quickly. Clutter: This scene consists of 500 uniformly distributed tetrahedra. An L-shaped object must move among them from one corner to the other. The configuration space will consist of many narrow corridors. There are multiple solutions to the query. Hole: A rather famous test scene. The moving object consists of four legs and must rotate in a complicated way to get through the hole. The hole is placed off-center to avoid that certain grid-based method have an advantage. The configuration space will have two large open areas with (most likely) two narrow winding passages between them. House: The house is a complicated scene consisting of 1600 polygons. It has many small rooms. As a result a large roadmap will be required to cover the free space. Also, because walls are thin, the collision checker must make rather small steps along the paths, resulting in much higher collision checking times.