Optimal Control-Based UAV Path Planning with
Dynamically-Constrained TSP with Neighborhoods
Dae-Sung Jang1, Hyeok-Joo Chae1, and Han-Lim Choi1
Abstract
This paper addresses path planning of an unmanned aerial vehicle (UAV) with remote sensing capabilities
(or wireless communication capabilities). The goal of the path planning is to ﬁnd a minimum-ﬂight-time closed
tour of the UAV visiting all executable areas of given remote sensing and communication tasks; in order to
incorporate the nonlinear vehicle dynamics, this problem is regarded as a dynamically-constrained traveling
salesman problem with neighborhoods. To obtain a close-to-optimal solution for the path planning in a tractable
manner, a sampling-based roadmap algorithm that embeds an optimal control-based path generation process is
proposed. The algorithm improves the computational efﬁciency by reducing numerical computations required for
optimizing inefﬁcient local paths, and by extracting additional information from a roadmap of a ﬁxed number
of samples. Comparative numerical simulations validate the efﬁciency of the presented algorithm in reducing
computation time and improving the solution quality compared to previous roadmap-based planning methods.
I. INTRODUCTION
Path planning is one of the key problems on automated operation of unmanned aerial vehicles (UAVs)
in reducing costs, ﬂight time, fuel consumption, and chemical emission. A traditional technique on UAV
operation is that a UAV equipped with attitude, heading, and speed controllers under a guidance rule
navigates and tracks certain waypoints in a given order of visiting speciﬁed by a human operator. In a
higher level of the UAV automation scheme, called decision-making, even the visiting order of given
tasks is determined by the UAV itself in accordance with its mission objective. In the case that the
tasks are assigned point-wise and performed by visiting the exact locations, the UAV path planning
with decision-making has been modeled as the traveling salesman problem (TSP) for a Dubins vehicle
[1], [2].
This paper focuses a generalized path planning problem of a UAV having extended capabilities
of processing tasks: such as remote sensing capabilities for surveillance (e.g. electro-optical imaging,
synthetic aperture radar, and lidar based ranging/imaging) or wireless communication capabilities for
1The authors are with Department of Aerospace Engineering, KAIST, Daejeon 34141, Republic of Korea. E-mail: {dsjang,
hjchae}@lics.kaist.ac.kr, hanlimc@kaist.ac.kr.
arXiv:1612.06008v1  [cs.RO]  18 Dec 2016
collecting data from a sensor network with low-energy transmitters; a similar issue to the latter case has
been raised in sensor network studies as data mule problems [3]–[9]. A UAV with such capabilities does
not need to visit the exact position for processing each task, but rather it can just pass through certain
region around the task point speciﬁed by remote sensing/communication ranges. The decision-making
level of the path planning with a UAV of this type can be represented as the TSP with neighborhoods
(TSPN) [10]–[13], where the executable regions of tasks are deﬁned as neighborhoods of nodes.
However, the TSPN formulation is only appropriate for vehicles of very high mobility, whose point-to-
point visits are approximated by straight line segments. With an assumption on a UAV that the ﬂight path
curvature is constrained in a ﬁxed speed, the path planning problem has been formulated as the Dubins
TSPN (DTSPN). There have been several studies on this topic using evolutionary computations [14]–[16]
in a global optimization framework and sampling-based roadmap methods [17], [18]. A sampling-based
roadmap method is a discretization approach using a ﬁnite number of state samples distributed in the
space, and the roadmap is composed of the optimal paths between the samples. The roadmap discretizes
the problem into the generalized TSP (GTSP) and it is solved by a TSP solver after the Noon-Bean
transfomation [19]. In [17], the implementations and the resolution completeness of the sampling-based
roadmap was analyzed to solve DTSPN with polygonal neighborhoods. In a roadmap, some sample on
a neighborhood can also be contained in other intersecting neighborhoods, which means that a path
though the sample visits two tasks’ neighborhoods at the same time. The intersecting neighborhoods
of the samples of this kind were considered in [18] for constructing a more informative roadmap, and
it is shown that the method in [18] is highly advantageous for densely distributed neighborhoods and
theoretically performs better than the method in [17].
With Dubins path assumptions, only the path length or the ﬂight time under a constant speed can
be handled as a cost metric in the UAV path planning. Furthermore, in a two dimensional top down
view of UAV path planning, the dynamics of a UAV including variable speed plays a crucial role in
determining maneuverability (e.g. turning radius) and costs, especially ﬂight time. Thus, for an effective
and practical planning, instead of the sampling-based roadmap with shortest Dubins paths of a ﬁxed
turning radius and a ﬁxed speed, the roadmap composed of optimal paths obeying the UAV dynamics
with variable speed can be preferable.
An optimal control approach for constructing the optimal path connecting two state samples can take
into account more complex dynamics of UAVs and various types of cost metrics, such as integrated
control inputs, fuel consumption, and carbon emissions, which are the functions of the history of states
and inputs of the UAVs. However, the computational burdens for optimal control paths for every pair
of samples from different task neighborhoods grow with the square of the number of tasks, and may
dominate the total computation time for the path planning.
Therefore, in this paper, three techniques are introduced into a sampling-based roadmap algorithm to
reduce the computation for the UAV path planning with nonlinear dynamics. The techniques are proposed
to improve solution qualities with a reduced computation, but sacriﬁcing the theoretical resolution
completeness, which are only achievable with a very large number of samples. The ﬁrst technique
directly reduces the number of optimal control paths by exempting the calculations of certain paths
that are hardly possible in the optimal solution. The second one extends the concept of intersecting
neighborhoods in [18] to necessarily intersecting neighborhoods on the trajectory of a UAV following
certain dynamics, so that the utilization of the sampled roadmap is enhanced in a TSP solver. Finally,
the solution path of the GTSP instance from the roadmap is locally reﬁned by an optimal control method
with preserving the visiting order of neighborhoods. Numerical simulations demonstrate the efﬁciency
of the presented algorithms in both the computational load reduction and the performance improvement
compared with other roadmap methods.
II. PROBLEM FORMULATION
This section provides a mathematical formulation for the problem considered throughout this paper:
a two dimensional path planning of a UAV in level ﬂight with turns. The objective of the problem is to
minimize the ﬂight time for a closed tour visiting all neighborhoods of given tasks. The neighborhood
Ni ⊂R2 of a task i is assumed to be a disk centered on the location of the task, and the collection of
all the neighborhoods is denoted by N.
The vehicle dynamics is modeled as a curvature constrained Dubins vehicle with variable speed in
the plane, as in (1). In this model, the UAV can select whether to take slow but small radius turning or
to ﬂy faster with sacriﬁcing the agility.
˙x
=
v cos θ
˙y
=
v sin θ
˙v
=
c1u1
(1)
˙θ
=
c2
v u2
The coordinates of the vehicle position are x and y; v is the speed of the vehicle bounded between
vmin and vmax; and θ is the heading of it. This system has two control inputs u1 and u2. u1 represents
excessive thrust per mass providing an acceleration to the vehicle and c1 is a corresponding constant. In
this paper, u1 is normalized by choosing c1 appropriately so that u1 ∈[−1, 1]. u2 denotes the steering
command that ranges between [−1, 1]; a negative command signiﬁes a left turn and a positive one steers
right. If the vehicle takes coordinate turns in level ﬂight, the constant for steering c2 can be assumed to
be g
p
n2
max −1, where g is the gravitational acceleration and nmax denotes the maximum load factor
of the vehicle.
The formulation of the vehicle model above has an ambiguity on the heading angle, and thus may
be unstable in numerical processes of optimal control. The dynamics can be restated as a system of
nonlinear second order differential equations for the coordinates:
¨x
=
c1 ˙x
p
˙x2 + ˙y2u1 −
c2 ˙y
p
˙x2 + ˙y2u2,
¨y
=
c1 ˙y
p
˙x2 + ˙y2u1 +
c2 ˙x
p
˙x2 + ˙y2u2,
(2)
which deﬁnes the states of the vehicle without any ambiguities.
The trajectory (x(t), y(t)) of the UAV can be obtained by numerically integrating the differential
equations (2) from some initial state (x(t0), y(t0)) at t = t0 with a control input sequence (u1(s), u2(s))
in s ∈[t0, t]. For given n tasks and their neighborhoods in the plane, a solution for the path planning
must construct a closed path, i.e. a tour, which passes every neighborhoods at least one time. Thus,
from the initial time t0 to the ﬁnal ﬂight time tf completing the tour, there must exist at least one time
ti so that (x(ti), y(ti)) ∈Ni for every task i, and (x(t0), y(t0)) = (x(tf), y(tf)). Then, the path planning
problem is stated as an optimal control problem that is to ﬁnd a tuple of the initial state (x(t0), y(t0))
and the control input sequence (u1(t), u2(t)) in t ∈[t0, tf] for minimizing tf such that the trajectory of
UAV coordinates satisﬁes these neighborhood visiting constraints and the differential equations in (2).
III. SOLUTION APPROACH
In this section, an algorithm of a sampling-based roadmap approach is presented for solving the UAV
path planning with nonlinear dynamics. The algorithm is brieﬂy summarized in the following subsection
with its grounds, followed by the subsections for detailed descriptions of four steps of the algorithm.
A. Algorithm Outline
In section II, the UAV path planning problem is formulated as an optimal control problem with
neighborhood visiting constraints. However, obtaining a stable optimal solution of a dynamic system
with complex path constraints from an one-shot numerical optimization is a hard task in practice. Thus,
a similar framework to the sampling-based roadmap approaches for DTSP and DTSPN is utilized: the
path planning problem is approximately solved by a discretization of the continuous state space and a
graph transformation to GTSP. Instead of using Dubins paths as in DTSP and DTSPN, optimal control
paths are numerically obtained between quasi-random samples; i.e. the UAV path planning problem is
handled as a TSPN for a nonlinear dynamic system: dynamically-constrained TSPN.
The presented algorithm for solving the path planning is partitioned into four steps:
1) Given n tasks and their circular neighborhoods, create m samples in the state space of a UAV along
the boundary of each neighborhood. Then, construct a reduced roadmap by creating optimally
controlled paths between the pairs of the samples, while excluding very curvy paths before
numerical calculations.
2) Create a GTSP instance for ﬁnding the shortest tour in the reduced roadmap, and transform it to
ATSP with appropriate modiﬁcations for necessarily intersecting neighborhoods.
3) Using a TSP solver, obtain the optimal (or sub-optimal) solution for the transformed ATSP, and
then interpret it to a solution of the GTSP for the reduced roadmap.
4) With keeping the order of visiting in the GTSP solution, sequentially (or repeatedly) reﬁne the
local paths connecting every successive three neighborhoods by using an optimal control solver.
In the problem size under consideration (several dozen tasks), the numerical path generation by an
optimal control solver in step 1 is the most time-consuming process. With a minimal or no degradation
of the ﬁnal quality of the solution, some devious paths hardly assumed to be in the optimal tour
are excluded before the numerical optimal control process. The shortest Dubins paths are utilized for
discriminating the devious paths, and also for initial guessing in the optimal control.
The roadmap constructed with a reduced number of the optimal paths is then represented as a GTSP
problem, and converted to an ATSP problem to be solved by a TSP solver. During the conversion
to ATSP, other neighborhoods necessarily intersected in the course of ﬂight through each sample are
identiﬁed to avoid visiting neighborhoods multiple times (refer III-C for the detail). Finally, the path
from the optimal visiting sequence in the reduced roadmap is locally reﬁned. By this procedure, the
number of samples for constructing the roadmap needs not to be very large, since a local optimization
in the continuous state space is conducted preserving the visiting sequence from the roadmap.
B. Roadmap Construction with Reduced Paths & Optimal Control
The sampling-based roadmap for the UAV path planning is constructed with a reduced number of
path calculations. First, a ﬁxed number of samples are generated for the neighborhood of each task in
the state space composed of the position, heading, and speed of the UAV for convenience. Though the
samples can be randomly created, but the quasi-random Halton sequence is utilized for more evenly
distributed samples in the 4-dimensional state space under following constraints: the position of the
state samples are on only the boundary of the circular neighborhoods; the heading is assigned to be
Fig. 1.
The state samples of a vehicle generated on the boundaries of given tasks’ neighborhoods: the coordinates of each sample is
pointed by the head of a vector, of which direction and magnitude signify the velocity of the sample. Two-way optimal paths are calculated
for each pair of samples (e.g. Pcd and Pdc) except some cases that the shortest Dubins paths are quite devious (e.g. Pab).
a direction that the UAV enters the neighborhoods; and the speed is selected between vmin and vmax.
Afterwards, the state samples are converted to the positions (x, y) and the velocities ( ˙x, ˙y) in Cartesian
coordinates.
For each pair of state samples of two different neighborhoods, the minimal time paths in both
directions between the states are calculated by an optimal control solver (see Fig. 1). To speed up
the optimization process, the minimum Dubins path using the turning radius at the average speed of
the two states and corresponding steering inputs are assigned as the initial guess; the speed of the UAV
is assumed to be constant in this guess. GPOPS-II [20] with SNOPT optimizer [21] is used as the
optimal control solver, and this numerical solver produces a local optimal path with state and control
input histories.
The number of path calculations for constructing a complete roadmap quadratically increases with the
number of samples per task and also with the number of tasks. Since solving an optimal control problem
is not a constant number of basic operations, but it is rather composed of time-consuming processes,
the sampling-based roadmap construction might be the dominant procedure on the computation for the
path planning with a nonlinear dynamic system, especially for practical UAV operations with scores of
tasks. Therefore, it is decided to reduce the number of path calculations by cutting-down some paths,
according to a heuristic rule, which are hardly expected to be in the optimal solution of the planning.
It is conjectured that a devious and lengthy path between two samples compared with the straight-line
distance is barely a part of the optimal tour (e.g. path Pab in Fig. 1). Thus, at the phase of creating
initial guess, if the shortest Dubins path using the minimum turning radius at vmin is longer than twice
the straight-line distance between two samples’ locations, then the numerical optimal path calculation
is skipped and the path is not included in the roadmap. The resultant reduced roadmap is deﬁcient
in a strict sense in that the resolution completeness in [17], [18] is no longer guaranteed. However,
the resolution completeness is only meaningful with a very large number of samples, which requires a
massive computation, whereas the numerical simulations in section IV show that the reﬁned tours from
the reduced and the complete roadmaps of the same number of samples have little or no difference.
C. Transformation to ATSP with Necessarily Intersecting Neighborhoods
With the given sampled roadmap with optimal control paths, the path planning problem is approxi-
mately discretized as being GTSP, a variant of TSP, which is to ﬁnd the shortest cycle visiting at least
one node in every group. Each sample in the roadmap corresponds to a sample node in the graph GR
of the GTSP, and each path represents a directed edge of GR having the path cost (ﬂight time) as
its weight. The samples generated along the boundary of the same task’s neighborhood Ni belong to
the same group Vi, i.e. a subset of the vertex set V (GR) of the graph. This graph can be transformed
into ATSP using the Noon-Bean transformation and then be solved by exact or heuristic TSP solvers.
However, with a roadmap constructed from a ﬁnite number of samples, this approach might perform
worse in the instances with intersecting neighborhoods of densely distributed tasks.
If a state sample a on a neighborhood Na is also included in another neighborhood Nb, a vehicle
passing this sample point obviously visits both of the neighborhoods. Since a is nominally generated
to represent an entering state to Na, a naive use of the roadmap searches a path that visits another
sample generated for Nb before or after the visit to a. Therefore, even with a number of samples, it
is likely that an unnecessarily circling path is induced in highly overlapping neighborhoods of dense
tasks. A modiﬁed transformation from GTSP to ATSP was proposed in [18], based on the Noon-Bean
transformation, to utilize the information on the visits at the samples that are included in multiple
intersecting neighborhoods. It was demonstrated that the proposed method in [18] outperforms or at
least equals to the roadmap method using the Noon-Bean transformation.
In this paper, the idea on the intersecting neighborhoods of samples is extended to extract more
information about unavoidable visits of paths from sampled points. Since UAV dynamics is non-
holonomic, curvature-constrained, any local paths propagated before and after the state of a sample
must be between the maximally steered trajectories in left- and right-wise directions (see Fig. 2).
Fig. 2.
An example of necessarily intersecting neighborhoods of a UAV state sample. A UAV passing a state sample a on the boundary
of N3 must visit the neighborhoods that intersect with both the left and right maximally steered trajectories before and after a, i.e. N1,
N2, and N4.
Each maximally steered trajectory presents the local reachability of a vehicle, when it decelerates
(accelerates) as far as possible with steering in one direction after the state (before the state). If a
neighborhood intersects with both of the left and right maximally steered trajectories, the UAV must
visit the neighborhood before or after passing the sample, even in the case the neighborhood does not
contain the sample. The neighborhoods of this type are named as necessarily intersecting neighborhoods
of the sample. The necessarily intersecting neighborhoods of each sample can be partially obtained by
simple calculations using the minimum turn radius circles at the slowest speed as in Fig. 2 and are
considered in the transformation presented in this paper.
Now, the original graph GR is transformed into an ATSP instance graph including intersection nodes
representing necessarily intersecting neighborhoods. The transformation is based on the Noon-Bean
transformation and is functionally identical to the work in [18], but it is presented in a concise but
still accurate description. The collection of the necessarily intersecting neighborhoods of an entry state
sample s is denoted as Ns ∈N. Then, for each state sample s and corresponding sample node vs, the
following procedure is applied.
If there is only one necessarily intersecting neighborhood Nk, i.e. |Ns| = 1, then,
1) Add an intersection node vs−k, corresponding to the intersection with Nk, to the graph as being
afﬁliated to the node group Vk.
2) Copy all leaving edges of the sample node vs to vs−k except the leaving edges to the nodes in
Fig. 3.
The ﬁrst step on the graph transformation from the GTSP with necessarily intersecting neighborhoods to ATSP: The leaving
edges from a sample node vs are transferred to an intersection node corresponding to a neighborhood in Ns, and vs is connected with
all of its intersection nodes via a zero-weight path.
Vk.
3) Delete all leaving edges of vs and add an edge from vs to vs−k with a zero weight.
Otherwise, if there are multiple p necessarily intersecting neighborhoods, denoted as Nk1, ..., Nkp,
and then,
1) Add intersection nodes vs−k1, ..., vs−kp corresponding to the intersections with Nk1, ..., Nkp, to the
graph as being afﬁliated to Vk1, ..., Vkp, respectively.
2) Copy all leaving edges of the sample node vs to vs−kp except the leaving edges to the nodes in
Vk1, ..., Vkp.
3) Delete all leaving edges of vs and add an edge from vs to vs−k1 with a zero weight.
4) Connect all the intersection nodes in sequence by a directed path from vs−k1 to vs−kp with zero
weights.
The remaining process is the same as the Noon-Bean transformation:
1) For each group, connect the nodes in the same group by an arbitrary cycle consisting of edges
with zero weights.
2) Add a large constant M to the weights of all inter-group edges.
3) For each node v, regardless of whether it is derived from a sample or an intersection, shift all the
Fig. 4.
The second step on the graph transformation from the GTSP with necessarily intersecting neighborhoods to ATSP: the nodes in
each group are linked by a zero-weight cycle; the inter-group leaving edges are cyclically shifted and their weights are increased by a
large constant M.
inter-group leaving edges of v to the preceding node in the zero-weight cycle of its group: the
tails of inter-group edges in the same group are cyclically shifted along the zero-weighted cycle
in the reverse direction.
It is sufﬁcient that the large constant M is selected to be larger than the sum of the n largest weights
in the graph [22].
A GTSP solution normally consists of n nodes, each of which is one of the nodes in each group,
whereas the transformed ATSP solution visits all given nodes, both from samples and intersections. Since
the nodes in a group are visited successively in the optimal solution of the ATSP, as an interpretation of
the ATSP solution, the ﬁrst visited node in a group is the visited node in the equivalent GTSP solution.
However, the original GTSP for the path planning does not include any intersection nodes, and thus the
solution from the ATSP solver should be handled with some care as in the next subsection.
D. Solving ATSP
The next process is solving the transformed ATSP instance by a TSP solver.1 For a fast computation
generating the order of visits, a well-implemented state-of-the-art heuristic solver, LKH-2 [23] is selected
1Generic TSP solvers provide the transformation of ATSP to TSP.
in this paper. LKH-2 is based on a revised implementation of the Lin-Kernighan heuristic [24], a famous
variable-depth local search algorithm for TSP. The Lin-Kernighan heuristic searches the neighborhoods
of a feasible solution derived by k-exchanges to ﬁnd a k-opt solution, i.e. a local optimum, while
determining the searching depth k. The practical effectiveness of the Lin-Kernighan heuristic and its
variations has been consistently reported [25]–[27].
The output of the ATSP solver is a sequence of all sample and intersection nodes representing a
directed closed tour, and the ﬁrst visited node of each group constitutes the solution of the equivalent
GTSP in the Noon-Bean transformation. Among the ﬁrst visited nodes in the sequence, only the sample
nodes are in the original GTSP for the path planning, and the intersection nodes are dummies representing
the neighborhoods of some tasks that are concomitantly and inevitably visited during the ﬂight passing
the states of the “ﬁrst visited” sample nodes. Thus, the concatenated paths connecting the ﬁrst visited
sample nodes compose a minimized tour in the sampling-based roadmap visiting all the given task
neighborhoods.
E. Tour Reﬁnement
The ﬁnal step of the presented algorithm is a reﬁnement of the tour from the ATSP solver. Since
any tour from the sampling-based roadmap is a crudely discretized solution from a practically limited
number of samples in a 4-dimensional state space, the paths from the ATSP solver sometimes might look
inefﬁcient and the performance is quite restricted. The sparsity of the same-sized sampling increases with
the dimension of the dynamic system, and a higher number of samples for an elaborate approximation
results in a signiﬁcant increase of computation time. Thus, in this paper, paths composing the tour from
the previous step are locally reﬁned by optimal control processes, which preserve the order of visiting
neighborhoods in the tour while improve the solution quality by searching in the continuous state space.
Although the improvement is limited since the visiting order is ﬁxed, this technique reduces the required
number of samples for obtaining solutions with favorable quality in a practical time.
The tour reﬁnement step is processed as follows. First, the tour from concatenating the paths between
the ﬁrst visited sample nodes of the ATSP solution is re-partitioned by entering points of all neigh-
borhoods along the tour. Since some of the neighborhoods do not have entering sample states among
the ﬁrst visited sample nodes, starting at an arbitrary point on the tour, new entering states, which re-
partition the tour, are created along the tour every time when a neighborhood is newly encountered. The
resultant tour has exactly n paths and n entering states. The local reﬁnement is performed between three
successive entering states: the two end states are ﬁxed and the optimally controlled path that intersects
with at least one point in the neighborhood of the middle entering state is calculated by the same optimal
TABLE I
STATISTICAL RESULTS WITH THE COMPLETE ROADMAP IN SOLVING EXAMPLE INSTANCES
n
m
roadmap
ﬂight time (s)
construction
without INa
with INa from [18]
with necessarily INa
time (m)
reﬁnement
reﬁnement
before
after
before
after
10
10
49.2, 1.2
143.1, 7.1
119.3, 9.9
108.3, 7.8
106.9, 10.1
98.3, 8.2
10
15
112.6, 4.5
131.7, 3.8
110.6, 11.3
101.2, 9.0
99.7, 12.0
91.8, 10.0
10
20
277.7, 43.0
123.4, 6.6
100.9, 10.0
89.8, 8.6
91.2, 10.0
82.2, 7.0
15
10
160.6, 1.9
190.9, 9.7
133.9, 8.6
122.4, 7.8
122.3, 8.8
112.7, 7.5
20
10
290.5, 3.4
232.8, 8.2
168.0, 8.3
149.0, 9.5
145.0, 6.1
131.6, 8.5
Each data is the average value followed by the standard deviation from 10 test instances.
aIN: intersecting neighborhoods.
TABLE II
STATISTICAL RESULTS WITH THE REDUCED ROADMAP IN SOLVING EXAMPLE INSTANCES
n
m
roadmap
ﬂight time (s)
construction
without INa
with INa from [18]
with necessarily INa
time (m)
reﬁnement
reﬁnement
before
after
before
after
10
10
21.5, 3.1
143.6, 7.3
121.3, 9.2
107.6, 7.6
104.7, 13.0
95.3, 11.8
10
15
49.4, 7.2
131.7, 3.8
111.8, 10.9
102.1, 9.6
100.3, 12.0
92.7, 10.2
10
20
120.8, 20.5
125.2, 5.6
101.8, 10.2
90.3, 8.1
91.7, 10.7
84.2, 9.5
15
10
69.7, 7.4
191.0, 10.2
134.2, 8.7
121.9, 7.7
123.1, 8.1
114.5, 6.7
20
10
121.5, 11.6
236.1, 9.1
166.8, 10.2
146.2, 12.3
147.7, 6.7
136.0, 8.6
Each data is the average value followed by the standard deviation from 10 test instances.
aIN: intersecting neighborhoods.
control solver used for constructing the roadmap. This reﬁnement is repeated in an alternating order
of the re-partitioned paths: even-numbered states may ﬁrst reﬁned while keeping the others and then
odd-numbered states are reﬁned in the same way.
IV. NUMERICAL SIMULATIONS
This section describes numerical simulations performed to validate the computational efﬁciency and an
enhancement in the solution quality of the presented algorithm, in comparison to the previous sampling-
based roadmap algorithms. The algorithms were implemented in a MATLAB environment on a PC with
Intel R⃝CoreTM i5-4670 3.40GHz CPU and 8.00GB RAM. The optimal paths between sample states
were calculated by using the MATLAB interface of GPOPS-II [20] with SNOPT optimizer [21], and
the ATSP instances were solved by LKH-2 [23].
For each of three problem sizes, i.e. n = 10, 15, 20, ten test instances were created with randomly
generated task points in a 10km×10km plane, and each task had a circular neighborhood with a radius
of 1km. To identify the effect of the number of samples on the simulation results, three cases of
-2
0
2
4
6
8
10
12
-2
0
2
4
6
8
10
12
169.72s
X (km)
Y (km)
Fig. 5.
A solution tour for a problem with 20 tasks, derived from the sampling-based roadmap method using intersecting neighborhoods
[18]. The complete roadmap is constructed from 10 samples per task.
m = 10, 15, 20 were tested with the instances of 10 tasks, and 10 samples per task was used for
other size problems. The parameters in the UAV dynamics were assigned as follows: vmin = 0.25km/s,
vmax = 0.46km/s, c1 = 0.1, and c2 = 37.96m/s2, by setting g = 9.8m/s2 and n = 4. The minimum
and maximum radii of coordinate turns under these parameters are 1.65km and 5.58km.
In this setting, ten different conﬁgurations of the sampling-based roadmap algorithms were tested,
from the generic and complete roadmap method to the presented algorithm. The conﬁgurations of
algorithms are classiﬁed according to the roadmap consturction level (complete/reduced) and the use of
intersection neighborhoods (none, intersection neighborhoods, necessarily intersecting neighborhoods),
and the algorithms using intersection neighborhoods are sorted into the cases before and after the path
reﬁnement.
Table I summarizes the simulation results from the algorithms using the complete roadmap of the
same set of samples: all numeric data are given as averages and standard deviations, separated by
commas, of the results from ten test instances. The third column of Table I lists the computation times
for constructing the roadmaps in different cases of tasks and samples. The times for other computations,
-2
0
2
4
6
8
10
12
-2
0
2
4
6
8
10
12
142.29s
X (km)
Y (km)
Fig. 6.
A pre-reﬁned solution tour for a problem with 20 tasks, obtained by using necessarily intersecting neighborhoods. The complete
roadmap is constructed from 10 samples per task.
including graph transformation, solving TSP, and path reﬁnement, are below than 1% of the roadmap
construction times. It is observed that the averaged solution qualities are improved as more information
on the visits of neighborhoods from state samples are utilized, and this improvement becomes remarkable
in the problems with 20 tasks, i.e. more densely distributed tasks. The path reﬁnement reduces the ﬂight
time by roughly around 10% of the one before the reﬁnement. The increase of samples also contributes
to the solution quality, but accompanied with a signiﬁcant computational burden. The simulation results
of the same set of algorithms but using the reduced roadmap are presented in Table II, and it is worth
noting that comparable solutions can be obtained in less than a half of the computation time required
for the algorithms using the complete roadmap.
Figs. 5 to 7 depict the solution tours of different sampling-based roadmap algorithms for an example
instance with 20 tasks. The tours in Figs. 5 and 6 are pre-reﬁned solutions from the algorithm using
intersection neighborhoods in [18] and necessarily intersecting neighborhoods proposed in this paper.
Since the algorithm in [18] was devised to use the complete roadmap, all the results of the ﬁgures are
based on the complete roadmap from the same number of samples: 10 samples per each of the tasks.
-2
0
2
4
6
8
10
12
-2
0
2
4
6
8
10
12
122.01s
X (km)
Y (km)
Fig. 7.
A reﬁned solution tour for a problem with 20 tasks, obtained by using necessarily intersecting neighborhoods: high-speed sections
in the tour are plotted as solid lines and low-speed sections are marked as dotted lines. The complete roadmap is constructed from 10
samples per task.
By extracting additional information on the intersections from the roadmap, the ﬂight time in Fig. 6
is shorten, comparing to the one in Fig. 5, and the ﬂight tour appears more reasonable in terms of
reducing deviated paths from neighborhoods. The tour from the roadmap is locally improved by the
reﬁnement as in Fig. 7, which shows more tightly turning paths. The tour in Fig. 7 is divided into the
parts moving slow (below (vmin + vmax)/2, marked as dotted lines), and the other parts with high speed
(above (vmin +vmax)/2, marked as solid lines). Fig. 7 shows that a UAV following the locally optimized
solution tour from the presented algorithm takes a low-speed for turning with a minimal radius and
speeds up for nearly straight courses.
V. CONCLUSIONS
In this paper, a sampling-based roadmap algorithm using an optimal control approach has been
presented to solve a dynamically-constrained TSPN, i.e. a path planning problem of a UAV performing
remote sensing or wireless communication tasks. With a minimal or no degradation of the ﬁnal solution
quality, the algorithm constructs a reduced roadmap with optimal control paths, excluding inefﬁcient
local paths, between state samples of the UAV. For an improved solution quality with this reduced
roadmap, the extra information of inevitable visits on neighborhoods of the non-holonomic UAV paths
are extracted, and the optimized GTSP solution from the roadmap is locally reﬁned in the continuous
state space of the UAV. Numerical simulations demonstrate that the presented algorithm produces
improved solutions than the previous methods in a reduced computation time.
ACKNOWLEDGMENT
This work was supported by Agency for Defense Development (contract: #UD140053JD).
REFERENCES
[1] K. Savla, E. Frazzoli, and F. Bullo, “Traveling salesperson problems for the Dubins vehicle,” Automatic Control, IEEE Transactions
on, vol. 53, no. 6, pp. 1378–1391, July 2008.
[2] J. Le Ny, E. Feron, and E. Frazzoli, “On the Dubins traveling salesman problem,” Automatic Control, IEEE Transactions on, vol. 57,
no. 1, pp. 265–270, 2012.
[3] R. C. Shah, S. Roy, S. Jain, and W. Brunette, “Data mules: Modeling and analysis of a three-tier architecture for sparse sensor
networks,” Ad Hoc Networks, vol. 1, no. 2, pp. 215–233, 2003.
[4] D. Jea, A. Somasundara, and M. Srivastava, “Multiple controlled mobile elements (data mules) for data collection in sensor networks,”
in Distributed Computing in Sensor Systems.
Springer, 2005, pp. 244–257.
[5] B. Yuan, M. Orlowska, and S. Sadiq, “On the optimal robot routing problem in wireless sensor networks,” Knowledge and Data
Engineering, IEEE Transactions on, vol. 19, no. 9, pp. 1252–1261, Sept 2007.
[6] M. Di Francesco, S. K. Das, and G. Anastasi, “Data collection in wireless sensor networks with mobile elements: A survey,” ACM
Transactions on Sensor Networks, vol. 8, no. 1, pp. 7:1–7:31, Aug. 2011.
[7] J.-S. Liu, S.-Y. Wu, and K.-M. Chiu, “Path planning of a data mule in wireless sensor network using an improved implementation
of clustering-based genetic algorithm,” in Proceedings of Computational Intelligence in Control and Automation (CICA), 2013 IEEE
Symposium on, April 2013, pp. 30–37.
[8] L. He, J. Pan, and J. Xu, “A progressive approach to reducing data collection latency in wireless sensor networks with mobile
elements,” Mobile Computing, IEEE Transactions on, vol. 12, no. 7, pp. 1308–1320, July 2013.
[9] W.-L. Chang, D. Zeng, R.-C. Chen, and S. Guo, “An artiﬁcial bee colony algorithm for data collection path planning in sparse
wireless sensor networks,” International Journal of Machine Learning and Cybernetics, vol. 6, no. 3, pp. 375–383, 2015.
[10] E. M. Arkin and R. Hassin, “Approximation algorithms for the geometric covering salesman problem,” Discrete Applied Mathematics,
vol. 55, no. 3, pp. 197–218, 1994.
[11] A. Dumitrescu and J. S. Mitchell, “Approximation algorithms for TSP with neighborhoods in the plane,” Journal of Algorithms,
vol. 48, no. 1, pp. 135–159, 2003.
[12] M. de Berg, J. Gudmundsson, M. J. Katz, C. Levcopoulos, M. H. Overmars, and A. F. van der Stappen, “TSP with neighborhoods
of varying size,” Journal of Algorithms, vol. 57, no. 1, pp. 22–36, 2005.
[13] B. Behdani and J. C. Smith, “An integer-programming-based approach to the close-enough traveling salesman problem,” INFORMS
Journal on Computing, vol. 26, no. 3, pp. 415–432, 2014.
[14] K. J. Obermeyer, “Path planning for a UAV performing reconnaissance of static ground targets in terrain,” in Proceedings of AIAA
Guidance, Navigation, and Control Conference, 2009.
[15] D. G. Macharet, A. A. Neto, V. F. da Camara Neto, and M. F. Campos, “An evolutionary approach for the Dubins’ traveling
salesman problem with neighborhoods,” in Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation,
ser. GECCO ‘12.
New York, NY, USA: ACM, 2012, pp. 377–384.
[16] Z. Xing, C. Jie, X. Bin, and P. Zhihong, “A memetic algorithm for path planning of curvature-constrained UAVs performing
surveillance of multiple ground targets,” Chinese Journal of Aeronautics, vol. 27, no. 3, pp. 622–633, 2014.
[17] K. J. Obermeyer, P. Oberlin, and S. Darbha, “Sampling-based path planning for a visual reconnaissance unmanned air vehicle,”
Journal of Guidance, Control, and Dynamics, vol. 35, no. 2, pp. 619–631, 2012.
[18] J. T. Isaacs and J. P. Hespanha, “Dubins traveling salesman problem with neighborhoods: a graph-based approach,” Algorithms,
vol. 6, no. 1, pp. 84–99, 2013.
[19] C. E. Noon and J. C. Bean, “An efﬁcient transformation of the generalized traveling salesman problem,” INFOR, vol. 31, no. 1,
p. 39, 1993.
[20] M. A. Patterson and A. V. Rao, “GPOPS-II: A MATLAB software for solving multiple-phase optimal control problems using hp-
adaptive Gaussian quadrature collocation methods and sparse nonlinear programming,” ACM Transactions on Mathematical Software,
vol. 41, no. 1, pp. 1:1–1:37, Oct. 2014.
[21] P. E. Gill, W. Murray, and M. A. Saunders, “SNOPT: An SQP algorithm for large-scale constrained optimization,” SIAM Journal
on Optimization, vol. 12, no. 4, pp. 979–1006, 2002.
[22] K. Helsgaun, “Solving the equality generalized traveling salesman problem using the Lin–Kernighan–Helsgaun algorithm,”
Mathematical Programming Computation, vol. 7, no. 3, pp. 269–287, 2015.
[23] ——, “General k-opt submoves for the Lin–Kernighan TSP heuristic,” Mathematical Programming Computation, vol. 1, no. 2-3,
pp. 119–163, 2009.
[24] S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Operations Research, vol. 21,
no. 2, pp. 498–516, 1973.
[25] K. Helsgaun, “An effective implementation of the Lin–Kernighan traveling salesman heuristic,” European Journal of Operational
Research, vol. 126, no. 1, pp. 106–130, 2000.
[26] R. K. Ahuja, ¨O. Ergun, J. B. Orlin, and A. P. Punnen, “A survey of very large-scale neighborhood search techniques,” Discrete
Applied Mathematics, vol. 123, no. 1, pp. 75–102, 2002.
[27] C. Rego, D. Gamboa, F. Glover, and C. Osterman, “Traveling salesman problem heuristics: leading methods, implementations and
latest advances,” European Journal of Operational Research, vol. 211, no. 3, pp. 427–441, 2011.