See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/334082300

A Constant-Factor Approximation Algorithm for Online Coverage Path Planning

with Energy Constraint

Preprint · June 2019

DOI: 10.48550/arXiv.1906.11750

CITATIONS READS
0 132

2 authors:

Ayan Dutta Gokarna Sharma

University of North Florida Kent State University
83 PUBLICATIONS 799 CITATIONS 121 PUBLICATIONS 1,327 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Ayan Dutta on 30 June 2019.

The user has requested enhancement of the downloaded file.

 A Constant-Factor Approximation Algorithm for Online
Coverage Path Planning with Energy Constraint
Ayan Dutta, Gokarna Sharma

Abstract— In this paper, we study the problem of coverage runs out. Due to practical relevance, in the recent years,
planning by a mobile robot with a limited energy budget. The there has been a significant volume of work on the energy-
objective of the robot is to cover every point in the environment constrained coverage planning problem [18], [14], [20], [19],
while minimizing the travelled path length. The environment is
initially unknown to the robot. Therefore, it needs to avoid the [17], [16]. The offline version of the problem, denoted as
obstacles in the environment on-the-fly during the exploration. O FFLINE CPP, is studied in [17], [20], [19] and the online
arXiv:1906.11750v1 [cs.RO] 27 Jun 2019

As the robot has a specific energy budget, it might not be able version, denoted as O NLINE CPP, is studied in [16], [17].
to cover the complete environment in one traversal. Instead, it The state-of-the-art algorithm for O FFLINE CPP is due to
will need to visit a static charging station periodically in order [19], which provides O(1)-approximation. For O NLINE CPP,
to recharge its energy. To solve the stated problem, we propose
a budgeted depth first search (DFS)-based exploration strategy the state-of-the-art algorithm is due to [16], which provides
that helps the robot to cover any unknown planar environment O(log(B/L))-approximation, where B is the energy budget
while bounding the maximum path length to a constant-factor and L is the size of the robot (assuming a L×L square robot).
of the shortest-possible path length. Our O(1)-approximation Our goal in this paper is to provide a better approximation
guarantee advances the state-of-the-art of log-approximation algorithm for O NLINE CPP, i.e., to reduce the O(log(B/L))-
for this problem. Simulation results show that our proposed
algorithm outperforms the current state-of-the-art algorithm approximation of [16] to O(1). This will show that asymptot-
both in terms of the travelled path length and run time in all ically there is no approximation gap between O NLINE CPP
the tested environments with concave and convex obstacles. and O FFLINE CPP.
Our proposed algorithm covers an unknown environment
I. I NTRODUCTION through a DFS traversal approach tailored for the limited
Coverage planning is the task of finding a path or a set energy budget B. Robot r performs a depth first search
of paths to cover all the points in an environment [5]. In traversal while building a tree map of the environment on-
robotics, this problem has many potential real-world appli- the-fly. It returns to the charging station to get its battery
cations including autonomous sweeping, vacuum cleaning, fully recharged (stopping the DFS exploration) when the path
and lawn mowing. In an online version of the problem, the length of the traversal becomes at most B. After the battery
area of interest is initially unknown to the robot. Therefore is fully charged, r then moves to the cell where it stopped the
it needs to discover and avoid the unknown obstacles in the DFS process, and continues traversing P . Simulation results
environment while covering all the points in the free space show that our proposed algorithm is up to 5.80 times faster
by traveling as minimum distance as possible [5]. and up to 2.53 times less costlier (in terms of traversed path
Traditionally, this problem has been studied assuming that length) than the state-of-the-art algorithm [16].
the robot has an unlimited energy budget, where given a Contributions. Initially, the robot is at the charging station
robot, a single path can be planned to cover the given S that is inside P . The goal of O NLINE CPP is to find a set
environment. The offline version of the problem where the of paths Q = {Q1 , . . . , Qk } for the robot such that
robot(s) have a priori knowledge of the environment includ- • Condition (a): Each path Qi starts and ends at S
ing obstacles has been well studied, e.g., see [9]. Many • Condition (b): Each path Qi has length l(Qi ) ≤ B
algorithms have been proposed such as the boustrophedon • Condition (c): The paths in Q collectively cover the
decomposition based coverage [4], [13], the spiral path cov- environment P , i.e., ∪ni=1 Qi = P ,
erage [10], and the spanning-tree based coverage [8]. These
and the following two performance metrics are optimized:
techniques can also be adapted to solve online coverage
• Performance metric 1: The number of paths in Q,
planning [20], [3].
In practice however, the robots do not have unlimited denoted as |Q|, is minimized, and
• Performance metric 2: The total lengths of the paths
energy available. Therefore, even covering a standard-size Pn
environment (e.g., a farm) while simultaneously using on- in Q, denoted as l(Q) = i=1 l(Qi ), is minimized.
board sensors (e.g., camera) becomes prohibitive with a We establish the following main theorem for O NLINE CPP.
single charge. A battery-powered robot needs to return to Theorem 1 (Main Result): Given an unknown planar
the charging station to get recharged before the battery polygonal environment P possibly containing obstacles and
a robot r of size L×L consisting of position and obstacle de-
A. Dutta is with the School of Computing, University of North Florida, tection sensors initially situated at a charging station S inside
Jacksonville, FL 32224, USA a.dutta@unf.edu
G. Sharma is with the Department of Computer Science, Kent State P with energy budget B, there is an algorithm that correctly
University, Kent, OH 44242, USA sharma@cs.kent.edu solves O NLINE CPP and guarantees 10-approximation to
both performance metrics compared to the optimal algorithm coordinate system through a compass on-board, that means
that has complete knowledge about P . it knows left (West), right (East), up (North), and down
This result clearly advances the current state-of-the-art as (South) cells consistently from its current cell. Robot r is
it improves upon the log-approximation provided in [16] and equipped with a position sensor (e.g., GPS) and an obstacle-
provides a constant-factor approximation. Furthermore, the detection sensor (e.g., laser rangefinder). We assume that
proposed algorithm is easier to implement than [16]. with the laser rangefinder, the robot can detect obstacles
Related Work. The most closely related works to ours are in any of its neighbor cells. The robot has sufficient on-
[16], [20], [19], [17]. Shnaps and Rimon [17] proposed an board memory to store information necessary to facilitate
1/(1 − ρ)-approximation algorithm for O FFLINE CPP, where the coverage process. Moreover, we assume that initially r
ρ is the ratio between the furthest distance between any two does not have any knowledge about P , i.e., P is an unknown
cells in the environment and half of the energy budget [17]. environment. For the feasibility of covering all cells of P ,
For O NLINE CPP, they proposed an O(B/L)-approximation we assume that P is as big as a circle of radius bB/2c with
algorithm. Wei and Isler [20] presented an O(log(B/L))- center at S. It is assumed that the energy consumption of the
approximation algorithm for O FFLINE CPP, which has been robot is proportional to the distance travelled, i.e., the energy
improved to a constant-factor approximation by them in [19]. budget of B allows the robot to move B units distance.
Recently, Sharma et al. [16] provided an O(log(B/L))- A path (route) Qi is a list of cells that r visits starting
approximation algorithm for O NLINE CPP. In this paper, we and ending with S. Notice that if there are some obstacles
improve upon the log-approximation bound and provide the within P located in such a way that they divide P into two
O(1)-approximation to O NLINE CPP. sub-polygons P1 and P2 with P1 and P2 sharing no common
The other related work is the coverage of a graph. The boundary, then r cannot fully cover P . Therefore, we assume
goal is to design paths to visit every vertex of the given that there is no such cell c in P . That means, there is (at least)
graph. Without energy constraints, it becomes the well- a route from S to any obstacle-free cell of P .
known Traveling Salesperson Problem (TSP) [1] and a We call a cell free if it is not occupied by an obstacle. We
DFS traversal provides a constant-approximation of the TSP. call a cell reachable if it satisfies the definition below.
With energy constraints, this coverage problem becomes the Definition 1 (Reachable Cell): Any cell c in P is called
Vehicle Routing Problem (VRP) [11]. One version of VRP reachable by the robot r, if and only if (a) it is a free cell,
is the Distance Vehicle Routing Problem (DVRP), which (b) it is within distance bB/2c from S, and (c) there must
models the energy consumption proportional to the distance be at least a route of consecutive free cells from S to c.
travelled. For DVPR on tree metrics, Nagarajan and Ravi [15] O NLINE CPP. The problem is formally defined as follows.
proposed a 2-approximation algorithm. Li et al. [12] used Definition 2: Given an unknown planar polygonal envi-
a TSP-partition method and their algorithm has a similar ronment P possibly containing obstacles with a robot r
approximation to the work in [17]. Most of these work having battery budget of B initially positioned at a charging
studied the offline version so that pre-processing on the station S inside P , O NLINE CPP is for r to visit all the
environment can be done prior to exploration obtaining better reachable cells of P through a set of paths so that
approximation. This is also the case in the algorithm of
• Conditions (a)–(c) are satisfied, and
[20], [19] for O FFLINE CPP. Coverage with multiple robots
• Performance metrics (1) and (2) are minimized.
has also received a lot of attention (e.g., see [2], [7]). In
Following [16], [19], we measure the efficiency of any
some cases, the paths planned for a single robot under
algorithm for O NLINE CPP in terms of approximation ratio
energy constraints can also be executed by multiple robots by
which is the worst-case ratio of the cost of the online
assigning the planned paths to the robots, without affecting
algorithm for some environment P over the cost of the
the total cost. In this paper, we consider coverage planning
optimal, offline algorithm for the same environment.
with a single robot.
III. P ROCESSING U NKNOWN E NVIRONMENT
II. P ROBLEM SETUP
In this section, we discuss how the robot decomposes the
In this paper, we use the same model as in [16], [20], [17]. environment into square grid cells and then construct a tree
Environment. The environment P is a planar polygon con- map of the environment on-the-fly.
taining a single charging station S inside it. P may possibly Decomposition of the Environment. Following [16], [19],
contain polygonal, static obstacles. See left of Fig. 1 for an we decompose the environment P into square cells of size
illustration of P with an obstacle O1 . The environment P is L × L, which is the size of the robot itself. An equi-distance
discretized into cells forming a 4-connected grid. contour is a poly-line where the cells on it has the same
Robot. We consider the robot r to be initially positioned distance to/from the base point S (the left of Fig. 1). The
at the charging station S. r has size L × L that it fits cells on a contour can be ordered from one side to the other.
within a grid-cell in P . The robot r moves rectilinearly in Let c be a cell and C be a contour. Let d(c) denote the
P , i.e., it may move to any of the four neighbor cells (if distance to S from c and let d(C) denote the distance to S
the cell is not occupied by an obstacle) from its current from C. If d(Cj ) = d(Ci ) + 1, we say that contour Cj is
cell. We also assume that r has the knowledge of the global contour Ci ’s next contour. The contour C with d(C) = 1 is
 11 12
