New lower bound techniques for robot motion planning problems

Authors:
  • JCJohn Canny
    John Canny
  • JRJohn Reif
    John Reif
Publisher website
Google Scholar
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.

This publication has 13 references indexed in Scilit: