A survey on coverage path planning for robotics <s> Grid-based Methods <s> We describe the use of multiple wide-angle sonar range measurements to map the surroundings of an autonomous mobile robot. A sonar range reading provides information concerning empty and occupied volumes in a cone (subtending 30 degrees in our case) in front of the sensor. The reading is modelled as probability profiles projected onto a rasterized map, where somewhere occupied and everywhere empty areas are represented. Range measurements from multiple points of view (taken from multiple sensors on the robot, and from the same sensors after robot moves) are systematically integrated in the map. Overlapping empty volumes re-inforce each other, and serve to condense the range of occupied volumes. The map definition improves as more readings are added. The final map shows regions probably occupied, probably unoccupied, and unknown areas. The method deals effectively with clutter, and can be used for motion planning and for extended landmark recognition. This system has been tested on the Neptune mobile robot at CMU. <s> BIB001 </s> A survey on coverage path planning for robotics <s> Grid-based Methods <s> Abstract Autonomous robots must be able to learn and maintain models of their environments. Research on mobile robot navigation has produced two major paradigms for mapping indoor environments: grid-based and topological. While grid-based methods produce accurate metric maps, their complexity often prohibits efficient planning and problem solving in large-scale indoor environments. Topological maps, on the other hand, can be used much more efficiently, yet accurate and consistent topological maps are often difficult to learn and maintain in large-scale environments, particularly if momentary sensor data is highly ambiguous. This paper describes an approach that integrates both paradigms: grid-based and topological. Grid-based maps are learned using artificial neural networks and naive Bayesian integration. Topological maps are generated on top of the grid-based maps, by partitioning the latter into coherent regions. By combining both paradigms, the approach presented here gains advantages from both worlds: accuracy/consistency and efficiency. The paper gives results for autonomous exploration, mapping and operation of a mobile robot in populated multi-room environments. <s> BIB002 </s> A survey on coverage path planning for robotics <s> Grid-based Methods <s> Abs t rac t Much of the focus of the research effort in path planning for mobile robots has centred on the problem of finding a path from a start location to a goal location, while minimising one or more parameters such as length of path, energy consumption or journey time. A path of complete coverage is a planned path in which a robot sweeps all areas of free space in an environment in a systematic and efficient manner. Possible applications for paths of complete coverage include autonomous vacuum cleaners, lawn mowers, security robots, land mine detectors etc. This paper will present a solution to this problem based upon an extension to the distance transform path planning methodology. The solution has been implemented on the self-contained autonomous mobile robot called the Yamabico. <s> BIB003 </s> A survey on coverage path planning for robotics <s> Grid-based Methods <s> We describe an on-line sensor based algorithm for covering planar areas by a square-shaped tool attached to a mobile robot. Let D be the tool size. The algorithm, called Spiral-STC, incrementally subdivides the planar work-area into disjoint D-size cells, while following a spanning tree of the resulting grid. The algorithm covers general grid environments using a path whose length is at most (n + m)D, where n is the number of D-size cells and m /spl les/ n is the number of boundary cells, defined as cells that share at least one point with the grid boundary. We also report that any on-line coverage algorithm generates a covering path whose length is at least (2 - /spl epsiv/)l/sub opt/ in the worst case, where l/sub opt/ is the length of the optimal covering path. Since (n + m)D /spl les/ 2l/sub opt/, Spiral-STC is worst-case optimal. Moreover, m << n in practical environments, and the algorithm generates close-to-optimal covering paths in such environments. Simulation results demonstrate the spiral-like covering patterns typical to the algorithm. <s> BIB004 </s> A survey on coverage path planning for robotics <s> Grid-based Methods <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> BIB005 </s> A survey on coverage path planning for robotics <s> Grid-based Methods <s> Complete coverage path planning requires the robot path to cover every part of the workspace, which is an essential issue in cleaning robots and many other robotic applications such as vacuum robots, painter robots, land mine detectors, lawn mowers, automated harvesters, and window cleaners. In this paper, a novel neural network approach is proposed for complete coverage path planning with obstacle avoidance of cleaning robots in nonstationary environments. The dynamics of each neuron in the topologically organized neural network is characterized by a shunting equation derived from Hodgkin and Huxley's (1952) membrane equation. There are only local lateral connections among neurons. The robot path is autonomously generated from the dynamic activity landscape of the neural network and the previous robot location. The proposed model algorithm is computationally simple. Simulation results show that the proposed model is capable of planning collision-free complete coverage robot paths. <s> BIB006 </s> A survey on coverage path planning for robotics <s> Grid-based Methods <s> The Backtracking Spiral Algorithm (BSA) is a coverage strategy for mobile robots based on the use of spiral filling paths; in order to assure the completeness, unvisited regions are marked and covered by backtracking mechanism. The BSA basic algorithm is designed to work in an environment modeled by a coarse-grain grid. BSA has been extended to cover, not only the free cells, but also the partially occupied ones. In this paper, the concepts and algorithms used to extend BSA are introduced. The ideas used to extend BSA are generic, thus a similar approach can be used to extend most of the grid-based coverage algorithms. Finally, some simulation results that demonstrate that BSA performs a complete coverage are presented. <s> BIB007 </s> A survey on coverage path planning for robotics <s> Grid-based Methods <s> This paper presents a sensor-based online coverage path planning algorithm guaranteeing a complete coverage of unstructured planar environments by a mobile robot. The proposed complete coverage algorithm abstracts the environment as a union of robot-sized cells and then uses a spiral filling rule. It can be largely classified as an approximate cellular decomposition approach as defined by Choset. In this paper, we first propose a special map coordinate assignment scheme based on active wall-finding using the history of sensor readings, which can drastically reduce the number of turns on the generated coverage path. Next, we develop an efficient path planner to link the simple spiral paths using the constrained inverse distance transform that we introduced the first time. This planner selects the next target cell which is at the minimal path length away from the current cell among the remaining non-contiguous uncovered cells while at the same time, finding the path to this target to save both the memory and time which are important concern in embedded robotics. Experiments on both simulated and real cleaning robots demonstrate the practical efficiency and robustness of the proposed algorithm. <s> BIB008 </s> A survey on coverage path planning for robotics <s> Grid-based Methods <s> We consider the problem of planning, on the fly, a path whereby a robotic vehicle will cover every point in an initially unknown spatial environment. We describe four strategies (Iterated WaveFront, Greedy-Scan, Delayed GreedyScan and Closest-First Scan) for generating cost-effective coverage plans in real time for unknown environments. We give theorems showing the correctness of our planning strategies. Our experiments demonstrate that some of these strategies work significantly better than others, and that the best ones work very well; e.g., in environments having an average of 64,000 locations for the robot to cover, the best strategy returned plans with less than 6% redundant coverage, and took only an average of 0.1 milliseconds per action. <s> BIB009 </s> A survey on coverage path planning for robotics <s> Grid-based Methods <s> Abstract This paper presents a new approach to a time and energy efficient online complete coverage solution for a mobile robot. While most conventional approaches strive to reduce path overlaps, this work focuses on smoothing the coverage path to reduce accelerations and yet to increase the average velocity for faster coverage. The proposed algorithm adopts a high-resolution grid map representation to reduce directional constraints on path generation. Here, the free space is covered by three independent behaviors: spiral path tracking, wall following control, and virtual wall path tracking. Regarding the covered region as a virtual wall, all the three behaviors adopt a common strategy of following the (physical or virtual) wall or obstacle boundaries for close coverage. Wall following is executed by a sensor-based reactive path planning control process, whereas the spiral (filling) path and virtual wall path are first modeled by their relevant parametric curves and then tracked via dynamic feedback linearization. For complete coverage, these independent behaviors are linked through a new path linking strategy, called a coarse-to-fine constrained inverse distance transform (CFCIDT). CFCIDT reduces the computational cost compared to the conventional constrained inverse distance transform (CIDT), which applies a region growing starting from the current robot position to find the nearest unexplored cell as well as the shortest path to it while constraining the search space. As for experimental validation, performance of the proposed algorithm is compared to those of conventional coverage techniques to demonstrate its completeness of coverage, energy and time efficiency, and robustness to the environment shape or the initial robot pose. <s> BIB010
Grid-based methods use a representation of the environment decomposed into a collection of uniform grid cells. This grid representation was first proposed by BIB001 to map an indoor environment using a sonar ring mounted on a mobile robot. In this representation, each grid cell has an associated value stating whether an obstacle is present or if it is rather free space. The value can be either binary or a probability  . Typically, each grid cell is a square, but also different grid cell shapes can be used, such as triangles. As grid representations only approximate the shape of the target region and its obstacles, Choset classified grid-based methods as approximate cellular decompositions BIB005 . As a result of this approximate representation, most grid-based methods are "resolutioncomplete", that is, their completeness depends on the resolution of the grid map. Fig. 19 shows an example grid map. It is easy to create a grid map, as it can be represented as an array where each element contains occupancy information associated with a cell. On the other hand, it is simple to mark covered areas in a grid map. As a result, grid-based representations are the most widely used for coverage algorithms. Nonetheless, grid maps suffer from exponential growth of memory usage because the resolution remains constant regardless of the complexity of the environment BIB002 ]. Also, they require accurate localization to maintain the map's coherency   ]. For these reasons, grid-based coverage methods are suited for indoor mobile robot operations, as the size of the area to be covered is typically relatively small. Usually, cells in a grid map are square in shape and robot-sized.  proposed a coverage algorithm that uses a grid map in which the cells are triangles instead. The rationale behind the choice of triangular cells is that they offer a higher resolution in comparison to rectangular cells of similar size. However, the resolution of the grid can also be augmented by using finer-grained squared cells. In mobile robotics, field for which the mentioned algorithm is intended, most mobile robots are not capable of making very fine movement adjustments, and hence there is no need for ultra high resolution in coverage path planning. Therefore, the extra effort devoted to implementing a triangular grid seems not to be worthwhile. 6.1 Grid-based Coverage using the Wavefront Algorithm BIB003 presented the first gridbased method for coverage path planning. In their off-line method, they use a grid representation and apply a complete coverage path planning algorithm to the grid. The method requires a start cell and a goal cell. A distance transform that propagates a wave front from goal to start is used to assign a specific number to each grid element. That is, the algorithm first assigns a 0 to the goal and then a 1 to all its surrounding cells. Then, all the unmarked cells neighboring the marked 1 are labeled with a 2. The process repeats incrementally until the start cell is reached by the wavefront . Fig 20(a) illustrates this procedure on an example environment. Once the distance transform is calculated, a coverage path can be found by starting on the start cell and selecting the neighboring cell with the highest label that is unvisited. If two or more unvisited neighbors share the same label, one of them is selected randomly. This process to find a coverage path is equivalent to using pseudo-gradient descent from the start point on the numeric potential function constituted by the labeling, that is, following the equipotential curves from top to bottom. Fig. 20(b) shows the generated coverage path for the example environment on Fig. 20(a) . A unique feature of this coverage algorithm is that a start and a goal point can be specified. [ BIB009 introduced a generalization of the wavefront algorithm to unknown environments to achieve on-line coverage with a mobile robot. 6.2 Grid-based Coverage using Spanning Trees BIB004 proposed the Spiral-STC (Spanning Tree Coverage) algorithm, an online approach for mobile robots which consists in subdividing the workspace into a grid map and following a systematic spiral path. This systematic spiral path is generated by following a spanning tree of the partial grid map that the robot incrementally constructs using its onboard sensors. The robot is able to cover every grid cell precisely once, and travel a complete coverage path. They validate the proposal in simulation. The Spiral-STC algorithm works as follows. Two different grid cell sizes are used. Bigger cells (so called mega cells) are divided in four smaller cells, which are the same size as the robot. This is shown in Fig 21(a) . To perform coverage, the robot executes the following procedure. Starting at the current cell, the robot chooses a new travel direction by selecting the first new mega cell in the free space in anti-clockwise direction. Then, a new spanning-tree edge is grown from the current mega cell to the new one. The algorithm is called recursively. The recursion stops only when the current cell has no new neighbors (a mega cell is considered old if at least one of its four smaller cells is covered, it is considered new otherwise). As a result of this recursion, the robot moves along one side of the spanning tree until it reaches the end of the tree. At that point, the robot turns around to traverse the other side of the tree. It is worth noticing that, when coverage is completed, the robot returns to the start cell, facilitating its collection and storage. On the other hand, STC never visits any small cell twice and thus minimizes the cover time. Fig 21(b) shows an example of a coverage path generated by the Spiral-STC algorithm. that, when coverage is completed, the robot returns to the start cell. Fig 21(b) shows an example of a coverage path generated by the Spiral-STC algorithm. (a) Approximate cell decomposition in mega cells and robot-sized cells. An extension to the Spiral-STC is the Backtracking Spiral Algorithm (BSA) BIB007 , which is also an on-line approach intended for mobile robots. As an advantage in regard to the Spiral-STC algorithm, they proposed an extension to cover not only unoccupied cells, but also the partially occupied ones. This extension is based on the idea that the partially-occupied cells are part of the external ring of the spiral path. These cells are covered by a wall-following procedure. The proposed extension can be applied to most grid-based coverage algorithms. Simulation experiments validate the proposed algorithm. [ BIB008 BIB010 proposed an on-line complete coverage path planning solution based on the ideas introduced by the Spiral-STC algorithm and the BSA algorithm. They also use systematic spiral paths to achieve coverage, based on active wall finding. Nonetheless, they introduce a map coordinate assignment scheme based on the history of sensor readings to improve the time-to-completion by reducing the number of turns on the generated path. The generated spiral paths are then linked by an inverse distance transform they introduce. This proposal is validated in simulation and also with real-world experiments conducted inside a room with a mobile robot. 6.3 Neural Network-based Coverage on Grid Maps BIB006 propose to use a neural network to achieve CPP on-line targeted to a floor cleaning application. They discretize a 2D space in a grid map where the diagonal length of each grid cell is equal to the robot sweeping radius, and then a neuron is associated to each and every grid cell. Each neuron has connections to its immediate 8 neighbors. These concepts are shown in Fig. 22 .