# Dubins car shortest paths: Decidable?

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.

• How is the description of these polygons given for the algorithm? – Wojowu Nov 11 '14 at 21:39
• @Wojowu: By coordinates of vertices, specified in a certain number of bits. – Joseph O'Rourke Nov 11 '14 at 22:12
• 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? – David Eppstein Nov 12 '14 at 5:57
• @DavidEppstein: Good question; I don't know. – Joseph O'Rourke Nov 12 '14 at 12:05