A survey on coverage path planning for robotics <s> Coverage under Uncertainty <s> This paper presents a planner that determines a path such that the robot does not have to heavily rely on odometry to reach its goal. The planner determines a sequence of obstacle boundaries that the robot must follow to reach the goal. Since this planner is used in the context of a coverage algorithm already presented by the authors, we assume that the free space is already, completely or partially, represented by a cellular decomposition whose cell boundaries are defined by critical points of Morse functions (isolated points at obstacle boundaries). The topological relationship among the cells is represented by a graph where nodes are the critical points and edges connect the nodes that define a common cell (i.e., the edges correspond to the cells themselves). A search of this graph yields a sequence of cells that directs the robot from a start to a goal. Once a sequence of cells and critical points are determined, a robot traverses each cell by mainly following the boundary of the cell along the obstacle boundaries and minimizes the accumulated dead-reckoning error at the intermediate critical points. This allows the robot to reach the goal robustly even in the presence of dead-reckoning error. <s> BIB001 </s> A survey on coverage path planning for robotics <s> Coverage under Uncertainty <s> Efficient coverage of an area by a mobile vehicle is a common challenge in many applications. Examples include automatic lawn mowers and vacuum cleaning robots. In this paper a vehicle with uncertain heading is studied. Five control strategies based on position measurements available only when the vehicle intersects the boundary of the area are compared. It is shown that the performance depends heavily on the heading error. The results are evaluated through extensive Monte Carlo simulations. An experimental implementation on a mobile robot is also presented. <s> BIB002 </s> A survey on coverage path planning for robotics <s> Coverage under Uncertainty <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> BIB003 </s> A survey on coverage path planning for robotics <s> Coverage under Uncertainty <s> We present a “leap-frog” path designed for a team of three robots performing cooperative localization. Two robots act as stationary measurement beacons while the third moves in a path that provides informative measurements. After completing the move, the roles of each robot are switched and the path is repeated. We demonstrate accurate localization using this path via a coverage experiment in which three robots successfully cover a 20m x 30m area. We report an approximate positional drift of 1.1m per robot over a travel distance of 140m. To our knowledge, this is one of the largest successful GPS-denied coverage experiments to date. <s> BIB004 </s> A survey on coverage path planning for robotics <s> Coverage under Uncertainty <s> Abstract : One of the major challenges in the field of underwater robotics is the opacity of the water medium to radio frequency transmission modes, which precludes the use of a global positioning system (GPS) and high speed radio communication in underwater navigation and mapping applications. One approach to underwater robotics that overcomes this limitation is vision-based simultaneous localization and mapping (SLAM), a framework that enables a robot to localize itself, while simultaneously building a map of an unknown environment. The SLAM algorithm provides a probabilistic map that contains the estimated state of the system, including a map of the environment and the pose of the robot. Because the quality of vision-based navigation varies spatially within the environment the performance of visual SLAM strongly depends on the path and motion that the robot follows. While traditionally treated as two separate problems, SLAM and path planning are indeed interrelated: the performance of SLAM depends significantly on the environment and motion; however, control of the robot motion fully depends on the information from SLAM. Therefore, an integrated SLAM control scheme is needed?one that can direct motion for better localization and mapping, and thereby provide more accurate state information back to the controller. This thesis develops perception-driven control, an integrated SLAM and path planning framework that improves the performance of visual SLAM in an informative and efficient way by jointly considering the reward predicted by a candidate camera measurement, along with its likelihood of success based upon visual saliency. The proposed control architecture identifies highly informative candidate locations for SLAM loop-closure that are also visually distinctive, such that a camera-derived pose-constraint is probable. Results are shown for autonomous underwater hull inspection experiments using the Bluefin Robotics Hovering Autonomous Underwater Vehicle (HAUV). <s> BIB005 </s> A survey on coverage path planning for robotics <s> Coverage under Uncertainty <s> In this paper, we suggest a new way to plan coverage paths for a mobile robot whose position and velocity are subject to bounded error. Most prior approaches assume a probabilistic model of uncertainty and maximize the expected value of covered area. We assume a worst-case model of uncertainty and-for a particular choice of coverage path-are still able to guarantee complete coverage. We begin by considering the special case in which the region to be covered is a single point. The machinery we develop to express and solve this problem immediately extends to guarantee coverage of a small subset in the workspace. Finally, we use this subset as a sort of virtual coverage implement, achieving complete coverage of the entire workspace by tiling copies of the subset along boustrophedon paths. <s> BIB006
In many scenarios, the lack of an absolute localization system such as GPS makes the robot accumulate drift, and hence a growing uncertainty about its pose. Although the topological representations such as the adjacency graph are tolerant to localization error, the performance of coverage algorithms, even if using such representations, is still affected BIB002 , BIB003 . This is because the amount of coverage within a cell depends on the direction of the zigzag pattern. Recent advances in SLAM (simultaneous localization and mapping) have greatly improved robot localization. SLAM uses statistical techniques to correct the robot's pose (position and orientation) estimation. However, the problem of correcting the robot's pose while performing coverage has been only addressed in few work. [ BIB001 , propose to plan the paths of their sensor-based Morse decomposition approach by relying on the boundaries of each cell, hence minimizing the dead-reckoning error. [ BIB004 ] used a fleet of three robots, each one of them equipped with a red ball (easily detectable using standard computer vision techniques) to follow a strategic path in formation to minimize the localization error. The mentioned robot fleet is shown in Fig. 26 . The path consists of a series of steps, or leaps. In each leap, two robots are static and serve the third one as beacons, and this later one advances. The robots successively interchange their roles. Real experiments show a minimization of the localization error, reporting one of the most successful 2-dimensional coverage experiments to date. However, obstacles are not considered in this work. [ BIB005 propose an active SLAM approach to coverage path planning for ship hull inspection in a 3D scenario. The proposed algorithm drives the robot along a pre-planned coverage trajectory on Figure 26 : Three robots used for experimental evaluation of the leap-frog localization and coverage strategy. the ship hull, and during trajectory execution the robot selects candidate locations that, once revisited, can help reduce the robot's pose uncertainty. The algorithm chooses to revisit a candidate location once the pose uncertainty surpasses a userprovided threshold, and otherwise follows the preplanned path. BIB006 suggest a way to plan modified coverage paths for a mobile robot whose position and velocity are subject to bounded error. Assuming a worst-case model of uncertainty they are able to guarantee complete coverage. This guarantee comes at the cost of a longer path, since paths generated by their algorithm include retracing. Nonetheless, this work provides the first guaranteed coverage results for the case of bounded position and velocity error. In the context of marine robotics, presented a coverage path planning technique for vast, open sea areas which minimizes the robot's position uncertainty along the path. This technique is especially targeted for bathymetric mapping applications and respects application constraints such as the desire to survey in parallel tracks and to avoid turns in the target area to maximize sonar measurements quality. The method uses the saliency on an a priori map to predict how the terrain will affect the robots belief at every point on the target area. Based on this magnitude, an algorithm provided in this work computes the order in which to trace parallel tracks to cover the target area minimizing the overall uncertainty along the path. A parti-cle filter keeps track of the robot's position uncertainty 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. Exploiting critical points BIB001 On-line Polygonal and differentiable boundaries (nonrectilinear) Efficiently increases actual percent coverage achieved. Active SLAM BIB005 On-line Ship hull Decides when to revisit a salient feature when executing coverage to reduce uncertainty. Leap-frog strategy BIB004 On-line Obstacles not considered Robots in a team use each other as beacons alternatively. Modified boustrophedon paths BIB006 Off-line Planar Guarantees complete coverage under bounded position and velocity error. Low uncertainty CPP for marine surveys Off-line Marine Uses saliency to determine parallel track order and key salient points to revisit.