Planner Overview

 

Jump to section:

 

·        Pre – processing

·        Roadmap Construction

·        Query Stage

·        Definitions

 

 

 

Pre-Processing: Compute information about the environment.

 

  • Compute Discretized GVD
    • Depth Buffer - For each voxel, stores the distance to closest obstacle.
      Color Buffer - Stored color represents the ID of the closest obstacle.

 

 

  • How We Use the Color Buffer

 

    • Boundary Graph of GVD The boundary graph encodes the connectivity of free space.  We extract the graph using a marching cubes algorithm.

 

  • How We Use the Depth Buffer

 

o       Narrow Passage

Identified by a heuristic.  If the clearance in an area is roughly equal to the robots enclosing sphere, we consider it narrow.

 

o       Medial Axis

From the depth buffer we can extract the medial axis.  The algorithm biases all sampling towards the medial axis.

 

 

o       Narrow Passage Gradient

We use the gradient to bias sampled angles. The idea is that we want to align the robot's principle axis with the gradient.

 

o       Collision Queries

Planners spend a high percentage of time performing collision queries (local planning, configuration classification, etc). So, to "make the common case fast", we use the depth buffer to quickly test if a configuration is in Cfree.  If our QR comparison is inconclusive, we use PQP for exact detection.

 

Roadmap Construction: Builds the network of configuration used in the queries.

 

  • The roadmap construction and query stage are combined.  Thus, each query contributes new connectivity to the roadmap over time.

 

 

 

Path Planning Query: Tries to find a path from initial to goal configuration.

 

  • This step adds connectivity information to the roadmap as it solves the query.

 

 

  • Algorithm:

 

1.    Grow The Roadmap

 

Let Ci and Cg be components initially containing only the initial and goal configuration respectively.  We iteratively expand each until a path is found from a node in Ci to one in Cg using a local planner.

 

2.    Expanding a Component

 

To expand C, select a few nodes Ne from C at random, giving priority to those near the medial axis, and in low-density areas.  For each Ne, we select a few random configurations Nr in the neighborhood of Ne.  The planner then inserts Nr into the roadmap, but only if it is in Cfree and can be connected to Ne via the local planner.

 

3.    Connect Components

 

The planner tries to join C with another component C’.  For each new node Nr, we search for a node in C’ that can connect to Nr via local planning.

 

Definitions

 

PRM (Probabilistic Roadmap Planner)

 

PRMs are a general class of motion planning algorithms.  These planners generate roadmaps in the form of networks of random configurations.  The idea is to construct a roadmap and then attempt to connect initial and goal configurations into the roadmap.

 

Roadmap

 

A roadmap consists of multiple disconnected components.  Each component is a graph of configurations in Cfree.  Two nodes are connected if a local planner can find a path between them.

 

Local Planner

 

This is generally an efficient routine to calculate a path between two configurations. Typically, these planners use simple linear interpolation.

 

Configuration Space

 

The configuration space (C-space) of a robot is the set of all possible values for q, the transformation that can be applied to a robot.  The dimension of the C-space is equal to the degrees of freedom of the robot.  Further, C-space is divided into three qualitative regions: contact space, blocked space and free space.

 

Free space (Cfree)

 

Free space refers to the subset of configurations that cause a robot to be in a collision free condition.

 

Copyright 1999. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the author.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

geom@cs.unc.edu

last updated: 12/12/1999