by Salik Syed
Motion planning is a branch of computer science concentrating upon the computation of
paths for robots or digital actors through complex spaces subject to various constraints.
Examples of motion planning include path computation for multilimbed robots in automobile assembly plants, path computation for climbing or walking robots, or even dosage
optimization for radiosurgery. In this article, I present new techniques that better compute paths for
vehicular robots, specifically those that move through terrain that affects the dynamics of vehicle
motion to a large degree. An excellent illustration of motion planning is a skateboarder moving
through a series of ramps in order to reach a goal location. In this situation, reasoning is essential—
a skateboarder may need to take a circuituous route and take ramps in order to reach a target location.
Unfortunately, computers have very limited “reasoning” abilities.
However, they have vast computational power. Due to this, the space
of motions of a robot must be searched until a motion that leads to
the goal location is reached. Unfortunately, the dimensionality of this
space is often sufficiently large that a typical search or even a probabilistic roadmap-based approach (see “Finding Paths”), would not be
computationally feasible. In order to overcome this fact, human-defined heuristic functions must be used to more efficiently explore
the space defining a robot’s set of available actions and their resulting
motion. This article will present a generalized overview of the
motion planning problem, as well as heuristic methods that improve
motion planning for vehicles in dynamic environments.
Formulating the Problem
In order to conduct motion planning, the robot’s location in space
must first be represented. In order to do this, the motion of an individual robot is generalized to a space known as the configuration
space. The simplest example of a configuration space is that of a
robot that moves on flat land, whose position is parameterized by the
vector, [x, y]. The configuration space, C, for this robot is the plane,
R2. Each point in C corresponds to a unique configuration of the
robot in the work space, W, which is either 2-D or 3-D Euclidean
space. More degrees of freedom in a robot increases the dimensionality of the configuration space, but not the work space. If an orientation to this robot is added, a 3-D configuration space is now
created, because the parameterization of the robot is now [x, y, Θ].
Obstacles in the work space can also be transformed to points in
the configuration space. By doing this, the configuration space is split
into two regions, free space and obstacle space. The free space, F, is
all points, p C, such that the robot’s configuration at point p does
not result in collision. The obstacle space is then simply the set of
points not in F (see Figure 1).
The obstacle space may be used to represent configurations of the
robot that result in self-intersection or unstable configurations and
need not represent physical obstacles. It is important to note that the
Figure 1: Work space and configuration space of a disc-shaped robot parameterized by [x, y]. Note that the obstacle in
the configuration space maps to the set of configurations,
which results in collision in the work space—this corresponds
to the swept area of the robot about the obstacle. The robot is
now reduced to a simple point.
topology and dimensionality of the configuration space may be vastly
different from that of the work space. The configuration space is often
a high-dimensional space with complex topology. In contrast, the
work space is almost always 2-D or 3-D Euclidean space. To demonstrate this, examine the example of the two-jointed arm (Figure 2).
Figure 2: Work space and configuration space of a two-joint
robot parameterized by joint angles, [q1,q2].
(Drawing courtesy of Prof. Jean-Claude Latombe)