A Survey on Coverage Path Planning for Robotics

Enric Galceran and Marc Carreras

University of Girona
Underwater Robotics Research Center (CIRS)
Parc Cientı́fic i Tecnològic de la Universitat de Girona
Pic de Peguera, 13
17003 Girona (Catalonia, Spain)
enricgalceran@eia.udg.edu, marc.carreras@udg.edu

September 24, 2013

Abstract cleaners (Farsi et al., 1994), just to name a few.

In one of the earliest works on CPP found in the litera-

The coverage path planning (CPP) problem is the task ture, Cao et al. (1988) defined the requirements a robot
of determining a path that passes over all points of must meet to perform a coverage operation. Albeit the
an area or volume of interest while avoiding obstacles. target application in the aforementioned paper is a mo-
This task is integral to many robotic applications, such bile robot moving in a flat 2-dimensional environment,
as vacuum cleaning robots, painter robots, autonomous the same criteria are applicable to other coverage sce-
underwater vehicles (AUVs), demining robots, lawn narios. The requirements are as follows:
mowers, automated harvesters and window cleaners,
just to name a few. A considerable body of research
1. robot must move through all the points in the tar-
has addressed the CPP problem. However, no updated
get area covering it completely.
surveys on CPP reflecting the recent advances in the
field have been presented in the past ten years. In 2. robot must fill the region without overlapping
this paper, we present a review of the most success- paths.
ful CPP methods, focusing on the achievements made
in the past decade. Furthermore, we discuss reported 3. continuous and sequential operation without any
field applications of the CPP methods described. This repetition of paths is required.
work aims to become a starting point for researchers 4. robot must avoid all obstacles.
who are initiating their endeavors in CPP. Likewise,
we aim to present a comprehensive review of the recent 5. simple motion trajectories (e.g., straight lines or
breakthroughs in the field, providing links to the most circles) should be used (for simplicity in control).
interesting and successful works.
6. an “optimal” path is desired under available con-
ditions.

1 Introduction However, it is not always possible to satisfy all these

criteria in complex environments. Therefore, some-
times a priority consideration is required.
The coverage path planning (CPP) problem is the task
of determining a path that passes over all points of The CPP problem is related to the covering salesman
an area or volume of interest while avoiding obsta- problem, a variant of the well-known traveling sales-
cles. This task is integral to many robotic applications, man problem where, instead of visiting each city, an
such as vacuum cleaning robots (Yasutomi et al., 1988), agent must visit a neighborhood of each city (Arkin and
painter robots (Atkar et al., 2005b), autonomous un- Hassin, 1994). However, in CPP, the agent must pass
derwater vehicles (AUVs) (Hert et al., 1996; Englot over all points in the target area in contrast to visiting
and Hover, 2012), demining robots (Gage, 1994; Na- all the neighborhoods. Since the traveling salesman
jjaran and Kircanski, 2000; Acar et al., 2003), lawn problem is NP-hard, the computational time required
mowers (Cao et al., 1988; Bosse et al., 2007), auto- to solve the problem increases drastically when the di-
mated harvesters (Ollis and Stentz, 1997) and window mension of the problem increases. Actually, finding a

1
path to cut all the grass of a given region covered by erations which deal intrinsically with a 3-dimensional
grass, which is known as the “lawnmower problem”, is space, it is difficult to think that a randomized “algo-
proven to be NP-hard (Arkin et al., 2000). Notice that rithm” could be usable, as the cost of operating the
the lawnmower problem does not account for obstacles. vehicle (energy and time) would be unaffordable.
In fact, even the basic path planning problem, known
as the “piano mover’s problem”, of finding a collision- A considerable body of research addressing the CPP
free path from a start configuration to a goal config- problem can be found in the literature. Choset (2001)
uration is shown to be PSPACE-hard, which implies presented a survey on the field. However, no updated
NP-hard (LaValle, 2006; Reif and Sun, 2001). Two surveys on CPP reflecting its recent advances have
additional, similar problems related to CPP are the been presented in the past ten years. In this paper,
art gallery problem and the watchman route problem. we present a review of the most successful CPP meth-
The art gallery problem calls for the minimum num- ods, focusing in the achievements made in the past
ber of guards needed to station in a polygonal gallery decade. Furthermore, we discuss reported field appli-
so that each point in the gallery is visible to at least cations of the CPP methods described. This work aims
one guard (Shermer, 1992). The watchman route prob- to become a starting point for researchers who are ini-
lem calls for the shortest route from a given point back tiating their endeavors in CPP. Likewise, we aim to
to itself so that each point in a given space is visible present a good review of the recent breakthroughs in
from at least one point along the route (Li and Klette, the field, providing links to the most interesting and
2008). Simple cases of the watchman route problem successful works.
such as covering the interior of simple polygons can be
achieved in polynomial time (Chin and Ntafos, 1991). Since most CPP algorithms decompose the target
But, in general, both the art gallery problem and the space in sub-regions (called cells) to achieve coverage,
watchman route problem are NP-hard (Shermer, 1992; Choset (2001) classified coverage algorithms according
Li and Klette, 2008). Some coverage algorithms we to the type of decomposition used. Hence, his taxon-
discuss in Subsec. 8.6 approach CPP as the art gallery omy comprises heuristic and randomized approaches
problem and the watchman route problem. (which typically do not use a representation of the en-
vironment and therefore neither use a decomposition),
Coverage algorithms can be classified as heuristic or and approximate, semi-approximate and exact cellu-
complete depending on whether or not they provably lar decompositions. However, we argue that qualita-
guarantee complete coverage of the free space. In- tively different approaches can be distinguished among
dependently, they can be classified as either off-line these categories. Thus, the outline of this article does
or on-line. This classification was originally proposed not bear a one-to-one correspondence with Choset’s
by Choset (2001). Off-line algorithms rely only on sta- taxonomy, but rather reflects the common underlying
tionary information, and the environment is assumed ideas used in the discussed approaches. Nonetheless,
to be known in advance. However, assuming full prior Choset’s taxonomy is commonly used throughout the
knowledge of the environment might be unrealistic in literature, and hence we also provide the corresponding
many scenarios. On the other hand, on-line algorithms Choset’s classification for the methods reviewed.
do not assume full prior knowledge of the environment
to be covered and utilize real-time sensor measure- Resulting from these considerations, the remainder of
ments to sweep the target space. Thus, these later this article is organized as follows. Sec. 2 reviews clas-
algorithms are also called sensor-based coverage algo- sical cellular decomposition algorithms which set the
rithms. fundamentals of the cellular decomposition approach.
Sec. 3 discusses the cellular decomposition based on
In certain scenarios, a valid approach to solve the critical points of Morse functions, which can deal with a
problem is to randomize. This is an approach that more general class of obstacles. Sec. 4 presents a cover-
some floor-cleaning robots rely on: if the floor is swept age approach based on detection of natural landmarks.
randomly for long enough, it should become cleaned. A coverage algorithm for robots equipped with only
Examples of commercial floor-cleaning robots based contact sensors operating in rectilinear environments
fully or partially on this strategy are the RC3000 is discussed in Sec. 5. Methods based on a grid rep-
by Karcher, Trilobite by Electrolux and Roomba by resentation of the space are reviewed in Sec. 6. Work
iRobot (Palacin et al., 2005). There are advantages to addressing the coverage problem in environments that
this approach, the main one being that no complex can be represented as a graph, such as a street or road
sensors for localization nor expensive computational network, is briefly reviewed in Sec. 7. In Sec. 8 sev-
resources are needed. However, for covering vast ar- eral methods for covering 3-dimensional environments
eas, and especially for underwater or aerial robotics op- are presented. Sec. 9 reviews some methods for achiev-

2
ing optimal coverage, and Sec. 10 focuses on methods sition generates a coverage path in two steps. First, it
that intend to reduce the accumulation of localization decomposes the free space into cells and stores the de-
error while planning a coverage path. In Sec. 11 sev- composition as an adjacency graph. Next, it computes
eral multi-robot CPP methods are reviewed. Finally, an exhaustive walk through the adjacency graph (i.e.,
concluding remarks including a summary table and di- a sequence that visits each node in the graph exactly
rections for further research are given in Sec. 12. once). It is worth noting that the exhaustive walk ob-
tained is a sequence of nodes (i.e., a sequence of cells),
and not an actual coverage path. Therefore, an ex-
plicit path for covering each cell must be derived using
2 Classical Exact Cellular De- simple motions as discussed above.
composition Methods
Next, two popular off-line cellular decomposition ap-
proaches (Subsec. 2.1 and Subsec. 2.2) that laid down
Exact cellular decomposition methods break the free the foundations for more advanced methods are dis-
space (i.e., the space free of obstacles) down into sim- cussed.
ple, non-overlapping regions called cells. The union
of all the cells exactly fills the free space. These re-
gions, which contain no obstacles, are “easy” to cover 2.1 Trapezoidal Decomposition
and can be swept by the robot using simple motions.
For instance, each cell could be covered using a zigzag,
One of the simplest exact cellular decomposition tech-
“mowing the lawn” pattern like the one shown in Fig. 1.
niques which can yield a complete coverage path is
Generation of these zigzag motions, also called seed-
the trapezoidal decomposition (Latombe, 1991; Choset
spreader motions, is well documented in the litera-
et al., 2005), which handles only planar, polygonal
ture (Lumelsky et al., 1990; Choset and Pignon, 1997;
spaces. Given that it uses no sensor information, this
Acar et al., 2002).
method can be classified as off-line. In the trapezoidal
decomposition, each cell is a trapezoid, as shown in
Fig. 2. Thereby, simple back-and-forth motions can be
used to cover each cell. Complete coverage is guaran-
teed by finding an exhaustive walk through the adja-
cency graph associated to the decomposition (overlaid
on the decomposition in Fig. 2). Finally, a specific
zigzag path to cover each cell is generated. The ex-
haustive walk determines the order in which the cells
are visited to achieve complete coverage. Finally, spe-
cific paths to cover each cell are generated, typically
using back-and-forth motions in a “mowing the lawn”
manner.
Figure 1: Typical “mowing the lawn” path. The
shaded area indicates the area already covered (darker)
and the area that will be covered (lighter) when the c2 c4 c6
robot finishes following the path. c9 c11
Two cells are said to be adjacent if they share a com-
mon boundary. An adjacency graph can be used to
c1 c8 12 c
represent the cellular decomposition, where a node rep-
resents a cell and an edge represents an adjacency re-
lationship between two cells (see Fig. 2). Exact cell c3 c5 c7 c10
decompositions can be generated by sweeping a line
through the space (e.g. from left to right). The cell
boundaries are then formed when some event is en-
countered by the sweep line. For instance, a change Figure 2: Trapezoidal decomposition of an example
on the number of times the sweep line intersects with workspace with its corresponding adjacency graph.
obstacle boundaries can be used as an event.
As an application example, Oksanen and Visala (2009)
Typically, a planner based on exact cellular decompo- proposed an off-line algorithm based on the trapezoidal

3
decomposition for coverage path planning in the case
of agricultural fields. Their algorithm applies a trape-
zoidal decomposition of the field followed by a cell
merging procedure. The resulting cells are similar to
those produced by the boustrophedon decomposition,
introduced in the next section (2.2). To optimize the
path, they use a path-based cost function to assess the
largest cell arising in six different trapezoidal decom-
positions obtained by using a sweep line inclined at (a)
30◦ intervals. Then, the three most favorable direc-
tions are selected and the process is repeated, with
additional decompositions at 15◦ either side of the se-
lected headings. The process continues iteratively un-
til the improvement per step falls below a threshold,
which for their application was achieved after 5 steps
(about 1◦ accuracy), requiring 36 separate decomposi-
tions. Then, the largest cell in the minimum-cost de-
composition is removed from the target area, and the
process is repeated for the remainder of the field until (b)
all the area is covered by the path. This scheme pro-
duces effectively optimal coverage paths for a convex Figure 3: A decomposition with less cells allows for
field and high-quality paths for a field whose bound- shorter coverage paths. Note how an extra strip is
aries consist of long, straight segments as well. needed in the trapezoidal decomposition in 3(a) with
respect to the boustrophedon decomposition in 3(b).

2.2 Boustrophedon Decomposition

