Contents I. Introduction
Motion planning is concerned with automatic planning of a collision-free path between initial and final configurations. The classical motion planning problem, termed the piano movers problem, is defined for complete a priori information about the obstacles in the environment. The piano movers model is formulated as follows [15]. Given are a solid object of known size and shape in two- or three-dimensional space, its initial and target position and orientation, and a set of obstacles in the environment. The shapes, positions and orientations of the obstacles in space are fully described. The task is to find a continuous path for the object from its initial position to the target position, while avoiding collisions with obstacles along the way. Because full information is assumed, the whole operation of path planning is a one-time off-line operation. The basic requirements become soundness (collision free path), completeness (guaranteed to find a path if it exists), optimality (being close to the optimal path) and complexity (time and space performance). The main difficulty of the piano movers model is to obtain a computationally efficient scheme.
