IEEE Robotics & Automation Magazine - September 2013 - 36

assume that these regions are connected in the sense
that there is a path between any two points. We also
assume that the fish remain stationary for the duration
of covering a region, which reduces the search problem
to a coverage problem.
The radio antenna has a limited sensing range. A given
robot path is said to cover a point if the point lies within the
sensing range of the robot at some instance along the path.
The coverage problem can be defined as follows: Given a set
of connected regions
R = {R 1, R 2, f, R n}, find
a
minimum length tour
Instead of using a fixed
that covers every point in
each region R i ! R.
path for k measurements,
A possible approach to
solving
this problem is
an adaptive algorithm
based on the traveling
salesperson problem
is used to choose
(TSP). We can discretize
each region with a resolumeasurement locations.
tion dependent on the
sensing range (Figure 3)
and compute a TSP tour of this set of points. However,
approximation algorithms for TSP usually require a metric
graph, which is typically represented as a complete graph
whose vertex set is the point set to be covered. In such a representation, the number of edges is quadratic in the number
of points. As the lake size or the sampling granularity
increases, maintaining and operating on this large graph can
become infeasible.
The coverage problem defined above is a generalization of
Euclidean TSP and, consequently, nondeterministic polynomial-time hard (NP-hard). Next, we present a general
approach for solving the coverage problem and show that the
length of the path using this approach does not deviate significantly from the length of an optimal tour.
Algorithm Description
Our general approach is composed of two steps. First, we
compute a tour xR that visits all the regions in R exactly
once. We say that region R i is visited if any point in R i is
visited by the tour. The tour xR imposes an ordering on
the regions, and defines (possibly the same) entry and exit
points for each region. The entry and exit points are
where xR intersects a region for the first and the last time,
respectively. Such a tour is not necessarily a solution to
the original problem, since it is not guaranteed to cover all
points in each region. We compute a coverage tour C R i for
each region R i ! R independently, starting and finishing
at the entry and exit points for each R i . The final tour x is
constructed by augmenting the coverage tours of each
region to the visiting tour xR .
We now analyze the performance of this algorithm. Let
OPT be an optimal tour that visits and covers all the regions
in R in minimum time. Let x )R be the optimal tour that visits
all the regions in R. Since OPT also visits all the regions in R,
36

IEEE ROBOTICS & AUTOMATION MAGAZINE

september 2013

we have OPT $ x )R , where x denotes the length of tour
)
x . Let C R be the optimal coverage tour for a region R i . OPT
covers ever y region in R: therefore, we have
OPT $ / R i ! R C )R i .
Suppose we use an α-approximation algorithm for computing x R and a b -approximation algorithm for finding the
coverage tour of each region. Then the tour x obtained by
visiting the regions according to the order given by xR and
covering each region independently when it is visited has a
cost of at most a x )R + / R i ! R b C R) i . Equivalently,
i

)

Ri ! R

C )R i # a OPT + b OPT

# (a + b) OPT .

Therefore, this approach costs at most a factor (a + b) of an
optimal algorithm.
We now present algorithms for the following two components of the strategy: computing a tour that visits the
regions and covering the regions with specified entry and
exit points.
Visiting the Regions: TSP with Neighborhoods
and the Zookeeper Problems
Computing a tour xR that visits all the regions depends on the
geometric properties of the regions. This problem is commonly known as TSP with neighborhoods (TSPN). Most geometric instances of the TSPN problem are NP-hard. In
general, we can use constant-factor approximation algorithms
for TSPN such as [15] to find xR and a .
In our application, it is reasonable to model the lake as a
simply connected region, i.e., without any holes. Furthermore,
more regions of interest where the fish are located are usually
close to the shore. If the regions are convex polygons touching
the boundary of a simply connected lake, the tour can be
computed using the so-called zookeeper's route [16]. This
special case of the TSPN can be solved optimally ^a = 1h in
polynomial time due to the following lemma.
Lemma 1 ([16]): Let R = {R 1, R 2, ..., R i, ..., R n} be a set of
convex regions located along the perimeter of a simply connected polygon P. An optimal solution exists for visiting the
regions in R, which visits them in the order they appear along
the boundary of P.
Once the ordering of the regions is known, the shortest
tour visiting all regions can be calculated using dynamic
programing. The exact solution is given in [16]. We use a
simpler solution by discretizing the boundary of the
regions to determine the entry and exit locations for each
region. We build a table C (i, s i) , which stores the length
of a tour that enters the region R i at location s i for the
first time. The entries of the table are computed using the
following recurrence:
C (i, s i) = min
8min (C (i - 1, s i -1)) + d (t i -1, s i)B,
t
i -1

S i -1

(1)

where s i -1 and t i -1 lie on the boundary of R i -1 , and d (x, y)
is the Euclidean distance between points x and y. The cost of

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2013