3 Morse-based Cellular Decom-
A drawback of the trapezoidal decomposition is that it position
generates many cells that, intuitively, can be merged
together to form bigger cells. This is clearly incon-
venient, as the more cells are present, the longer the Later, Acar et al. (2002) generalized the boustrophedon
final coverage path becomes, as shown in Fig. 3. This decomposition by proposing a novel cellular decompo-
happens because the trapezoidal decomposition creates sition approach based on critical points of Morse func-
only convex cells. However, non-convex cells can also tions (Milnor, 1963). In fact, they show that the bous-
be completely covered by simple motions. To overcome trophedon decomposition is a particular case of Morse
this limitation, Choset & Pignon proposed the bous- decomposition. With respect to the original bous-
trophedon cellular decomposition (Choset and Pignon, trophedon decomposition, the Morse-based decomposi-
1997; Choset et al., 2000a). The word “boustrophe- tion has the advantage of handling also non-polygonal
don” comes from ancient Greek, and literally means obstacles. By choosing different Morse functions, dif-
“the way of the ox”, signifying the pattern in which an ferent cell shapes are obtained, e.g. circular or spiked
ox drags a plow back and forth. The boustrophedon cells. Theoretically, Morse-decompositions can be ap-
decomposition is similar to the trapezoidal decomposi- plied to any n-dimensional space. Moreover, they pre-
tion introduced above, but it only considers vertices in sented a method to perform coverage of planar spaces
the environment where a vertical segment can be ex- by detecting the critical points using sensory range
tended both above and below the vertex. The vertices information, and a motion-template-based algorithm
where this occurs are called critical points. that ensures to encounter all the critical points in the
target area. Therefore, this method allows complete
By adhering to this strategy, the boustrophedon de- coverage on-line (Acar and Choset, 2001, 2002a).
composition effectively reduces the number of cells in
trapezoidal decomposition. Hence, shorter coverage The Morse decomposition is based on a roadmap
paths are obtained. Notice that, as the trapezoidal method for start-to-goal path planning proposed by
decomposition, this method assumes polygonal obsta- Canny (Canny, 1988, 1993). Critical points of a Morse
cles and the terrain to be known a priori, and thus function restricted to the obstacle boundaries are used
classifies as an off-line method. to determine the cell decomposition. Recall that, given

4
a real-valued function h : Rm → R, its differential at Sweep direction
∂h ∂h
p ∈ Rm is dh(p) = [ ∂x 1
(p) . . . ∂x m
(p)]. A critical point
m
is a value p ∈ R where either the function is not
differentiable or all its partial derivatives are 0, i.e.,
∂h ∂h ∂2h Critical
∂x1 (p) = . . . = ∂xm (p) = 0, and its Hessian ( ∂xi ∂xj (p))
is non-singular. For instance, in the case of a single Surface point
variable function, a critical point corresponds either to normal
a local maximum, a local minimum or an inflection.
A Morse function is one whose critical points are non-
degenerate (Milnor, 1963). Practically speaking, this
Sweep line
means that critical points are isolated from one an-
other.
Figure 4: Cell boundaries in Morse decomposition are
To determine the cell decomposition, a slice is swept placed at critical points, where the surface normal of
through the target space. Formally, the slice is a codi- the obstacle is perpendicular to the sweep slice, and
mension one manifold defined in terms of the preimage parallel to the sweep direction.
of a real-valued Morse function, h : W → R, where
W is the robot’s workspace, i.e., the space to be cov-
ered. For instance, in the plane (W = R2 ), choosing slice pieces are merged into larger pieces (the connec-
h(x, y) = x will make the slice be effectively a vertical tivity of the slice in the free space decreases). The
line. Changes on the connectivity of the slice occur at points where these connectivity changes occur are the
critical points of the Morse function restricted to the critical points. (Recall that critical points are always
obstacle boundaries. To put it more simply, at a criti- located on the obstacle boundaries.) Thus, at critical
cal point the sweep line encounters an obstacle whose points, the slice is used to determine the cells in the
surface normal is perpendicular to the sweep line, as decomposition. Notice that within a cell, the slice con-
shown in Fig. 4. Morse theory guarantees that, be- nectivity remains constant. Fig. 5(a) shows how, at
tween critical points, the connectivity of the slice re- the critical point, the connectivity of the slice changes
mains unchanged. Thus, as no obstacles lay between from one to two, and hence the old cell is closed and
critical points, the space between them can be covered two new cells are created. In Fig. 5(b), at the critical
easily by simple motions, and critical points can be point, the connectivity of the slice changes from two to
used to determine the cell boundaries. one, and hence two old cells are closed and a new cell
is created.
Choosing different Morse functions produces different
slice shapes and hence different cell decomposition pat-
terns. For simplicity, we will describe the Morse-based Once the cell decomposition is constructed, an exhaus-
boustrophedon decomposition (Choset, 2000), which tive walk through its associated adjacency graph is de-
happens in the plane. Later, we will give examples termined by the planner. Then, it generates the ex-
of different decomposition patterns obtained using dif- plicit coverage path in each cell. The coverage pattern
ferent Morse functions. within each cell has three parts: motion along a slice,
motion orthogonal to the slice, and motion along the
In the boustrophedon decomposition, a vertical slice, cell boundary, as shown in Fig. 6. First, the robot laps
defined in terms of the Morse function h(x, y) = x, is along the current slice, Wλ . Then the robot steps out-
swept from left to right in the workspace, i.e., along the ward of the slice by going orthogonally to it by an inter-
abscissae axis. Thus, the vertical slice is determined by lap distance, typically by a distance of one robot sensor
the pre-image of this Morse function, Wλ = h−1 (λ). range; λ is also increased by this distance to form a new
The slice is parametrized by λ ∈ R, which fixes its slice. If the robot encounters an obstacle (i.e., the cell
location in the target space. Increasing the value of boundary) while moving along the slice, the planner
the slice parameter, λ, sweeps the slice from left to directs the robot to follow the obstacle boundary until
right through the workspace. it has moved an inter-lap distance and then a new lap
along a new slice is started. The process repeats until
As the slice sweeps the space it intersects (or stops in- the cell is completely covered.
tersecting) obstacles, which divide it into smaller pieces
as the slice first encounters an obstacle, that is, the con- Fig. 7 shows the Morse-based boustrophedon cell de-
nectivity of the slice in the free space increases. Also, composition of an example workspace with its associ-
immediately after the slice leaves an obstacle, smaller ated adjacency graph overlaid.

5
 c2 c5
c8
Sweep direction
c1 c4 c7 c9
Old cell New cell 1

Surface Critical c3 c6
normal point
Sweeping slice

Figure 7: Morse decomposition of an example

New cell 2 workspace with its associated adjacency graph.

(a) A key point of Morse decompositions is that, by choos-

ing different Morse functions to define the slice that
Sweep direction
is swept through the space, different decomposition
and coverage path patterns can be generated, like the
Sweeping slice

Old cell 1 spiral pattern (Acar et al., 2002). Figure 8 shows

a spiral pattern
p obtained using the morse function
h(x, y) = x2 + y 2 . Allowing different coverage pat-
Critical Surface terns is useful for vehicles with kinematic constraints.
point normal For instance, a spiral path can be easily followed by
an underactuated car-like vehicle unable to make hard
Old cell 2 turns (Bosse et al., 2007).

(b)

Figure 5: Cell determination with the Morse-based

boustrophedon cell decomposition method.

Figure 8: Spiral Morse decomposition

p obtained using
the Morse function h(x, y) = x2 + y 2 .
λ+2δ
λ+δ
λ

A limitation of the Morse decomposition method is

Motion along that it cannot handle rectilinear environments. This
the slice is because it is not possible to determine critical points
Motion along in those environments which correspond to a change in
Motion orthogonal the boundary
to the slice the topology of the space (the critical points are said
δ
to be degenerate in this case (Milnor, 1963)).

(Galceran and Carreras, 2012) presented a CPP

method based on Morse decomposition to minimize re-
Figure 6: Boustrophedon path construction process, dundant coverage for AUVs and autonomous surface
where δ is the inter-lap spacing and λ is the slice pa- vehicles (ASVs) imaging the ocean floor. To this aim,
rameter this method determines a sweep direction on each cell
of the decomposition and adjusts the inter-lap spacing
of the boustrophedon path on a lap by lap basis accord-
ing to the ocean depth. The efficacy of the method is

6
demonstrated in simulation using a real-world dataset.

3.1 On-line Morse-based Boustrophe-

don Decomposition
Sweep direction
To face the sensor-based coverage problem, Acar and
Choset (2002a, 2000) gave a method to detect the crit-
ical points of a Morse-based boustrophedon decompo-
sition on-line using range sensor information. Further- c0
more, they presented an algorithm that ensures to en- rdi(x) x
counter all the critical points while performing cover- di(x)
age. To detect the critical points, they use an omni-
directional range sensor to look for points where the
surface normals ∇m(x) of obstacles and the sweep di-
rection are parallel. Given a robot located at point x, Sweep line
let c0 be the closest point to x on the surface of obstacle
Ci : Figure 9: Critical point detection occurs on the side
of the range sensing robot, whose heading is indicated
by the rectangular mark on the circle representing the
c0 = argmin ||x − c|| , (1)
c∈Ci robot.

and let di (x) be the distance between point x and the

obstacle Ci . Now, the gradient of di (x), ∇di (x) can be
calculated as

x − c0
∇di (x) = . (2)
||x − c0 ||

Recall that, by definition, a gradient is a unit vector

normal to a surface at a given point. In Eq. 2, as c0 is
a point laying on the surface of the obstacle Ci , x − c0
is a vector pointing outward from c0 towards x. Given
that c0 is the closest point to x on the obstacle surface,
the vector x − c0 is hence normal to the surface of the
obstacle. By dividing by its norm, ||x − c0 ||, the result
is turned into a unit vector.

A detection of a critical point occurs when ∇di (x) is

parallel to the sweep direction. Or, in other words,
when the sweep direction and the obstacle surface nor-
mal are parallel. Fig. 9 graphically shows this situa- Missed critical points
tion.

Notice the fact that critical points can only be detected Figure 10: With Morse decomposition, a range sensing
when they are the closest point on the obstacle surface robot following a simple zigzag path will miss the criti-
from the robot compared to all other points on the cal points in the figure unless it performs wall following
obstacle surface. This implies that they can only be both on the top and the bottom of a cell.
detected when the robot is performing wall following.
Therefore, using a simple zigzag can result in some
critical points being missed, as those shown in Fig. 10.

To address this issue, (Acar et al., 2002) presented an

algorithm that uses repeated rectangular motion cycles

7
with wall following on both ends of a lap, as shown in In order to store and incrementally construct the
Fig. 11. The algorithm is termed “Cycle Algorithm”. Morse decomposition on-line, it is stored as a Reeb
Notice that this cyclic path includes retracing, and graph (Reeb, 1946). The Reeb graph is dual to the ad-
hence is longer than the simple zigzag path. jacency graph in that the nodes of the Reeb graph are
the critical points and the edges connect neighboring
critical points, i.e., correspond to cells. An example
Morse decomposition with its associated Reeb graph is
shown in Fig. 13.

Cp5

Cp1
Cp4
Cp3
Cp2 Cp6

Critical points detected

Figure 11: A path composed of rectangular cycles al-

lows detection of all the critical points. This pattern Figure 13: Morse decomposition of an example
is used in on-line Morse decomposition and the CCR workspace with its associated Reeb graph. Cp1 ...Cp6
algorithm as well. are the critical points.

The cycle path generation process of their proposed al- Whenever a critical point is encountered, the robot up-
gorithm is shown in Fig 12. Initially (Fig 12(a)), the dates the Reeb graph. When a cycle path where critical
robot starts a forward phase at point Si and moves points were found is finished, the robot looks for uncov-
downward. When it encounters an obstacle, it per- ered cells at the last encountered critical point. If the
forms wall following until it has reached the next strip critical point is associated with two uncovered cells, the
or until a critical point is detected. If a critical point robot picks one of the cells associated as the next cell
is detected, the robot then enters in a reverse phase to cover. If there are no uncovered cells associated with
where it moves upward (see Fig 12(b)). In this phase, the last encountered critical point, a depth-first search
if an obstacle is detected, the robot wall-follows it. If is performed on the Reeb graph. To travel to the se-
a critical point is detected on the obstacle boundary, lected uncovered cell, the robot follows the Reeb graph
the next strip is moved to where the critical point is. and plans a path that passes through cells and critical
The motion continues until Si is reached again on the points. When no uncovered cells (edges) remain in the
current strip. Then, the robot starts a new cycle at Reeb graph, the environment is completely covered.
point Si+1 . The algorithm is proven to detect all the
critical points. The Cycle algorithm just described, however, may fail
to detect critical points on certain non-convex obsta-
cles. In particular, concave critical points such as Cp2
Current Next Current Old next in Fig. 14 cannot be detected by range data when the
strip strip strip strip
boundary’s curvature is smaller than the robot’s pe-
Si Si Si+1 riphery (Garcia and de Santos, 2004). However, the
closest convex critical point (Cp3 in the example shown
New next strip

in Fig. 14) to a critical point like Cp2 in Fig. 14 will

indeed be detected. This leads to adding a spurious
edge to the Reeb graph that does not correspond to
any existing cell. As a result, the algorithm will fail
to detect the closing critical point for the newly added
New critical
Point detected edge. Garcia and de Santos (2004) proposed a solu-
tion to this issue which involves associating each crit-
(a) Forward phase (b) Reverse phase ical point with its obstacle and defining unique entry
and exit critical points for each obstacle. Additionally,
Figure 12: Critical point detection using the cycle al- their paper discusses several implementation details of
gorithm. the Cycle algorithm.

8
 Cell3 Cell4 step considers the narrow or cluttered spaces where ob-
