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.

Reachability Analysis of Sampling Based Planners

The coverage and maximal connectivity criteria have been met. The reachability regions of the white nodes cover the complete free space and are connected via the black node.

Abstract

In the last fifteen years, sampling-based planners like the Probabilistic Roadmap Method (PRM) have proved to be successful in solving complex motion planning problems. While theoretically, the complexity of the motion planning problem is exponential in the number of degrees of freedom, sampling-based planners can successfully handle this curse of dimensionality in practice. We give a reachability-based analysis for these planners which leads to a better understanding of the success of the approach. This analysis compares the techniques based on coverage and connectivity of the free configuration space. The experiments show, contrary to general belief, that the main challenge is not getting the free space covered but getting the nodes connected, especially when the problems get more complicated, e.g. when a narrow passage is present. By using this knowledge, we can tackle the narrow passage problem by incorporating a refined neighbor selection strategy, a hybrid sampling strategy, and a more powerful local planner, leading to a considerable speed-up.

References

  • Roland Geraerts and Mark H. Overmars. Reachability-based Analysis for Probabilistic Roadmap Planners. Robotics and Autonomous Systems (RAS), 55:824-836, 2007.

    pdf
  • Roland Geraerts and Mark H. Overmars. Reachability Analysis of Sampling Based Planners In IEEE International Conference on Robotics and Automation (ICRA'05), pp. 406-412, 2005

    pdf pptx
  • Roland Geraerts and Mark H.Overmars. On the Analysis and Success of Sampling Based Motion Planning. In Conference of the Advanced School for Computing and Imaging (ASCI'05), pp. 313-319, 2005.

    pdf poster

Examples

A 2D star-shaped reachability region, and a 3D reachability region for a manipulator arm with 3 DOFs.

A 2D star-shaped reachability region, and a 3D reachability region for a manipulator arm with 3 DOFs.

Using a more powerful local planner results in a larger reachability region.

Straight-line and Potential field local planner.

Straight-line and Potential field local planner.

The potential field local planner is also able to 'find' the entry of a narrow passage which eases making connections through the passage:

Straight-line and Potential field local planner.

Straight-line and Potential field local planner.