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.
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)
References:
Archives