Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Genetic Algorithm <s> Unmanned Aerial Vehicles (UAVs) are steadily replacing conventional manned aerial vehicles in multitude of tasks. Many of those tasks can be performed more efficiently by using a coordination between a team of UAVs rather than a single UAV. In this paper problem of cooperative area coverage using team of UAVs is addressed. Digital pheromones are used to convey information about search area. UAVs communicate indirectly by depositing and sensing digital pheromones which exist in pheromone map. Two approaches for path planning using pheromone maps are proposed. First approach is based on genetic algorithm, whereas second one relies on roulette wheel selection. Both approaches are evaluated in terms of distance required to cover given percentage of the area. <s> BIB001 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Genetic Algorithm <s> This paper presents an optimized method to employ a multirotor for collecting images to generate a 3D map of an area of interest with attention to man-made structures in the area. A genetic algorithm is combined with space partitioning methods to find an optimized path to ensure complete coverage of a desired area with necessary overlap for generating a 3D map. This path provides for the collection of detailed information of man-made structures within the area and also consider areas of avoidance and adjust for problematic terrain (such as tall vegetation). The result is a flight path for a multirotor that includes waypoint, altitude, heading, and camera angle for all points along the flight path. This allows for the collection of all necessary images to produce a 3D map of the area with high resolution models of the buildings within the area. <s> BIB002 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Genetic Algorithm <s> This paper presents an optimized method to employ a team of multirotors for collecting images to generate a 3D map of an area with emphasis on special features (e.g. man-made structures) and areas of avoidance. When an area is too large to be mapped by one multirotor within its battery life, then either several flights or several multirotors need to be employed to complete the job. This paper introduces a method for equitably dividing the task of collecting images utilizing multiple vehicles to map a large area with man-made structures, which need to be mapped with high resolution. First, the number of vehicles or flights required must be determined and then the special features within the area that require more time must be considered. A parallel flood fill algorithm incorporating game theory is used to determine the best way to divide the tasking. <s> BIB003 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Genetic Algorithm <s> We propose a multi-objective optimization algorithm to allocate tasks and plan paths for a team of UAVs. The UAVs must find a target in a bounded area and then continuously communicate the target information to the ground personnel. Our genetic algorithm approach aims to minimize the mission completion time, which includes the time to find the target (area coverage) and the time to setup a communication path (network connectivity). We evaluate strategies using a data mule, a relay chain, and a novel hybrid approach to communicate with the ground personnel. The algorithm can be tuned to prioritize coverage or connectivity, depending on the mission demands. Simulation results show reduced overall mission completion times (up to 65%), with more improvement as the UAV density increases. <s> BIB004
A combination of digital pheromones and evolutionary strategies for coordination of multiple UAVs is explored by Paradzik et al. BIB001 . The workspace is decoupled in rectangular sub-regions assigned to each vehicle using a Genetic Algorithm (GA), originally proposed by Holland  . The population individuals carry information regarding the vertices' coordinates and the width/length of the rectangular sub-regions. The individuals go through the selection, the reproduction and the mutation phases for generating new individuals during the natural evolution process of the algorithm. A fitness function evaluates the best individuals (sub-regions) based on digital pheromones containing information about the region. Figure 27 shows an example of sub-region created using the GA. The authors use two pheromone flavors: search and path. Search pheromone corresponds to the uncertainty and the need for coverage of a region, while path pheromone indicates the locations that are already included in the path of some vehicle. Path pheromone is applied to prevent collisions and decrease the revisiting probability. The aerial vehicles should pursuit trajectories aiming at maximizing the amount of search pheromone, while minimizing the quantity of path pheromone. The pheromone-based GA only divides the environment and the vehicles employ back-and-forth motions to cover each sub-region. In addition, each vehicle uses the A* algorithm to plan a path from its initial location to the nearest vertex of the assigned sub-region. Considering another effort based on a GA BIB002 , a coverage path planning approach with 3D structure mapping is proposed to handle scenarios with obstacles and buildings. The area of interest is a polygon discretized as a grid containing buildings (yellow), tall vegetation (green) and forbidden flight zones (red), as shown in Figure 28a . The cells are labeled with the following values: 0 for free areas, −1 for forbidden zones or outside zones, −2 for tall vegetation that demands altitude adjustments and −3 for buildings. Using a GA, the coverage path is generated considering only the free spaces and the areas with vegetation below the altitude flight. During the path execution, adjacent cells containing buildings may be detected, triggering the 3D mapping. In this case, the vehicle stops the coverage and surrounds the building at a certain distance to photograph it, following the next steps: hovers at the current altitude (A), goes up/down according to the height of the building (B), changes the camera angle (C) and flies surrounding the building (D), as shown in Figure 28b . Once the mapping is completed, the vehicle continues the original coverage coverage path. Figure 29 illustrates a complete path avoiding forbidden flight zones, while surrounding the buildings. The approach proposed by Trujillo et al. BIB002 is extended by Darrah et al. BIB003 for coverage missions over larger areas using multiple multi-rotors. The area of interest is partitioned into equitable sub-areas to be covered by multiple vehicles or by several flights performed by a single vehicle. The partitioning method applies the flood fill algorithm integrated with game theory. In this scenario, each UAV is a player and has a starting position. These players take turns flooding the neighbor cells according to a predefined pattern in a diamond shape, as illustrated in Figure 30 . The corresponding order is from left to right, flooding the closest neighbors. The players can not flood building cells or cells previously occupied by other players. The sub-areas are not equally sized. A smaller sub-area may contain building structures to be mapped, while a larger area may present areas of avoidance. Thus, the partitioning method balances the tasks and guarantees an approximate amount of work for each assigned UAV. The coverage paths for each sub-area are obtained using an improved version of the approach proposed by Trujillo et al. BIB002 . The changes ensure that the multi-rotor's path ends as close as possible to where it started. Hayat et al. BIB004 proposed a Multi-Objective Path Planning (MOPP) with a Genetic Algorithm for Search and Rescue (SAR) missions using multiple UAVs. The mission is composed by two steps, search and response. The former one monitors an event (e.g., stationary target) by guaranteeing the whole coverage in a given area. The latter one spreads detection updates on the network. The planning task that occurs during the search phase is performed in a centralized way by the MOPP algorithm, while the time-to-complete the mission is minimized by the GA. This time comprises the period to discover the target and the period to configure a communication trajectory. Thus, the approach needs to optimize two main features, the area coverage and the network connectivity.