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








A Constant-Factor Approximation Algorithm for Online 
Coverage Path Planning with Energy Constraint
    Ayan Dutta, Gokarna Sharma
A. Dutta is with the School of Computing, University of North Florida, Jacksonville, FL 32224, USA
a.dutta@unf.edu G. Sharma is with the Department of Computer Science,
Kent State University, Kent, OH 44242, USA
sharma@cs.kent.edu


    December 30, 2023
=======================================================================================================================================================================================================================================================================

empty
empty


In this paper, we study the problem of coverage planning by a mobile robot with a limited energy budget. The objective of the robot is to cover every point in the environment while minimizing the travelled path length. The environment is initially unknown to the robot. Therefore, it needs to avoid the obstacles in the environment on-the-fly during the exploration. As the robot has a specific energy budget, it might not be able to cover the complete environment in one traversal. Instead, it will need to visit a static charging station periodically in order to recharge its energy. To solve the stated problem, we propose a budgeted depth first search (DFS)-based exploration strategy that helps the robot to cover any unknown planar environment while bounding the maximum path length to a constant-factor of the shortest-possible path length. Our O(1)-approximation guarantee advances the state-of-the-art of log-approximation for this problem. 
Simulation results show that our proposed algorithm outperforms the current state-of-the-art algorithm both in terms of the travelled path length and run time in all the tested environments with concave and convex obstacles.




§ INTRODUCTION


Coverage planning is the task of finding a path or a set of paths to cover all the points in an environment <cit.>. In robotics, this problem has many potential real-world applications including autonomous sweeping, vacuum cleaning, and lawn mowing. In an online version of the problem, the area of interest is initially unknown to the robot. Therefore it needs to discover and avoid the unknown obstacles in the environment while covering all the points in the free space by traveling as minimum distance as possible <cit.>. 

Traditionally, this problem has been studied assuming that the robot has an unlimited energy budget, where given a robot, a single
path can be planned to cover the given environment. 
The  offline version of the problem where the robot(s) have a priori knowledge of the environment including obstacles has been well studied, e.g., see <cit.>. Many algorithms have been proposed such as the boustrophedon decomposition
based coverage <cit.>, the spiral path coverage
<cit.>, and the spanning-tree based coverage
<cit.>. 
These techniques can also be adapted to solve online coverage planning <cit.>. 

In practice however, the robots do not have unlimited energy available. Therefore, even covering a standard-size environment (e.g., a farm) while simultaneously using on-board sensors (e.g., camera) becomes prohibitive with a single charge. A battery-powered robot needs to return to the charging station to get recharged before the battery runs out. Due to practical relevance, in the recent years, there has been a significant volume of work on the energy-constrained coverage planning problem  <cit.>. 
The offline version of the problem, denoted as , is studied in  <cit.> and the online version, denoted as , is studied in <cit.>. 
The state-of-the-art algorithm for  is due to <cit.>, which provides O(1)-approximation. For , the state-of-the-art algorithm is due to <cit.>, which provides  O(log (B/L))-approximation, where B is the energy budget and L is the size of the robot (assuming a L × L square robot). 
Our goal in this paper is to provide a better approximation algorithm for , i.e., to reduce the O(log (B/L))-approximation of <cit.> to O(1). 
This will show that asymptotically there is no approximation gap between  and . 

Our proposed algorithm covers an unknown environment through a DFS traversal approach tailored for the limited energy budget B. Robot r performs a depth first search traversal while building a tree map of the environment on-the-fly. It returns to the charging station to get its battery fully recharged (stopping the DFS exploration) when the path length of the traversal becomes at most B. 

After the battery is fully charged, r then moves to the cell where it stopped the DFS process, and continues traversing P.  
Simulation results show that our proposed algorithm is up to 5.80 times faster and up to 2.53 times less costlier (in terms of traversed path length) than the state-of-the-art algorithm <cit.>.















Contributions.




Initially, the robot is at the charging station S that is inside P.

The robot is equipped with an obstacle detection sensor (e.g., laser rangefinder) as well as position sensor (e.g., GPS). 
The robot is represented as a square  L × L that moves rectilinearly in P (the environment is discretized into cells forming a 4-connected grid). Initially, the robot is at the charging station S that is inside P. 
The robot has sufficient on-board memory to store information necessary to facilitate the coverage process.  

