A search algorithm for motion planning with six degrees of freedom (Q1097053): Difference between revisions

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.