Motion Planning Using Random Networks

(c) 2001 Matthias S. Benkmann <m.s.b (a) gmx.net>

Permission granted to reproduce this article non-commercially as long as it remains unmodified with copyright and this notice intact.

This article gives a short overview of methods used for planning the movements of abstract objects with several degrees of freedom, followed by a complete discussion of a probabilistic roadmap-based approach. The algorithm described is well-suitable to many motion planning problems in (mostly) static environments. The article describes the algorithm in general terms and also gives a discussion of implementation details and possible optimizations.


Table of Contents
1. Introduction
2. Defining the Problem
3. Different Approaches
4. The Probabilistic Roadmap Planner
4.1. Algorithm Overview
4.2. Preprocessing Phase
4.3. Query Phase
4.4. Solving Problems with Narrow Spaces
4.5. Implementation Issues
5. Literature