The energy consumption of the robot is assumed to be proportional to the distance travelled, i.e., the energy budget of B allows the robot to move B units distance
[We do not consider the charging time of the battery  since this delay does not impact the cost related to these metrics.].  
The robot has to go back to the charging
station S to get its battery recharged before it runs out of it. 
It is assumed that the size of P is such that the robot cannot fully cover P in a single path with budget B. 


The goal of  is to find a set of paths ={_1,…,_k} for the robot such that 


  * Condition (a): Each path _i starts and ends at S 

  * Condition (b): Each path _i has length l(_i)≤ B 

  * Condition (c): 
The paths in  collectively cover the environment P, i.e., ∪_i=1^n_i=P, 




and the following two performance metrics are optimized:  


  * Performance metric 1: The number of paths 
in , denoted as ||, is minimized, and

  * Performance metric 2: The total lengths of the paths in , denoted as l()=∑_i=1^n l(_i), is minimized. 




We establish the following main theorem for . 




Given an unknown planar polygonal environment P possibly containing obstacles and a robot r of size L× L consisting of position and obstacle detection sensors initially situated at a charging station S inside P with energy budget B, there is an algorithm that correctly solves  and guarantees 
10-approximation to both performance metrics compared to the optimal algorithm that has complete knowledge about P.  










This result clearly advances the current state-of-the-art as it improves upon the log-approximation provided in <cit.> and provides a constant-factor approximation. 
Furthermore, the proposed algorithm is easier to implement than <cit.>. 







Related Work.
The most closely related works to ours are 
<cit.>.  



Shnaps and Rimon <cit.>  proposed an 1/(1-ρ)-approximation algorithm for , where ρ is the ratio between the furthest distance between any two cells in the environment
and half of the energy budget <cit.>. 
For , they proposed an
O(B/L)-approximation algorithm. 

Wei and Isler <cit.> presented an
O(log(B/L))-approximation algorithm for , which has been improved to a constant-factor approximation by them in <cit.>. 
Recently, Sharma et al. <cit.> provided an O(log (B/L))-approximation algorithm for . 
In this paper, we improve upon the log-approximation bound and provide the O(1)-approximation to . 




The other related work is the coverage of a graph. The goal is to design paths to visit every vertex of the given graph. Without energy constraints, it becomes the well-known Traveling Salesperson Problem (TSP) <cit.> and a DFS traversal provides a constant-approximation of the TSP. With energy constraints, this coverage problem becomes the Vehicle Routing
Problem (VRP) <cit.>. One version of VRP is the Distance Vehicle Routing Problem (DVRP), which models the energy consumption proportional to the distance travelled.
For DVPR on tree metrics, Nagarajan and Ravi <cit.>
proposed a 2-approximation algorithm. Li et al. <cit.> used a TSP-partition method and their algorithm has a similar approximation to the work in <cit.>. Most of these work studied the offline version 
so that pre-processing on the environment can be done prior to exploration obtaining better approximation. This is also the case in the algorithm of <cit.> for . 

Coverage with multiple robots has also received a lot of attention (e.g., see <cit.>). In some cases, the paths planned for a single robot
under energy constraints can also be executed by multiple robots by assigning the planned paths to the robots, without affecting the total cost. In this paper, we consider coverage planning with a single robot. 




§ PROBLEM SETUP


In this paper, we use the same model as in <cit.>.



Environment. The environment P is a planar polygon containing a single charging station S inside it. 
P may possibly contain polygonal, static obstacles. 
See left of Fig. <ref> for an illustration of P with an obstacle O_1. 
The environment P is discretized into cells forming a 4-connected grid. 



