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.
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
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.
1. Grow The
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
one in Cg using a local planner.
2. Expanding a
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.
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
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.
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
This is generally an efficient routine
to calculate a path between two configurations. Typically, these planners use
simple linear interpolation.
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.
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.
last updated: 12/12/1999