Topologically, the configuration space of this robot is a torus. This
is easy to see because the orientation, 2π, is equivalent to the orientation, 0, for both joints. If this torus is “unwrapped,” the correspondence between the work space and configuration spaces can be seen
(see Figure 3).
Figure 3: Work space and configuration space of a two-joint
robot parameterized by angles, [q1,q2]. Note that the mapping
from work space to configuration space is not as intuitive as
the disc robot. (Drawing courtesy of Prof. Jean-Claude Latombe)
Moving obstacles in the work space can be elegantly represented
by simply introducing another dimension, time, to the configuration
space. The configuration space provides a simple mathematical representation of the robot’s possible states, given the present environment. The generalized planning problem now reduces to finding a
path fully contained in the free space that connects two configurations, p, p . It is easy to see that while all robot states actually occur in
2-D or 3-D Euclidean space, there are many parameters that define
those states. Because there are many such parameters (to define a
human’s exact state can take hundreds of parameters), this space is
often high dimensional and of complex topology.
The free space can be analyzed using standard search methods, such
as gradient descent, or even by explicitly computing and partitioning
the free space and obstacle geometry. However, these techniques
generally work only for low-dimensional configuration spaces.
Explicit computation of the geometry of configuration spaces is
extremely difficult for spaces of more than three dimensions.
Gradient descent works well for slightly higher dimensions but fails
to find solutions when the dimensionality further increases, because
of its tendency to get “trapped” in local minima [ 5].
Because standard algorithms fail to produce results in high-dimensional spaces, a new method known as the probabilistic
roadmap was introduced. A probabilistic roadmap chooses configurations at random in the configuration space. Configurations that
belong to the free space and are within a certain metric of each other
are connected via an arc. This arc must also satisfy the property that
all points on the arc are in the free space. The primary cost of building the roadmap is checking this arc to ensure that it is collision free.
After many samples, this method creates a graph approximating the
connectivity of the free space (see Figure 4).
This graph is known as the probabilistic roadmap. The nodes of
this graph are often referred to as milestones. In order to find a path,
the roadmap is simply searched to see if a configuration can be
Figure 4: Probabilistic roadmaps of a simple configuration space.
Nodes are connected to approximate connectivity of free space.
reached within some metric of the goal configuration. This can be
done using standard graph-search algorithms. It is important to note
that the path returned by the roadmap may be far from optimal, due
to the random nature of milestone selection. The running time of the
roadmap, however, is bounded, given that the configuration space
satisfies a geometric property known as expansiveness. Expansiveness, in the simplest sense, is the lack of “narrow passages” in the
space being sampled. To picture this concept, consider two rooms
connected by a long hallway. As the width of the hallway decreases,
so does the expansiveness of the space. If this expansiveness is sufficiently high, the probability of the planner finding a path grows exponentially with the number of configurations sampled. Thus, this type
of planner is said to be probabilistically complete .
Various improvements can also be implemented to better characterize the connectivity. One simple method is to oversample regions
where failed nodes and successful nodes occur within a certain distance
of each other—the intuition being that more information is needed near
obstacle boundaries than near large empty portions of free space [ 1].
Planning with Non-Holonomic or Dynamic Robots
The probabilistic roadmap approach assumes that given two configurations whose connecting arc is in the free space, the robot can travel
from one to the other. This works well for multijoint arm type robots
or omnidirectional robots, which can move along any arc in free
space. This is not the case if there is a robot with a non-holonomic
constraint. A non-holonomic robot’s motion constraints are
described by a set of nonintegrable differential equations. The theory
behind these constraints is quite complex. For the purposes of this
paper, the main point is that such constraints limit the robot from
travelling along an arbitrary path in the free space. Given constraints
such as these, a path found in the free space may not be feasible
because the vehicle cannot transition between two milestones.
Because of this limitation, a new planning method was created that
extends the basic roadmap; this method is known as kinodynamic
roadmap-based planning [ 6]. Instead of randomly sampling configurations in the configuration space, the initial position, p, is the starting point. From p, new configurations are expanded based on a
sampling of the control space. The control space is simply the set of
possible actions the robot can take from the present state. For a car,
this may correspond to turning the wheels left or right or accelerating.
The application of a control results in new configuration that is reachable from p. Thus, the roadmap takes the form of a tree, with the initial position being the root node. Any node can be chosen to expand