Robot. We consider the robot r to be initially positioned at the charging station S. r has size L× L that it fits within a grid-cell in P. 
The robot r moves rectilinearly in P, i.e., it may move to any of the four neighbor cells (if the cell is not occupied by an obstacle) from its current cell.  
We also assume that r has the knowledge of the global coordinate system through a compass on-board, that means it knows left (West), right (East), up (North), and down (South) cells consistently from its current cell. 
Robot r is equipped with a position sensor (e.g., GPS) and an obstacle-detection sensor (e.g., laser rangefinder). We assume that with the laser rangefinder, the robot can detect obstacles in any of its neighbor cells. 
The robot has sufficient on-board memory to store information necessary to facilitate the coverage process. 
Moreover, we assume that initially r does not have any knowledge about P, i.e., P is an unknown environment. For the feasibility of covering all cells of P, we assume that P is as big as a circle of radius ⌊ B/2⌋ with center at S. It is assumed that the energy consumption of the robot is proportional to the distance travelled, i.e., the energy budget of B allows the robot to move B units distance.

A path (route) _i is a list of cells that r visits starting and ending with S. 
Notice that if there are some obstacles within P located in such a way that they divide P into two sub-polygons P_1 and P_2 with P_1 and P_2 sharing no common boundary, then r cannot fully cover P. Therefore, we assume that there is no such cell c in P. That means, there is (at least) a route from S to any obstacle-free cell of P. 

We call a cell free if it is not occupied by an obstacle. We call a cell reachable if it satisfies the definition below. 

We now prove the correctness lemma below that all free cells of P that are reachable from the base point S by a cable of length L  are covered by r. 

The reachability definition for a cell in P comes from Observations <ref> and <ref> as follows.




Any cell c in P is called reachable by the robot r, if and only if 
(a) it is a free cell,
(b) it is within distance ⌊ B/2⌋ from S, and 
(c) there must be at least a route of consecutive free cells from S to c.







. 
The problem is formally defined as follows.

Given an unknown planar polygonal environment P possibly containing obstacles with a robot r having battery budget of B initially positioned at a charging station S inside P,  is for r to visit all the reachable cells of P  through a set of paths  so that 


  * Conditions (a)–(c) are satisfied, and 

  * Performance metrics (1) and (2) are minimized.






Following <cit.>, we measure the efficiency of any algorithm for  in terms of approximation ratio which is the worst-case ratio of the cost of the online algorithm for some environment P over the cost of the optimal, offline algorithm for the same environment. 








An algorithm solving  is k-competitive if the cost of solving any instance p of the problem does not exceed k times the cost of solving p using an optimal algorithm.






§ PROCESSING UNKNOWN ENVIRONMENT






In this section, we discuss how the robot decomposes the environment into square grid cells and then construct a tree map of the environment on-the-fly.



Decomposition of the Environment. 


Following <cit.>, we decompose the environment P into square cells of size L × L, which is the size of the robot itself. 



An equi-distance contour is a poly-line where the cells on it has the same distance to/from the base point S (the left of Fig. <ref>). The cells on a contour can be ordered from one side to the other.

Let c be a cell and C be a contour. Let d(c) denote the distance to S from c and let d(C) denote the distance to S from C. If d(C_j)=d(C_i)+1, we say that contour C_j is contour C_i's next contour. The contour C with d(C)=1 is called the first contour. Each cell in a contour has at most 4 reachable cells from S that are its neighbors.


Notice that since P is unknown, the information about contours is not provided a priori and the robot r has to determine these contours on-the-fly while under coverage. The robot uses its position sensor to determine for the cell (it is currently positioned) in which contour the cell belongs to and also the at most 4 neighboring cells (that are not occupied by obstacles). The robot r can do this as follows. Since it has a position sensor with respect to S (which works as an origin of the coordinate system). It will measure its Manhattan distance. Consider the cell 12 on the top row in the middle of Fig. <ref>. When the robot is at cell 12, it considers a horizontal line passing through S and the vertical line passing through cell 12. This gives the information for r that the current position is 12. 



This method works if the horizontal and vertical lines passing through S do not intersect any obstacle present P. If intersection happens, then r  uses the approach as described in Fig. <ref> to appropriately modify in which contour they belong. This is needed since otherwise the algorithm we design may not visit those cells and the full coverage of P is not achieved. In the left of Fig. <ref>, since the horizontal line passing through S intersects obstacle O_1, the number of the cells based on pure distances from S is problematic for the cells on the right of O_1 (the cells numbered 6, 7 to 7, 8 bottom to top). This is because the DSF never visits those cells. The robot r detects the situation based on the obstacle sensor and corrects the numbering on-the-fly handing the issue (the right of Fig. <ref>). 