12 13

Fig. 2. An illustration of changes on contour numbers

Fig. 1. (left) An environment P with an obstacle O1 and a charging station

S. P is shown decomposed as cells of size L×L same as the robot; (right) of the obstacle. For example, see the left of Fig. 2.
An example tree map TP (right) constructed for the environment P on the
left. The cells at any contour Cd are at depth d in TP . We solve this problem in Algorithm 1 using an approach
where the robot r detects this problem and changes the
contour numbers of those cells on-the-fly. See for example
called the first contour. Each cell in a contour has at most 4 the right of Fig. 2 that depicts how the contour numbers for
reachable cells from S that are its neighbors. the cells on the right of O1 are updated on-the-fly by the
robot. Details are omitted on how r detects the problem and
Constructing a Tree Map. Initially, the robot r is placed at solves it due to space constraints.
the fixed charging station S. In this case, the tree, denoted
by TP , has only one node S, which we call the root of TP . IV. A LGORITHM
If there is no obstacle in P , each cell except the boundary In the description of the algorithm and its analysis, we
cells of P will have exactly four neighbor cells. assume that L = 1. A simple adaptation will work when L >
Robot r picks the first free cell c1 according to a clockwise 1. The pseudocode is given in Algorithm 1 and illustration
ordering of its neighbors starting from the west and ending of the working principle of the algorithm is given in Fig. 3.
in the south neighbor cell. r then inserts it into TP as a
child of S. If the cell labeled West is a reachable cell, then A. A Naive Approach without Energy Constraint
r picks that cell. Otherwise, it goes in order of North, East, The main idea behind our algorithm is to let r incre-
and South until it finds the first cell that is reachable. We mentally explore the environment P while simultaneously
now have two nodes in TP = {S, c1 }, with c1 as a child constructing a tree map TP of P to keep track of the new
node of S. Furthermore, c1 is a cell in the first contour C1 . frontiers that need to be visited by it.
Since r is building TP while exploring P , it will move to For simplicity, let us first consider that TP (or P ) is known
c1 after it is included as a child in TP . The robot r then again a priori and r has no energy constraint (i.e., B = ∞). Let
repeats the process of building TP from its current cell c1 . Q∞ (r) be a route in T that visits all the nodes of TP ,
While at c1 , r is only allowed to add one of the neighboring obtained performing a Depth First Search (DFS) traversal of
cells of c1 that are in the second contour C2 (i.e., d(C2 ) = 2) TP . Since TP is a tree, it is known that all the nodes of TP
as a child of c1 . For this, r will include a neighboring cell c2 can be covered by the DFS traversal by visiting each node of
of c1 in TP only if c2 is a cell in contour C2 . Furthermore, TP at most twice. Therefore, if there are n nodes in TP , then
if some cell is already a part of TP , then this cell will not be the length of the route l(Q(r)) ≤ 2n. Moreover, an optimal
included in TP again. This process will then continue. The algorithm for r to traverse all n nodes of TP must have
right of Fig. 1 provides an illustration of the tree map TP length l(QOP T (r)) ≥ n, since r can only visit the nodes
developed for the environment P shown on the left. of TP sequentially one after another using any algorithm.
Essentially, any edge of TP connects two cells ci , ci+1 of Therefore, without any energy constraint (B = ∞), we have
P such that ci ∈ Ci and ci+1 ∈ Ci+1 , for 0 ≤ i ≤ bB/2Lc− a 2-approximation algorithm. The 2-approximation can also
1; in Fig. 1, each cell of contour Ci on the environment P on be guaranteed for O NLINE CPP when B = ∞ since with the
the left are at depth i in TP shown on the right. Therefore, knowledge of the global coordinate system, r can visit all
using this approach, all the cells in the first contour C1 will the nodes of TP as if TP is known a priori, satisfying the
be children of S (the root of TP ), all the cells in the second length of the route l(Q(r)) ≤ 2n.
contour C2 will be children of the nodes of TP that are cells
in the first contour C1 , and so on. B. Incorporating the Energy Constraint
There is one potential problem in certain situations. Con- Now suppose that r has energy budget B < 2n. The
sider the environment shown in Fig. 2 where the horizontal aforementioned algorithm is not sufficient anymore since
line passing through S is crossing obstacle O1 . The contour each route of r can be at most of length B. Therefore, r needs
numbering and constructing TP based on contour numbers to return to S to get recharged before the length of the robot’s
do not work as the cells in the right of O1 may not be visited path reaches B. Our proposed algorithm uses the same idea
by r following Algorithm 1 as it requires the robot to visit of performing a DFS traversal of TP as described in the
the cells in an increasing order of contour numbers. This is previous subsection while stopping the DFS traversal process
because the contour numbers for those cells are smaller than before the route of r has length at most B. Let Q∞ (r) =
the contour number of the cells on North, South, and West {S, v1 , v2 , . . . , vl } be the route with respective nodes visited
by r while running DFS assuming B = ∞. Let Qi (r) denote Algorithm 1: O NLINE CPPA LG
a route of r visiting the nodes of Q∞ (r) when B < 2n. The 1 Robot: Initially positioned at the charging station S and it
goal is to obtain Q0 (r) = (Q1 (r), Q2 (r), . . . , Qk (r)), such knows its size L and the energy budget B.
that the three conditions listed in Section I are satisfied. 2 Environment: Planar area with radius at most bB/2c with
The challenge is to plan each route Qi (r) in an online center S possibly containing obstacles; obstacle positions and
numbers not known.
fashion satisfying all three criteria while minimizing both 3 Data structures: Tree map TP and new frontier stack F .
the number of paths |Q0 (r)| and the total length of the 4 Initialize: TP = {S}, F = {S}, distance (i.e., depth in tree
paths l(Q0 (r)). We use the following approach: Q1 (r) starts TP for a node v of TP ) Dv = 0, the energy budget remaining
from S and visits the nodes of Q∞ (r) in a sequence. As Bremain = B, and node in TP to continue coverage in the
soon as Q1 (r) reaches to a node vi ∈ Q∞ (r) such that next route nodenext = S.
5 while F 6= ∅ do
dist(vi , S) ≤ Bremain , it terminates the DFS traversal and 6 if B is not even then
returns to S. Bremain is the energy remained after each 7 Bremain = B − 1;
move. In route Q2 (r), r moves to vi (where it stopped 8 Move to nodenext from S using the shortest path in TP ;
the DFS traversal in Q1 (r)) from S and continues the DFS 9 Dv ← the distance from S to nodenext in TP ;
traversal until it reaches to a node vj ∈ Q∞ (r) from which 10 Bremain ← Bremain − Dv ;
dist(vj , S) ≤ Bremain . Like last route, r then returns to S. 11 while Bremain > Dv do
This process then continues until the last node vl ∈ Q∞ (r) 12 if nodenext has unvisited child nodes in TP or the
cell on top of F is the child node of nodenext in
is visited in some route Qk (r). We later prove that using this TP then
approach, r visits all nodes of TP providing correctness and 13 if the child nodes of nodenext are not already
approximation guarantee claimed in Theorem 1. included in F and TP then
14 Include all the child nodes of nodenext in
TP and F (ordered clockwise from left to
right starting from the leftmost child node
and insert to F from right to left);
15 v ← the node on the top of F or the leftmost in
TP (v will be the node pushed into F last);
16 Robot r removes v from F , moves to v, marks v
visited in TP ;
17 else
18 v ← the parent node of nodenext in TP ;
19 Robot r moves to v;
20 nodenext ← v;
Fig. 3. An illustration of the budgeted DFS traversal by using Algorithm 21 Bremain ← Bremain − 1;
1 when energy budget B is 30 (left) and 40 (left) for the environment P 22 Dv ← the distance from S to nodenext ;
shown in Fig. 1.For B = 30, r needs 4 paths whereas only 3 paths are
needed when B = 40. The nodes of TP where Qi−1 (r) stops the DFS 23 Robot r goes to S following a path in TP ;
traversal are marked by double circles; the next path Qi (r) continues the 24 Bremain ← B (after r is fully changed) after reaching S;
DFS traversal from these nodes.

