A search algorithm for motion planning with six degrees of freedom (Q1097053)

The problem of moving an arbitrary, rigid, polyhedral object with three translational and three rotational degrees of freedom is discussed. Solution to the classical three-dimensional movers problem is proposed. The algorithm is complete in a search-space (at a given resolution) and finds a collision-free path for taking the object from some initial configuration to a desired goal-configuration. The solution to the movers problem given in the paper is by transforming the problem to the point navigation problem in \({\mathbb{R}}^ 3\times SO(3)\) (hence-after called configuration space or C-space), where obstacles appear as six- dimensional manifolds, bounded by five-dimensional C-surfaces. Topological properties of these surfaces as well as intersections are characterized in the paper. For travelling in C-space among obstacles three basic operators are introduced, whose closure completely defines the search space. Some heuristic navigation strategies in C-space, based on local geometrical information are proposed and then the best first search algorithm is employed in order to find a path. The algorithm has been implemented for 6 d.o.f. Cartesian manipulators. Graphical simulation results are illustrating the paper. Two appendices concerning the geometry of obstacles in C-space and some useful mathematical definitions for motion planning complete this clearly written paper. The bibliography is comprehensive.