stacles lie within detector range, and thus the detector
“fills” the surrounding area. In this case, the robot can
Cell1 Cell5
cover the narrow space by simply following the Gener-
Cp3
alized Voronoi Diagram (GVD) of that space, which
Cp1 are sets of points equidistant to two obstacles (Choset
Cp4
and Burdick, 2000; de Berg et al., 2008) (see Fig. 15, on
Cp2 the left). The GVD can be constructed on-line using
Cell2 range sensor information and has been previously used
for sensor-based exploration (Choset et al., 2000b) and
Cp3 Cp4 inspection of 3D structures (Choset and Kortenkamp,
1999). A hierarchical decomposition that combines the
Cp1 Morse decompositions and the GVDs is introduced to
Incorrect edge ensure that the robot indeed visits all vast, open, as
well as narrow, cluttered, spaces. In their article, it
Figure 14: A concave critical point will not be detected is shown how to construct this decomposition on-line
if the boundary’s curvature is smaller than the robot’s using sensor data accumulated while the robot covers
periphery and will lead to an incoherent Reeb graph. the environment.
This is the case of Cp2 in this example environment,
which does not get detected and produces an incorrect
edge emanating from Cp3.

Acar et al. (2003) discussed coverage path planning in

relation to a demining application. In this article, they
show that Morse decomposition overcomes the random
coverage approach in this task, which used to be con-
sidered the state of the art on demining operations.

Figure 15: Combination of Morse decomposition and

3.2 Morse-based Cellular Decomposi- GVD for extended range sensor coverage. In cluttered
tion Combined with the General- spaces (left) the robot just follows the GVD of that
ized Voronoi Diagram space. In vast areas (right), the robot follows the pat-
tern generated using a Morse decomposition scheme.
(Acar et al., 2001, 2006) presented a sensor-based cov-
erage approach with extended range sensors. As they
point out, “prior work in coverage tends to fall into one
of two extremes: coverage with an effector the same 4 Landmark-based Topological
size of the robot, and coverage with an effector that Coverage
has infinite range.” In this work, they consider cov-
erage in the middle of this spectrum: coverage with a
detector range that goes beyond the robot, and yet is Wong and MacDonald (2003) presented an on-line
still finite in range. They term these sensors extended topological coverage algorithm for mobile robots based
range sensors. In this work, coverage is achieved in on detection of natural landmarks. This work is in-
two steps: the first step considers vast, open spaces, tended for simple planar environments. As in Morse
where the robot can use the full range of its detector; decomposition, their method also uses concepts in-
the robot covers these spaces as if it were as big as its troduced by boustrophedon decomposition. However,
detector range (see Fig. 15, on the right). Here pre- the topological algorithm proposed here uses different
vious work in using Morse cell decompositions (Acar events to determine cell boundaries. Morse decompo-
et al., 2002) is employed to cover unknown spaces. As sition places cell boundaries on the critical points on
explained above, cells in this decomposition can be cov- the obstacles surface. However, as commented before,
ered via simple back-and-forth motions, and coverage rectilinear environments cannot be handled by Morse
of the vast space is then reduced to ensuring that the decomposition, as the critical points in such environ-
robot visits each cell in the vast space. The second ments are degenerate. On the other hand, as critical

9
points can only be discovered on the side of the robot
while performing wall following, a rectangular coverage
pattern which includes retracing is needed. In contrast,
the topological approach presented here uses simpler
landmarks to determine an exact cellular decomposi-
tion termed “slice decomposition”. Due to the use of
simpler landmarks, slice decomposition can handle a
larger variety of environments, including those with
polygonal, elliptical and rectilinear obstacles. More-
over, obstacles can be detected from all sides of the
robot, allowing a simpler zigzag pattern without re-
tracing to be used. As a result, the generated coverage
path is shorter with this method.

4.1 Slice Decomposition

The slice decomposition is constructed by sweeping a

line through the space. It uses five different events to (a) Split event (b) Merge event
determine the cell boundaries:

1. Split event: A free space segment in the previous

strip is split into two by the emergence of an ob-
stacle, as in Fig. 16(a).
2. Merge: Two free space segments in the previous
strip are merged into one by the disappearance of
an obstacle, as in Fig. 16(b).
(c) Lengthen event (d) Shorten event
3. Lengthen: The current strip is much longer than
the previous strip, as in Fig. 16(c).
4. Shorten: The current strip is much shorter than
the previous strip, as in Fig. 16(d).
5. End : The previous free space segment is the final
one in the current cell, as in Fig. 16(e).

All these events or landmarks can be detected us-

ing a combination of range measurements thresholding (e) End event
and temporal sequence comparisons (comparing cur-
rent sensor reading with previous ones) and odometry
Figure 16: Events (landmarks) in the slice decompo-
(comparing length of consecutive strips). An alterna-
sition. In all the events shown ci is the current cell
tive solution that uses a neural network to detect the
(shaded) and si is the current strip. The dashed arrow
events is also presented in this work (Wong, 2006).
indicates the sweep direction.
Whenever one of the stated events occur, a cell bound-
ary is placed along the sweep line where the event takes
place. The slice decomposition can be encoded as a
topological map. A topological map is represented as
a planar graph, where the nodes represent landmarks
(i.e., split, merge, end, lengthen or shorten events) and
edges indicate the types of motion required to travel
between nodes they are incident upon. For example,
whether the edge is next to a wall and which side the

10
wall is on. They also store estimated distances sepa- 5 Contact Sensor-based Cover-
rating the two nodes they connect.
age of Rectilinear Environ-
ments
4.2 On-line Topological Coverage Algo-
Butler et al. (1999) proposed CCR , an exact cell de-
rithm composition algorithm for contact sensing robots (i.e.,
robots without range sensing capabilities) covering un-
An algorithm that constructs the slice decomposition known rectilinear environments on-line. Their moti-
on-line while performing coverage is presented in Wong vating application for coverage of rectilinear environ-
et al.’s work. The algorithm guarantees complete cov- ments is calibration of an automated assembly system
erage. It iteratively constructs the topological map in which planar linear motors operate on table-like sur-
associated to the slice decomposition of the environ- faces to transfer products through a factory.
ment using a finite state machine with three states –
boundary, normal, and travel. Fig. 17 shows its state In CCR (for contact-based coverage of rectilinear en-
transition diagram. The algorithm starts in the bound- vironments), the robot follows a cyclic path with re-
ary state, as it is assumed that the robot is initially tracing as shown in Fig. 11. At the same time, it iter-
located in a corner of the environment. This assump- atively constructs a cellular decomposition of the en-
tion is not a shortcoming as it is easy to program a vironment. An example rectilinear decomposition pro-
robot to look for a corner by following simple forward duced by CCR is shown in Fig. 18. In fact, the decom-
and wall following motions. In the boundary state, the position constructed by CCR can be seen as the case of
robot explores the current cell boundary. The aim of Morse decomposition where all the critical points are
the boundary exploration is to expose all cells neigh- degenerate, as this is the case in rectilinear environ-
boring the current border. Whenever the robot arrives ments.
at a landmark or at an end of the cell boundary, the
topological map is updated. When the boundary ex-
ploration has finished, the algorithm switches to the
travel state. In the travel state, the robot searches the
topological map for an uncovered cell and it is directed
to that cell. Then, the robot enters the normal state,
where it follows a zigzag pattern to cover the current
cell. Again, whenever a landmark is found the topo-
logical map is updated and the algorithm switches to
the boundary state. The algorithm finishes when there
are no more uncovered cells in the topological map.

Figure 18: CCR uses an exact cell decomposition for

Event occurred Start
New landmark reached rectilinear environments.

Normally, CCR follows the cyclic path. An event (and

Normal Boundary
hence a cell boundary) occurs whenever the robot is
prevented from successfully executing a full path cy-
cle. When such an event occurs, CCR chooses a new
Boundary
fully trajectory based only the robot’s environment and its
explored current position. The next trajectory is determined by
Arrived at
uncovered a list of rules that are designed to continue coverage in
Travel
cell all possible cases.
Exit
All
covered A proof of completeness for CCR is given by creating a
finite state machine (FSM) that describes all possible
Figure 17: State transition diagram of the topological events encountered by the robot, and demonstrating
coverage algorithm. that the FSM has no infinite loops and that it stops
only when coverage is complete.

11
6 Grid-based Methods triangles instead. The rationale behind the choice of
triangular cells is that they offer a higher resolution in
comparison to rectangular cells of similar size. How-
Grid-based methods use a representation of the en- ever, the resolution of the grid can also be augmented
vironment decomposed into a collection of uniform by using finer-grained squared cells. In mobile robotics,
grid cells. This grid representation was first proposed field for which the mentioned algorithm is intended,
by Moravec and Elfes (1985) to map an indoor envi- most mobile robots are not capable of making very fine
ronment using a sonar ring mounted on a mobile robot. movement adjustments, and hence there is no need for
In this representation, each grid cell has an associated ultra high resolution in coverage path planning. There-
value stating whether an obstacle is present or if it is fore, the extra effort devoted to implementing a trian-
rather free space. The value can be either binary or a gular grid seems not to be worthwhile.
probability (Elfes, 1987). Typically, each grid cell is a
square, but also different grid cell shapes can be used,
such as triangles. As grid representations only approx-
6.1 Grid-based Coverage using the
imate the shape of the target region and its obstacles,
Choset classified grid-based methods as approximate Wavefront Algorithm
cellular decompositions (Choset, 2001). As a result
of this approximate representation, most grid-based Zelinsky et al. (1993) presented the first grid-based
methods are “resolution-complete”, that is, their com- method for CPP. In their off-line method, they use
pleteness depends on the resolution of the grid map. a grid representation and apply a complete coverage
Fig. 19 shows an example grid map. path planning algorithm to the grid. The method re-
quires a start cell and a goal cell. A distance transform
that propagates a wave front from goal to start is used
to assign a specific number to each grid element. That
is, the algorithm first assigns a 0 to the goal and then
a 1 to all its surrounding cells. Then, all the unmarked
cells neighboring the marked 1 are labeled with a 2.
The process repeats incrementally until the start cell
is reached by the wavefront. Fig 20(a) illustrates this
procedure on an example environment.

Once the distance transform is calculated, a coverage

path can be found by starting on the start cell and se-
Figure 19: An example grid map. Grid cells with ob- lecting the neighboring cell with the highest label that
stacles present are shaded. is unvisited. If two or more unvisited neighbors share
the same label, one of them is selected randomly. This
It is easy to create a grid map, as it can be repre- process to find a coverage path is equivalent to using
sented as an array where each element contains occu- pseudo-gradient descent from the start point on the
pancy information associated with a cell. On the other numeric potential function constituted by the labeling,
hand, it is simple to mark covered areas in a grid map. that is, following the equipotential curves from top to
As a result, grid-based representations are the most bottom. Fig. 20(b) shows the generated coverage path
widely used for coverage algorithms. Nonetheless, grid for the example environment on Fig. 20(a). A unique
maps suffer from exponential growth of memory us- feature of this coverage algorithm is that a start and a
age because the resolution remains constant regardless goal point can be specified.
of the complexity of the environment (Thrun, 1998).
Also, they require accurate localization to maintain Shivashankar et al. (2011) introduced a generalization
the map’s coherency (Castellanos et al., 1997; Thrun, of the wavefront algorithm to unknown environments
2003). to achieve on-line coverage with a mobile robot.

For these reasons, grid-based coverage methods are

suited for indoor mobile robot operations, as the size 6.2 Grid-based Coverage using Span-
of the area to be covered is typically relatively small.
ning Trees
Usually, cells in a grid map are square in shape and
robot-sized. Oh et al. (2004) proposed a coverage al- Gabriely and Rimon (2002) proposed the Spiral-STC
gorithm that uses a grid map in which the cells are (Spanning Tree Coverage) algorithm, an on-line ap-

12
 proach for mobile robots which consists in subdividing
the workspace into a grid map and following a system-
atic spiral path. This systematic spiral path is gener-
ated by following a spanning tree of the partial grid
map that the robot incrementally constructs using its
onboard sensors. The robot is able to cover every grid
cell precisely once, and travel a complete coverage path.
They validate the proposal in simulation. The Spiral-
STC algorithm works as follows. Two different grid cell
sizes are used. Bigger cells (so called mega cells) are
divided in four smaller cells, which are the same size
as the robot. This is shown in Fig 21(a). To perform
coverage, the robot executes the following procedure.
Starting at the current cell, the robot chooses a new
S 8 7 7 7 7 7 7 7 7 7 8 9 10
travel direction by selecting the first new mega cell in
9 8 7 6 6 6 6 6 6 6 7 8 9 10
the free space in anti-clockwise direction. Then, a new
8 5 5 5 5 5 8 9 10
spanning-tree edge is grown from the current mega cell
7 4 4 4 9 9 9
to the new one. The algorithm is called recursively.
6 3 10 9 8 8
The recursion stops only when the current cell has no
6 5 2 7
new neighbors (a mega cell is considered old if at least
6 5 4 1 1 1 6 7

6 5 4 3 2 1 G 1 2 3 4 5 6 7
one of its four smaller cells is covered, it is consid-
6 5 4 3 2 1 1 1 2 3 4 5 6 7
ered new otherwise). As a result of this recursion, the
robot moves along one side of the spanning tree until
(a) Wavefront distance transform for the selec- it reaches the end of the tree. At that point, the robot
tion of the start position (S) goal position (G). turns around to traverse the other side of the tree. It is
worth noticing that, when coverage is completed, the
S 8 7 7 7 7 7 7 7 7 7 8 9 10 robot returns to the start cell, facilitating its collec-
9 8 7 6 6 6 6 6 6 6 7 8 9 10 tion and storage. On the other hand, STC never visits
8 5 5 5 5 5 8 9 10 any small cell twice and thus minimizes the coverage
7 4 4 4 9 9 9 time. Fig 21(b) shows an example of a coverage path
6 3 10 9 8 8 generated by the Spiral-STC algorithm.
6 5 2 7

