Approximate constrained motion planning

Anup Basu, John AloimonosICRA 1990 · OpenReview

Abstract

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.<
BibTeX
@inproceedings{basu1990approximate,
  author = {Anup Basu and John Aloimonos},
  title = {{Approximate constrained motion planning}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {1990},
  url = {https://openreview.net/forum?id=CY3gRK1wIsQ},
}

Loading related content...

Figure