the next paragraph needs modifications
why do we need this para? We are never using the concept of split cells. Suggesting to remove this whole para. We define a notion of split cell similar to Wei and Isler <cit.>.
A split cell is a cell on a contour which is adjacent to the boundary (obstacle boundary or perimeter of P) and not on the endpoints of the contour. Let v be
a split cell on a contour C. Based on C's next contour, there
are two types of split cells: (i) From v the next contour splits
into two segments, and (ii) Two
contour segments merge into one at v. For example the middle cell 7 in the rightmost part of Fig. <ref> is a split cell as it splits contour 9 and above. We omit further discussion on this for brevity but can be found in  Wei and Isler <cit.>. 







Constructing a Tree Map.



Initially, the robot r is placed at the fixed charging station S. In this case, the tree, denoted by T_P, has only one node S, which we call the root of T_P. If there is no obstacle in P, each cell except the boundary cells of P will have exactly four neighbor cells. 




Robot r picks the first free cell c_1 according to a clockwise ordering of its neighbors starting from the west and ending in the south neighbor cell. r then inserts it into T_P as a child of S. If the cell labeled West is a reachable cell, then r picks that cell. Otherwise, it goes in order of North, East, and South until it finds the first cell that is reachable. 
We now have two nodes in T_P={S,c_1}, with c_1 as a child node of S.  Furthermore, c_1 is a cell in the first contour C_1. 


Since r is building T_P while exploring P, it will move to c_1 after it is included as a child in T_P. The robot r then again repeats the process of building T_P from its current cell c_1. While at c_1, r is only allowed to add one of the neighboring cells of c_1 that are in the second contour C_2 (i.e., d(C_2)=2) as a child of c_1. For this, r will include a neighboring cell c_2 of c_1 in T_P only if c_2 is a cell in contour C_2. 
Furthermore, if some cell is already a part of T_P, then this cell will not be included in T_P again. 

This process will then continue. The right of Fig. <ref> provides an illustration of the tree map T_P developed for the environment P shown on the left.  

Essentially, any edge of T_P connects two cells c_i,c_i+1 of P such that c_i∈ C_i and c_i+1∈ C_i+1, for 0≤ i≤⌊ B/2L⌋-1; in Fig. <ref>, each cell of contour C_i on the environment P on the left are at depth i in T_P shown on the right.  
Therefore, using this approach, all the cells in the first contour C_1  will be children of S (the root of T_P), all the cells in the second contour C_2 will be children of the nodes of T_P that are cells in the first contour C_1, and so on. 





The following two lemmas are immediate. 



In tree T_P,final, each cell c ∈ C_x is positioned at depth x. Furthermore, any non-leaf node of T_P,final has at least one and at most four children nodes.  





Follows easily from construction of T_P since the cells at contour C_x become the children of the cells of contour C_p such that p=x-1, for 1≤ x≤⌊ L/D⌋.   






For complete coverage, the corresponding tree map (T_P,final) of any unknown polygonal environment P, will have Depth(T_P,final)≤⌊ B/2L⌋.  





This lemma follows combining the results of Observation <ref> and Lemma <ref>. 






 §.§ Partitioning the Tree Map into Levels



We denote a level of the tree T_P by i. To be able to partition T_P into levels, it is not required that T_P is known a priori. This helps in partitioning T_P into levels incrementally on-the-fly while under coverage. We guarantee that this does not have effect on how partitioning is obtained. This guarantee makes easy to run the algorithm for any unknown polygonal P  containing obstacles.   
Our goal is to partition T_P into levels proportional to B/L (for simplicity, we assume L=1 in the description below which works even if L>1). 

Figure  <ref> provides an illustration on how T_P is partitioned into levels, where D_1,D_2,…,D_i,… denote the level boundaries and all the nodes of T_P from D_i to D_i+1 are considered the nodes of level-i.  
Each level i of T_P is a set of nodes  which are located at certain depth in T_P. 
We can also say that a level i is defined starting from a contour (say C_start,i) and ending at the counter (say C_end,i) such that d(C_start,i)≤ d(C_end,i).
All the nodes of T_P starting from C_start,i and ending at C_end,i are called the level-i nodes of T_P.  All the nodes of T_P at contour C_start,i
are called the level-i roots of T_P. Level-i roots are denoted by a set N_i={v_1i,v_2i,…}.  