We call our algorithm O NLINE CPPA LG (shown in Al-

gorithm 1). Initially, the robot r is at S with the energy nodes in the tree TP starting from its current node.
budget B < 2n. This is a special situation where v = S and
Bremain = B. Robot r then includes the child nodes of S (in V. A NALYSIS OF THE A LGORITHM
contour 1) in TP making them child nodes of root S in TP In this section, we provide theoretical analysis of O N -
and moves to the leftmost child node, say v1,lef t . The node LINE CPPA LG . We first prove its correctness and then ana-
v1,lef t is marked visited. Bremain is decreased by 1 (line 21). lyze the costs for the performance metrics (1) and (2).
Robot r then moves from v1,lef t to the leftmost child node Correctness. We start with the following lemma.
v2,lef t (in contour 2). The node v2,lef t is marked visited and Lemma 1: Let {S, v1 , v2 , . . . , vl } be the order of the
Bremain is decreased by 1. This process continues until at nodes of TP (i.e., cells in P ) visited by the DFS
some node vi (in some contour i), Bremain = Dvi , where traversal Q∞ (r) when B = ∞. Let Q0 (r) =
Dvi is the distance from vi to S in TP . Robot r then returns {Q1 (r), Q2 (r), . . . , Qk (r)} be the routes of r that collec-
to S following the path in TP (line 23). After getting fully tively visit the nodes of TP at least once when B < 2n.
charged at S, r follows the path in TP to reach vi to continue The not-yet-visited nodes of TP (or cells of P ) are visited
the DFS traversal. in Q0 (r) in the same order as in Q∞ (r).
At any cell of P (node of TP ), if it has a unvisited neighbor Proof: Consider the paths in Q0 (r) when B = ∞. In
cell in the next contour (child node in TP ), then r moves to this case, instead of stopping the DFS traversal at some node
that cell. Otherwise, r retreats back to the parent node cell of α and make a round trip to S from α, each subsequent paths
its current cell in TP (lines 18 − 19). During the exploration, continue their traversal without this stoppage. This simulates
anytime r realizes that it has just enough energy remaining essentially the behavior of r when B = ∞ giving Q∞ (r)
Bremain to reach back to S, it does so by visiting the parent and hence the nodes of TP (or cells in P ) are visited in the
same order in both (except the nodes visited in the roundtrip the robot size L×L, a simple adaptation of the analysis again
to S from the stopped node α). gives 10-approximation for O NLINE CPPA LG for L > 1. The
Theorem 2 (Correctness): O NLINE CPPA LG completely correctness analysis remains unchanged. t
u
covers the environment P .
Proof: When P is known a priori, r can visit all VI. E VALUATION
the reachable cells in P with an unlimited budget. If P
is unknown but B = ∞, it is also known that through Settings. We have implemented the proposed algorithm
a DFS traversal, each reachable cell of P is guaranteed O NLINE CPPA LG using Java programming language on a
to be visited where the traversal path is represented by desktop computer with an Intel i7-7700 CPU and 16GB
Q∞ (r) = {S, v1 , v2 , . . . , vl }. We have proved in Lemma RAM. The robot size L is set to 1. We have created
1 that when P is unknown but B < 2n, the nodes of TP five different environments with both convex and concave
are visited in the same order. This immediately provides the obstacles in them. The test environments are of the same
guarantee that all reachable cells of P will be visited by r. dimension – 8 × 8 (l = 8). The budget B is set to 4l (unless
Hence, proved. otherwise mentioned), i.e., four times the size of each side of
the environment. Note that this is the lowest possible budget
Approximation Ratio. We prove the following theorem. to completely cover the environment. The charging station S
Theorem 3 (Approximation): O NLINE CPPA LG achieves is placed at the left-bottom corner in every test environment.
10-approximation for both performance metrics – the number These environments are shown in Fig. 4 (Conf1 to Conf5).
of paths and the total lengths of the paths. Empirically, we have mainly focused on three metrics to
Proof: Let T be a tree of depth at most bB/2c. Let r evaluate the quality of the proposed algorithm: 1) time to
be a robot with energy budget at least B. After r starts from cover the environment, 2) total path length traversed by
S to visit the nodes of T , due to the limited energy budget, the robot, and 3) approximation ratio. We also compare
r may need to stop the coverage of T and visit the charging our results against the current state-of-the-art algorithm that
station S again before rest of the nodes in T can be covered. solves O NLINE CPP under energy constraint [16].
Let OP T be the DFS exploration strategy for r that Results. First we empirically verify the theoretically-proved
consists of the minimum number of routes, i.e., the minimum constant-factor approximation bound. Let n denote the num-
number of times r needs to visit S before T is completely ber of reachable cells in the environment. Then M IN = 2n B
covered. Let ALG be the DFS exploration strategy that visits will indicate the absolute minimum number of paths required
the nodes of T (starting from S) using a DFS traversal where by the robot to completely cover the environment [16], [20].
length of each route is bounded by B. As soon as the battery No optimal DFS strategy (OP T ) can guarantee a better
is fully charged at S, in the next route, r directly goes to approximation bound than M IN . Here, we compare our
the node of T where it stopped the DFS traversal in the last experimental result against M IN as a comparison against
route and continues covering the unvisited nodes of T . For any OP T cannot make our empirical approximation bound
any tree T of depth bB/2c and any robot r of energy budget worse. The result is shown in Fig. 5(a). The state-of-the-art
at least B, we have the following result from [6] on the bound of log(B) (when L = 1) is also plotted for reference.
number of routes |QALG (r)|, of the strategy ALG, compared The figure shows that in practice, the approximation bound
to the number of routes |QOP T (r)|, of strategy OP T : is well below the 10-factor theoretical worst-case bound.
|QALG (r)| ≤ 10 · |QOP T (r)|. Moreover, let l(QALG (r)) Also, in all of the test environments, our proposed algorithm
be the total length traversed by r while using the strategy outperforms the state-of-the-art log(B)-approximation [16].
ALG. Let l(OP T (r)) be the optimal length traversed by r. As we are minimizing the total path length travelled
Again from [6], we have that l(QALG (r)) ≤ 10·l(OP T (r)). by the robot to completely cover the environment, we are
The above results are interesting meaning that the bounds interested to compare this metric for our algorithm against
hold for any arbitrary DFS traversal Q(r) of T by r. That the algorithm in [16]. The result is shown in Fig. 5(b). It
means that the whole DFS traversal Q(r) does not need to be can be clearly observed from this plot, that our proposed
known beforehand (i.e., can be computed online not knowing algorithm outperforms the algorithm in [16] in terms of the
T in advance). Moreover, each route can be constructed travelled path length – by an average ratio of 2.03 while the
without any knowledge on the yet unvisited part of T . maximum ratio is 2.53 (Conf3).
We now discuss how the two results can be adapted to Next we are interested to investigate the effect of changing
prove the same bounds for O NLINE CPPA LG. Consider a the budget amount on the travelled path length. In order to
DFS traversal Q∞ (r) of P (or equivalently TP ) by r when do this, we vary B between {4l, 6l, 8l}. The result is shown
B = ∞. We have from Lemma 1 that the routes in Q0 (r) in Fig. 6(a). With higher budget, r could cover more cells in
visit the not-yet-visited nodes of P in the order same as in one path than with a lower budget. This fact is also reflected
Q(r). Moreover, the tree map TP of P formed during the in the plot where travelled path length is higher with lower
exploration is of depth at most bB/2c. Therefore, |Q0 (r)| ≤ budget and vice-versa. Similarly, when the budget is higher
10 · |QOP T (r)| and l(Q0 (r)) ≤ 10 · l(OP T (r)). and r is covering more cells in a single path, it needs to come
Proof of Theorem 1: Theorems 2 and 3 prove Theorem 1 back to the charging station less often and consequently, the
for L = 1. Since the cells are decomposed proportional to total number of paths also reduces. This can be observed
 8 8 8 8 8