6 5 4 1 1 1 An extension to the Spiral-STC is the Backtracking

6 7

6 5 4 3 2 1 G 1 2 3 4 5 Spiral Algorithm (BSA) (Gonzalez et al., 2005), which

6 7

6 5 4 3 2 1 1 1 2 3 4 5 6 7 is also an on-line approach intended for mobile robots.

As an advantage in regard to the Spiral-STC algo-
(b) Coverage path generated using the wave- rithm, they proposed an extension to cover not only
front distance transform with the selection of the
start position (S). unoccupied cells, but also the partially occupied ones.
This extension is based on the idea that the partially-
Figure 20: Coverage path planning using the wavefront occupied cells are part of the external ring of the spi-
algorithm for an example environment. ral path. These cells are covered by a wall-following
procedure. The proposed extension can be applied to
most grid-based coverage algorithms. Simulation ex-
periments validate the proposed algorithm.

Choi et al. (2009) proposed an on-line complete cov-

erage path planning solution based on the ideas intro-
duced by the Spiral-STC algorithm and the BSA algo-
rithm. They also use systematic spiral paths to achieve
coverage, based on active wall finding. Nonetheless,
they introduce a map coordinate assignment scheme
based on the history of sensor readings to improve the
time-to-completion by reducing the number of turns
on the generated path. The generated spiral paths are
then linked by an inverse distance transform they intro-

13
 duce. This proposal is validated in simulation and also
with real-world experiments conducted inside a room
with a mobile robot.

6.3 Neural Network-based Coverage on

Grid Maps

Luo et al. (2002) and, in a latter work, Yang and Luo

(2004) propose to use a neural network to achieve CPP
on-line targeted to a floor cleaning application. They
discretize a 2D space in a grid map where the diagonal
length of each grid cell is equal to the robot sweeping
radius, and then a neuron is associated to each and
every grid cell. Each neuron has connections to its
immediate 8 neighbors. These concepts are shown in
Fig. 22.

(a) Approximate cell decomposition in

mega cells and robot-sized cells.

Obstacle neuron Uncovered area neuron

Covered area neuron Robot

Figure 22: Schematic of the neural network used by

Luo, Yang and others to achieve coverage.

A shunting equation based on the membrane equation

by Hodgkin and Huxley (1952) determines the dynam-
ics of each neuron in the network. The activity land-
scape (i.e., the output value of all neurons at a given
instant) of the shunting model used attracts the robot
to unclean areas, while the robot is repulsed by already
cleaned areas and obstacles.

(b) Coverage path generated with the

The next position of the robot is determined by the cur-
Spiral-STC algorithm. rent position of the robot and the activity of the neu-
ron associated to its current position, without any prior
Figure 21: Coverage path planning using Spiral-STC knowledge about the environment. It is assumed that
algorithm. the current state of the robot (if it’s in a clean or dirty
area, or in front of an obstacle, and its location) can be
determined via sensory information. The state of the
robot is an input to the neural network. The model
used has 6 parameters that can be tuned in a wide
range of values at the neural network design phase,
and hence coverage is achieved without any learning
procedures. An advantage of this method is that it can
handle non-stationary environments (i.e., dynamically

14
changing obstacles). The proposed neural network ap- fold. On one hand, distance does not need to be taken
proach is validated in simulation. In (Luo and Yang, into account in the objective functions, because the
2008) further simulation results are presented as well as
distance from a given cell to its neighboring cells is
a method to perform mapping on-line simultaneously the same. On the other hand, assuming the hexagons
with coverage navigation. In this later work, they con-are small enough, visiting one cell guarantees cover-
sider a typical grid-based map and also a triangular age of two neighboring cells by the side-looking sensor,
mesh representation of the space, such as the one used minimizing the amount of partially covered cells. Al-
by Oh et al. (2004). though the proposed method is able to cover target ar-
eas with non-convex shapes, obstacles present amidst
An application of this neural network-based method the workspace are not considered. The efficacy of this
to an AUV covering a 2-D workspace in the seabed method is demonstrated in simulation and experimen-
is proposed in (Yan and Zhu, 2011). The proposal tally on an AUV conducting mine countermeasure op-
is validated in simulation. However, a 2-D underwa- erations.
ter workspace is rather unrealistic. Furthermore, dis-
cretization in a grid map of a vast environment such
as the seabed presents a tough challenge in terms of
computational burden. 7 Graph-based Coverage
Qiu et al. (2006) added a local path planning tech-
nique on top of the biologically inspired neural net- Xu (2011) presented coverage algorithms for environ-
work approach discussed above. In their approach, the ments that can be represented as a graph, such as a
next robot position is not determined immediately but street or road network. In particular, this work ad-
rather a local path planning occurs in a window com- dresses the following issues in the coverage problem.
prising a determined vicinity of the robot. By using First, it takes into account that the prior map infor-
this technique, they reduce the computational burden mation provided as a graph might be incomplete. Sec-
in comparison with the neural-network-only approach. ond, it accounts for environmental constraints in the
environment, such as restrictions in certain directions
In a similar approach, Guo and Balakrishnan in the graph (corresponding to a one-way street, for
(2006) present a neural network-based method to gen- example). Third, it provides strategies for on-line re-
erate continuous steering control for a robot to com- planning when changes in the graph are detected by
pletely cover a bounded region over a finite time. First, the robot’s sensors when performing coverage. Finally,
they discretize the space in a regularly spaced, disk- strategies for coverage using multiple robots are pro-
shaped grid. Then, a neural network based on the vided.
same biologically inspired shunting equation as in the
works discussed above is used to provide continuous Graph search algorithms are proposed to solve the cov-
steering to the robot. The algorithm works for car-like erage problems considered. Optimality is addressed by
robots which have non-holonomic motion constraints. assigning a cost to each edge in the graph and either
The approach is validated in simulation. looking for the optimal solution when deliberation time
allows or rather quickly finding an approximated solu-
tion when time constraints apply.

6.4 Hexagonal Grid Decomposition for

Robots Equipped with Side-looking
Sensors 8 3D Coverage

Paull et al. (2010, 2012) presented an on-line cover- Most coverage path planning methods, and in partic-
age method for robots equipped with side-looking sen- ular the methods reviewed so far in this article, as-
sors. Their target application is mine countermeasure sume that the environment can be modeled as a sim-
operations using an AUV equipped with a side-scan ple planar surface. This assumption is valid for floor
sonar. This coverage method continuously directs the cleaning, land mine detection, lawn mowing, etc. How-
vehicle’s heading using multi-objective optimization to ever, some surfaces in nature are 3-dimensional, and
maximize the information gain produced by the sen- 3-dimensional coverage path planning is required in-
sor measurements. The optimization procedure uses stead to cover these surfaces. This is the case of an
a grid decomposition composed of uniform hexagonal AUV covering the seabed (Hert et al., 1996) or a robot
cells. The advantage of using a hexagonal grid is two- spray-painting vehicle parts (Atkar et al., 2005b), for

15
instance. Next, we review several 3-dimensional cover- by moving along its boundary. After covering a given
age methods. It is worth noticing that, except the algo- diversion inlet, the robot exits it by resuming its path
rithm discussed in Subsec. 8.1, the methods discussed as if the diversion inlet did not exist. When the area to
below actually focus on coverage of a surface of lower be covered is not simply connected and contains islands
dimension than the robot’s workspace. Indeed, in 3- as well as inlets, the same basic procedures are used,
dimensional coverage, covering 2-dimensional surfaces but with minor modifications to ensure that the area
embedded in 3-dimensional space such as the bound- surrounding every island is covered. The robot is able
aries of automotive parts, the boundaries of buildings, to convert the part of the area around each island that
the ocean floor, rugged agricultural fields or the bound- would normally not be covered into an artificial inlet
aries of the in-water part of a ship hull are the main by remembering certain points along its path. Artificial
focus. This contrasts with the standard CPP problem, inlets are covered in the same way that real diversion
in which all the free space must be covered. inlets are. Fig. 23 illustrates this procedure. It is worth
noticing, however, that details on how to detect the
inlets used by the algorithm using sensor information
8.1 3D Coverage using a Planar Cover- are not provided.
age Algorithm in Successive Hori- The work of Hert et al. (1996) was extended later
zontal Planes by Lee et al. (2009) to cover only areas that are close
to the sea bottom surface. In this latter work, it is as-
Hert et al. (1996) presented a 3D coverage algo- sumed that the regions of interest in underwater envi-
rithm that is based on a planar 2-dimensional terrain- ronments are the ones close to the sea bottom. There-
covering algorithm (Lumelsky et al., 1990). Their tar- fore, aiming to make the robot navigate only in ar-
get application is an AUV imaging the sea bottom. eas close to the surface, artificial obstacles (artificial
Their solution applies to a 3D projectively planar en- islands) are introduced in the robot’s map of the envi-
vironment by applying the planar terrain-covering al- ronment. This way, the volume of water at a certain
gorithm in the successive horizontal planes laying at distance from the seafloor surface is discarded and a
different depths. The restriction to projectively planar more exploration of the sea bottom is achieved.
environments means that elements such as caves are
A theoretical proof of correctness of the algorithm is
not handled by this method. Their 2D terrain-covering
given in (Hert et al., 1996) and the extension proposed
algorithm uses a partial discretization of the space in
in (Lee et al., 2009) is validated in simulation.
where the space is divided in vertical slices of the same
width, but where the top and bottom of each slice can
have any shape. This discretization is classified as a
semi-approximate cellular decomposition according to
8.2 3D Cellular Decomposition
Choset’s taxonomy (Choset, 2001). A robot following
this algorithm may start at an arbitrary point in the en- Atkar et al. (2001) considered the problem of trajec-
vironment and will zigzag along parallel straight lines tory generation for spray-painting robots. In their ini-
(grid lines) to cover the given area. Portions of the tial work, they proposed an on-line, 3-dimensional CPP
3
area that either would not be covered or would be cov- method for closed, orientable surfaces embedded in R .
ered twice using the zigzag procedure are detected by The method extended the ideas of Morse decomposi-
the robot and covered using the same procedure; that tion to non-planar spaces. However, obstacles on the
is, the procedure is applied recursively. These smaller target surface are not considered in this work. Address-
areas, called inlets, are covered as soon as they are de- ing their spray-painting target application, the method
tected and inlets within inlets are treated in the same does not plan a coverage path on the target surface, but
way. Hence, the inlets are covered in a depth-first or- the coverage path is rather planned in an offset surface
der. By requiring the robot to remember the points at from which the end effector will spray the target sur-
which it enters and exits every inlet it covers (which face. That is, the path is planned on a “virtual” surface
define the inlet doorways), the algorithm assures that that wraps the target object at a fixed offset distance.
each inlet is covered only once. The coverage path is generated by intersecting a slice
plane with the offset surface at equally spaced inter-
When entering or exiting a certain type of inlet, the vals. At each interval, the intersection of the slice plane
robot may cover the same area more than once, or miss with the offset surface forms a closed one-dimensional
some area at the inlet. Those inlets are called diversion loop around the object. The robot traces this loop
inlets, and special procedures are necessary for covering and moves to the next slice plane, and iteratively re-
them effectively. The robot enters a diversion inlet peats the process. If the target surface is convex, the

16
 described process will achieve complete coverage. How-
ever, if the surface is non-convex and includes elements
such as a bifurcation, the planner will use the critical
points occurring in such shape changes to divide the
surface in cells that will be covered individually. As
in the on-line Morse decomposition for planar spaces,
a Reeb graph is used to encode the topology of the
target surface. When all edges in the graph are cov-
ered, the coverage task is successfully completed. The
method was validated in simulation using target sur-
faces constituted by polyhedra. It is worth noting that
this method requires a robot equipped with a 2D om-
nidirectional range sensor in order to detect the critical
points.
(a)
In later work (Atkar et al., 2003, 2005a,b), they pre-
sented an off-line CPP method specifically targeted for
spray-painting of automotive parts. They term such
surfaces pseudo-extruded surfaces. In contrast with
their initial work, the problem tackled here is the uni-
form coverage problem, where the target surface not
only needs to be completely covered but also the re-
sulting paint deposition must meet certain uniformity
requirements. To achieve uniform coverage, their pro-
(b) posed method takes a CAD model of the target auto-
motive parts as input and segments their surface into
topologically simple cells of similar curvature. Then,
individual, optimal paint-deposition coverage paths in
each cell are determined. Simulations as well as exper-
iments with real robots validate their proposal.

8.3 3D Urban Structure Coverage

