Reference

• Roland Geraerts. Sampling-based Motion Planning: Analysis and Path Quality. Ph.D. thesis. Utrecht University. 2006.

  

  

Overview

This thesis has been divided into two parts. The first part deals with comparing and analyzing sampling-based motion planning techniques, in particular variants of the Probabilistic Roadmap Method (PRM).
The PRM consists of two phases: a construction and a query phase. In the construction phase, a roadmap (graph) is built, approximating the motions that can be made in the environment. First, a free random sample is created. Such a sample describes a particular placement of the moving object (robot) in the workspace. Then, a simple local planner is employed to connect the sample to some neighbors. Samples and connections are added to the graph until the roadmap is dense enough. In the query phase, the start and goal samples are connected to the graph. The path is obtained by a Dijkstra's shortest path algorithm.

Many variants of the PRM have been developed over the past decade. Using both time-based as well as reachability-based analysis, we compare some of the most prominent techniques. The results are surprising in the sense that techniques often perform differently than claimed by the designers. In addition, contrary to general belief, 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 more powerful local planner, a refined neighbor selection strategy and a hybrid sampling strategy. The analysis also shows why the PRM successfully deals with many motion planning problems.

The second part deals with quality aspects of paths and roadmaps. A good path is relatively short, keeps some distance (clearance) from the obstacles, and is smooth.
We will provide algorithms that increase path clearance. A big advantage of these algorithms is that high-clearance paths can now be efficiently created without using complex data structures and algorithms. We also elaborate on algorithms that successfully decrease path length. Then, we introduce the Reachability Roadmap Method which creates small roadmaps for two- and three-dimensional problems. Such a small roadmap has many advantages over a roadmap that is created by the PRM. In particular, the method assures low query times, low memory consumption, and the roadmap can be optimized easily. The algorithm also ensures that a path is always found (if one exists) at a given resolution.
We unify the techniques to create high-quality roadmaps for interactive virtual environments. That is, we use the Reachability Roadmap Method to create an initial roadmap. We add useful cycles to provide alternative routes and short paths, and we add clearance to the roadmap to obtain high-clearance paths in real-time.

Publication overview

• Comparative studies
• Reachability analysis
• Clearance (workspace)
• Clearance (C-space) and short paths
• High-quality roadmaps
• Experimental research
• Ph.D. thesis (this page)

Invited lectures

• Invited speaker for 3rd International Planning in Games workshop: Way to go - A framework for multi-level planning in games, Rome, Italy. 2013.
• Guest lecture at Hogeschool Utrecht: Path planning in games, Utrecht, the Netherlands. 2012.
• Invited speaker for Informaticalunchlezing TUDelft: Path planning in games, Delft, the Netherlands. 2012.
• Panel participant in IROS workshop: Progress and Open Problems in Motion Planning, San Francisco, CA, USA. 2011.
• Invited speaker for Workshop: Motion Planning: From Theory to Practice, Zaragoza, Spain. 2010.
• Invited speaker for Dutch Computational Geometry Day: Planning Short Paths with Clearance using Explicit Corridors, Utrecht, the Netherlands. 2009.
• Invited speaker for a Workshop on Benchmarks in Robotics Research, Beijing, China. 2006.
• Invited speaker for seminar on Robot Navigation, Dagstuhl, Germany. 2003.