On Polygonal Paths with Bounded Discrete-Curvature: The Inflection-Free Case - Discrete and Computational Geometry and Graphs - page 49

We will be interested in characterizing shortest dcc-paths that satisfy speci-
fied endpoint configurations:
Definition 2. A discrete-geodesic joining endpoint configurations ( v 1 ,ˆ 1 ) and
( v n ,ˆ n ) , is a dcc-path that (i) satisfies the endpoint configurations ( v 1 ,ˆ 1 ) and
( v n ,ˆ n ) , and (ii) has minimum total length among paths satisfying (i).
Remark 5. It is by no means obvious that discrete-geodesics exist for all endpoint
configurations. Dubins' proof [ 15 ] of the existence of smooth geodesics makes
use of tools from functional analysis (in particular, Ascoli's theorem); in Sect. 4 ,
we describe an alternative approach to establishing the existence of discrete-
geodesics, having established a suitable characterization of the form the discrete-
geodesics must take (if they exist).
Remark 6. It is straightforward to confirm that if a path contains a pair of suc-
cessive edges v i− 1 v i and v i v i +1 whose shortcut , edge v i− 1 v i +1 , has length at most
d ʸ , then the path can be made both shorter and smaller (fewer edges) by replac-
ing the edges by their shortcut, without violating the curvature constraint. It
follows that for the purposes of characterizing discrete-geodesics, we can restrict
our attention to paths with finitely many edges formed by maximal 2 discrete
circular arcs connected by (possibly degenerate) line segments. This assertion,
which follows immediately from our definition, is the discrete analogue of a non-
trivial property of smooth curvature-bounded geodesics, proved as Proposition
13 in [ 15 ].
1.1 Related Work
The topics [ 26 , 27 ] provide general references that discuss curvature-constrained
path planning in the broader context of non-holonomic motion planning. We
note that study of curvature-constrained path planning has a rich history that
long predates and goes well beyond robot motion planning, see for example the
work of Markov [ 29 ] on the construction of railway segments.
The Dubins characterization of smooth geodesics has been rederived using
techniques from optimal control theory in [ 7 , 40 ]. Variations and generalizations
of the problem are studied in [ 6 , 8 - 10 , 12 - 14 , 19 , 28 , 30 - 34 , 37 - 39 ]. In addition,
Dubins' characterization plays a fundamental role in establishing the existence
as well as the optimality of curvature-constrained paths. Jacobs and Canny [ 23 ]
showed that even in the presence of obstacles it suces to restrict attention
to paths of Dubins form between obstacle contacts and that if such a path
exists then the shortest such path is well-defined. Fortune and Wilfong [ 20 ]
give a super-exponential time algorithm for determining the existence of, but
not actually constructing, such a path. Characterizing the intrinsic complex-
ity of the existence problem for curvature-constrained paths is hampered by
2 We ignore for the present the fact that successive maximal discrete circular arcs of
opposite orientation could share an edge. In this case we are free to impose disjoint-
ness of arcs by assigning the shared edge to just one of the two arcs.