(c)
Cheng et al. (2008) presented an off-line approach
Figure 23: The path a robot R follows in a non-simply for planning time-optimal trajectories for unmanned
connected environment when applying the algorithm aerial vehicles (UAVs) performing 3D urban struc-
proposed in (Hert et al., 1996). First (a), the robot ture coverage. First, they simplify the structures to
detects an inlet at d1 and starts to cover it following be covered, namely buildings, into hemispheres and
a depth-first order. A second inlet is detected at d2 , cylinders. Then, trajectories are planned to cover
and the robot starts covering it likewise. The robot these simpler surfaces. Their proposal is validated
continues to cover the rest of the inlets until it goes in hardware-in-the-loop simulations using a fixed-wing
back to d1 (b). Here, the robot continues to cover the aircraft. Fig. 24 illustrates this method.
main region until it detects an inlet at d3 . This inlet
corresponds to an island, and hence the robot continues
to circumnavigate it completely (c). Then, the robot 8.4 Coverage of Bathymetric Surfaces
will eventually pass through d3 again and there it will
resume the covering of the main area.
Bathymetric maps are elevation maps of the ocean
floor. Such maps are used for planning of ocean sur-
vey missions for AUVs. A typical survey consists of
a lawnmower-like pattern which follows the elevation
profile of the terrain, imaging the bottom from an over-
head point of view with some sensor. However, rugged,
high-relief terrain cannot be properly imaged from such

17
 erosion cost and the skipped area. The method is
validated on real-world elevation maps of agricultural
fields.

8.6 Random Sampling-based Coverage

of Complex 3D Structures
(a) Simplified model of an urban envi-
ronment.
In confined 3-dimensional areas where a robot cannot
go through the spaces between component structures,
or where occluded areas are only visible from a reduced
set of viewpoints, modular approaches such as those
described above are unsuitable. To handle this fam-
ily of problems, global path planning strategies, uti-
lizing sampling-based planning (Danner and Kavraki,
2000) have been applied to find feasible, collision-free,
paths through confined areas and obtain full coverage
(b) Illustration of a coverage path. of a 2-dimensional target structure. Their approach
is based on the art gallery problem. Building upon
Figure 24: Coverage scheme presented in (Cheng et al., a similar idea, Englot and Hover (2012) introduce an
2008). off-line, sampling-based coverage algorithm to achieve
complete sensor coverage of complex, 3-dimensional
structures. Their target application is autonomous
point of view since the imaging angle is too large on ver- ship hull inspection, in which the robot must cover
tical protrusions. In contrast, an imaging angle close the in-water part of the hull surface using a sensor
to the surface normal is desired. To address this is- such as a sonar. The sensory data collected in situ
sue, Galceran and Carreras (2013) presented a CPP is later used to construct an accurate 3-dimensional
method that plans a coverage path on a bathymetric model where anomalies in the hull surface can be
map. The method determines regions that cannot be searched for. They consider the planning problem with
properly imaged using a traditional survey according to a fully-actuated, six degree-of-freedom hovering AUV
the terrain’s gradient. Then, on each identified region, that uses a bathymetry sonar to inspect the structures
it plans a 3D coverage path that follows the horizon- in the ship hull. The method requires a discrete model
tal contours of the surface, in a similar fashion as the of the structure to be inspected provided in the form
method discussed in 8.2. On the remaining, effectively of a closed triangular mesh. The planning is performed
planar regions, it uses a standard lawnmower-like path in two steps. First, a graph of feasible paths for the
for coverage. As a result, the entire target bathymetric robot is constructed using random sampling until the
surface is covered and a fair imaging angle is provided set of nodes of the graph allows complete coverage of
throughout the coverage path. The method is vali- the structure. This is equivalent to solving a variant of
dated on a real-world bathymetric map comprising a the art gallery problem. Then, a minimum-cost closed
large underwater volcanic area at 350 m. depth. walk along the graph which fully covers the structure
is searched for in the graph. This second step involves
solving a variant of the traveling salesman problem.
8.5 3D Coverage for Arable Farming By favoring a random sampling method, they reduce
the computational burden necessary to face the high-
Jin and Tang (2011) presented coverage algorithms for dimensionality of the problem. It should be noted that
arable fields represented as elevation maps. Previous the generated paths cover cluttered spaces where com-
work in coverage for agricultural fields dealt with pla- plex structures such as shafts and rudders are present.
nar terrain, but many fields present 3-dimensional fea- The approach is validated using sensor imagery of real
tures that have an impact on coverage performance. vessels and with experiments conducted at sea. Fur-
Addressing this issue, this work provides coverage al- thermore, a method for smoothing and shortening the
gorithms based on a seed curve that is incrementally paths initially generated is provided. This procedure
offset on both sides to generate a coverage path. The can be incrementally applied while computation time
method optimizes the seed curve selection by taking allows. Fig. 25 shows examples of planned inspection
into account its associated number of turns, the soil paths for a ship hull with and without smoothing.

18
As discussed above, the approach by Englot and Hover
(2012) first generates a set of view configurations that
completely cover the target surface (by solving an in-
stance of the art gallery problem) and then finds a
path that connects them (by solving an instance of the
traveling salesman problem). This might pose a prob-
lem for robots with differential constraints, given that a
path connecting to a given view configuration might be
infeasible. To tackle this problem, Papadopoulos et al.
(2013) presented a random sampling-based algorithm
that incrementally explores the robot’s configuration
space while constructing an inspection path until all
points on the target surface are guaranteed to be cov-
ered. In contrast to the aforementioned approaches,
which first plan a set of view configurations that cover
the target environment, their algorithm generates view
configurations and at the same time validates the fea-
sibility of the path connecting them. Only view con-
figurations reached by feasible paths are incorporated
in the final coverage path. Additionally, this method
is probabilistically optimal with respect to a given cost
function. The method is validated in simulation.

Given the wide variety of structures that are able to

handle, these approaches constitute the state of the (a) Feasible tour for full coverage of a ship running gear. The
art in coverage of complex 3-dimensional structures. tour is 176 m in length and contains 121 nodes.

9 Optimal Coverage

Work addressing the optimality of the planned cov-

erage paths, in terms such as path length and time to
completion, appears in the CPP literature. Notice that
it is only possible to find an optimal solution for an a
priori known environment, or partially known at least,
since an antagonistic example can always be found for a
sensor-based approach. Hence optimal coverage meth-
ods are classified as off-line methods.
(b) Tour of (a) after applying the refinement procedure. The
Huang (2001) presented an optimal line-sweep based shortened tour is 102 m in length and contains 97 configurations.
method for cellular decomposition algorithms in pla-
nar spaces. This approach produces an optimal length Figure 25: Full-coverage inspection paths obtained
coverage path by allowing different sweep directions with the method of Englot and Hover (2012).
in the lawnmower paths used to cover each cell. The
main idea is to minimize the number of turns in the
path, as each turn typically implies the added cost of
the robot decelerating and accelerating again after the
turn. This is achieved by allowing a different sweep
direction in each cell. The number of turns is mini-
mized by sweeping each cell in parallel to its maximal
altitude axis. That is, the method intends to maximize
the length of the laps in the zigzag pattern in order to
minimize the number of turns. However, this approach
does not take into account the cost of traveling from

19
cell to cell. The method is validated in simulation. forming coverage has been only addressed in few work.

Jimenez et al. (2007) proposed to use a genetic algo- Acar and Choset (2002b) propose to plan the paths of
rithm to achieve optimal coverage. In this proposal, their sensor-based Morse decomposition approach by
workspace and obstacles are assumed to be polygonal relying on the boundaries of each cell, hence minimiz-
and known beforehand. Then, the free space is divided ing the dead-reckoning error.
in subregions using the trapezoidal cellular decompo-
sition method (Latombe, 1991; Choset et al., 2005). Tully et al. (2010) used a fleet of three robots, each
Finally, a genetic algorithm is used to plan an optimal one of them equipped with a red ball (easily detectable
path that covers all the subregions. This proposal is using standard computer vision techniques) to follow a
tested in simulation. strategic path in formation to minimize the localization
error. The mentioned robot fleet is shown in Fig. 26.
Mannadiar and Rekleitis (2010) proposed an algorithm The path consists of a series of steps, or leaps. In
based on the Boustrophedon cellular decomposition each leap, two robots are static and serve the third one
that achieves complete coverage of known spaces while as beacons, and this later one advances. The robots
minimizing the path of the robot. The algorithm en- successively interchange their roles. Real experiments
codes the cells to be covered as edges of the Reeb graph. show a minimization of the localization error, report-
Then, the optimal solution to the Chinese Postman ing one of the most successful 2-dimensional coverage
Problem is used to calculate an Euler tour, which guar- experiments to date. However, obstacles are not con-
antees complete coverage of the available free space sidered in this work.
while minimizing the coverage path length.

Xu et al. (2011) presented an application of the

optimal Morse-based boustrophedon decomposition
method (Mannadiar and Rekleitis, 2010) for UAVs.
First, they generate an optimal exhaustive walk
through the adjacency graph of the cell decomposition
of the terrain. Then, they cover each cell with zigzag
motions taking into account the kinematic constraints
of the vehicle, as the fixed-wing UAV they use has non-
holonomic constraints. Extensive experimental results
in simulation validate the presented system, along with
data from over 100 kilometers of coverage flights using Figure 26: Three robots used for experimental evalua-
a real fixed-wing aircraft. tion of the leap-frog localization and coverage strategy.

Kim (2012) propose an active SLAM approach to cov-

10 Coverage under Uncertainty erage path planning for ship hull inspection in a 3D sce-
nario. The proposed algorithm drives the robot along
a pre-planned coverage trajectory on the ship hull, and
In many scenarios, the lack of a global localization sys- during trajectory execution the robot selects candi-
tem such as GPS makes the robot accumulate drift, date locations that, once revisited, can help reduce the
and hence a growing uncertainty about its pose. Al- robot’s pose uncertainty. The algorithm chooses to re-
though the topological representations such as the ad- visit a candidate location once the pose uncertainty
jacency graph are tolerant to localization error, the surpasses a user-provided threshold, and otherwise fol-
performance of coverage algorithms, even if using such lows the pre-planned path.
representations, is still affected (Mazo and et al., 2004;
Choset, 2001). This is because the amount of cover- Bretl and Hutchinson (2013) suggest a way to plan
age within a cell depends on the direction of the zigzag modified coverage paths for a mobile robot whose po-
pattern. sition and velocity are subject to bounded error. As-
suming a worst-case model of uncertainty they are able
Recent advances in simultaneous localization and map- to guarantee complete coverage. This guarantee comes
ping (SLAM) have greatly improved robot localization. at the cost of a longer path, since paths generated by
SLAM uses statistical techniques to correct the robot’s their algorithm include retracing. Nonetheless, this
pose (position and orientation) estimation. However, work provides the first guaranteed coverage results for
the problem of correcting the robot’s pose while per- the case of bounded position and velocity error.

20
In the context of marine robotics, Galceran et al. (2013) nar cellular decomposition as the Boustrophedon sin-
presented a coverage path planning technique for vast, gle robot coverage algorithm, but provide extensions to
open sea areas which minimizes the robot’s position un- handle how robots cover a single cell, and how robots
certainty along the path. This technique is especially are allocated among cells. Their solution takes into ac-
targeted for bathymetric mapping applications and re- count communication restrictions among the members
spects application constraints such as the desire to sur- of the team. To achieve coverage in line-of-sight-only
vey in parallel tracks and to avoid turns in the target communications, the robots take two roles: some mem-
area to maximize sonar measurements quality. The bers, called explorers, cover the boundaries of the cur-
method uses the saliency on an a priori map to predict rent target cell, while the other members, called cov-
how the terrain will affect the robot’s belief at every erers, perform simple back-and-forth motions to cover
point on the target area. Based on this magnitude, an the remainder of the cell, as shown in Fig. 27. For
algorithm provided in this work computes the order in task/cell allocation among the robots, a greedy auction
which to trace parallel tracks to cover the target area mechanism is used. Experimental results from differ-
minimizing the overall uncertainty along the path. A ent simulated and real environments are provided to
particle filter keeps track of the robot’s position uncer- illustrate their proposed approach.
tainty during the planning process and, in order to find
useful loop- closures for mapping, crossing tracks that
visit salient locations are added when the uncertainty
surpasses a user-provided threshold. The method is
tested on real-world datasets and results show that it
offers benefits over a standard lawnmower-type path.

11 Multi-robot Methods

There are advantages in using multiple robots in a CPP

task. Using multiple robots clearly decreases the time
Figure 27: Explorer/coverer approach, where two ex-
to complete the task due to workload division. But
plorer robots outline the top and bottom boundaries
a team of robots can go further, for example using
while the remaining robots (coverers) execute simple
each other as beacons to minimize localization error.
back-and-forth coverage of the target cell.
Additionally, using multiple robots improves robust-
ness, as failure of some members of the robot team
can be compensated by others. There exist a number
of multi-robot CPP proposals in the literature. Most
approaches extend single-robot ideas presented above
to multiple robots by using a strategy to divide the
workload. In this section, we discuss multi-robot cover- 11.2 Multi-robot Contact Sensor-based
age methods based on the single-robot boustrophedon Coverage of Rectilinear Environ-
decomposition, on spanning trees, on the biologically ments
inspired neural-network approach and on the graph-
based approach. Nonetheless, there are genuine multi-
robot approaches which are not based in any particular
A strategy for covering rectilinear environments using
single-robot algorithm, which we also discuss below.
robots equipped only with contact sensors was pro-
posed by Butler et al. (2000). The strategy is based
on CCR , discussed in Sec. 5, and is called DCR . DCR
11.1 Multi-robot Boustrophedon De- decouples cooperation and coverage by executing CCR
composition individually on each robot and adding a higher-level
coordinator, termed the overseer, which is in charge
Rekleitis et al. (2009) presented a collection of algo- of controlling the cooperation among the robots. The
rithms for the complete coverage path planning prob- overseer operates in such a way that coverage directed
lem using a team of mobile robots on an unknown en- by CCR on each robot can continue without CCR be-
vironment (on-line). Their algorithms aim to minimize ing aware that cooperation is occurring. A proof of
repeated coverage. The algorithms use the same pla- completeness for DCR is provided in this work.

