New Lower Bound Techniques for Robot Motion Planning Problems

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.

Authors

• John F. Canny
• John H. Reif

Keywords

• Robot motion
• Motion planning
• Path planning
• Contracts
• Encoding
• Uncertainty
• Orbital robotics
• Polynomials
• Technology planning
• Laboratories
• Lower Bound
• Straight Line
• Shortest Path
• Polyhedral
• Problem In Robotics
• Shortest Path Problem
• Transition State
• Path Length
• Hardness
• Point Source
• Local Coordinate
• Constant Velocity
• Direction Of Motion
• Position Of Point
• Algorithm For Problem
• Most Significant Bit
• Straight-line Distance
• Points In Plane
• Virtual Source
• Turing Machine
• Motion Sequences
• Velocity Commands
• Forward Projection
• Sequence Of Edges
• Path Segment
• Results Section
• Convex Polygon