8
$\begingroup$

A Dubins car follows a Dubins path in $\mathbb{R}^2$, with constant wheel speed and limited turning radius. It is known that the shortest Dubins path in the absence of obstacles follows circular arcs and straight segments, in fact, in no more than six patterns:


         
          Figure from Huifang Elizabeth Wang's PhD thesis
The literature is vast, and I am having difficulty determining:

Q. Is there an algorithm to determine the shortest Dubins path between any two points in $\mathbb{R}^2$, in the presence of polygonal obstacles?

Assume that the start and end points, and the $n$ polygonal vertices, are specified by integer coordinates using at most $L$-bits. An algorithm polynomial-time in $L$ & $n$ is perhaps too much to hope for, but Q asks if the problem is decidable.

Answered (11 Nov 2014). user3097732 pointed me to the paper, Curvature-Constrained Shortest Paths in a Convex Polygon, which says in the Introduction

Reif and Wang[29] confirmed that the problem of deciding whether there exists a collision-free curvature-constrained path for $B$ between two given configurations amid polygonal obstacles is NP-hard.

where [29] is: J. Reif and H. Wang, "The complexity of the two-dimensional curvature-constrained shortest-path problem," in Robotics: The Algorithmic Perspective (Houston, TX), A. K. Peters, 1998, pp. 49–57.

NP-hard could still be undecidable, but Fortune and Wilfong proved the problem is decidable, by providing an algorithm with time complexity $2^{\mathrm{poly}(n, L)}$, where $n$ is the number of vertices of the obstacles and $L$ the number of bits in the coordinates. (Their algorithm does not actually find the path!) "Planning constrained motion," Ann. Math. Artificial Intelligence, 3 (1991), pp. 21–82.

$\endgroup$
  • $\begingroup$ How is the description of these polygons given for the algorithm? $\endgroup$ – Wojowu Nov 11 '14 at 21:39
  • 1
    $\begingroup$ @Wojowu: By coordinates of vertices, specified in a certain number of bits. $\endgroup$ – Joseph O'Rourke Nov 11 '14 at 22:12
  • 1
    $\begingroup$ NP-hard but not known to be NP-complete, for problems of the form "does there exist a geometric object", often really means complete for the existential theory of the reals. Any idea whether that might be true in this case? $\endgroup$ – David Eppstein Nov 12 '14 at 5:57
  • $\begingroup$ @DavidEppstein: Good question; I don't know. $\endgroup$ – Joseph O'Rourke Nov 12 '14 at 12:05
4
$\begingroup$

You might want to take a look at "Curvature-constrained shortest paths in a convex polygon" (Agarwal et al. 2002).

Use another method to decompose your environment into convex polygons, e.g "A navigation mesh for dynamic environments" (Van Toll, W. G., Cook, A. F., & Geraerts, R. 2012).

Then, run a global planning algorithm, to find the subset of convex polygons that are to be traversed. For each polygon, use the 1st method to plan between polygon edges.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.