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.
Best Answer
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.