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.
