[mod.ai] Seminar - Advances in Computational Robotics

Richard.Wallstein@A.CS.CMU.EDU (10/20/86)

	     Robotics Seminar, FRIDAY Oct. 24, 2 PM, 4623 WeH
 
			   John H. Reif
		    Computer Science Department
			  Duke University
 
	      ADVANCES IN THE THEORY OF COMPUTATIONAL ROBOTICS
 
This talk surveys work on the computational complexity of various movement
planning problems relevant to robotics.  The generalized mover's problem is to
plan a sequence of movements of linked polyhedra through 3-dimensional
Euclidean space, avoiding contact with a fixed set of polyhedra obstacles.
We discuss algorithms for solving restricted mover's problems and our proof
that generalized mover's problems are polynominal space hard.
We also discuss our results on the computational complexity (both algorithms
and lower bounds) of three other quite different types of movement problems;
 
	1.  movement planning in the presence of friction;
 
	2.  minimal movement planning;
 
	3.  dynamic movement planning with moving obstacles.