One of the ultimate goals in robotics is the creation of 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 dome rather than how to do it. This book discusses a central problem in the development of autonomous robots. Motion planning, the central theme of this book, can be loosely defined as follows: how can a robot decide what motions to perform in order to achieve as a goal the arrangement 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 own motions.