Complexity of the Generalized Mover's Problem.

Abstract

This paper concerns the problem of planning a sequence of movements of linked polyhedra through 3 dimensional Euclidean space, avoiding contact with a fixed set of polyhedra obstacles. We prove this generalized mover's problem is polynomial space hard. Our proof provides strong evidence that robot movement planning is computationally intractable, i.e., any algorithm requires time growing exponentially with the number of degrees of freedom. Keywords: Robotics; Mover's problem; Obstacle avoidence; PSPACE; Combinatorial; Geometry; Collision avoidence.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1985
Accession Number
ADA161378

Entities

People

  • John Reif

Organizations

  • Harvard University

Tags

Communities of Interest

  • Autonomy

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Automata Theory
  • Computational Complexity
  • Computations
  • Computer Science
  • Formal Languages
  • Geometry
  • Language
  • Mathematics
  • Military Research
  • Polynomials
  • Robotics
  • Robots
  • Sequences
  • Three Dimensional
  • Two Dimensional

Fields of Study

  • Engineering

Readers

  • Artificial Intelligence
  • Economics
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • AI & ML
  • AI & ML - Autonomous Systems
  • AI & ML - Machine Learning Algorithms
  • Autonomy
  • Space
  • Space - Spacecraft Maneuvers