According to this definition, 
it is easy to see that the first level (level-1) consists of the root of T_P, which is the charging station S, and the nodes of T_P up to depth D_2 (excluding the nodes of T_P at depth D_2). Therefore, the starting contour C_start,1 for level 1 is S. We say C_start,1 is D_1 which is 0. At the charging station S, the energy budget is B. 
We say that the starting contour C_start,2 for level 2 is at depth ⌈ B-(1-γ) B ⌉ from S, where 

0<γ<1; we will set the value of γ later. We denote C_start,2 by D_2. 


All the nodes of T_P from contour D_1 to D_2 are called the level-1 cells. Furthermore, all the cells at contour D_2 are called level-2 roots.   


We say that the starting contour C_start,3 for level 2 is at depth ⌈ B-(1-γ)^2 B_1 ⌉ from S. We denote C_start,3 by D_3. 
All the nodes of T_P from  D_2 to contour D_3 are called the level-2 cells. Furthermore, all the cells at contour D_3 are called level-3 roots.   

This definition then extends to any level i, i>2. For any level-i, the starting and the end contours are C_start,i=D_i and C_end,i=D_i+1, respectively, and all the cells from contour D_i to contour D_i+1 are 
called the level-i cells and the cells in contour D_i+1 are called level-(i+1) roots.


The energy budget for the robot at any level-i root is B_i= (B-D_i), where D_i is the depth of the root level of the level-i. This can also be directly computed using the following formula B_i=(1-γ)^i-1B; we provide the proof of this below which will help in proving a bound on the number of levels in Lemma <ref>. 



For any i≥ 0, B_i+1=B- (1-γ)^i B.


We prove this lemma by induction. We use two variables D_i and B_i, where D_i denotes the depth of level-i from the root of T_P 
and B_i denotes the energy budget for level-i for the root of that level.   
We have that for level-1, D_1=0 and B_1=B. For any level-i, i>1, D_i=D_i-1+γ B_i-1, where B_i-1=B-D_i-1.

We argue through induction that, for any i≥ 1, D_i=B-(1-γ)^i-1 B. For i=1, D_1=B-(1-γ)^0 B=0, which is trivially true and serves as the base case. 
Assuming that  D_i=B-(1-γ)^i-1 B holds for some i>1, we now show that D_i+1=B-(1-γ)^i B, which will complete the proof. Particularly, we have that

    D_i+1    =     D_i+ γ B_i
        =     D_i+γ (B-D_i)
        =     (1-γ)D_i+γ B
        =     (1-γ) (B-(1-γ)^i-1 B) + γ B
        =     B-(1-γ)^i-1B -γ B +γ (1-γ)^i-1B +γ B 
        =     B-(1-γ)^i-1B +γ (1-γ)^i-1B
        =     B- (1-γ)^i-1B (1-γ)
        =     B- (1-γ)^i B.




We are now ready to prove the following lemma regarding the number of levels for the partitioning approach discussed above. 



When L=1, the number of levels in the tree map T_P according to the partitioning algorithm discussed above is log_1/1-γ(B/2). 


Observe that the depth of the tree map T_P cannot be more than B/2 (Lemma <ref>). Therefore, the partitioning of T_P into levels stops as soon as (1-γ)^i (B/2) ≤ 1, i.e., there is at most one contour of nodes of T_P in a level (notice that these nodes are the leaves in T_P). Therefore, setting i=log_1/1-γ(B/2), we have that (1-γ)^i B/2≤ 1 and hence we have i=log_1/1-γ(B/2) levels in T_P. 

When L>1, a simple adaptation gives log_1/1-γ(B/2L) levels. 


There is one potential problem in certain situations. Consider the environment shown in  Fig. <ref> where the horizontal line passing through S is crossing obstacle O_1. The contour numbering and constructing T_P based on contour numbers do not work as the cells in the right of O_1 may not be visited by r following Algorithm <ref> as it requires the robot to visit the cells in an increasing order of contour numbers.  
This is because the contour numbers for those cells are smaller than the contour number of the cells on North, South, and West of the obstacle. For example, see the left of Fig. <ref>.   


