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.