Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Cellular Decomposition <s> This paper surveys recent results in coverage path planning, a new path planning approach that determines a path for a robot to pass over all points in its free space. Unlike conventional point-to-point path planning, coverage path planning enables applications such as robotic de-mining, snow removal, lawn mowing, car-body painting, machine milling, etc. This paper will focus on coverage path planning algorithms for mobile robots constrained to operate in the plane. These algorithms can be classified as either heuristic or complete. It is our conjecture that most complete algorithms use an exact cellular decomposition, either explicitly or implicitly, to achieve coverage. Therefore, this paper organizes the coverage algorithms into four categories: heuristic, approximate, partial-approximate and exact cellular decompositions. The final section describes some provably complete multi-robot coverage algorithms. <s> BIB001 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Cellular Decomposition <s> Coverage Path Planning (CPP) is the task of determining a path that passes over all points of an area or volume of interest while avoiding obstacles. This task is integral to many robotic applications, such as vacuum cleaning robots, painter robots, autonomous underwater vehicles creating image mosaics, demining robots, lawn mowers, automated harvesters, window cleaners and inspection of complex structures, just to name a few. A considerable body of research has addressed the CPP problem. However, no updated surveys on CPP reflecting recent advances in the field have been presented in the past ten years. In this paper, we present a review of the most successful CPP methods, focusing on the achievements made in the past decade. Furthermore, we discuss reported field applications of the described CPP methods. This work aims to become a starting point for researchers who are initiating their endeavors in CPP. Likewise, this work aims to present a comprehensive review of the recent breakthroughs in the field, providing links to the most interesting and successful works. <s> BIB002
One of the major concerns about the CPP problem is to guarantee a complete coverage of the scenario. This is usually achieved applying cellular decomposition in the area of interest, splitting the target free space into cells in order to simplify the coverage BIB001 . In literature, there are different cellular decomposition methods and the most common used in CPP problem involving UAVs are exact and approximate cellular decomposition. Exact cellular decomposition consists of splitting the workspace into sub-areas, also known as cells, whose re-union exactly occupy the target area. These cells are usually explored by simple motions as back-and-forth. In this way, the CPP problem can be reduced to motion planning from one cell to another BIB001 . These motions are performed between adjacent cells sharing a mutual border. Considering the adjacency graph representation, nodes can denote cells, while edges can identify neighbor cells, as depicted in Figure 2 . Thus, the decomposed cells are created by sweeping a line from one side to another in the area of interest. The limits of the cells are defined by events triggered every time the sweep line crosses an obstacle boundary. The resulting decomposition can be stored as an adjacency graph and a search can be executed in order to find a connected path exploring each node only once. The final coverage path is composed of the simple motions performed inside the cells and the inter-cell connections BIB002 . There are two important exact cellular decomposition techniques worth to be mentioned: trapezoidal decomposition and boustrophedon decomposition (Boustrophedon literally refers to "the way of the ox", an analogy to the animal's motion while dragging a plow in a field.), as shown in Figure 3a ,b, respectively. The former one divides the area of interest into convex trapezoidal cells, performs back-and-forth motions and uses an exhaustive walk to determine the cells exploration sequence to fulfill the coverage. The latter one creates non-convex larger cells considering only obstacle-vertices. A sweeping line is prolonged in both ways of the obstacles and these zones are called critical points. The boustrophedon decomposition is able to diminish the amount of trapezoidal cells and minimize the coverage path length in comparison to the trapezoidal decomposition. The approximate cellular decomposition technique discretizes the area into a set of regular cells BIB001 . These regular cells usually assume a square form, but they can also be represented either in a triangle or hexagonal form. Grid-based methods can be applied over approximate areas to generate coverage paths BIB002 . The size of the cells usually fits the robots dimensions when considering coverage using land robots. However, in aerial coverage the UAVs fly at a certain altitude from the ground carrying a camera as a sensor to perform the task. In this case, the size of the cells is proportional to the footprint of the camera in the UAV, as illustrated in Figure 4a , and the grid resolution is obtained through the image requirements, such as resolution and overlapping rates, and the image sensor characteristics. The UAV coverage path is composed of a set of k waypoints {w 1 , ..., w k }. Each waypoint w i represents a navigation command to the vehicle, such as take-off, change of speed or move to a specific location, and contains information about the latitude, longitude and altitude. Since the waypoints have all the necessary localization information to guide the vehicle and the cells are proportional to the footprint of the camera, we can simplify the problem assuming that the center of each cell refers to a waypoint, as shown in Figure 4b. 