DocumentCode :
2185794
Title :
New lower bound techniques for robot motion planning problems
Author :
Canny, John ; Reif, John
fYear :
1987
fDate :
12-14 Oct. 1987
Firstpage :
49
Lastpage :
60
Abstract :
We present new techniques for establishing lower bounds in robot motion planning problems. Our scheme is based on path encoding and uses homotopy equivalence classes of paths to encode state. We first apply the method to the shortest path problem in 3 dimensions. The problem is to find the shortest path under an Lp metric (e.g. a euclidean metric) between two points amid polyhedral obstacles. Although this problem has been extensively studied, there were no previously known lower bounds. We show that there may be exponentially many shortest path classes in single-source multiple-destination problems, and that the single-source single-destination problem is NP-hard. We use a similar proof technique to show that two dimensional dynamic motion planning with bounded velocity is NP-hard. Finally we extend the technique to compliant motion planning with uncertainty in control. Specifically, we consider a point in 3 dimensions which is commanded to move in a straight line, but whose actual motion may differ from the commanded motion, possibly involving sliding against obstacles. Given that the point initially lies in some start region, the problem of finding a sequence of commanded velocities which is guaranteed to move the point to the goal is shown to be non-deterministic exponential time hard, making it the first provably intractable problem in robotics.
Keywords :
Contracts; Encoding; Laboratories; Motion planning; Orbital robotics; Path planning; Polynomials; Robot motion; Technology planning; Uncertainty;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1987., 28th Annual Symposium on
Conference_Location :
Los Angeles, CA, USA
ISSN :
0272-5428
Print_ISBN :
0-8186-0807-2
Type :
conf
DOI :
10.1109/SFCS.1987.42
Filename :
4568255
Link To Document :
بازگشت