21
11.3 Multi-robot Spanning Tree Cover- a 2-dimensional boundary coverage algorithm for mul-
age tiple robots. It is worth mentioning that, as in the ma-
jority of 3-dimensional coverage methods discussed in
Sec. 8, this work focuses on covering only the boundary
The STC method was generalized to multi-robot teams
of the target environment. In the multi-robot bound-
by Hazon and Kaminka (2005) using a heuristic ap-
ary coverage problem, introduced in this work, a team
proach. They termed their algorithm MSTC. Zheng
of robots must inspect all points on the boundary of
et al. (2005) presented an improved (with respect to
the 2-dimensional target environment. A motivating
MSTC) method to find a coverage tree for a team of
application of the multi-robot boundary coverage prob-
robots to cover known terrain with a team of robots. In
lem is inspection of separated blade surfaces inside a
this work they also provide an upper bound on the per-
turbine. The boundary coverage problem is converted
formance of a multi-robot coverage algorithm on known
into an equivalent graph representation where a heuris-
terrain, guaranteeing a performance of at most eight
tic search is used to plan the inspection routes of every
times the optimal cost. Their reported experimental
robot. The planned routes provide complete coverage
results show their method to perform significantly bet-
of the boundary while balancing inspection load among
ter than MSTC. Agmon et al. (2006) propose a span-
the robots. The algorithm is validated in simulations.
ning tree construction algorithm that provides efficient
paths in terms of distance. The spanning tree con-
struction algorithm can be used as base for MSTC.
An extension of MSTC to terrain with non-uniform
11.6 Bio-inspired Multi-robot Cover-
traversability (that is, terrain where traversing certain age
areas is costlier than others) was presented by Zheng
and Koenig (2007). Hazon et al. (2006) presented an Several muli-robot coverage path planning proposals
on-line, robust version of MSTC. They show analyti- have been presented which are inspired by behaviors
cally that the algorithm is robust, guaranteeing cover- found in nature. Many of them are inspired by ant
age as log as a single robot is able to move. Empirical behavior, using evaporating traces to achieve an emer-
results validating the algorithm are reported. gent coverage behavior (Wagner et al., 1999, 2008;
Menezes et al., 2007). In (Batalin and Sukhatme, 2002)
A more recent off-line spanning tree-based multi-robot two algorithms are presented which are based on the
coverage method presented by Fazli et al. (2010) deals premise that to achieve coverage the team of robots
with the case where the robots have a limited visibility must “spread out” over the environment. The authors
range. This approach is shown to be complete and note that “this premise is loosely inspired by the diffu-
robust with respect to robot failure. sive motion of fluid particles”. Using these algorithms
robots perform obstacle avoidance and at the same
time are mutually repelled by each other within their
11.4 Multi-robot Neural-network- sensor range. These bio-inspired works are validated
based Coverage in simulation, but their practical application has been
very limited up to date.
Luo and Yang (2002) presented a straightforward adap-
tation of the biologically inspired neural network ap-
proach for coverage tasks to multi-robot scenarios
11.7 Multi-robot Coverage for Aerial
where the robots see each other as moving obstacles. Robotics
In a later work (Luo et al., 2003), an extension was pro-
vided to avoid deadlock situations between the robots. A considerable body of research has addressed multi-
Their approach is validated in simulation. robot coverage path planning for fleets of aerial robots,
taking into account the particulars of this domain. No-
tice that in the works discussed below it is assumed
11.5 Multi-robot Graph-based and that the vehicles fly at a safe altitude, and as a result
Boundary Coverage obstacles are not considered.

Ahmadzadeh et al. (2006) proposed a coverage algo-

Extensions of the graph-based techniques discussed in rithm for surveillance using a fleet of UAVs. Their
Sec. 7 for coverage using multiple robots were provided proposal takes into account the limited maneuverabil-
by Xu (2011). In a previous multi-robot graph-based ity of the aerial platforms and visibility constraints on
coverage approach, Easton and Burdick (2005) discuss the body-fixed cameras imposed by the application at

22
hand. The problem is posed using the integer pro- erage patterns, such as spiral patterns, that can sim-
gramming (IP) formalism, which provides a convenient plify the path following to vehicles with motion con-
representation for the aforementioned constraints. The straints.
solution of the IP problem instance produces a control
policy for the UAV fleet to accomplish the surveillance However, the Morse-based cellular decomposition
task operating within the constraint limits. The effi- method cannot handle rectilinear environments, and
cacy of this approach is validated by simulation and the cyclic rectangular paths used to detect all the crit-
experimental results. ical points include retracing, which makes them longer
than a standard zigzag path. This limitations are over-
Maza and Ollero (2007) proposed a terrain coverage come by the landmark-based topological coverage ap-
strategy using a heterogeneous fleet of UAVs. First, proach. This method uses a cellular decomposition
their method generates a polygonal partition of the tar- based on natural landmarks of the environment which
get area. The partition takes into account the capabili- determine the cell boundaries. An algorithm is given
ties of each individual vehicle, such as flight endurance to perform coverage on-line on unknown environments
and range. Each polygon in the partition is assigned using this technique.
to an UAV which will cover it using a zig-zag pattern.
Each vehicle plans its zig-zag pattern according to the For the particular case of robots with only contact sen-
geometric characteristics of its assigned polygonal area sors (i.e., with no range sensing capabilities) operating
to determine a sweep direction that minimizes the num- in rectilinear environments, the CCR algorithm guar-
ber of turns. An important consideration in this work antees complete on-line coverage.
is low complexity of the algorithms used, seeking oper-
ation in near-real time. The proposed method is vali- Grid-based methods such as the wavefront algorithm,
dated in simulation. the Spiral-STC algorithm and its derivatives, and the
described neural-network-based and hexagonal decom-
Targeting remote sensing in agriculture, Barrientos position approaches, provide complete coverage on a
et al. (2011) presented an approach to area coverage discretized representation of the target environment.
using fleets of mini aerial robots. Regarding multi- However, the grid representation of the environment
robot coverage, they first present a task scheduler to used is highly sensitive to localization error and incurs
partition the global target area into k non-overlapping an exponential memory consumption. On the other
subtasks for the k UAVs. In contrast with the previous hand, it is easy to create and operate with a grid map.
work, this partition procedure is based on a negotia- It is worth noticing, as a unique capability among the
tion process in which each robot claims covering as reviewed methods, that the discussed neural network-
much area as possible, rather than on geometric con- based methods are able to handle environments with
siderations. Second, the wavefront algorithm discussed moving obstacles.
in 6.1 is used to cover each subarea.
Some methods aimed to cover 3-dimensional environ-
ments have been reviewed. Hert’s algorithm can com-
12 Conclusion pletely cover projectively planar 3-dimensional envi-
ronments. However, details on how to detect the in-
lets used by the algorithm using sensor data are not
In this paper, we have seen that the coverage path plan- provided, making it difficult to implement. Modu-
ning problem has been addressed using many differ- lar approaches, such as the coverage methods targeted
ent approaches. For planar spaces, the trapezoidal de- for spray-painting tasks proposed by Atkar et al. or
composition guarantees complete coverage for a known the simplified model of a urban environment used by
polygonal environment. An improvement to the trape- Cheng et al. can achieve complete coverage of certain
zoidal decomposition is the “classical” boustrophedon 3-dimensional environments. The method for cover-
decomposition, which generates shorter complete cov- age of bathymetric surfaces by Galceran et al. and
erage paths for the same class of environments. The the coverage algorithm for arable farming by Jin et al.
Morse-based cellular decomposition provides complete provide coverage of 3-dimensional environments taking
coverage paths for environments whose obstacle bound- into account application-specific constraints. However,
aries are differentiable. A method to detect the critical in confined 3-dimensional areas where a robot cannot
points that determine the cell boundaries using range go through the spaces between component structures,
sensor information allows to perform Morse-based cel- or occluded areas only visible from a reduced set of
lular decomposition coverage on-line. Furthermore, viewpoints, these modular approaches do not suffice.
Morse decomposition allows generation of different cov- To overcome this limitation, Englot et al. introduced a

23
sampling-based coverage algorithm to achieve complete
sensor coverage of complex, 3-dimensional structures.
The paths generated using this method are able to
cover cluttered spaces where complex structures such
as shafts and rudders are present. The approach is
validated using triangular mesh models constructed us-
ing sensor imagery of real-world vessels. Also building
upon the idea of sampling-based coverage, Papadopou-
los et al. presented an algorithm that generates cov-
erage paths for complex 3-dimensional structures suit-
able for vehicles with differential constraints. Further-
more, their algorithm is proven asymptotically optimal
with respect to a given cost function. This approaches
constitute the state of the art in coverage of complex
3-dimensional structures.

We have discussed several approaches to generate op-

timal coverage paths in planar spaces and to reduce
localization error while performing coverage.

Finally, we have reviewed some multi-robot coverage

methods in which time to completion is reduced by di-
viding the workload among the individual robot team
members, besides providing increased robustness guar-
antees.

The features of the most relevant CPP methods re-

viewed in this article are summarized in Table 1. For
each method (rows), the table underlines (columns
from left to right) its category, its approach, its main
bibliographical reference, whether it can be used on-
line or not, the kind of environments it can handle and
some remarks.

Probabilistic sampling-based algorithms have revolu-

tionized the state of the art in path planning in the re-
cent years, and they have proven to be extremely pow-
erful as demonstrated in the work by Englot et al. on
ship hull inspection. Therefore, exploiting these tech-
niques opens the door to developing algorithms able
to realize coverage tasks of unprecedented complexity.
On the other hand, in real-world applications, a robot
often does not have perfect knowledge about its lo-
cation. In this situation, incorporating uncertainty in
future location estimates in the planning phase can sig-
nificantly improve motion performance. Although sev-
eral research works have explored taking uncertainty
into account in path planning problems, few attention
has been given to incorporating uncertainty in cover-
age path planning methods. Hence, this remains as an
open issue for further research.

24
 Survey summary
On/Off- Environments
Category Approach Reference(s) Remarks
line Handled
Lays the concept of using events to de-
Trapezoidal De- (Choset et al.,
Off-line Polygonal termine cell divisions, a concept a num-
composition 2005)
Classical Exact Cell ber of other approaches are based upon.
Decomposition Generates less cells and hence shorter
Boustrophedon De- (Choset and
Off-line Polygonal paths than the trapezoidal decomposi-
composition Pignon, 1997)
tion.
Polygonal and
Morse Decomposi- Allows for generation of different de-
differentiable
tion & Cycle Algo- (Acar et al., 2002) On-line composition and coverage path pat-
boundaries (non-
Morse-based Cell rithm terns.
rectilinear)
Decomposition
Polygonal and
Morse Decomposi- differentiable Avoids generation unnecessary zigzag
(Acar et al., 2006) On-line
tion + GVD boundaries (non- paths in narrow environments.
rectilinear)
Natural Landmark- Landmark-based
(Wong and Mac- Generic planar ob- Handles a large variety of environments
based Topological Coverage Algo- On-line
Donald, 2003) stacles (including rectilinear environments).
25

Coverage rithm
Rectilinear decom-
Contact Sensor- (Butler et al., Targeted for robots equipped only with
position (CCR al- On-line Rectilinear
based Coverage 1999) contact sensors.
gorithm)
Wavefront Algo- (Zelinsky et al.,
Off-line Grid-discretized Simple, easy to implement algorithm.
rithm 1993)
Spiral-STC Algo- (Gabriely and Ri- Minimizes repeated coverage by visiting
On-line Grid-discretized
Grid-based Cover- rithm mon, 2002) each grid cell only once.
age (Luo et al., 2002;
Yang and Luo,
Neural Network On-line Grid-discretized Handles dynamic obstacles.
2004; Luo and
Yang, 2008)
Maximizes information gain along the
Hexagonal Grid (Paull et al., 2012) On-line Grid-discretized
path.
Applies to environments that can be
Various graph Environmental con-
Graph Coverage (Xu, 2011) On-line represented as a graph, such as a street
search algorithms straints
or road network.
 Planar terrain cov-
Theoretically proven, however no de-
ering algorithm ap- Projectively planar
(Hert et al., 1996) On-line tails on how to detect the inlets used
plied at successive (2.5D)
by the algorithm are provided.
depths

Closed, orientable Theoretically proven. Demonstrated in

