Motion Planning with Six Degrees of Freedom

The motion planning problem is of central importance to the fields of robotics, spatial planning, and automated design. In robotics we are interested in the automatic synthesis of robot motions, given high-level specifications of tasks and geometric models of the robot and obstacles. The Mover...

Full description

Bibliographic Details
Main Author: Donald, Bruce R.
Language:en_US
Published: 2004
Online Access:http://hdl.handle.net/1721.1/6944
_version_ 1826190250762829824
author Donald, Bruce R.
author_facet Donald, Bruce R.
author_sort Donald, Bruce R.
collection MIT
description The motion planning problem is of central importance to the fields of robotics, spatial planning, and automated design. In robotics we are interested in the automatic synthesis of robot motions, given high-level specifications of tasks and geometric models of the robot and obstacles. The Mover's problem is to find a continuous, collision-free path for a moving object through an environment containing obstacles. We present an implemented algorithm for the classical formulation of the three-dimensional Mover's 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 intersections, collision-free paths may be found by the closure of three operators which (i) slide along 5-dimensional intersections of level C-Space obstacles; (ii) slide along 1- to 4-dimensional intersections of level C-surfaces; and (iii) jump between 6 dimensional obstacles. Implementing the point navigation operators requires solving fundamental representational and algorithmic questions: we will derive new structural properties of the C-Space constraints and shoe how to construct and represent C-Surfaces and their intersection manifolds. A definition and new theoretical results are presented for a six-dimensional C-Space extension of the generalized Voronoi diagram, called the C-Voronoi diagram, whose structure we relate to the C-surface intersection manifolds. The representations and algorithms we develop impact many geometric planning problems, and extend to Cartesian manipulators with six degrees of freedom.
first_indexed 2024-09-23T08:37:22Z
id mit-1721.1/6944
institution Massachusetts Institute of Technology
language en_US
last_indexed 2024-09-23T08:37:22Z
publishDate 2004
record_format dspace
spelling mit-1721.1/69442019-04-09T18:49:48Z Motion Planning with Six Degrees of Freedom Donald, Bruce R. The motion planning problem is of central importance to the fields of robotics, spatial planning, and automated design. In robotics we are interested in the automatic synthesis of robot motions, given high-level specifications of tasks and geometric models of the robot and obstacles. The Mover's problem is to find a continuous, collision-free path for a moving object through an environment containing obstacles. We present an implemented algorithm for the classical formulation of the three-dimensional Mover's 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 intersections, collision-free paths may be found by the closure of three operators which (i) slide along 5-dimensional intersections of level C-Space obstacles; (ii) slide along 1- to 4-dimensional intersections of level C-surfaces; and (iii) jump between 6 dimensional obstacles. Implementing the point navigation operators requires solving fundamental representational and algorithmic questions: we will derive new structural properties of the C-Space constraints and shoe how to construct and represent C-Surfaces and their intersection manifolds. A definition and new theoretical results are presented for a six-dimensional C-Space extension of the generalized Voronoi diagram, called the C-Voronoi diagram, whose structure we relate to the C-surface intersection manifolds. The representations and algorithms we develop impact many geometric planning problems, and extend to Cartesian manipulators with six degrees of freedom. 2004-10-20T20:09:58Z 2004-10-20T20:09:58Z 1984-05-01 AITR-791 http://hdl.handle.net/1721.1/6944 en_US AITR-791 25460704 bytes 9664942 bytes application/postscript application/pdf application/postscript application/pdf
spellingShingle Donald, Bruce R.
Motion Planning with Six Degrees of Freedom
title Motion Planning with Six Degrees of Freedom
title_full Motion Planning with Six Degrees of Freedom
title_fullStr Motion Planning with Six Degrees of Freedom
title_full_unstemmed Motion Planning with Six Degrees of Freedom
title_short Motion Planning with Six Degrees of Freedom
title_sort motion planning with six degrees of freedom
url http://hdl.handle.net/1721.1/6944
work_keys_str_mv AT donaldbrucer motionplanningwithsixdegreesoffreedom