We solve this problem in Algorithm <ref> using an approach where the robot r detects this problem and changes the contour numbers of those cells on-the-fly. See for example the  right of Fig. <ref> that depicts how the contour numbers for the cells on the right of O_1 are updated on-the-fly by the robot. Details are omitted on how r detects the problem and solves it 
due to space constraints. 




§ ALGORITHM



In the description of the algorithm and its analysis, we assume that L=1. A simple adaptation will work when L>1.
The pseudocode is given in Algorithm <ref> and illustration of the working principle of the algorithm is given in Fig. <ref>. 



 §.§ A Naive Approach without Energy Constraint

The main idea behind our algorithm is to let r incrementally explore the environment P while simultaneously constructing a tree map T_P of P to keep track of the new frontiers that need to be visited by it. 

For simplicity, let us first consider that T_P (or P) is known a priori and r has no energy constraint (i.e., B=∞). Let _∞(r) be a route in T that visits all the nodes of T_P,  obtained performing a Depth First Search (DFS) traversal of T_P. 
Since T_P is a tree, it is known that all the nodes of T_P can be covered by 
the DFS traversal by visiting each node of T_P at most twice. Therefore, if there are n nodes in T_P, then the length of the route l((r))≤ 2n. 
Moreover, an optimal algorithm for r to traverse all n nodes of T_P must have length l(Q_OPT(r))≥ n, since r can only visit the nodes of T_P sequentially one after another using any algorithm. 
Therefore, without any energy constraint (B=∞), we have a 2-approximation algorithm. 
The 2-approximation can also be guaranteed for  when B=∞ since with the knowledge of the global coordinate system, r can visit all the nodes of T_P as if T_P is known a priori, satisfying  the length of the route l((r))≤ 2n.   



 §.§ Incorporating the Energy Constraint

Now suppose that r has energy budget B<2n. The aforementioned algorithm is not sufficient anymore since each route of r can be at most of length B.   
Therefore, r needs to return to S to get recharged before the length of the robot's path reaches B.
Our proposed algorithm uses the same idea of  performing a DFS traversal of T_P as described in the previous subsection while stopping the DFS traversal process before the route of r has length at most B. 
Let _∞(r)={S,v_1,v_2,…,v_l} be the route with respective nodes visited by r while running DFS assuming B=∞. 
Let _i(r) denote a route of r visiting the nodes of _∞(r) when B<2n. 
The goal is to obtain '(r)=(_1(r),_2(r),…,_k(r)), such that the three conditions listed in Section <ref> are satisfied.



    
  * the length of each route C(_i(r))≤ B
    
  * each route _i(r) starts and ends at S
    
  * _1(r)∪_2(r)∪…∪_k(r)=(r), i.e., the nodes visited by _i,1≤ i≤ k, should collectively cover all the nodes of T_P at least once. 



The challenge is to plan each route _i(r) in an online fashion satisfying all three criteria while minimizing both the number of paths |'(r)| and the total length of the paths l('(r)). We use the following approach: 
_1(r) starts from S and visits the nodes of _∞(r) in a sequence. As soon as _1(r) reaches to a node v_i∈_∞(r) such that (v_i,S) ≤ B_remain, it terminates the DFS traversal and returns to S. B_remain is the energy remained after each move. In route _2(r), r moves to v_i (where it stopped the DFS traversal in _1(r)) from S and continues the DFS traversal until it reaches to a node v_j∈_∞(r) from which (v_j,S) ≤ B_remain. Like last route, r then returns to S.  
This process then continues until the last node v_l∈_∞(r) is visited in some route _k(r). We later prove that using this approach,
r visits all nodes of T_P 
providing correctness and approximation guarantee claimed in Theorem <ref>. 








