Complexity of the mover's problem and generalizations
Published 1 October 1979
John H. Reif
Citations763
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper concerns the problem of moving a polyhedron through Euclidean space while avoiding polyhedral obstacles.
Abstract
This paper concerns the problem of moving a polyhedron through Euclidean space while avoiding polyhedral obstacles.
Keywords
Computer ScienceMathematics
Journal of Computer and System SciencesRelationships between nondeterministic and deterministic tape complexities
1,362 Citations1970Walter J. Savitch
The amount of storage needed to simulate a nondeterministic tape bounded Turingmachine on a deterministic Turing machine is investigated and a specific set is produced, namely the set of all codings of threadable mazes, such that, if there is any set which distinguishes nondeter microscopic complexity classes from deterministic tape complexity classes, then this is one such set.
A Mobile Automaton: An Application of Artificial Intelligence Techniques
542 Citations1969Nils J. Nilsson
The main theme of the research is the integration of the necessary planning systems, models of the world, and sensory processing systems into an efficient whole capable of performing a wide range of tasks in a real environment.
Modelling, Trajectory Calculation and Servoing of a Computer Controlled Arm
369 Citations1972Richard Paul
In modelling the author uses a symbolic data structure to represent objects in the environment and a planning program interprets symbolic arm control instructions and generates a plan consisting of arm motions and hand actions.
CaltechTHESIS (California Institute of Technology)Collision Detection and Avoidance in Computer Controlled Manipulators
279 Citations2018Shriram Mahabal Udupa
It is shown how the principles of hierarchical decomposition can be used to reduce the complexity of the manipulator trajectory planning problem and how it is possible to decompose the planning task so as to get the best of both cartesian space and joint space representations, and yet avoid the constant conversion overhead problem.
Journal of the ACMA Procedure for Detecting Intersections of Three-Dimensional Objects
62 Citations1968Paul G. Comba
A procedure has been developed for detecting intersections of convex regions in 3-space by means of a pseudocharacteristic function and a system of programs embodying these techniques is described.
ComputerRobots, Models, and Automation
13 Citations1979Gavin Paul
Low-cost, mass-produced industrial robots could free human workers from the tedium of the assembly line within the next decade, according to researchers at the Massachusetts Institute of Technology.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Finding the Intersection of a Set of n Half-Spaces in Time O(nlogn).
5 Citations1977F. P. Preparata, David E. Muller
A significant consequence of this result is that a three-variable linear, or convex, programming problem can be asymptotically solved faster than by the Simplex algorithm, in the worst case.