3D cellular decom-
(Atkar et al., 2001) On-line surfaces embedded simulation for simple 3D surfaces (poly-
position
in R3 hedra).
3-dimensional Cov- Hierarchical seg-
Car-like parts Specifically targeted for coverage of au-
erage mentation of
(Atkar et al., 2009) Off-line (pseudo-extruded tomotive parts. Generates paths which
pseudo-extruded
surfaces) optimize paint deposition uniformity.
surfaces
Urban environ-
Coverage path gen-
(Cheng et al., ments simplified as Suitable for covering urban structures
eration on simpli- On-line
2008) hemispheres and with sufficient clearance between them.
fied 3D surfaces
cylinders
26

Coverage of Bathy- (Galceran and Car- Bathymetric (eleva- Provides fair imaging angles on rugged
Off-line
metric Surfaces reras, 2013) tion) maps terrain.
Coverage for (Jin and Tang,
Off-line Elevation maps Minimizes application-specific costs.
Arable Farming 2011)
Allows for coverage of complex 3-
Random sampling- (Englot and Hover, Complex 3D struc-
Off-line dimensional structures such as a ship
based 2012) tures
propeller.
Random sampling-
(Papadopoulos Complex 3D struc- Can handle differential constraints and
based with differen- Off-line
et al., 2013) tures probabilistically guarantees optimality.
tial constraints
Cell decomposition
Takes into account “cell height” to se-
with variable sweep (Huang, 2001) Off-line Polygonal
lect the optimal sweep direction.
direction
Trapezoidal decom-
(Jimenez et al., A genetic algorithm quickly finds a spe-
Optimal Coverage position + genetic Off-line Polygonal
2007) cific coverage paths among the cells.
algorithm
 Morse decompo- Polygonal and
sition + optimal (Mannadiar and differentiable Finds an optimal walk through the ad-
On-line
adjacency graph Rekleitis, 2010) boundaries (non- jacency graph.
traversal rectilinear)
Polygonal and
Exploiting critical (Acar and Choset, differentiable Efficiently increases actual percent cov-
On-line
points 2002b) boundaries (non- erage achieved.
rectilinear)
Coverage under Decides when to revisit a salient feature
Uncertainty Active SLAM (Kim, 2012) On-line Ship hull when executing coverage to reduce un-
certainty.
Obstacles not con- Robots in a team use each other as bea-
Leap-frog strategy (Tully et al., 2010) On-line
sidered cons alternatively.
Modified boustro- (Bretl and Guarantees complete coverage under
Off-line Planar
phedon paths Hutchinson, 2013) bounded position and velocity error.
Low uncertainty Uses saliency to determine parallel
(Galceran et al.,
CPP for marine Off-line Marine track order and key salient points to re-
2013)
surveys visit.
Polygonal and
Boustrophedon- (Rekleitis et al., differentiable Extension of Morse decomposition to
On-line
27

based 2009) boundaries (non- multi-robot teams.

rectilinear)
Contact sensor- (Butler et al., Extension of CCR using a decoupled
On-line Rectilinear
based 2000) high-level coordinator.
Multi-robot Cover- Extension of Spiral-STC to multi-robot
age Spiral-STC-based (Zheng et al., 2005) Off-line Grid-discretized
teams.
(Hazon et al., On-line extension of Spiral-STC to
Spiral-STC-based On-line Grid-discretized
2006) multi-robot teams.
Neural-network- Robots see each other as moving obsta-
(Luo et al., 2003) On-line Grid-discretized
based cles.
(Easton and Bur- Focused on coverage of obstacle bound-
Boundary coverage Off-line 2D
dick, 2005) aries.
(Wagner et al., Validated in simulation, but of limited
Bio-inspired On-line 2D
2008) and others practical application.
(Ahmadzadeh Account for limited maneuverability
Aerial (obstacle-
Aerial et al., 2006) and Off-line and for load balancing in heterogeneous
free)
others teams.
Table 1: Survey summary
References Arkin, E. M., Fekete, S. P., and Mitchell, J. S. (2000).
Approximation algorithms for lawn mowing and
Acar, E. and Choset, H. (2002a). Sensor-based cov- milling. Computational Geometry, 17(12):25 – 50.
erage of unknown environments: Incremental con-
struction of morse decompositions. International Arkin, E. M. and Hassin, R. (1994). Approximation al-
Journal of Robotics Research, 21(4):345–366. gorithms for the geometric covering salesman prob-
lem. Discrete Applied Mathematics, 55(3):197–218.
Acar, E., Choset, H., and Atkar, P. (2001). Complete
sensor-based coverage with extended-range detec- Atkar, P., Choset, H., and Rizzi, A. (2003). Towards
tors: a hierarchical decomposition in terms of critical optimal coverage of 2-dimensional surfaces embed-
points and voronoi diagrams. In Intelligent Robots ded in ir3: choice of start curve. In Intelligent Robots
and Systems, 2001. Proceedings. 2001 IEEE/RSJ In- and Systems, 2003. (IROS 2003). Proceedings. 2003
ternational Conference on, volume 3, pages 1305 – IEEE/RSJ International Conference on, volume 4,
1311 vol.3. pages 3581 – 3587 vol.3.

Acar, E. U. and Choset, H. (2000). Critical point sens- Atkar, P., Conner, D., Greenfield, A., Choset, H., and
ing in unknown environments. In Proceedings of the Rizzi, A. (2009). Hierarchical segmentation of piece-
2000 IEEE International Conference on Robotics & wise pseudoextruded surfaces for uniform coverage.
Automation. Automation Science and Engineering, IEEE Trans-
actions on, 6(1):107 –120.
Acar, E. U. and Choset, H. (2001). Robust sensor-
based coverage of unstructured environments. In Atkar, P., Greenfield, A., Conner, D., Choset, H., and
Proc. IEEE/RSJ International Intelligent Robots Rizzi, A. (2005a). Hierarchical segmentation of sur-
and Systems Conference, volume 1, pages 61–68. faces embedded in r3 for auto-body painting. In
Robotics and Automation, 2005. ICRA 2005. Pro-
Acar, E. U. and Choset, H. (2002b). Exploiting critical ceedings of the 2005 IEEE International Conference
points to reduce positioning error for sensor-based on, pages 572 – 577.
navigation. In Proc. IEEE Int. Conf. Robotics and
Automation ICRA 2002, volume 4, pages 3831–3837. Atkar, P., Greenfield, A. L., Conner, D. C., Choset, H.,
and Rizzi, A. (2005b). Uniform coverage of automo-
Acar, E. U., Choset, H., and Lee, J. Y. (2006). Sensor- tive surface patches. The International Journal of
based coverage with extended range detectors. IEEE Robotics Research, 24(11):883 – 898.
Transactions on Robotics, 22(1):189–198.
Atkar, P. N., Choset, H., Rizzi, A. A., and Acar, E. U.
Acar, E. U., Choset, H., Rizzi, A. A., Atkar, P. N., and (2001). Exact cellular decomposition of closed ori-
Hull, D. (2002). Morse decompositions for coverage entable surfaces embedded in r3. In Proc. ICRA
tasks. International Journal of Robotics Research, Robotics and Automation IEEE Int. Conf, volume 1,
21(4):331–344. pages 699–704.

Acar, E. U., Choset, H., Zhang, Y., and Schervish, M. Barrientos, A., Colorado, J., del Cerro, J., Martinez,
(2003). Path planning for robotic demining: Robust A., Rossi, C., Sanz, D., and Valente, J. (2011). Aerial
sensor-based coverage of unstructured environments remote sensing in agriculture: A practical approach
and probabilistic methods. International Journal of to area coverage and path planning for fleets of mini
Robotics Research, 22(7-8):441–466. aerial robots. Journal of Field Robotics, 28(5):667–
689.
Agmon, N., Hazon, N., and Kaminka, G. (2006). Con-
structing spanning trees for efficient multi-robot cov- Batalin, M. A. and Sukhatme, G. S. (2002). Spread-
erage. In Robotics and Automation, 2006. ICRA ing out: A local approach to multi-robot coverage.
2006. Proceedings 2006 IEEE International Confer- In Proceedings of the 6th International Symposium
ence on, pages 1698 –1703. on Distributed Autonomous Robotics Systems, pages
373–382.
Ahmadzadeh, A., Keller, J., Jadbabaie, A., and Ku-
mar, V. (2006). An optimization-based approach Bosse, M., Nourani-Vatani, N., and Roberts, J. (2007).
to time critical cooperative surveillance and cover- Coverage algorithms for an under-actuated car-like
age with unmanned aerial vehicles. In International vehicle in an uncertain environment. In Proc. IEEE
Symposium on Experimental Robotics. Int Robotics and Automation Conf, pages 698–703.

28
Bretl, T. and Hutchinson, S. (2013). Robust coverage Choset, H., Acar, E., Rizzi, A. A., and Luntz, J.
by a mobile robot of a planar workspace. In Proc. (2000a). Exact cellular decompositions in terms of
International Conference on Robotics and Automa- critical points of morse functions. In Proc. IEEE Int.
tion. Conf. Robotics and Automation ICRA ’00, volume 3,
pages 2270–2277.
Butler, Z. J., Rizzi, A. A., and Hollis, R. L. (1999).
Contact sensor-based coverage of rectilinear envi- Choset, H. and Burdick, J. (2000). Sensor-based
ronments. In Proc. IEEE Int Intelligent Con- exploration: The hierarchical generalized voronoi
trol/Intelligent Systems and Semiotics Symposium, graph. The International Journal of Robotics Re-
pages 266–271. search, 19(2):96–125.
Butler, Z. J., Rizzi, A. A., and Hollis, R. L. (2000).
Choset, H. and Kortenkamp, D. (1999). Path planning
Complete distributed coverage of rectilinear environ-
and control for aercam, a free-flying inspection robot
ments. In Proc. of the Workshop on the Algorithmic
in space. ASCE Journal of Aerospace Engineering,
Foundations of Robotics.
12(2):74–81.
Canny, J. F. (1988). Constructing roadmaps of semi-
algebraic sets i: Completeness. Artificial Intelli- Choset, H., Lynch, K., Hutchinson, S., Kantor, G.,
gence, 37(1-3):203–222. Burgard, W., Kavraki, L., and Thrun, S. (2005).
Principles of Robot Motion: Theory, Algorithms,
Canny, J. F. (1993). An opportunistic global path plan- and Implementation. The MIT Press.
ner. Algorithmica, 10:102–120.
Choset, H. and Pignon, P. (1997). Coverage path
Cao, Z. L., Huang, Y., and Hall, E. L. (1988). Re-
planning: The boustrophedon cellular decomposi-
gion filling operations with random obstacle avoid-
tion. In Proceedings of International Conference on
ance for mobile robotics. Journal of Robotic Systems,
Field and Service Robotics.
5(2):87–102.
Castellanos, J., Tardos, J., and Schmidt, G. (1997). Choset, H., Walker, S., Eiamsa-Ard, K., and Burdick,
Building a global map of the environment of a mobile J. (2000b). Sensor-based exploration: Incremental
robot: the importance of correlations. In Robotics construction of the hierarchical generalized voronoi
and Automation, 1997. Proceedings., 1997 IEEE In- graph. The International Journal of Robotics Re-
ternational Conference on, volume 2, pages 1053 – search, 19(2):126–148.
1059 vol.2.
Danner, T. and Kavraki, L. (2000). Randomized plan-
Cheng, P., Keller, J., and Kumar, V. (2008). Time- ning for short inspection paths. In Robotics and Au-
optimal uav trajectory planning for 3d urban struc- tomation, 2000. Proceedings. ICRA ’00. IEEE Inter-
ture coverage. In Intelligent Robots and Systems, national Conference on, volume 2, pages 971 –976
2008. IROS 2008. IEEE/RSJ International Confer- vol.2.
ence on, pages 2750 –2757.
de Berg, M., Cheong, O., v. Kreveldand, M., and
Chin, W.-P. and Ntafos, S. (1991). Shortest watchman Overmars, M. (2008). Computational Geometry.
routes in simple polygons. Discrete & Computational Springer, 3rd edition edition.
Geometry, 6(1):9–31.
Easton, K. and Burdick, J. (2005). A coverage al-
Choi, Y.-H., Lee, T.-K., Baek, S.-H., and Oh, S.-Y.
gorithm for multi-robot boundary inspection. In
(2009). Online complete coverage path planning
Robotics and Automation, 2005. ICRA 2005. Pro-
for mobile robots based on linked spiral paths us-
ceedings of the 2005 IEEE International Conference
ing constrained inverse distance transform. In Proc.
on, pages 727–734.
IEEE/RSJ Int. Conf. Intelligent Robots and Systems
IROS 2009, pages 5788–5793. Elfes, A. (1987). Sonar-based real-world mapping and
Choset, H. (2000). Coverage of known spaces: the navigation. Robotics and Automation, IEEE Journal
boustrophedon cellular decomposition. Autonomous of, 3(3):249 –265.
Robots, 9(3):247–253.
Englot, B. and Hover, F. (2012). Sampling-based cov-
Choset, H. (2001). Coverage for robotics–a survey of erage path planning for inspection of complex struc-
recent results. Annals of Mathematics and Artificial tures. In International Conference on Automated
Intelligence, 31:113–126. Planning and Scheduling (ICAPS).