We call our algorithm  (shown in Algorithm <ref>). Initially, the robot r is at S with the energy budget B<2n. 
This is a special situation where v=S and B_remain=B. 
Robot r then includes the child nodes of S (in contour 1) in T_P making them child nodes of root S in T_P and moves to the leftmost child node, say v_1,left. The node v_1,left is marked visited. 
B_remain is decreased by 1 (line 21).
Robot r then moves from v_1,left to the leftmost child node v_2,left (in contour 2).  The node v_2,left is marked visited and B_remain is decreased by 1.  This process continues until at some node v_i (in some contour i), B_remain=D_v_i, where D_v_i is the distance from v_i to S in T_P. 
Robot r then returns to S following the path in T_P (line 23). After getting fully charged at S, r follows the path in T_P to reach v_i to continue the DFS traversal.

	



At any cell of P (node of T_P), if it has a unvisited neighbor cell in the next contour (child node in T_P), then r moves to that cell. 
Otherwise, r retreats back to the parent node cell of its current cell in T_P (lines 18-19). 


During the exploration, anytime r realizes that it has just enough energy remaining B_remain to reach back to S, it does so by visiting the parent nodes in the tree T_P starting from its current node.



§ ANALYSIS OF THE ALGORITHM


In this section, we provide theoretical analysis of . We first prove its correctness and then analyze the costs for the performance metrics (1) and (2). 


Correctness.

We start with the following lemma.



Let {S,v_1,v_2,…,v_l} be the order of the nodes of T_P (i.e., cells in P) visited by the DFS traversal _∞(r) when B=∞. Let '(r)={_1(r),_2(r),…, _k(r)} be the routes of r that collectively visit the nodes of T_P  at least once when B<2n. The not-yet-visited nodes of T_P (or cells of P) are visited in '(r) in the same order as in _∞(r).


Consider the paths in '(r) when B=∞. In this case, instead of stopping the DFS traversal at some node α and make a round trip to S from α, each subsequent paths continue  their traversal without this stoppage. This simulates essentially the behavior of r when B=∞ giving _∞(r) and hence the nodes of T_P (or cells in P) are visited in the same order in both (except the nodes visited in the roundtrip to S from the stopped node α).   





 completely covers the environment P.


When P is known a priori, r can visit all the reachable cells in P with an unlimited budget. 
If P is unknown but B=∞, it is also known that through a DFS traversal, each reachable cell of P is guaranteed to be visited where the traversal path is represented by _∞(r)={S,v_1,v_2,…,v_l}. 

We have proved in Lemma <ref> that when P is unknown but B < 2n, the nodes of T_P are visited in the same order. This immediately provides the guarantee that all reachable cells of P will be visited by r. Hence, proved.




Approximation Ratio. We prove the following theorem. 



 achieves 10-approximation for both performance metrics – the number of paths and the total lengths of the paths.


Let T be a tree of depth at most ⌊ B/2⌋. Let r be a robot with energy budget at least B. 
After r starts from S to visit the nodes of T, due to the limited energy budget, r may need to stop the coverage of T and visit the charging station S again before rest of the nodes in T can be covered. 

Let OPT be the DFS exploration strategy for r that consists of the minimum number of routes, i.e., the minimum number of times r needs to visit S before T is completely covered. 
Let ALG be the DFS exploration strategy 
that visits the nodes of T (starting from S) using a DFS traversal where length of each route is bounded by B. As soon as the battery is fully charged at S, in the next route, r directly goes to the node of T where it stopped the DFS traversal in the last route and continues covering the unvisited nodes of T.   
For any tree T of depth ⌊ B/2⌋ and any robot r of energy budget at least B, 
we have the following result from <cit.> on the number of routes |_ALG(r)|, of the strategy ALG, compared to the number of routes |_OPT(r)|, of strategy OPT: |_ALG(r)|≤ 10· |_OPT(r)|. 

Moreover, let l(_ALG(r)) be the total length traversed by r while using the strategy ALG. Let l(OPT(r)) be the optimal length traversed by r. 
Again from <cit.>, we have that l(_ALG(r)) ≤ 10· l(OPT(r)).

The above results are interesting meaning that the bounds hold for any arbitrary DFS traversal (r) of T by r. That means that the whole DFS traversal (r) does not need to be known beforehand (i.e., can be computed online not knowing T in advance). Moreover, each route can be constructed without any knowledge on the yet unvisited part of T. 