7 7 7 7 7
6 6 6 6 6
5 5 5 5 5
Latitude

Latitude

Latitude

Latitude

Latitude
4 4 4 4 4
3 3 3 3 3
2 2 2 2 2
1 1 1 1 1
0 0 0 0 0
0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8
Longitude Longitude Longitude Longitude Longitude

Fig. 4. An illustration of five different configurations (Conf1 to Conf5) and the paths followed by r using O NLINE CPPA LG. The obstacles are represented
with ‘x’. S is in the bottom-left corner cell. When plotted, later paths have been given higher priority and they are shown in the foreground.

4 450

3.5 400
ONLINECPPALG
Log-approx. algo.
is also submitted.
Total Path Travelled (m.)
3 350
Approximation

Our proposed
Log(B)-approximation
VII. C ONCLUSION AND F UTURE W ORK
2.5 300
MIN
2 250 We have presented an algorithm for O NLINE CPP by an
1.5 200 energy-constrained robot achieving 10-approximation, im-
1 150 proving significantly on the state-of-the-art O(log(B/L))-
0.5
Conf1 Conf2 Conf3 Conf4 Conf5
100
Conf1 Conf2 Conf3 Conf4 Conf5 approximation [16]. It is also simpler to implement compared
Test Environments Test Environments
to [16]. Our simulation results validate the approximation
(a) (b) bound established theoretically. We have empirically shown
Fig. 5. a) Empirical validation of the constant-factor approximation
on different environment configurations; b) Comparison of path lengths that our proposed approach outperforms the state-of-the-art
travelled by the robot using our algorithm and the algorithm in [16]. algorithm both in terms of run time and total traversal cost
for the complete coverage. In the future, we plan to test our
250
B=4l
7
B=4l
algorithm in a real-world setting.
B=6l 6 B=6l
Total Path Travelled (m.)

