Robot Modeling and Control, 2nd Edition

CHAPTER 7PATH AND TRAJECTORY PLANNING

In previous chapters we studied the geometry of robot arms, developing solutions for both the forward and inverse kinematics problems. The solutions to these problems depend only on the intrinsic geometry of the robot, and they do not reflect any constraints imposed by the workspace in which the robot operates. In particular, they do not take into account the possibility of collision between the robot and objects in the workspace or collision between the robot and the boundaries of its workspace (e.g., walls, floor, closed doors). In this chapter we address the problem of planning collision-free paths for robots. We will assume that the initial and final configurations of the robot are specified and that the problem is to find a collision-free path connecting these configurations.

The description of this problem is deceptively simple, yet the path planning problem is among the most difficult problems in computer science. For example, the computation time required by the best known complete¹ path planning algorithm grows exponentially with the number of internal degrees of freedom of the robot. For this reason, complete algorithms are used in practice only for simple robots with few degrees of freedom, such as mobile robots that translate in the plane. For robots that have more than a few degrees of freedom or are capable of rotational motion, path planning problems are often treated as search problems. The algorithms that are used for such ...