We now discuss how the two results can be adapted to prove the same bounds for . Consider a DFS traversal _∞(r) of P (or equivalently T_P) by r when B=∞. We have from Lemma <ref> that the routes in '(r) visit the not-yet-visited nodes of P in the order same as in (r). Moreover, the tree map T_P of P formed during the exploration is of depth at most ⌊ B/2⌋. Therefore, |'(r)|≤ 10· |_OPT(r)| and l('(r))≤ 10· l(OPT(r)).   




Proof of Theorem <ref>: Theorems <ref> and  <ref> prove Theorem <ref> for L=1. Since the cells are decomposed proportional to the robot size L× L, a simple adaptation of the analysis again gives 10-approximation for  for L>1. The correctness analysis remains unchanged. 






§ EVALUATION


Settings.
We have implemented the proposed algorithm  using Java programming language on a desktop computer with an Intel i7-7700 CPU and 16GB RAM. The robot size L is set to 1. We have created five different environments with both convex and concave obstacles in them. The test environments are of the same dimension – 8 × 8 (l=8). The budget B is set to 4l (unless otherwise mentioned), i.e., four times the size of each side of the environment. Note that this is the lowest possible budget to completely cover the environment. The charging station S is placed at the left-bottom corner in every test environment. These environments are shown in Fig. <ref> (Conf1 to Conf5). 

Empirically, we have mainly focused on three metrics to evaluate the quality of the proposed algorithm: 1) time to cover the environment, 2) total path length traversed by the robot, and 3) approximation ratio. We also compare our results against the current state-of-the-art algorithm that solves  under energy constraint <cit.>. 


Results.
First we empirically verify the theoretically-proved constant-factor approximation bound. Let n denote the number of reachable cells in the environment. Then MIN = 2n/B will indicate the absolute minimum number of paths required by the robot to completely cover the environment <cit.>. No optimal DFS strategy (OPT) can guarantee a better approximation bound than MIN. Here, we compare our experimental result against MIN as a comparison against any OPT cannot make our empirical approximation bound worse. 
The result is shown in Fig. <ref>(a). The state-of-the-art bound of log(B) (when L=1) is also plotted for reference. The figure shows that in practice, the approximation bound is well below the 10-factor theoretical worst-case bound. Also, in all of the test environments, our proposed algorithm outperforms the state-of-the-art  log(B)-approximation <cit.>. 



As we are minimizing the total path length travelled by the robot to completely cover the environment, we are interested to compare this metric for our algorithm against the algorithm in <cit.>. The result is shown in Fig. <ref>(b). It can be clearly observed from this plot, that our proposed algorithm outperforms the algorithm in <cit.> in terms of the travelled path length – by an average ratio of 2.03 while the maximum ratio is 2.53 (Conf3). 



Next we are interested to investigate the effect of changing the budget amount on the travelled path length. In order to do this, we vary B between {4l,6l,8l}. The result is shown in Fig. <ref>(a). With higher budget, r could cover more cells in one path than with a lower budget. This fact is also reflected in the plot where travelled path length is higher with lower budget and vice-versa. Similarly, when the budget is higher and r is covering more cells in a single path, it needs to come back to the charging station less often and consequently, the total number of paths also reduces. This can be observed in Fig. <ref>(b). On average, r visited S 2.30 times more with B=4l than with B=8l.



Next we are interested to investigate the run time of the proposed algorithm. We also compare this metric against the algorithm proposed in <cit.>. The result is shown in Fig. <ref>. On average, our algorithm is shown to be 2.74 times faster than <cit.> while the maximum ratio is 5.80 (Conf1). 
Finally, the paths followed by r in different environment configurations are shown in Fig. <ref>; a video of the simulation is also submitted.




§ CONCLUSION AND FUTURE WORK

We have presented an algorithm for  by an energy-constrained robot achieving 10-approximation, improving significantly on the state-of-the-art O(log(B/L))-approximation <cit.>. 
It is also simpler to implement compared to <cit.>. Our simulation results validate the approximation bound established theoretically. We have empirically shown that our proposed approach outperforms the state-of-the-art algorithm both in terms of run time and total traversal cost for the complete coverage. In the future, we plan to test our algorithm in a real-world setting.


abbrv



