Finding curvature-constrained paths that avoid polygonal obstacles

ABSTRACT

We describe an algorithm to find a unit-curvature path between specified configurations in an arbitrary polygonal domain. Whenever such a path exists, the algorithm returns an explicit description of one such path in time that is polynomial in n (the number of features of the domain), m (the precision of the input) and k (the number of segments on the simplest obstacle-free Dubins path connecting the specified configurations). Our algorithm is based on a new normal form for unit-curvature paths and a dynamic path filtering argument that exploits a separation bound for distinct paths in this normal form.The best result known for the feasibility of bounded-curvature motion in the presence of arbitrary polygonal obstacles involves a reduction to the first-order theory of the reals. It just determines if a feasible path exists (it does not return a path) and requires exponential time and space.

REFERENCES

• 1: Pankaj K. Agarwal , Therese Biedl , Sylvain Lazard , Steve Robbins , Subhash Suri , Sue Whitesides, Curvature-constrained shortest paths in a convex polygon (extended abstract), Proceedings of the fourteenth annual symposium on Computational geometry, p.392-401, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276928]
• 2: Pankaj K. Agarwal , Prabhakar Raghavan , Hisao Tamaki, Motion planning for a steering-constrained robot through moderate obstacles, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.343-352, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225158]
• 3: Sergey Bereg , David Kirkpatrick, Curvature-bounded traversals of narrow corridors, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064135]
• 4: Jean-Daniel Boissonnat , Sylvain Lazard, A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles (extended abstract), Proceedings of the twelfth annual symposium on Computational geometry, p.242-251, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237393]
• 5: Christoph Burnikel , Stefan Funke , Kurt Mehlhorn , Stefan Schirra , Susanne Schmitt, A Separation Bound for Real Algebraic Expressions, Proceedings of the 9th Annual European Symposium on Algorithms, p.254-265, August 28-31, 2001
• 6: L.E. Dubins. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Amer. J. Math., 79:497--516, 1957.
• 7: Steven Fortune and Gordon Wilfong. Planning constrained motion. Ann. Math. Artificial Intelligence, 3(1):21--82, 1991. Algorithmic motion planning in robotics.
• 8: Paul Jacobs and John Canny. Planning smooth paths for mobile robots. In Proceedings of the 1989 IEEE International Conference on Robotics and Automation, pages 2--7, 1989.
• 9: J.A. Reeds and L.A. Shepp. Optimal paths for a car that goes both forwards and backwards. Pacific J. Math., 145(2):367--393, 1990.
• 10: John Reif , Hongyan Wang, The complexity of the two dimensional curvature-constrained shortest-path problem, Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics : the algorithmic perspective: the algorithmic perspective, p.49-57, August 1998, Houston, Texas, United States
• 11: Hongyan Wang , Pankaj K. Agarwal, Approximation algorithms for curvature-constrained shortest paths, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.409-418, January 28-30, 1996, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
bounded-curvature, motion planning, path feasibility