200 B=8l B=8l R EFERENCES

Number of paths

5
150 4 [1] D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook. The
3
Traveling Salesman Problem: A Computational Study. Princeton
100
University Press, Princeton, NJ, USA, 2007.
2
50
[2] P. Brass, A. Gasparri, F. Cabrera-Mora, and J. Xiao. Multi-robot tree
1 and graph exploration. In ICRA, pages 495–500, 2009.
0 0 [3] Y. Choi, T. Lee, S. Baek, and S. Oh. Online complete coverage
Conf1 Conf2 Conf3 Conf4 Conf5 Conf1 Conf2 Conf3 Conf4 Conf5
Test Environments Test Environments
path planning for mobile robots based on linked spiral paths using
constrained inverse distance transform. In IROS, pages 5788–5793,
(a) (b) 2009.
Fig. 6. Varying the budget: a) Comparison of travelled path lengths; b) [4] H. Choset. Coverage of known spaces: The boustrophedon cellular
Comparison of total number of paths (i.e., number of visits to S). decomposition. Auton. Robots, 9(3):247–253, Dec. 2000.
[5] H. Choset. Coverage for robotics–a survey of recent results. Annals
of mathematics and artificial intelligence, 31(1-4):113–126, 2001.
[6] S. Das, D. Dereniowski, and P. Uznanski. Brief announcement: Energy
in Fig. 6(b). On average, r visited S 2.30 times more with constrained depth first search. In ICALP, pages 165:1–165:5, 2018 (A
B = 4l than with B = 8l. full version in http://arxiv.org/abs/1709.10146).
[7] P. Fraigniaud, L. Ga̧sieniec, D. R. Kowalski, and A. Pelc. Collective
tree exploration. Netw., 48(3):166–177, 2006.
16 [8] Y. Gabriely and E. Rimon. Spanning-tree based coverage of continuous
14 areas by a mobile robot. Annals of Mathematics and Artificial
Intelligence, 31(1-4):77–98, May 2001.
12
Run time (ms.)

[9] E. Galceran and M. Carreras. A survey on coverage path planning for

10 ONLINECPPALG
robotics. Robot. Auton. Syst., 61(12):1258–1276, Dec. 2013.
Log-approx. algo. [10] E. González, O. Álvarez, Y. Dı́az, C. Parra, and C. Bustacara. Bsa: A
8
complete coverage algorithm. ICRA, pages 2040–2044, 2005.
6 [11] G. Laporte. The vehicle routing problem: An overview of exact and
approximate algorithms. European Journal of Operational Research,
4
59(3):345–358, 1992.
2 [12] C.-L. Li, D. Simchi-Levi, and M. Desrochers. On the distance
Conf1 Conf2 Conf3 Conf4 Conf5 constrained vehicle routing problem. Oper. Res., 40(4):790–799, 1992.
Test Environments
[13] R. Mannadiar and I. M. Rekleitis. Optimal coverage of a known
Fig. 7. Runtime comparison against the log-approximation algorithm [16]. arbitrary environment. ICRA, pages 5525–5530, 2010.
[14] S. Mishra, S. Rodrı́guez, M. Morales, and N. M. Amato. Battery-
constrained coverage. In CASE, pages 695–700, 2016.
Next we are interested to investigate the run time of the [15] V. Nagarajan and R. Ravi. Approximation algorithms for distance
proposed algorithm. We also compare this metric against constrained vehicle routing problems. Netw., 59(2):209–214, 2012.
[16] G. Sharma, A. Dutta, and J.-H. Kim. Optimal online coverage path
the algorithm proposed in [16]. The result is shown in Fig. planning with energy constraints. In AAMAS, 2019 (Accepted).
7. On average, our algorithm is shown to be 2.74 times [17] I. Shnaps and E. Rimon. Online coverage of planar environments by
faster than [16] while the maximum ratio is 5.80 (Conf1). a battery powered autonomous mobile robot. IEEE Trans. Automation
Science and Engineering, 13(2):425–436, 2016.
Finally, the paths followed by r in different environment [18] G. P. Strimel and M. M. Veloso. Coverage planning with finite
configurations are shown in Fig. 4; a video of the simulation resources. In IROS, pages 2950–2956, 2014.
 [19] M. Wei and V. Isler. Coverage path planning under the energy
constraint. In ICRA, pages 368–373, 2018.
[20] M. Wei and V. Isler. A log-approximation for coverage path planning
with the energy constraint. In ICAPS, pages 532–539, 2018.

View publication stats