Finding Feasible Paths for a Two-Point Body.

Motion planning or the problem of finding a path for a robot is a fundamental problem in the fields of robotics and industrial automation. In particular, it has become increasing important to design efficient algorithms to solve the following problem: Given a robot and a description of its environment, plan a path for the robot between two specified positions which avoids collision with the obstacles in the environment. This type of motion planning problem is sometimes referred to as the Piano Movers' Problem. Polynomial algorithms have been developed for instances of this problem in which the degrees of freedom of both the environment and the robot have been constrained.