Skip to main content
main-content

Über dieses Buch

One of the ultimate goals in Robotics is to create autonomous robots. Such robots will accept high-level descriptions of tasks and will execute them without further human intervention. The input descriptions will specify what the user wants done rather than how to do it. The robots will be any kind of versatile mechanical device equipped with actuators and sensors under the control of a computing system. Making progress toward autonomous robots is of major practical inter­ est in a wide variety of application domains including manufacturing, construction, waste management, space exploration, undersea work, as­ sistance for the disabled, and medical surgery. It is also of great technical interest, especially for Computer Science, because it raises challenging and rich computational issues from which new concepts of broad useful­ ness are likely to emerge. Developing the technologies necessary for autonomous robots is a formidable undertaking with deep interweaved ramifications in auto­ mated reasoning, perception and control. It raises many important prob­ lems. One of them - motion planning - is the central theme of this book. It can be loosely stated as follows: How can a robot decide what motions to perform in order to achieve goal arrangements of physical objects? This capability is eminently necessary since, by definition, a robot accomplishes tasks by moving in the real world. The minimum one would expect from an autonomous robot is the ability to plan its x Preface own motions.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction and Overview

Abstract
A robot is a versatile mechanical device — for example, a manipulator arm, a multi-joint multi-fingered hand, a wheeled or legged vehicle, a free-flying platform, or a combination of these — equipped with actuators and sensors under the control of a computing system. It operates in a workspace within the real world. This workspace is populated by physical objects and is subject to the laws of nature. The robot performs tasks by executing motions in the workspace.
Jean-Claude Latombe

Chapter 2. Configuration Space of a Rigid Object

Abstract
In Chapter 1 we introduced configuration space as a space in which the robot maps to a point. The mathematical structure of this space, however, is not completely straightforward, and deserves some specific consideration. The purpose of this chapter and the next one is to provide the reader with a general understanding of this structure when the robot is a rigid object not constrained by any kinematic or dynamic constraint. This chapter mainly focuses on topological and differential properties of the configuration space. More detailed algebraic and geometric properties related to the mapping of the obstacles into configuration space will be investigated in Chapter 3.
Jean-Claude Latombe

Chapter 3. Obstacles in Configuration Space

Abstract
Obstacles in the workspace W map in the configuration space C to regions called C-obstacles. In Chapter 2 we defined the C-obstacle CB corresponding to a workspace obstacle B as the following region in C:
$$CB = \{ q \in C/A(q) \cap B \ne 0\} $$
.
Jean-Claude Latombe

Chapter 4. Roadmap Methods

Abstract
In this chapter we describe a first approach to robot path planning which we name the roadmap approach. This approach is based on the following general idea: capture the connectivity of the robot’s free space C free in the form of a network of one-dimensional curves — the roadmap — lying in C free or its closure cl(C free ). Once constructed, a roadmap R is used as a set of standardized paths. Path planning is reduced to connecting the initial and goal configurations to R, and searching R for a path.
Jean-Claude Latombe

Chapter 5. Exact Cell Decomposition

Abstract
In this chapter we describe a second approach to motion planning, exact cell decomposition. The principle of this approach is to first decompose the robot’s free space C free into a collection of non-overlapping regions, called cells, whose union is exactly1 C free (or its closure). Next, the connectivity graph which represents the adjacency relation among the cells is constructed and searched. If successful, the outcome of the search is a sequence of cells, called a channel, connecting the cell containing the initial configuration to the cell containing the goal configuration. A path is finally extracted from this sequence.
Jean-Claude Latombe

Chapter 6. Approximate Cell Decomposition

Abstract
In this chapter we investigate another cell decomposition approach to path planning which is known as the approximate cell decomposition approach. It consists again of representing the robot’s free space C free as a collection of cells. But it differs from the exact cell decomposition approach in that the cells are now required to have a simple prespecified shape, e.g. a rectangloid shape. Such cells do not in general allow us to represent free space exactly. Instead, a conservative approximation of this space is constructed, hence the name of the approach. As with the exact cell decomposition approach, a connectivity graph representing the adjacency relation among the cells is built and searched for a path.
Jean-Claude Latombe

Chapter 7. Potential Field Methods

Abstract
The planning methods described in the previous three chapters aim at capturing the global connectivity of the robot’s free space into a condensed graph that is subsequently searched for a path. The approach presented in this chapter proceeds from a different idea. It treats the robot represented as a point in configuration space as a particle under the influence of an artificial potential field U whose local variations are expected to reflect the “structure” of the free space. The potential function is typically (but not necessarily) defined over free space as the sum of an attractive potential pulling the robot toward the goal configuration and a repulsive potential pushing the robot away from the obstacles. Motion planning is performed in an iterative fashion. At each iteration, the artificial force \( \vec{F}(q) = - \vec{\nabla }U(q) \) induced by the potential function at the current configuration is regarded as the most promising direction of motion, and path generation proceeds along this direction by some increment.
Jean-Claude Latombe

Chapter 8. Multiple Moving Objects

Abstract
In this chapter as well as the next three, we investigate various extensions of the basic motion planning problem. In the present chapter we begin this investigation with a series of extensions which all involve multiple moving objects.
Jean-Claude Latombe

Chapter 9. Kinematic Constraints

Abstract
In this chapter we study the path planning problem for a robot subject to kinematic constraints, i.e. an object (or a collection of objects) that cannot translate and rotate freely in the workspace. Indeed, so far, we have only investigated the case of free-flying robots. The only exception occurred in the last section of the previous chapter, when we considered articulated robots made of several objects connected by joints. The constraint imposed by a joint on the relative motion of the two objects it connects is a simple example of kinematic constraint.
Jean-Claude Latombe

Chapter 10. Dealing with Uncertainty

Abstract
In the previous chapters we assumed that the robot was able to perfectly control its motions, i.e. to exactly follow the geometrical paths generated by the planner. This assumption is realistic when the workspace is relatively uncluttered and the goal configuration does not have to be achieved too precisely. In those cases, if necessary, uncertainty in robot’s control can be taken into account by slightly “growing” the C-obstacles and planning a free path among the grown C-obstacles. Motions that can be planned in this way are often called gross motions.
Jean-Claude Latombe

Chapter 11. Movable Objects

Abstract
So far we have considered workspaces populated by one or several robots and by obstacles which are either stationary and not movable, or moving along predetermined trajectories. In this chapter we introduce a third kind of object: the movable object. Such an object is like a stationary obstacle, except that its location can be changed by a robot. The most usual way for a robot to change the location of a movable object, in fact the only way that we will study in some depth in this chapter, is by grasping it and moving with it.
Jean-Claude Latombe

Backmatter

Weitere Informationen