Approximate constrained motion planning

The problem of finding a collision-free path connecting two points (start and goal) in the presence of obstacles, with constraints on the curvature of the path, is examined. This problem of curvature-constrained motion planning arises when, for example, a vehicle with constraints on its steering mechanism needs to be maneuvered through obstacles. Though no lower bound on the difficulty of the problem in 2-D is known, exact algorithms given to date for the reachability questions are exponential. It is shown that a variation of the problem is NP-hard. Notably, however, the same variation to polynomially solvable motion planning problems does not make them intractable. In addition, it is proven that epsilon -approximations to this problem cannot exist unless the underlying decision problem is polynomially solvable. An algorithm which is expected to find a desired path, when one exists, with a required probability is presented. Results indicate that a variable-size discretization is necessary for the task, linking the required probability to the size of the discretization locally. >

Authors

• Anup Basu
• Yiannis Aloimonos

Keywords

• Polynomials
• Path planning
• Computer vision
• Joining processes
• Vehicles
• Mobile robots
• Orbital robotics
• Laboratories
• Automation
• Computer science
• Free Space
• General Case
• Decision Problem
• Exact Algorithm
• Problem Difficulty
• Variant Of Problem
• Discrete Size
• Path Curvature
• Best Fit
• Straight Line
• Grid Points
• Shortest Path
• Dynamic Programming
• Estimation Strategy
• Line Segment
• Discrete Space
• Minimum Path
• Road Width
• Quadtree