Planning, Geometry, and Complexity of Robot Motion

Planning, Geometry, and Complexity of Robot Motion
Edited by Jacob T. Schwartz, Micha Sharir, John Hopcroft


TJ211.4, P57, 1987

Jacob T. Schwartz and Micha Sharir, On the Piano Movers' Problem I. The Case of a Two-Dimensional Rigid Polygonal Body Moving Amidst Polygonal Barriers
In moving a body which is a line segment or "ladder" among obstacles consisting of polyhedral walls from a starting position to a goal position, either find a continuous motion connecting the two positions or show that no such motion exists.


Jacob T. Schwartz and Micha Sharir, On the Piano Movers' Problem II. General Techniques for Computing Topological Properties of Real Algebraic Manifolds
Extends the discussion of part I to include bodies which may be hinged (that is, they may allow motion around various joints).


Jacob T. Schwartz and Micha Sharir, On the Piano Movers' Problem III. Coordinating the Motion of Several Independent Bodies: The Special Case of Circular Bodies Moving Amidst Polygonal Barriers
Extends the discussion of part I to 2-dimensional circular bodies which avoid collision with the walls and with each other.


Micha Sharir and Elka Ariel-Sheffi, On the Piano Movers' Problem IV. Various Decomposable Two-Dimensional Motion Planning Problems
Addresses various special problems involving arbitrarily many degrees of freedom which have relatively simple solutions by the techniques of determing the non-critical regions and using a connectivity graph.


Jacob T. Schwartz and Micha Sharir, On the Piano Movers' Problem V. The Case of a Rod Moving in Three-Dimensional Space Amidst Polyhedral Obstacles
Addresses some 3-dimensional special cases, principally the motion of a rod moving among polyhedral obstacles.

Learn about Micha Sharir
Learn about Jacob T Schwartz

Report by Eric Johnson, CPSC 643, Fall 1996

Eric's Home Page