AN APPROXIMATION ALGORITHM FOR A SHORTEST DUBINS PATH PROBLEM
Sivakumar Rathinam
Associate Professor
Department of Mechanical Engineering
Texas A & M University
College station, Texas, U.S.A, 77843
Pramod Khargonekar
Professor
Department of Electrical and Computer Engineering
University of Florida
Gainesville, Florida, U.S.A., 32611
ABSTRACT
The problem of finding the shortest path for a vehicle vis-
iting a given sequence of target points subject to the motion
constraints of the vehicle is an important problem that arises in
several monitoring and surveillance applications involving un-
manned aerial vehicles. There is currently no algorithm that can
find an optimal solution to this problem. Therefore, heuristics
that can find approximate solutions with guarantees on the qual-
ity of the solutions are useful. The best approximation algorithm
currently available for the case when the distance between any
two adjacent target points in the sequence is at least equal to
twice the minimum radius of the vehicle has a guarantee of 3.04.
This article provides a new approximation algorithm which im-
proves this guarantee to 1+ π
3 ≈2.04. The developed algorithm
is also implemented for hundreds of typical instances involving
at most 30 points to corroborate the performance of the proposed
approach.
1
Introduction
Advances in sensing, robotics and wireless networks have
enabled the use of teams of small Unmanned Vehicles (UVs) for
environmental sensing applications including crop monitoring
[1, 2], ocean bathymetry [3], forest fire monitoring [4], ecosys-
tem management [5, 6], and civil security applications such as
border surveillance [7, 8] and disaster management [9]. These
applications frequently require vehicles to collect data such as
visible/infra-red/thermal images, videos of specified target sites,
and environmental data such as temperature, moisture, humidity
using onboard sensors, and deliver them to a base station. To
accomplish this requirement, small unmanned vehicles with mo-
tion and fuel constraints commonly visit a set of target points.
There are many fundamental problems that arise here which re-
late to path planning, control and navigation. This article ad-
dresses an important path planning problem that arises in a typi-
cal surveillance mission involving a fixed wing Unmanned Aerial
Vehicle (UAV) with minimum turning radius constraints.
Given a sequence of target points to visit on a ground plane,
this article considers the problem of finding a shortest path pass-
ing through the points in the given sequence such that the ra-
dius of curvature of any point on the path is at least equal to a
positive constant. The curvature constraint imposed on the path
models the minimum turning radius of a fixed wing UAV. If the
vehicle is traveling at constant speed, this constraint also models
the bound on the maximum yaw rate of a fixed wing UAV. On-
board resources such as fuel are limited for small vehicles and
therefore, minimizing the length of a vehicle’s path can lead to
using the resources as efficiently as possible. This problem is
referred to as the Curvature constrained Shortest path Problem
(CSP) in this article (refer to figure 1). The CSP is also one of
the two important subproblems of the well known Dubins Trav-
eling Salesman Problem which has received significant attention
in the literature [10–19].
The CSP is a generalization of the two point shortest path
problem solved by L.E. Dubins [20] in 1957. Dubins [20] ad-
dressed the problem of finding a shortest path for a vehicle to
travel from a point at (x1,y1) with heading angle θ1 to a point at
(x2,y2) with heading angle θ2 such that the radius of curvature at
any point along the path is at least equal to ρ ≥0. Dubins [20]
showed that any shortest path to this two point problem must
consist of at most three segments where each of the segments
must be an arc of radius ρ (denoted by C) or a straight line seg-
ment (denoted by S). Specifically, any shortest path is of type
CSC or CCC, or a degenerate form of these paths. These paths
arXiv:1604.05064v1  [cs.RO]  18 Apr 2016
p1
p2
p3
p4
p6
p5
Figure 1.
A possible feasible path for the CSP visiting a sequence of
points denoted by (p1,··· , p6).
are generally referred to as the Dubins paths in the literature. If
the heading angle at each point is known, then the CSP simply
reduces to finding an optimal Dubins path between any two ad-
jacent target points in the given sequence. Therefore, solving
the CSP requires us to find an optimal heading angle at each of
the target points. This is a non-trival problem because the length
of the CSP is a non-linear function of the heading angles at the
target points.
There is currently no algorithm that can find an optimal
solution to the CSP. Therefore, algorithms that can find fea-
sible solutions with theoretical guarantees on the deviation of
the solutions from the optimum are useful. The CSP was first
considered by Lee et al.
in [21] where they provide a 5.03-
approximation algorithm. The approximation factor of this algo-
rithm has been recently improved to (2+ 2
π + π
2 ≈4.21) in [22].
An α-approximation algorithm for a minimization problem is an
algorithm that finds a feasible solution whose cost is at most α
times the optimal cost for any instance of the problem. The factor
α is also referred to as the approximation factor of the algorithm.
This article considers an important case of this problem
where the distance between any two adjacent points is at least
equal to 2ρ. In many practical applications, the sensors onboard
a vehicle covers a wide swath of the monitoring area, and as a
result, the vehicle may not be required to visit points that are
close [19]. For this case, a 3.04-approximation algorithm was
provided by Rathinam et al. in [19]. In this article, we improve
on this bound and develop a new approximation algorithm with
a factor of 1+ π
3 +ε ≈2.04+ε for any small constant ε > 0.
2
Problem Statement
Consider a sequence of n points denoted by (p1, p2,··· , pn)
on a plane. Let the position coordinates of the point pi be denoted
as (xi,yi). Without loss of generality, assume n = 3k where k
is any positive integer. The vehicle is first required to visit p1,
then p2, and so on. The minimum turning radius of the vehicle
is denoted as ρ. Let the Euclidean distance between any two
adjacent points in the path visited by the vehicle be at least equal
to 2ρ. The objective of the CSP is to find a path such that the path
visits each of the points in the order given by (p1, p2,··· , pn), the
radius of curvature at any point along the path is at least equal to
ρ and the length of the path is a minimum.
In the next section, we present a (1 + ε)-approximation al-
gorithm for any given ε > 0 when n = 3. We then use this three
point algorithm to develop an approximation algorithm for the
general case in the subsequent section.
3
(1+ε)-Approximation algorithm for 3 points
Let the Euclidean distance between points p1 and p2 be
denoted as d12 and the Euclidean distance between points p2
and p3 be denoted as d23. Without loss of generality, assume
p1 is at (x1,y1), p2 is at the origin and p3 is at (d23,0). Also,
the case when x1 ≤0,y1 = 0 is not considered since the optimal
solution in this case is just a straight line from p1 to p3.
A
curved segment C may either require the vehicle to turn in the
clockwise direction (this curved segment with a right turn is
denoted as R) or turn in the counter clockwise direction (this
curved segment with a left turn is denoted as L).
(d23, 0)
(0, 0)
x-axis
y-axis
p2
p3
p1
P
¯P
θ
¯θ
P
¯P
Figure 2.
Let P denote a SL path from p1 to p2 and a RS path from
p2 to p3. The heading angle θ corresponding to path P at p2 can be
reduced by a small amount to say ¯θ to obtain a new path ¯P with a shorter
length. The difference between the angles θ and ¯θ is magnified just for
illustration.
Lemma 1. The shortest path of bounded curvature through
points p1, p2 and p3 must be of type SRS if y1 < 0, SLS if y1 > 0
and either SRS or SLS if y1 = 0. The point p2 lies on the curved
segment of the path.
(d23, 0)
(0, 0)
x-axis
y-axis
p2
p3
p1
¯P
θ
P
¯P
Figure 3.
In this example y1 > 0. P here denotes a SRS path from p1
to p3. The straight line segments of P cross each other when y1 > 0.
Therefore, SRS cannot be optimum because one can find a shorter path
of type SLS where the straight line segments (dotted blue lines) do not
cross each other. It is easy to verify that the length of the SLS path will
be less than the length of the SRS path when y1 > 0.
Proof. Given the heading angle θ at p2, as d12 ≥2ρ and
d23 ≥2ρ, it is known [23] that the shortest path from p1 to p2
must be of type SC while the shortest path from p2 to p3 must be
of type CS. For example, the path from p1 to p2 can be of type
SL or SR. However, it is not optimal to arrive at p2 in the counter
clockwise direction and leave p2 in the clockwise direction as
shown in figure 2. Similarly, it is also not optimal to arrive at p2
in the clockwise direction and leave p2 in the counter clockwise
direction.
Therefore, SCS is the only possibility where the
vehicle is turning either left or right in the curved segment while
visiting p2.
In addition, SRS cannot be optimal when the y coordinate of
point p1 is greater than zero (refer to figure 3). Similarly, SLS
cannot be optimal when the y coordinate of point p1 is less than
zero. Hence proved. ■
For the three point problem, if the heading angle at the
first point is given, authors in [18] prove a similar result by
formulating the shortest path problem as an optimal control
problem and using Pontryagin’s minimum principle. Apart from
the difference in our approaches and the fact that we do not have
any heading angle constraint at the first point, our work differs
from the need to also understand the computational complexity
of finding an optimal path. The next theorem shows that given
any small ε > 0, the number of steps required to find an optimum
is in the order of log2
1
ε (which is a constant).
Theorem 1. Given any ε > 0, a path within (1 + ε) times the
length of the shortest path can be found in polynomial time for
three points.
Proof. From lemma 1, the shortest path is of type SLS or SRS.
Here, we show that a path of type SRS with length (1+ε) times
the optimal length can be found in polynomial time when y1 < 0.
A similar proof can also be provided for SLS. Refer to figure 4
for an illustration of the SRS path when y1 < 0 and all the nota-
tions for the involved angles. Note that the angles φ and ψ shown
in figure 4 are functions of θ. Let D1 be the length of the SR path
from p1 to p2 as a function of the heading angle θ at p2. Let
D2 be the length of the RS from p2 to p3 as a function of the
heading angle θ at p2. The function D1(θ)+D2(θ) is discontin-
uous at θ = 0 and θ = β. At all other values of θ, both the length
functions D1(θ) and D2(θ) are continuously differentiable [24].
Using the results for the derivatives of the length function of an
RS path in [24], wherever the derivatives exist, we have,
dD1
dθ + dD2
dθ = −d12 sinψ+d23 sinφ.
dD1
dθ + dD2
dθ = 0 implies that the sum of the length functions can
reach a minimum or a maximum when d12 sinψ = d23 sinφ. Now,
d12 sinψ reaches a maximum value of 2ρ when θ = θ∗
12 (refer
to figure 5) and reduces to zero as θ is further increased to β.
Without loss of generality, assume that −π ≤θ∗
12 ≤π. It is easy
to verify that d12 sinψ is a strictly decreasing function when θ ∈
[θ∗
12,β]. This is because 0 < ψ < π
2 and d12 cosψ > L12 for θ ∈
(θ∗
12,β). Therefore, using the results in [24], we get,
d(d12 sinψ)
dθ
= −d12 cosψ(d12 cosψ−L12
L12
) < 0.
Similarly, d23 sinφ reaches a minimum value of 0 when
θ = 0 and increases to 2ρ when θ becomes equal to θ∗
23 (refer
to figure 6). Also, d23 sinφ is a strictly increasing function when
θ ∈[0,θ∗
23].
Now, the set [θ∗
12,β] ∩[0,θ∗
23] is always nonempty because
0 ≤β and θ∗
12 ≤π
2 ≤θ∗
23 ≤π. Therefore, one can verify that for
θ ∈[θ∗
12,β] ∩[0,θ∗
23], the functions d12 sinψ and d23 sinφ must
intersect at some angle θ = θ∗. In addition, for any θ ∈(θ∗
12,β)∩
(0,θ∗
23),
d2D1
dθ2 + d2D2
dθ2 = d12 cosψ(d12 cosψ−L12
L12
) +
d23 cosφ(d23 cosφ−L23
L23
)
> 0.
Hence, D1(θ) + D2(θ) reaches an unique minimum at θ =
θ∗. This minimum can be found using an interval bisection algo-
rithm with the number of iterations of the algorithm in the order
of log2( 1
ε) for any given ε > 0 [25]. ■
θ
φ
θ
φ
(d23, 0)
(0, 0)
ρ
x-axis
y-axis
p2
p3
p1
d12
ψ
β
Figure 4.
A SRS path from p1 to p3 via p2.
(0, 0)
2ρ
x-axis
y-axis
p1
d12
ψ
β
θ∗
12
L12
Figure 5. SR path from p1 to p2. Note that when θ = θ∗
12, d12 sinψ
reaches a maximum value of 2ρ. As θ is increased further to β, d12 sinψ
reduces to zero.
The following lemma proves an additional property about
the nature of the optimal paths for the 3 point problem. This
property is useful for numerical implementations and can be
used as a termination criteria.
Again, the following result is
shown for the SRS path. SLS path can be handled in a similar
way.
Lemma 2. For the optimal SRS path when y1 ≤0, the angle of
turn in the curved segment from point p1 to p2 is equal to the
angle of turn in the curved segment from p2 to p3.
Proof. Refer to figure 4. Using the result in [24], we get,
dD2
dθ = d23 sinφ
= ρ−ρcos(θ+φ) = ρ−ρcos(turn23)
φ
(d23, 0)
(0, 0)
2ρ
x-axis
y-axis
p3
θ∗
23
L23
Figure 6.
RS path from p2 to p3. Note that when θ = 0, d12 sinφ = 0.
As θ is increased further to θ∗
23, d12 sinψ increases and reaches its
maximum value which is equal to 2ρ.
where turn23 = θ + φ is the turn angle of the curved segment
from p2 to p3. Similarly,
dD1
dθ = −d12 sinψ = −(ρ−ρcos(turn12))
where turn12 is the turn angle of the curved segment from p1 to
p2.
Therefore,
dD1
dθ + dD2
dθ
= 0 implies that cos(turn12) =
cos(turn23). Either turn12 = turn13 or turn12 +turn13 = 2π. But
turn12 +turn13 cannot be equal to 2π because this would imply
that y1 > 0 which is not true. Therefore, turn12 = turn13. ■
4
Approximation algorithm for n points
The approximation algorithm first finds three feasible solu-
tions for the CSP and then chooses the best of these three solu-
tions. The three solutions are constructed in the following way:
1. Solution F1:
Use the three point algorithm to find a
path for each of the following sequences of points:
(p1, p2, p3),(p4, p5, p6),··· ,(p3k−2, p3k−1, p3k).
These
paths will fix the heading angle of the vehicle at each of the
points. Now, use these heading angles to find the shortest
Dubins path from p3 to p4, p6 to p7 and so on. Concatenate
all these Dubins paths along with the paths obtained using
the three point algorithm such that the resulting solution
(F1) visits the points in the given sequence.
2. Solution F2:
Use the three point algorithm to find a
path for each of the following sequences of points:
(p2, p3, p4),(p5, p6, p7),··· ,(p3k−4, p3k−3, p3k−2). In addi-
tion, join points p3k−1 and p3k using a line segment. These
paths will fix the heading angle of the vehicle at each of the
points except p1. Choose any arbitrary angle for visiting p1.
Now, use these heading angles to find the shortest Dubins
path from p1 to p2, p4 to p5 and so on. Concatenate all these
Dubins paths along with the paths obtained using the three
point algorithm and the line segment such that the resulting
solution (F2) visits the points in the given sequence.
3. Solution F3:
Use the three point algorithm to find
a path for each of the following sequences of points:
(p3, p4, p5),(p6, p7, p8),··· ,(p3k−3, p3k−2, p3k−1). In addi-
tion, join points p1 and p2 using a line segment.
These
paths will fix the heading angle of the vehicle at each of the
points except p3k. Choose any arbitrary angle for visiting
p3k. Now, use these heading angles to find the shortest Du-
bins path from p2 to p3, p5 to p6 and so on. Concatenate all
these Dubins paths along with the paths obtained using the
three point algorithm such that the resulting solution (F3)
visits the points in the given sequence.
Among these three solutions, the approximation algorithm
chooses a solution (Fa) that corresponds to the least of the
lengths of F1, F2 and F3. Let cost(F ) denote the length of
any solution F .
The algorithm runs in polynomial time as
it primarily relies on solving the three point problems which
can be solved in polynomial time for given ε > 0.
The fol-
lowing theorem shows the approximation factor of the algorithm:
Theorem 2. Let Fopt and Fa respectively denote an optimal
solution to the CSP and the solution obtained by the approxima-
tion algorithm. Consider any constant ε > 0. The length of the
solution Fa is at most equal to (1 + π
3 + ε) times the length of
Fopt. That is, cost(Fa) ≤(1+ π
3 +ε)cost(Fopt).
Proof. For i, j = 1,··· ,n, i < j, let F (pi, pj) denote the part of
the solution F from point pi to point pj. Hence, cost(F (pi, pj))
essentially denotes the length of the part of the solution F from
pi to pj. Also, let di, j represent the Euclidean distance between
points pi and pj.
Cost(F1) =
k
∑
i=1
cost(F1(p3i−2, p3i))+
k−1
∑
i=1
cost(F1(p3i, p3i+1)).
(1)
By construction, for any i = 1,··· ,k, the three point algo-
rithm finds a path of bounded curvature with an approximation
guarantee of (1 + ε) from p3i−2 to p3i. Therefore, the length of
this path must be at most equal to (1+ε) times length of the part
of the path Fopt from p3i−2 to p3i. Hence,
cost(F1(p3i−2, p3i)) ≤(1+ε)cost(Fopt(p3i−2, p3i)).
(2)
Similarly, a shortest Dubins path is constructed from p3i to p3i+1
for all i = 1,··· ,k −1. Using the bound shown in [22], we get,
cost(F1(p3i, p3i+1)) ≤(1+π)d3i,3i+1
≤(1+π)cost(Fopt(p3i, p3i+1)).
(3)
Substituting for the bounds from equations (2) and (3) in (1),
we get,
cost(F1)
≤(1+ε)
k
∑
i=1
cost(Fopt(p3i−2, p3i))+(1+π)
k−1
∑
i=1
cost(Fopt(p3i, p3i+1))
= (1+ε)
k
∑
i=1
cost(Fopt(p3i−2, p3i))+
k−1
∑
i=1
cost(Fopt(p3i, p3i+1))
|
{z
}
≤(1+ε)cost(Fopt)
+π
k−1
∑
i=1
cost(Fopt(p3i, p3i+1))
= (1+ε)cost(Fopt)+π
k−1
∑
i=1
cost(Fopt(p3i, p3i+1)).
(4)
Similarly, we can also bound the length of solutions F2 and
F3 as follows:
cost(F2) ≤(1+ε)cost(Fopt)+π
k
∑
i=1
cost(Fopt(p3i−2, p3i−1)).
(5)
cost(F3) ≤(1+ε)cost(Fopt)+π
k
∑
i=1
cost(Fopt(p3i−1, p3i)).
(6)
We use the following notations to simplify the terms that
appear in equations (4),(5) and (6). Let,
L1 =
k−1
∑
i=1
cost(Fopt(p3i, p3i+1)).
L2 =
k
∑
i=1
cost(Fopt(p3i−2, p3i−1)).
L3 =
k
∑
i=1
cost(Fopt(p3i−1, p3i)).
One can verify that L1 +L2 +L3 = cost(Fopt). Therefore, as
L1,L2,L3 ≥0, we obtain,
min(L1,L2,L3) ≤1
3cost(Fopt).
(7)
Combining all the bounds for the length of the three solu-
tions and the above equation, we get,
cost(Fa) = min(cost(F1),cost(F2),cost(F3))
≤(1+ε)cost(Fopt)+πmin(L1,L2,L3)
≤(1+ π
3 +ε)cost(Fopt).
■
5
Numerical Results
The approximation algorithm was implemented on problem
instances with 12, 15, 18, 21, 24, 27 and 30 target points. For
a given number of target points, we generated 100 instances.
The turning radius of the vehicle was set to 100 units.
The
coordinates of the points were uniformly randomly generated
on a 2D plane with the requirement that the minimum distance
between any two adjacent points in the sequence is at least twice
the turning radius of the vehicle.
For a given problem instance I, the bound on the a posterior
guarantee provided by the approximation algorithm is defined as
CIapprox
CI
lb
where CI
approx is the cost of the feasible solution found by
the approximation algorithm and CI
lb is the lower bound on the
length of the shortest path for the CSP. The parameter ε in the
approximation algorithm was set to 10−4. The lower bound for
each instance was obtained using the procedure outlined in [24].
This lower bounding algorithm involved discretizing the set of
possible heading angles [0,2π] at each point into 32 uniform
intervals (refer to [24] for more details on this computation). All
the algorithms were coded in MATLAB and the computations
were run on a Dell Precision Workstation (Intel Xeon Processor
@2.53 GHz, 12 GB RAM). The average running time of the
approximation algorithm was in the order of a second for all the
instances.
The max and average a posterior guarantee of the solutions
found by the approximation algorithm is shown in table 1 along
with the theoretical approximation guarantee. Even though the
theoretical guarantee is 2.04, the numerical results show that the
max and average a posterior guarantee was less than 1.28 and
1.15 respectively for the considered instances. These results im-
ply that the proposed algorithm produced solutions with bounds
that are significantly better than the guarantees indicated by the
approximation factor. The solutions obtained by the approxima-
tion algorithm for an instance is shown in figure 7.
6
Conclusions
This article provided a new approximation algorithm for a
curvature constrained shortest path problem (CSP) for visiting a
given sequence of target points. First, an algorithm that finds a
0
200
400
600
800
1000
1200
1400
1600
1800
2000
-1000
-800
-600
-400
-200
0
200
400
(a) F1
0
200
400
600
800
1000
1200
1400
1600
1800
2000
-1200
-1000
-800
-600
-400
-200
0
200
400
(b) F2
0
200
400
600
800
1000
1200
1400
1600
1800
2000
-1200
-1000
-800
-600
-400
-200
0
200
400
(c) F3
Figure 7.
The three solutions obtained by the algorithm for a problem
instance with 12 points.
Table 1.
Comparison of the theoretical and numerical results for the ap-
proximation algorithm
No. of Points
Theoretical upper
bound
Max a posteriori
bound
Average a posteriori
bound
12
2.04
1.27
1.09
15
2.04
1.25
1.09
18
2.04
1.24
1.11
21
2.04
1.22
1.11
24
2.04
1.24
1.11
27
2.04
1.23
1.13
30
2.04
1.20
1.12
good path for 3 points is presented. Next, the given sequence
is broken into subsequences with 3 points in each subsequence,
and a solution is obtained for each subsequence using the three
point algorithm. Finally, the solutions corresponding to all the
subsequences are concatenated in a suitable way to find a feasi-
ble solution to the SPP. This basic idea can be improved in sev-
eral directions to provide better approximation guarantees for the
CSP. First, if one can solve a four point problem with an approx-
imation factor of (1 + ε) for some small ε > 0, using the ideas
presented in this article, a guarantee of (1 + π
4 + ε) can be ob-
tained for the CSP. Second, the bounds presented in this article
are mainly based on the Euclidean distances with no consider-
ation given to the angle of turn of the vehicle as it passes the
points. Including the turn angles has a potential to reduce the ap-
proximation factor further. In fact, the algorithm provided in [21]
uses the constraints on the turn angles in a clever way to provide a
constant factor approximation guarantee. We believe that a com-
bination of the ideas presented in this article with lower bounds
that are computed based on the Euclidean distances and the turn
angles can improve the approximation guarantees significantly
even for the more general case when adjacent points are closed
spaced.
REFERENCES
[1] Geiser, K., Slack, D., Allred, E., and Stange, K., 1982. “Ir-
rigation scheduling using crop canopy air temperature dif-
ferences”. Transactions of the American Society of Agri-
cultural and Biological Engineers, 25(3), pp. 689–694.
[2] Jackson, R., Idso, S., Reginato, R., and Pinter, P., 1981.
“Canopy temperature as a crop water stress indicator”. Wa-
ter Resources Research, 17(4), pp. 1133–1138.
[3] Ferreira, H., Almeida, C., Martins, A., Almeida, J., Dias,
N., Dias, A., and Silva, E., 2009. “Autonomous bathymetry
for risk assessment with roaz robotic surface vehicle”. In
OCEANS 2009 - EUROPE, pp. 1–6.
[4] Casbeer, D., Beard, R., McLain, T., Li, S.-M., and Mehra,
R., 2005. “Forest fire monitoring with multiple small uavs”.
In American Control Conference, 2005. Proceedings of the
2005, pp. 3530–3535 vol. 5.
[5] Corrigan, C. E., Roberts, G. C., Ramana, M. V., Kim, D.,
and Ramanathan, V., 2008. “Capturing vertical profiles of
aerosols and black carbon over the indian ocean using au-
tonomous unmanned aerial vehicles”. Atmospheric Chem-
istry and Physics, 8(3), pp. 737–747.
[6] Zajkowski, T., Dunagan, S., and Eilers, J., 2006. “Small
UAS communications mission”.
[7] Maza, I., Caballero, F., Capitan, J., de Dios, J. R. M., and
Ollero, A., July 2010. “Firemen Monitoring with Multiple
UAVs for Search and Rescue Missions”.
[8] Krishnamoorthy, K., Casbeer, D., Chandler, P., Pachter, M.,
and Darbha, S., 2012. “UAV search and capture of a mov-
ing ground target under delayed information”. In Confer-
ence on Decision and Control, IEEE.
[9] Maza, I., Caballero, F., Capitan, J., de Dios, J. R. M., and
Ollero, A., 2011. “Experimental Results in Multi-UAV Co-
ordination for Disaster Management and Civil Security Ap-
plications”. Journal of Intelligent and Robotic Systems, 61,
pp. 563–585.
[10] Medeiros, A. C., and Urrutia, S., 2010. “Discrete optimiza-
tion methods to determine trajectories for dubins’ vehi-
cles”. Electronic Notes in Discrete Mathematics, 36, pp. 17
– 24. {ISCO} 2010 - International Symposium on Combi-
natorial Optimization.
[11] Macharet, D., and Campos, M., 2014. “An orientation as-
signment heuristic to the dubins traveling salesman prob-
lem”. In Advances in Artificial Intelligence – IBERAMIA
2014, A. L. Bazzan and K. Pichara, eds., Vol. 8864 of
Lecture Notes in Computer Science. Springer International
Publishing, pp. 457–468.
[12] Macharet, D. G., Alves Neto, A., da Camara Neto, V. F.,
and Campos, M. F., 2013. “Efficient target visiting path
planning for multiple vehicles with bounded curvature”. In
IEEE International Conference on Intelligent Robots and
Systems (IROS), pp. 3830–3836.
[13] Macharet, D. G., Neto, A. A., da Camara Neto, V. F., and
Campos, M. F., 2012. “Data gathering tour optimization for
dubins’ vehicles”. In Congress on Evolutionary Computa-
tion (CEC), pp. 1–8.
[14] Sujit, P., Hudzietz, B., and Saripalli, S., 2013. “Route plan-
ning for angle constrained terrain mapping using an un-
manned aerial vehicle”. Journal of Intelligent & Robotic
Systems, 69(1-4), pp. 273–283.
[15] Kenefic, R. J., 2008.
“Finding good dubins tours for
uavs using particle swarm optimization”.
Journal of
Aerospace Computing, Information, and Communication,
5(2), pp. 47–56.
[16] Macharet, D. G., Neto, A. A., da Camara Neto, V. F., and
Campos, M. F., 2011. “Nonholonomic path planning opti-
mization for dubins’ vehicles”. In IEEE International Con-
ference on Robotics and Automation (talk), pp. 4208–4213.
[17] Tang, Z., and Ozguner, U., 2005. “Motion planning for
multitarget surveillance with mobile sensor agents”. IEEE
Transactions on Robotics, 21(5), Oct, pp. 898–908.
[18] Ma, X., Casta˜n´on, D., et al., 2006. “Receding horizon plan-
ning for dubins traveling salesman problems”. In Confer-
ence on Decision and Control, IEEE, pp. 5453–5458.
[19] Rathinam, S., Sengupta, R., and Darbha, S., 2007. “A re-
source allocation algorithm for multivehicle systems with
nonholonomic constraints”. IEEE Transactions on Automa-
tion Science and Engineering, 4, pp. 98–104.
[20] L.E.Dubins, 1957. “On curves of minimal length with a
constraint on average curvature, and with prescribed initial
and terminal positions and tangents”. American Journal of
Mathematics, 79(3), pp. 487–516.
[21] Lee, J.-H., Cheong, O., Kwon, W.-C., Shin, S., and Chwa,
K.-Y., 2000.
“Approximation of curvature-constrained
shortest paths through a sequence of points”. In Algorithms
- ESA 2000, M. Paterson, ed., Vol. 1879 of Lecture Notes
in Computer Science. Springer Berlin Heidelberg, pp. 314–
325.
[22] Kim, H.-S., and Cheong, O., 2013. “The cost of bounded
curvature”. Computational Geometry, 46(6), pp. 648 – 672.
[23] Boissonnat, J.-D., and Bui, X.-N., 1994. Accessibility re-
gion for a car that only moves forwards along optimal paths.
Tech. Rep. RR-2181, INRIA.
[24] Manyam, S., and Rathinam, S., 2015. “A tight lower bound-
ing procedure for the dubins traveling salesman problem”.
Presented at the International Symposium on Mathematical
Programming.
[25] Nemirovski, A., 1994. Efficient methods in convex pro-
gramming, lecture notes.