29
Farsi, M., Ratcliff, K., Johnson, J. P., Allen, C. R., Hazon, N., Mieli, F., and Kaminka, G. (2006). Towards
Karam, K. Z., and Pawson, R. (1994). Robot con- robust on-line multi-robot coverage. In Robotics and
trol system for window cleaning. In Proc. American Automation, 2006. ICRA 2006. Proceedings 2006
Control Conf, volume 1, pages 994–995. IEEE International Conference on, pages 1710 –
1715.
Fazli, P., Davoodi, A., Pasquier, P., and Mackworth, A.
(2010). Complete and robust cooperative robot area Hert, S., Tiwari, S., and Lumelsky, V. (1996). A
coverage with limited range. In Intelligent Robots terrain-covering algorithm for an auv. Autonomous
and Systems (IROS), 2010 IEEE/RSJ International Robots, 3:91–119.
Conference on, pages 5577–5582.
Hodgkin, L. and Huxley, A. F. (1952). A quantita-
Gabriely, Y. and Rimon, E. (2002). Spiral-stc: an on- tive description of membrane current and its appli-
line coverage algorithm of grid environments by a cation to conduction and exitation in nerve. Journal
mobile robot. In Proc. IEEE Int. Conf. Robotics and of Physics London, 117:500–544.
Automation ICRA ’02, volume 1, pages 954–960.
Huang, W. H. (2001). Optimal line-sweep-based de-
Gage, D. W. (1994). Randomized search strategies compositions for coverage algorithms. In Proc. ICRA
with imperfect sensors. In Proc. SPIE, Mobile Robots Robotics and Automation IEEE Int. Conf, volume 1,
VIII–Int. Soc. Optical Engineering, pages 270–279, pages 27–32.
Boston, MA.
Jimenez, P. A., Shirinzadeh, B., Nicholson, A., and
Galceran, E. and Carreras, M. (2012). Efficient seabed
Alici, G. (2007). Optimal area covering using genetic
coverage path planning for asvs and auvs. In Proc.
algorithms. In Proc. IEEE/ASME international con-
IEEE/RSJ International Intelligent Robots and Sys-
ference Advanced intelligent mechatronics, pages 1–
tems Conference.
5.
Galceran, E. and Carreras, M. (2013). Planning cov-
erage paths on bathymetric maps for in-detail in- Jin, J. and Tang, L. (2011). Coverage path planning on
spection of the ocean floor. In Proc. International three-dimensional terrain for arable farming. Journal
Conference on Robotics and Automation. of Field Robotics, 28(3):424–440.

Galceran, E., Nagappa, S., Carreras, M., Ridao, P., Kim, A. (2012). Active Visual SLAM with Exploration
and Palomer, A. (2013). Uncertainty-driven survey for Autonomous Underwater Navigation. PhD the-
path planning for bathymetric mapping. In Proc. sis, The University of Michigan.
IEEE/RSJ International Intelligent Robots and Sys-
Latombe, J. C. (1991). Robot motion planning. Kluwer
tems Conference.
Academic Publishers.
Garcia, E. and de Santos, P. G. (2004). Mobile-robot
navigation with complete coverage of unstructured LaValle, S. M. (2006). Planning Algorithms, chapter
environments. Robotics and Autonomous Systems, Chapter 4: The Configuration Sace, pages 130–131.
46:195–204. Cambridge University Press.

Gonzalez, E., Alvarez, O., Diaz, Y., Parra, C., and Lee, T.-S., Choi, J.-S., Lee, J.-H., and Lee, B.-H.
Bustacara, C. (2005). Bsa: A complete coverage (2009). 3-d terrain covering and map building al-
algorithm. In Proc. IEEE Int. Conf. Robotics and gorithm for an auv. In Proc. IEEE/RSJ Int. Conf.
Automation ICRA 2005, pages 2040–2044. Intelligent Robots and Systems IROS 2009, pages
4420–4425.
Guo, Y. and Balakrishnan, M. (2006). Complete cov-
erage control for nonholonomic mobile robots in dy- Li, F. and Klette, R. (2008). An approximate algo-
namic environments. In Robotics and Automation, rithm for solving the watchman route problem. In
2006. ICRA 2006. Proceedings 2006 IEEE Interna- Sommer, G. and Klette, R., editors, Robot Vision,
tional Conference on, pages 1704 –1709. volume 4931 of Lecture Notes in Computer Science,
pages 189–206. Springer Berlin Heidelberg.
Hazon, N. and Kaminka, G. (2005). Redundancy, ef-
ficiency and robustness in multi-robot coverage. In Lumelsky, V. J., Mukhopadhyay, S., and Sun, K.
Robotics and Automation, 2005. ICRA 2005. Pro- (1990). Dynamic path planning in sensor-based ter-
ceedings of the 2005 IEEE International Conference rain acquisition. IEEE Transactions on Robotics and
on, pages 735 – 741. Automation, 6(4):462–472.

30
Luo, C. and Yang, S. (2002). A real-time coopera- Oksanen, T. and Visala, A. (2009). Coverage path
tive sweeping strategy for multiple cleaning robots. planning algorithms for agricultural field machines.
In Intelligent Control, 2002. Proceedings of the 2002 Journal of Field Robotics, 26:651–558.
IEEE International Symposium on, pages 660 – 665.
Ollis, M. and Stentz, A. (1997). Vision-based percep-
Luo, C. and Yang, S. (2008). A bioinspired neural tion for an automated harvester. In Proc. IEEE/RSJ
network for real-time concurrent map building and Int Intelligent Robots and Systems IROS ’97. Conf,
complete coverage robot navigation in unknown en- volume 3, pages 1838–1844.
vironments. Neural Networks, IEEE Transactions
on, 19(7):1279 –1298. Palacin, J., Palleja, T., Valganon, I., Pernia, R., and
Roca, J. (2005). Measuring coverage performances of
Luo, C., Yang, S., and Stacey, D. (2003). Real-time a floor cleaning mobile robot using a vision system.
path planning with deadlock avoidance of multiple In Robotics and Automation, 2005. ICRA 2005. Pro-
cleaning robots. In Robotics and Automation, 2003. ceedings of the 2005 IEEE International Conference
Proceedings. ICRA ’03. IEEE International Confer- on, pages 4236–4241.
ence on, volume 3, pages 4080 – 4085 vol.3.
Papadopoulos, G., Kurniawati, H., and Patrikalakis,
Luo, C., Yang, S. X., Stacey, D. A., and Jofriet, J. C.
N. M. (2013). Asymptotically optimal inspection
(2002). A solution to vicinity problem of obstacles in
planning using systems with differential constraints.
complete coverage path planning. In Proc. IEEE Int.
In Proc. International Conference on Robotics and
Conf. Robotics and Automation ICRA ’02, volume 1,
Automation.
pages 612–617.

Mannadiar, R. and Rekleitis, I. (2010). Optimal cov- Paull, L., Saeedi, S., Li, H., and Myers, V. (2010).
erage of a known arbitrary environment. In Proc. An information gain based adaptive path planning
IEEE Int Robotics and Automation (ICRA) Conf, method for an autonomous underwater vehicle using
pages 5525–5530. sidescan sonar. In Automation Science and Engi-
neering (CASE), 2010 IEEE Conference on, pages
Maza, I. and Ollero, A. (2007). Distributed Au- 835–840.
tonomous Robotic Systems 6, chapter Multiple UAV
cooperative searching operation using polygon area Paull, L., SaeediGharahbolagh, S., Seto, M., and Li,
decomposition and efficient coverage algorithms, H. (2012). Sensor driven online coverage planning
pages 221–230. Springer. for autonomous underwater vehicles. In Intelligent
Robots and Systems (IROS), 2012 IEEE/RSJ Inter-
Mazo, M. and et al. (2004). Robust area coverage using national Conference on, pages 2875–2880.
hybrid control. TELEC 2004, Santiago de Cuba.
Qiu, X., Song, J., Zhang, X., and Liu, S. (2006). A
Menezes, R., Martins, F., Vieira, F. E., Silva, R., and complete coverage path planning method for mo-
Braga, M. (2007). A model for terrain coverage in- bile robot in uncertain environments. In Proc. Sixth
spired by ant’s alarm pheromones. In Proceedings World Congress Intelligent Control and Automation
of the 2007 ACM symposium on Applied computing, WCICA 2006, volume 2, pages 8892–8896.
SAC ’07, pages 728–732, New York, NY, USA. ACM.
Reeb, G. (1946). Sur les points singuliers d’une forme
Milnor, J. (1963). Morse Theory. Princeton University de Pfaff complètement intégrable ou d’une fonc-
Press. tion numérique. Comptes Rendus Acad. Sciences,
Moravec, H. and Elfes, A. (1985). High resolution maps 222:847–849.
from wide angle sonar. In Proc. IEEE Int. Conf.
Reif, J. H. and Sun, Z. (2001). Algorithmic and Com-
Robotics and Automation, volume 2, pages 116–121.
putational Robotics: New Directions, chapter An ef-
Najjaran, H. and Kircanski, N. (2000). Path planning ficient approximation algorithm for weighed region
for a terrain scanner robot. In Proc. 31st Int. Symp. shortest path problem, pages 191–203. A. K. Peters.
Robotics, pages 132–137, Montreal, QC, Canada.
Rekleitis, I., New, A., Rankin, E., and Choset,
Oh, J. S., Choi, Y. H., Park, J. B., and Zheng, Y. H. (2009). Efficient boustrophedon multi-robot
(2004). Complete coverage navigation of cleaning coverage: an algorithmic approach. Annals of
robots using triangular-cell-based map. Industrial Mathematics and Artificial Intelligence, 52:109–142.
Electronics, IEEE Transactions on, 51(3):718–726. 10.1007/s10472-009-9120-2.

31
Shermer, T. (1992). Recent results in art galleries [ge-Yang, S. X. and Luo, C. (2004). A neural network ap-
ometry]. Proceedings of the IEEE, 80(9):1384–1399. proach to complete coverage path planning. IEEE
Transactions on Systems, Man, and Cybernetics,
Shivashankar, V., Jain, R., Kuter, U., and Nau, D. Part B: Cybernetics, 34(1):718–724.
(2011). Real-time planning for covering an initially-
unknown spatial environment. In Proceedings of the Yasutomi, F., Yamada, M., and Tsukamoto, K. (1988).
Twenty-Fourth International Florida Artificial Intel- Cleaning robot control. In Proc. Conf. IEEE Int
ligence Research Society Conference. Robotics and Automation, pages 1839–1841.

Thrun, S. (1998). Learning metric-topological maps Zelinsky, A., Jarvis, R. A., Byrne, J. C., and Yuta, S.
for indoor mobile robot navigation. Artif. Intell., (1993). Planning paths of complete coverage of an
99(1):21–71. unstructured environment by a mobile robot. In Pro-
ceedings of International Conference on Advanced
Thrun, S. (2003). Robotic mapping: a survey. In Robotics, pages 533–538.
Exploring Artificial Intelligence in the New Millen-
nium, pages 1–35. Morgan Kaufmann Publishers Zheng, X., Jain, S., Koenig, S., and Kempe, D. (2005).
Inc., San Francisco, CA, USA. Multi-robot forest coverage. In Intelligent Robots
and Systems, 2005. (IROS 2005). 2005 IEEE/RSJ
Tully, S., Kantor, G., and Choset, H. (2010). Leap- International Conference on, pages 3852 – 3857.
frog path design for multi-robot cooperative local-
Zheng, X. and Koenig, S. (2007). Robot coverage
ization. In Howard, A., Iagnemma, K., and Kelly,
of terrain with non-uniform traversability. In In-
A., editors, Field and Service Robotics, volume 62
telligent Robots and Systems, 2007. IROS 2007.
of Springer Tracts in Advanced Robotics, pages 307–
IEEE/RSJ International Conference on, pages 3757
317. Springer Berlin / Heidelberg. 10.1007/978-3-
–3764.
642-13408-1 28.

Wagner, I. A., Altshuler, Y., Yanovski, V., and Bruck-

stein, A. M. (2008). Cooperative cleaners: A study in
ant robotics. The International Journal of Robotics
Research, 27(1):127–151.

Wagner, I. A., Lindenbaum, M., and Bruckstein, A. M.

(1999). Distributed covering by ant-robots using
evaporating traces. IEEE Transactions on Robotics
and Automation, 15(5):918–933.

Wong, S. C. (2006). Qualitative topological coverage of

unknown environments by mobile robots. PhD thesis,
The University of Auckland.

Wong, S. C. and MacDonald, B. A. (2003). A topolog-

ical coverage algorithm for mobile robots. In Proc.
IEEE/RSJ Int. Conf. Intelligent Robots and Systems
(IROS 2003), volume 2, pages 1685–1690.

Xu, A., Virie, P., and Rekleitis, I. (2011). Optimal

complete terrain coverage using an unmanned aerial
vehicle. In Proceedings of the 2011 IEEE Interna-
tional Conference on Robotics & Automation.

Xu, L. (2011). Graph Planning for Environmental Cov-

erage. PhD thesis, Carnegie Mellon University.

Yan, M. and Zhu, D. (2011). An algorithm of complete

coverage path planning for autonomous underwater
vehicles. Key Engineering Materials, 467-469:1377–
1385.

32