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.