Shortest Paths of Bounded Curvature for the Dubins Interval
Problem
Satyanarayana Manyam1, Sivakumar Rathinam2, David Casbeer3 and Eloy Garcia4
Abstract—The Dubins interval problem aims to ﬁnd the
shortest path of bounded curvature between two targets such that
the departure angle from the ﬁrst target and the arrival angle
at the second target are constrained to two respective intervals.
We propose a new and a simple algorithm to this problem based
on the minimum principle of Pontryagin.
I. INTRODUCTION
Path planning problems involving Dubins vehicles have
received signiﬁcant attention in the literature due to their
applications involving unmanned vehicles [1]–[13]. A Dubins
vehicle [14] is a vehicle that travels at a constant speed and has
a lower bound on the radius of curvature at any point along its
path. The basic problem of ﬁnding a shortest path for a vehicle
from a point at (x1, y1) with heading θ1 to a point at (x2, y2)
with heading θ2 was solved by Dubins in [14], and later by
authors in [15], [16] using Pontryagin’s minimum principle
[17]. This article considers a generalization of this standard
problem called the Dubins Interval Problem and is stated as
follows: Given two targets located at (x1, y1) and (x2, y2),
respectively, on a plane, a closed interval Θ1 of departure
angles from target 1, and a closed interval Θ2 of arrival angles
at target 2, ﬁnd a departure angle θ1 ∈Θ1, an arrival angle
θ2 ∈Θ2 and a path from (x1, y1, θ1) to (x2, y2, θ2) such
that the radius of curvature at any point in the path is lower
bounded by ρ and the length of the path is a minimum (refer
to Fig. 1).
(x1, y1)
(x2, y2)
Fig. 1.
A feasible solution to the Dubins Interval Problem.
1National Research Council Fellow, Air Force Research Laboratory,
Dayton-OH, 45433,
2Assistant Professor, Mechanical Engineering, Texas A & M University,
College Station, TX-77843,
3Research Scientist, Air Force Research Laboratory, Dayton-OH, 45433,
4Research Scientist, Infoscitex Corp., Dayton-Ohio, 45431.
Variants of the Dubins interval problem arise in search and
attack problems [18], [19] where a vehicle must reach a target
such that the arrival angle of the vehicle at the target must
be within given bounds. The Dubins interval problem also
arises while lower bounding Traveling Salesman Problems
(TSPs) involving Dubins vehicles [20]. In [20], the lower
bounding problem was posed as a generalized TSP where
the cost of traveling between any two nodes requires one
to solve the Dubins interval problem. The Dubins interval
problem was solved using calculus and some monotonicity
properties of the optimal paths in [20]. In this article, we give
a simple and a direct algorithm using Pontryagin’s minimum
principle [17]. The application of the minimum principle leads
to an additional set of complementary slackness conditions
corresponding to the angle constraints at the targets. The key
contribution of this article lies in interpreting these conditions
and characterizing an optimal solution to the Dubins interval
problem. Similar to solving the standard Dubins problem,
an optimal solution to the Dubins interval problem can be
obtained by simply comparing the length of few candidate
solutions. After proving the main result for the Dubins interval
problem, we also solve the special case of the Dubins interval
problem where the departure angle is given at target 1 while
a closed interval of angles is given at target 2. In this special
case, the objective is to ﬁnd an optimal Dubins path and the
corresponding arrival angle at target 2.
II. NOTATIONS
The two targets lie on a ground plane and the motion of
the vehicle also occurs on the same plane. As commonly
assumed, any angle measured with respect to the x-axis in
the counterclockwise direction is positive. The interval Θk
at target k is deﬁned as Θk = [θmin
k
, θmax
k
] ⊆[0, 2π] with
θmin
k
< θmax
k
for k = 1, 2. Given an initial conﬁguration
(x1, y1, θ1) and a ﬁnal conﬁguration (x2, y2, θ2), L.E. Dubins
[14] showed that the shortest path for a vehicle to travel be-
tween the two conﬁgurations subject to the minimum turning
radius (ρ) constraint must consist of at most three segments
where each segment is a circle of radius ρ or a straight line.
In particular, if a curved segment of radius ρ along which the
vehicle travels in a counterclockwise (clockwise) rotational
motion is denoted by L(R), and the segment along which
the vehicle travels straight is denoted by S, then the shortest
path is one of RSR, RSL, LSR, LSL, RLR and LRL or a
degenerate form of these paths. For example, the degenerate
forms of RSL are S, L, R, RS, SL and RL. We also subscript
a curved segment in some places (Lψ or Rψ) to indicate the
angle of turn (ψ) in the curved segment. In the results stated in
the ensuing sections, the open interval (θmin
k
, θmax
k
) is denoted
as Θo
k for k = 1, 2.
arXiv:1507.06980v2  [math.OC]  31 Aug 2015
III. MAIN RESULT
Theorem 1. Any shortest path which is C1 and piecewise
C2 of bounded curvature between the two targets with the
departure angle θd ∈Θ1 = [θmin
1
, θmax
1
] at target 1 and the
arrival angle θa ∈Θ2 = [θmin
2
, θmax
2
] at target 2 must be
one of the following or a degenerate form of these:
Case 1: S or Lψ or Rψ or LψRψ or RψLψ with ψ > π.
Case 2: θd = θmax
1
and θa = θmax
2
and the path is LSR.
Case 3: θd = θmax
1
and θa = θmin
2
and the path is either
LSL or LRψL with ψ > π.
Case 4: θd = θmin
1
and θa = θmin
2
and the path is RSL.
Case 5: θd = θmin
1
and θa = θmax
2
and the path is either
RSR or RLψR with ψ > π.
Case 6: θd = θmax
1
and θa ∈Θo
2 and the path is either LS
or LRψ with ψ > π.
Case 7: θd = θmin
1
and θa ∈Θo
2 and the path is either RS
or RLψ with ψ > π.
Case 8: θd ∈Θo
1 and θa = θmax
2
and the path is either SR
or LψR with ψ > π.
Case 9: θd ∈Θo
1 and θa = θmin
2
and the path is either SL
or RψL with ψ > π.
Remark: Note that in cases 1 and 6-9, the departure and
arrival angles are implicitly speciﬁed by each of the paths.
For example, if LψRψ with ψ > π exists between the two
targets, as the length of the segment L is equal to the length
of the segment R, the departure and arrival angles are simply
speciﬁed by geometry (we will later discuss this in the proofs;
refer to Fig.2). Similarly, if θd = θmax
1
(case 6), the arrival
angle at target 2 is determined by the LS or LR paths. The
only remaining part would be to check if the arrival angle at
target 2 lies in the interval [θmin
2
, θmax
2
]. If it does, then the
corresponding path is a candidate for an optimal solution to
the Dubins interval problem.
IV. THE MINIMUM PRINCIPLE
Let vo be the speed of the vehicle, and u(t) denote the
control input for the vehicle at time t. Let x(t), y(t), θ(t)
denote the position and angle coordinates of the vehicle as
a function of time on the ground plane. At time t = 0, let
the vehicle be located at (x1, y1). Let the travel time of the
vehicle be denoted by T. Note that θd = θ(0) and θa = θ(T).
The Dubins interval problem can be formulated as an optimal
control problem as follows:
min
u(t)∈[−1,1]
Z T
0
1dt
(1)
subject to
dx
dt = vo cos θ,
dy
dt = vo sin θ,
dθ
dt = u
ρ,
(2)
and the following boundary conditions:
x(0) = x1, x(T) = x2,
(3)
y(0) = y1, y(T) = y2,
(4)
θmin
1
−θ(0) ≤0,
(5)
θ(0) −θmax
1
≤0,
(6)
θmin
2
−θ(T) ≤0,
(7)
θ(T) −θmax
2
≤0.
(8)
Let
the
adjoint
variables
associated
with
p(t)
=
(x(t), y(t), θ(t)) be denoted as Λ(t) = (λx(t), λy(t), λθ(t)).
The Hamiltonian associated with above system is deﬁned as:
H(Λ, p, u) = 1 + vo cos θλx + vo sin θλy + u
ρλθ,
(9)
and the differential equations governing the adjoint variables
are deﬁned as:
dλx
dt = 0,
dλy
dt = 0,
dλθ
dt = vo sin θλx −vo cos θλy.
(10)
Applying the fundamental theorem of Pontryagin [17] to
the above problem, we obtain the following: If u∗is an
optimal control to the Dubins interval problem, then there
exists a non-zero adjoint vector Λ(t) and T > 0 such that
p(t), Λ(t) being the solution to the equations in (2) and (10)
for u(t) = u∗(t), the following conditions must be satisﬁed:
• ∀t ∈[0, T], H(Λ, p, u∗) ≡minu∈[−1,1] H(Λ, p, u).
• ∀t ∈[0, T], H(Λ, p, u∗) ≡0.
• Suppose α1, α2, β1, β2 are the Lagrange multipliers cor-
responding to the boundary conditions in (5)-(8) respec-
tively. Then, we have,
α1, α2, β1, β2 ≥0,
(11)
α1(θmin
1
−θ(0)) = 0,
(12)
α2(θ(0) −θmax
1
) = 0,
(13)
β1(θmin
2
−θ(T)) = 0,
(14)
β2(θ(T) −θmax
2
) = 0,
(15)
λθ(T) = β2 −β1,
(16)
λθ(0) = α1 −α2.
(17)
Given a departure angle at target 1 and an arrival angle at
target 2, the following facts are known for the basic Dubins
problem in [15], [16]. We will use them in our proofs later.
Fact 1. Consider any point P on an optimal path which is
either an inﬂexion point of the path (point joining two curved
segments or a point joining a curved segment and a straight
line) or any point on a straight line segment of the path.
Suppose the vehicle crosses this point at time t ∈[0, T].
Then, λθ(t) = 0.
Fact 2. All the points of an optimal path where λθ(t) = 0 lie
on the same straight line.
Fact 3. Consider any curved segment of an optimal path.
Let the times t1, t2 be such that 0 ≤t1 < t2 ≤T, the
vehicle is located on the curved segment at times t1, t2, and
λθ(t1) = λθ(t2) = 0. Then, the length of the curved segment
between the times t1 and t2 must be greater than πρ.
Fact
4.
For
any
t
∈
[0, T],
the
optimal
control
u∗(t) = −sign(λθ(t)) if λθ(t) ̸= 0.
V. PROOF OF THEOREM 1
The departure angle in any optimal solution must either
be an interior point in Θ1 or belong to one of the boundary
values of Θ1. Similarly, the arrival angle in any optimal
solution must either be an interior point in Θ2 or belong
to one of the boundary values of Θ2. The combination of
choices for the departure angle and arrival angle coupled
with the complementary slackness equations in (11)-(17)
provides constraints for the values of λθ(0) and λθ(T). These
constraints can then be used to ﬁnd the candidate solutions for
solving the Dubins interval problem. The following lemma
ﬁrst shows the relationship between the departure, arrival
angles and the constraints on λθ(0) and λθ(T).
Lemma 1. The constraints for the adjoint variable λθ at
times t = 0 and t = T corresponding to the departure and
arrival angles are given in the table below:
Case
No.
Conditions on the departure
and arrival angles of any op-
timal path
Implied constraints on
λθ(0) and λθ(T)
1
θ(0) ∈Θo
1, θ(T) ∈Θo
2
λθ(0) = 0, λθ(T) = 0
2
θ(0) = θmax
1
, θ(T) = θmax
2
λθ(0) ≤0, λθ(T) ≥0
3
θ(0) = θmax
1
, θ(T) = θmin
2
λθ(0) ≤0, λθ(T) ≤0
4
θ(0) = θmin
1
, θ(T) = θmin
2
λθ(0) ≥0, λθ(T) ≤0
5
θ(0) = θmin
1
, θ(T) = θmax
2
λθ(0) ≥0, λθ(T) ≥0
6
θ(0) = θmax
1
, θ(T) ∈Θo
2
λθ(0) ≤0, λθ(T) = 0
7
θ(0) = θmin
1
, θ(T) ∈Θo
2
λθ(0) ≥0, λθ(T) = 0
8
θ(0) ∈Θo
1, θ(T) = θmax
2
λθ(0) = 0, λθ(T) ≥0
9
θ(0) ∈Θo
1, θ(T) = θmin
2
λθ(0) = 0, λθ(T) ≤0
Proof: Consider the ﬁrst set of conditions, θ(0) ∈Θo
1,
θ(T) ∈Θo
2, in the table. If θ(0) ∈Θo
1, then equations (12)
and (13) imply α1 = 0 and α2 = 0 respectively. Using (17),
we obtain λθ(0) = α1 −α2 = 0. Similarly, if θ(T) ∈Θo
2, then
equations (14) and (15) imply β1 = 0 and β2 = 0 respectively.
Using (16), we obtain λθ(T) = β2 −β1 = 0. Each of the
other constraints in the table can be veriﬁed using a similar
procedure. Hence proved.
We now use the constraints on λθ(0) and λθ(T) to infer
the candidate solutions for the Dubins interval problem.
Lemma 2. Let λθ(0) = λθ(T) = 0. Then the optimal path
for the Dubins interval problem must be either S or Lψ or
Rψ or LψRψ or RψLψ with ψ > π.
Proof: An optimal path can just be a straight line from
fact 2. From fact 3, a curved segment of length greater than
πρ can satisfy the boundary conditions λθ(0) = λθ(T) = 0.
In addition, any path containing three curved segments and
satisfying the boundary conditions must have the length of
each curved segment (between any two inﬂexion points)
greater than πρ; however, as shown in [16], such a path
cannot be optimal. Therefore, an optimal path may consist of
either one or two curved segments with the length of each
segment greater than πρ.
If an optimal path consists of exactly two curved segments,
then there are three points ((x1, y1), (x2, y2) and the inﬂexion
point) where λθ(t) becomes zero for t ∈[0, T]. From fact
2, all these three points must lie on the same straight line.
Therefore, the length of the ﬁrst curved segment must be equal
to the length of the second curved segment as shown in Fig.
2 (in this case, θ(0) = θ(T)).
λθ(0) = 0
λθ(T) = 0
(x1, y1)
(x2, y2)
Fig. 2.
A RS path with the boundary values of λθ equal to 0.
Note that a set of constraints, say λθ(0) ≤0, λθ(T) ≥0,
can be satisﬁed if either λθ(0)
=
λθ(T)
=
0 or
λθ(0) < 0, λθ(T) = 0 or λθ(0) < 0, λθ(T) > 0 or
λθ(0) = 0, λθ(T) > 0 is satisﬁed. The following lemma
identiﬁes all the candidate solutions for any combination of
these constraints on λθ(0) and λθ(T).
Lemma 3. Candidate optimal paths for the Dubins interval
problem corresponding to the constraints on λθ(0) and λθ(T)
are given in the table below:
Constraints on λθ(0)
and λθ(T)
Candidate solutions
(ψ > π)
λθ(0) = 0, λθ(T) = 0
S,Lψ,Rψ,LψRψ,RψLψ
λθ(0) < 0, λθ(T) = 0
LS, LRψ with ψ > π
λθ(0) < 0, λθ(T) < 0
LSL, LRψL with ψ > π
λθ(0) < 0, λθ(T) > 0
LSR
λθ(0) = 0, λθ(T) < 0
SL, RLψ with ψ > π
λθ(0) = 0, λθ(T) > 0
SR, LRψ with ψ > π
λθ(0) > 0, λθ(T) = 0
RS, RLψ with ψ > π
λθ(0) > 0, λθ(T) < 0
RSL
λθ(0) > 0, λθ(T) > 0
RSR, RLψR with ψ > π
Proof: The candidate solutions corresponding to λθ(0) =
λθ(T) = 0 has already been shown in lemma 2. Consider the
next set of constraints λθ(0) < 0 and λθ(T) = 0. If λθ(0) < 0,
the ﬁrst segment of the path must be L (fact 4). LSRψ or
LSLψ with ψ > 0 is not possible because this path would
violate fact 2 unless the length of the straight line is equal
to 0. LRL is also not possible because the length of the R
segment and the last L segment would each be greater than
πρ which then cannot be optimal [16]. Therefore, the possible
candidates are LS or LRψ with ψ > π. Each of the remaining
set of the constraints can be shown using a similar procedure.
The theorem follows by combining lemmas 1 and 3.
VI. SOLUTION FOR THE SPECIAL CASE
In this special case of the Dubins interval problem, the
departure angle θd is given while the arrival angle at target
2 must belong to a closed interval Θ2.
Theorem 2. Any shortest path which is C1 and piecewise
C2 of bounded curvature between the two targets with
the departure angle θd at target 1 and the arrival angle
θa ∈Θ2 = [θmin
2
, θmax
2
] at target 2 must be one of the
following or a degenerate form of these:
Case 1: The path is either LS or RS or LRψ or RLψ with
ψ > π.
Case 2: θa = θmax
2
and the path is either LSR or RSR
RLψR with ψ > π.
Case 3: θa = θmin
2
and the path is either RSL or LSL
LRψL with ψ > π.
This theorem can be proved following the same procedure
as in the previous section.
REFERENCES
[1] J.-H. Lee, O. Cheong, W.-C. Kwon, S. Shin, and K.-Y. Chwa, “Ap-
proximation of curvature-constrained shortest paths through a sequence
of points,” in Algorithms - ESA 2000, ser. Lecture Notes in Computer
Science, M. Paterson, Ed. Springer Berlin Heidelberg, 2000, vol. 1879,
pp. 314–325.
[2] A. C. Medeiros and S. Urrutia, “Discrete optimization methods to
determine trajectories for dubins’ vehicles,” Electronic Notes in Discrete
Mathematics, vol. 36, pp. 17 – 24, 2010, {ISCO} 2010 - International
Symposium
on
Combinatorial
Optimization.
[Online].
Available:
http://www.sciencedirect.com/science/article/pii/S1571065310000041
[3] D. Macharet and M. Campos, “An orientation assignment heuristic
to the dubins traveling salesman problem,” in Advances in Artiﬁcial
Intelligence – IBERAMIA 2014, ser. Lecture Notes in Computer Science,
A. L. Bazzan and K. Pichara, Eds.
Springer International Publishing,
2014, vol. 8864, pp. 457–468.
[4] D. G. Macharet, A. Alves Neto, V. F. da Camara Neto, and M. F.
Campos, “Efﬁcient target visiting path planning for multiple vehicles
with bounded curvature,” in Intelligent Robots and Systems (IROS), 2013
IEEE/RSJ International Conference on.
IEEE, 2013, pp. 3830–3836.
[5] D. G. Macharet, A. A. Neto, V. F. da Camara Neto, and M. F. Campos,
“Data gathering tour optimization for dubins’ vehicles,” in Evolutionary
Computation (CEC), 2012 IEEE Congress on.
IEEE, 2012, pp. 1–8.
[6] P. Sujit, B. Hudzietz, and S. Saripalli, “Route planning for angle
constrained terrain mapping using an unmanned aerial vehicle,” Journal
of Intelligent & Robotic Systems, vol. 69, no. 1-4, pp. 273–283, 2013.
[7] R. J. Keneﬁc, “Finding good dubins tours for uavs using particle
swarm optimization,” Journal of Aerospace Computing, Information, and
Communication, vol. 5, no. 2, pp. 47–56, 2008.
[8] D. G. Macharet, A. A. Neto, V. F. da Camara Neto, and M. F. Campos,
“Nonholonomic path planning optimization for dubins’ vehicles,” in
Robotics and Automation (ICRA), 2011 IEEE International Conference
on.
IEEE, 2011, pp. 4208–4213.
[9] Z. Tang and U. Ozguner, “Motion planning for multitarget surveillance
with mobile sensor agents,” Robotics, IEEE Transactions on, vol. 21,
no. 5, pp. 898–908, Oct 2005.
[10] K. Savla, E. Frazzoli, and F. Bullo, “Traveling salesperson problems for
the dubins vehicle,” IEEE Transactions on Automatic Control, vol. 53,
pp. 1378–1391, 2008.
[11] S. Rathinam, R. Sengupta, and S. Darbha, “A resource allocation
algorithm for multivehicle systems with nonholonomic constraints,”
IEEE Transactions Automation Science and Engineering, vol. 4, pp.
98–104, 2007.
[12] J. Le Ny, E. Feron, and E. Frazzoli, “On the dubins traveling salesman
problem.” IEEE Trans. Automat. Contr., vol. 57, no. 1, pp. 265–270,
2012.
[13] X. Ma, D. Casta˜n´on, et al., “Receding horizon planning for dubins
traveling salesman problems,” in Decision and Control, 2006 45th IEEE
Conference on.
IEEE, 2006, pp. 5453–5458.
[14] L.E.Dubins, “On curves of minimal length with a constraint on average
curvature, and with prescribed initial and terminal positions and tan-
gents,” American Journal of Mathematics, vol. 79, no. 3, pp. 487–516,
1957.
[15] J.-D. Boissonnat, A. Crzo, and J. Leblond, “Shortest paths of
bounded curvature in the plane,” Journal of Intelligent and Robotic
Systems, vol. 11, no. 1-2, pp. 5–20, 1994. [Online]. Available:
http://dx.doi.org/10.1007/BF01258291
[16] X.-N. Bui, J.-D. Boissonnat, P. Soueres, and J.-P. Laumond, “Shortest
path synthesis for dubins non-holonomic robot,” in Robotics and Au-
tomation, 1994. Proceedings., 1994 IEEE International Conference on,
May 1994, pp. 2–7 vol.1.
[17] L. S. Pontryagin, V. G. Boltianski, R. V. Gamkrelidze, E. F.
Mishchenko, and D. E. Brown, “The mathematical theory of optimal
processes,” London, Paris, 1964, a Pergamon Press book. [Online].
Available: http://opac.inria.fr/record=b1122221
[18] E. Garcia, D. W. Casbeer, K. Pham, and M. Pachter, “Cooperative
aircraft defense from an attacking missile,” in Decision and Control
(CDC), 2014 IEEE 53rd Annual Conference on. IEEE, 2014, pp. 2926–
2931.
[19] E. Garcia, D. W. Casbeer, and M. Pachter, “Active target defense
differential game with a fast defender,” arXiv preprint arXiv:1502.02747,
2015.
[20] S. Manyam and S. Rathinam, “A tight lower bounding procedure for
the dubins traveling salesman problem,” Presented at the International
Symposium on Mathematical Programming, 2015. [Online]. Available:
http://arxiv.org/abs/1506.08752