Motion Planning with Six Degrees of Freedom. Revision

Abstract

The motion planning problem is of central importance to the fields of robotics, spatial planning, and automated design. An implemented algorithm is presented for the 'classical' formulation of the three-dimensional Movers' problem: Given an arbitrary rigid polyhedral moving object 'p' with three translational and three rotational degrees of freedom, find a continuous, collision free path taking 'p' from some initial configuration to a desired goal configuration. This thesis describes the first known implementation of a complete algorithm (at a given resolution) for the full six degree of freedom Movers' problem. The algorithm transforms the six degree of freedom planning problem into a point navigation problem in a six-dimensional configuration space (called C-Space). The C-Space obstacles, which characterize the physically unachievable configurations, are directly represented by six-dimensional manifolds whose boundaries are five dimensional C-surfaces. By characterizing these surfaces and their intersection collision-free paths may be found by the closure of three operators which (i) slide along 5-dimensional level C-surfaces parallel to C-Space obstacles; (ii) slide along 1- to 4-dimensional intersections of level C-surfaces; and (iii) jump between 6-dimensional obstacles.