A survey on coverage path planning for robotics
---
paper_title: Region filling operations with random obstacle avoidance for mobile robots

paper_content:

The article presents a new topic in path planning for mobile robots, region filling. which involves a sweeping operation to fill a whole region with random obstacle avoidance. The approaches for global strip filling and local path searching driven by sensory data procedures are developed. A computer graphic simulation is used to verify the filling strategy available. The research was developed from the program for the design of a robot lawn mower. However, the solution appears generic. The significance is that a problem of wide application and generic solutions for general autonomous mobile robots have been developed.
---
paper_title: Cleaning robot control

paper_content:

A small and lightweight cleaning robot powered from the AC power supply is produced for testing purposes. The robot provides a cable-length control function which prevents tangling of the cables during traveling, an ultrasonic sensor function which detects obstacles and dodges them, and a distance measuring function which makes it possible to run parallel to the wall. In a simple room with few obstacles, the robot can travel even if it does not incorporate information but in areas with complicated placement of obstacles, it is necessary to teach the robot the obstacle positions and the room size in advance. >
---
paper_title: Randomized search strategies with imperfect sensors

paper_content:

In two previous papers we explored some of the systems aspects of applying large numbers of inexpensive robots to real world applications. The concept of coverage can help the user of such a system visualize its overall function and performance in mission-relevant terms, and thereby support necessary system command control functions. An important class of coverage applications are those that involve a search, in which a number of searching elements move about within a prescribed search area in order to find one or more target objects, which may be stationary or mobile. A simple analytical framework was employed in the previous work to demonstrate that the design of a cost-effective many-robot search system can depend sensitively on the interplay of sensor cost and performance levels with mission-specific functional and performance requirements. In the current paper we extend these results: we consider additional measures of effectiveness for area search systems to provide a broader basis for a tradeoff of coordinated versus random search models, and we explore how to deliberately achieve effectively randomized search strategies that provide uniform search coverage over a specified area.
---
paper_title: Shortest Watchman Routes in Simple Polygons

paper_content:

In this paper we present an O(n4, log logn) algorithm to find a shortest watchman route in a simple polygon through a point,s, in its boundary. A watchman route is a route such that each point in the interior of the polygon is visible from at least one point along the route.
---
paper_title: Coverage Algorithms for an Under-actuated Car-Like Vehicle in an Uncertain Environment

paper_content:

A coverage algorithm is an algorithm that deploys a strategy as to how to cover all points in terms of a given area using some set of sensors. In the past decades a lot of research has gone into development of coverage algorithms. Initially, the focus was coverage of structured and semi-structured indoor areas, but with time and development of better sensors and introduction of GPS, the focus has turned to outdoor coverage. Due to the unstructured nature of an outdoor environment, covering an outdoor area with all its obstacles and simultaneously performing reliable localization is a difficult task. In this paper, two path planning algorithms suitable for solving outdoor coverage tasks are introduced. The algorithms take into account the kinematic constraints of an under-actuated car-like vehicle, minimize trajectory curvatures, and dynamically avoid detected obstacles in the vicinity, all in real-time. We demonstrate the performance of the coverage algorithm in the field by achieving 95% coverage using an autonomous tractor mower without the aid of any absolute localization system or constraints on the physical boundaries of the area.
---
paper_title: Sampling-based coverage path planning for inspection of complex structures

paper_content:

We present several new contributions in sampling-based coverage path planning, the task of finding feasible paths that give 100% sensor coverage of complex structures in obstacle-filled and visually occluded environments. First, we establish a framework for analyzing the probabilistic completeness of a sampling-based coverage algorithm, and derive results on the completeness and convergence of existing algorithms. Second, we introduce a new algorithm for the iterative improvement of a feasible coverage path; this relies on a sampling-based subroutine that makes asymptotically optimal local improvements to a feasible coverage path based on a strong generalization of the RRT* algorithm. We then apply the algorithm to the real-world task of autonomous in-water ship hull inspection. We use our improvement algorithm in conjunction with redundant roadmap coverage planning algorithm to produce paths that cover complex 3D environments with unprecedented efficiency.
---
paper_title: Approximation algorithms for lawn mowing and milling

paper_content:

We study the problem of finding shortest tours/paths for “lawn mowing” and “milling” problems: Given a region in the plane, and given the shape of a “cutter” (typically, a circle or a square), find a shortest tour/path for the cutter such that every point within the region is covered by the cutter at some position along the tour/path. In the milling version of the problem, the cutter is constrained to stay within the region. The milling problem arises naturally in the area of automatic tool path generation for NC pocket machining. The lawn mowing problem arises in optical inspection, spray painting, and optimal search planning. ::: ::: Both problems are NP-hard in general. We give efficient constant-factor approximation algorithms for both problems. In particular, we give a (3+e)-approximation algorithm for the lawn mowing problem and a 2.5-approximation algorithm for the milling problem. Furthermore, we give a simple 65-approximation algorithm for the TSP problem in simple grid graphs, which leads to an 115-approximation algorithm for milling simple rectilinear polygons.
---
paper_title: Robot control system for window cleaning

paper_content:

Window cleaning is a two-stage process; application of cleaning fluid, which is usually achieved by using a wetted applicator and removal of cleaning fluid by a squeegee blade without spillage on to other areas of the facade or previously cleaned areas of glass. This is particularly difficult for example if the window is located on the roof of a building and cleaning is performed from inside by the human window cleaner. Simulation studies were conducted to demonstrate the feasibility of a robot system to act and mimic the human operator; an end effector had to be designed to accommodate different tools such as applicator and squeegee; the pay load for tool handling, sensory feedback requirements; force and compliance control; and finally the cost of the overall system had to be feasible. As a result of the studies it was conceived that the end effector should contain a combined datuming/cleaning head. This arrangement would allow automatic datuming and location of the window pane relative to the robot using a specially designed and constructed compliant head. One advantage of a combined head being the elimination of tool changes between the datuming and wiping operation. A dedicated XYZR robot system was designed which makes use of an Industrial IBM PC connected to a DELTA-7AV systems PMAC card to drive the robot and to: coordinate its actions with those of the OCS roof mounted gantry delivery carrier system.
---
paper_title: Coverage for robotics – A survey of recent results

paper_content:

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.
---
paper_title: Measuring Coverage Performances of a Floor Cleaning Mobile Robot Using a Vision System

paper_content:

This work introduces a method and apparatus for measuring real mobile robot cleaning performances based on a dedicated vision system. The measurement method can be applied to any kind of floor cleaning mobile robot but in this work it has been applied to a proprietary design. The paper presents the analysis of the first results obtained and ends with the main conclusions.
---
paper_title: An Approximate Algorithm for Solving the Watchman Route Problem

paper_content:

The watchman route problem (WRP) was first introduced in 1988 and is defined as follows: How to calculate a shortest route completely contained inside a simple polygon such that any point inside this polygon is visible from at least one point on the route? So far the best known result for the WRP is an O(n3log n) runtime algorithm (with inherent numerical problems of its implementation). This paper gives an κ(Ɛ) × O(kn) approximate algorithm for WRP by using a rubberband algorithm, where n is the number of vertices of the simple polygon, k the number of essential cuts, Ɛ the chosen accuracy constant for the minimization of the calculated route, and κ(Ɛ) equals the length of the initial route minus the length of the calculated route, divided by Ɛ.
---
paper_title: Path Planning for Robotic Demining: Robust Sensor-Based Coverage of Unstructured Environments and Probabilistic Methods

paper_content:

Demining and unexploded ordnance (UXO) clearance are extremely tedious and dangerous tasks. The use of robots bypasses the hazards and potentially increases the efficiency of both tasks. A first cr...
---
paper_title: Uniform Coverage of Automotive Surface Patches

paper_content:

In spray painting applications, it is essential to generate a spray gun trajectory such that the entire surface is completely covered and receives an acceptably uniform layer of paint deposition; we call this the “uniform coverage” problem. The uniform coverage problem is challenging because the atomizer emits a non-trivial paint distribution, thus making the relationships between the spray gun trajectory and the deposition uniformity complex. To understand the key issues involved in uniform coverage, we consider surface patches that are geodesically convex and topologically simple as representative of subsets of realistic automotive surfaces. In addition to ensuring uniform paint deposition on the surface, our goal is to also minimize the associated process cycle time and paint waste. Based on the relationships between the spray gun trajectory and the output characteristics (i.e., uniformity, cycle time and paint waste), our approach decomposes the coverage trajectory generation problem into three subpro...
---
paper_title: Approximation Algorithms For The Geometric Covering Salesman Problem

paper_content:

Abstract We introduce a geometric version of the Covering Salesman Problem: Each of the n salesman's clients specifies a neighborhood in which they are willing to meet the salesman. Identifying a tour of minimum length that visits all neighboirhoods is an NP-hard problem, since it is a generalization of the Traveling Salesman Problem. We present simple heuristic procedures for constructing tours, for a variety of neighborhood types, whose length is guaranteed to be within a constant factor of the length of an optimal tour. The neighborhoods we consider include parallel unit segments, translates of a polygonal region, and circles.
---
paper_title: Coverage path planning: The Boustrophedon Cellular Decomposition

paper_content:

Coverage path planning is the determination of a path that a robot must take in order to pass over each point in an environment. Applica­ tions include vacuuming, floor scrubbing, and inspection. We developed the boustrophedon cellular decomposition, which is an exact cel­ lular decomposition approach, for the purposes of coverage. Each cell in the boustrophedon is covered with simple back and forth motions. Once each cell is covered, then the entire envi­ ronment is covered. Therefore, coverage is re­ duced to finding an exhaustive path through a graph which represents the adjacency relation­ ships of the cells in the boustrophedon decom­ position. This approach is provably complete and Experiments on a mobile robot validate this approach.
---
paper_title: Morse Decompositions for Coverage Tasks

paper_content:

Exact cellular decompositions represent a robot's free space by dividing it into regions with simple structure such that the sum of the regions fills the free space. These decompositions have been widely used for path planning between two points, but can be used for mapping and coverage of free spaces. In this paper, we define exact cellular decompositions where critical points of Morse functions indicate the location of cell boundaries. Morse functions are those whose critical points are non-degenerate. Between critical points, the structure of a space is effectively the same, so simple control strategies to achieve tasks, such as coverage, are feasible within each cell. This allows us to introduce a general framework for coverage tasks because varying the Morse function has the effect of changing the pattern by which a robot covers its free space. In this paper, we give examples of different Morse functions and comment on their corresponding tasks. In a companion paper, we describe the sensor-based algo...
---
paper_title: Robot Motion Planning

paper_content:

1 Introduction and Overview.- 2 Configuration Space of a Rigid Object.- 3 Obstacles in Configuration Space.- 4 Roadmap Methods.- 5 Exact Cell Decomposition.- 6 Approximate Cell Decomposition.- 7 Potential Field Methods.- 8 Multiple Moving Objects.- 9 Kinematic Constraints.- 10 Dealing with Uncertainty.- 11 Movable Objects.- Prospects.- Appendix A Basic Mathematics.- Appendix B Computational Complexity.- Appendix C Graph Searching.- Appendix D Sweep-Line Algorithm.- References.
---
paper_title: Coverage path planning algorithms for agricultural field machines

paper_content:

In this article, a coverage path planning problem is discussed in the case of agricultural fields and agricultural machines. Methods and algorithms to solve this problem are developed. These algorithms are applicable to both robots and human-driven machines. The necessary condition is to cover the whole field, and the goal is to find as efficient a route as possible. As yet, there is no universal algorithm or method capable of solving the problem in all cases. Two new approaches to solve the coverage path planning problem in the case of agricultural fields and agricultural machines are presented for consideration. Both of them are greedy algorithms. In the first algorithm the view is from on top of the field, and the goal is to split a single field plot into subfields that are simple to drive or operate. This algorithm utilizes a trapezoidal decomposition algorithm, and a search is developed of the best driving direction and selection of subfields. This article also presents other practical aspects that are taken into account, such as underdrainage and laying headlands. The second algorithm is also an incremental algorithm, but the path is planned on the basis of the machine's current state and the search is on the next swath instead of the next subfield. There are advantages and disadvantages with both algorithms, neither of them solving the problem of coverage path planning problem optimally. Nevertheless, the developed algorithms are remarkable steps toward finding a way to solve the coverage path planning problem with nonomnidirectional vehicles and taking into consideration agricultural aspects. © 2009 Wiley Periodicals, Inc.
---
paper_title: Exact cellular decompositions in terms of critical points of Morse functions

paper_content:

Exact cellular decompositions are structures that globally encode the topology of a robot's free space, while locally describing the free space geometry. These structures have been widely used for path planning between two points, but can be used for mapping and coverage of robot free spaces. In this paper, we define exact cellular decompositions where critical points of Morse functions indicate the location of cell boundaries. Morse functions are those whose critical points are non-degenerate. Between critical points, the structure of a space is effectively the same, so simple control strategies to achieve tasks, such as coverage, are feasible within each cell. In this paper, we derive a general framework for defining decompositions in terms of critical points and then give examples, each corresponding to a different task. All of the results in this paper are derived in an m-dimensional Euclidean space, but the examples depicted in the figures are 2D and 3D for ease of presentation.
---
paper_title: Coverage path planning: The Boustrophedon Cellular Decomposition

paper_content:

Coverage path planning is the determination of a path that a robot must take in order to pass over each point in an environment. Applica­ tions include vacuuming, floor scrubbing, and inspection. We developed the boustrophedon cellular decomposition, which is an exact cel­ lular decomposition approach, for the purposes of coverage. Each cell in the boustrophedon is covered with simple back and forth motions. Once each cell is covered, then the entire envi­ ronment is covered. Therefore, coverage is re­ duced to finding an exhaustive path through a graph which represents the adjacency relation­ ships of the cells in the boustrophedon decom­ position. This approach is provably complete and Experiments on a mobile robot validate this approach.
---
paper_title: Coverage Algorithms for an Under-actuated Car-Like Vehicle in an Uncertain Environment

paper_content:

A coverage algorithm is an algorithm that deploys a strategy as to how to cover all points in terms of a given area using some set of sensors. In the past decades a lot of research has gone into development of coverage algorithms. Initially, the focus was coverage of structured and semi-structured indoor areas, but with time and development of better sensors and introduction of GPS, the focus has turned to outdoor coverage. Due to the unstructured nature of an outdoor environment, covering an outdoor area with all its obstacles and simultaneously performing reliable localization is a difficult task. In this paper, two path planning algorithms suitable for solving outdoor coverage tasks are introduced. The algorithms take into account the kinematic constraints of an under-actuated car-like vehicle, minimize trajectory curvatures, and dynamically avoid detected obstacles in the vicinity, all in real-time. We demonstrate the performance of the coverage algorithm in the field by achieving 95% coverage using an autonomous tractor mower without the aid of any absolute localization system or constraints on the physical boundaries of the area.
---
paper_title: Constructing roadmaps of semi-algebraic sets I: completeness

paper_content:

Abstract This paper describes preliminary work on an algorithm for planning collision-free motions for a robot manipulator in the presence of obstacles. The physical obstacles lead to forbidden regions in the robots configuration space, and for collision-free motion we need paths through configuration space which avoid these regions. Our method is to construct a certain one-dimensional subset or “roadmap” of the space of allowable configurations. If S denotes the set of allowable configurations, the roadmap has the property that any connected component of S contains a single connected component of the roadmap. It is also possible, starting from an arbitrary point p ∈ S to rapidly construct a path from p to a point on the roadmap. Thus given any two points in S we can rapidly determine whether they lie in the same connected component of S, and if they do, we can return a candidate path between them. We do not give a complete description of the algorithm here, but we define the roadmap geometrically, and verify that it has the necessary connectivity.
---
paper_title: An opportunistic global path planner

paper_content:

A robot planning algorithm that constructs a global skeleton of free-space by incremental local methods is described. The curves of the skeleton are the loci of maxima of an artificial potential field that is directly proportional to the distance of the robot from obstacles. The method has the advantage of fast convergence of local methods in uncluttered environments, but it also has a deterministic and efficient method of escaping local extremal points of the potential function. The authors present a general algorithm, for configuration spaces of any dimension, and describe instantiations of the algorithm for robots with two and three degrees of freedom. >
---
paper_title: Efficient seabed coverage path planning for ASVs and AUVs

paper_content:

Coverage path planning is the problem of moving an effector (e.g. a robot, a sensor) over all points in a given region. In marine robotics, a number of applications require to cover a region on the seafloor while navigating above it at a constant depth. This is the case of Autonomous Surface Vehicles, that always navigate at the water surface level, but also of several Autonomous Underwater Vehicle tasks as well. Most existing coverage algorithms sweep the free space in the target region using lawnmower-like back-and-forth motions, and the inter-lap spacing between these back-and-forth laps is determined by the robot's sensor coverage range. However, while covering the seafloor surface by navigating above it at a constant depth, the sensor's field of view varies depending on the seafloor height. Therefore, to ensure full coverage one would need to use the inter-lap spacing determined by the shallowest point on the target surface, resulting in undesired coverage overlapping among the back-and-forth laps. In this work, we propose a novel method to generate a coverage path that completely covers a surface of interest on the seafloor by navigating in a constant-depth plane above it. The proposed method uses environment information to minimize the coverage overlapping by segmenting the target surface in regions of similar depth features and addressing them as individual coverage path planning problems. A cell decomposition coverage method is applied to each region. The surface gradient is used to determine the best sweep orientation in each cell, and the inter-lap spacing in the lawnmower-like paths used to cover each cell is maximized on a lap-by-lap basis, hence obtaining a shorter, more efficient coverage path. The proposal is validated in simulation experiments conducted with a real-world bathymetric dataset that show a significant increase on path efficiency in comparison with a standard boustrophedon coverage path.
---
paper_title: Morse Decompositions for Coverage Tasks

paper_content:

Exact cellular decompositions represent a robot's free space by dividing it into regions with simple structure such that the sum of the regions fills the free space. These decompositions have been widely used for path planning between two points, but can be used for mapping and coverage of free spaces. In this paper, we define exact cellular decompositions where critical points of Morse functions indicate the location of cell boundaries. Morse functions are those whose critical points are non-degenerate. Between critical points, the structure of a space is effectively the same, so simple control strategies to achieve tasks, such as coverage, are feasible within each cell. This allows us to introduce a general framework for coverage tasks because varying the Morse function has the effect of changing the pattern by which a robot covers its free space. In this paper, we give examples of different Morse functions and comment on their corresponding tasks. In a companion paper, we describe the sensor-based algo...
---
paper_title: Coverage of Known Spaces: The Boustrophedon Cellular Decomposition

paper_content:

Coverage path planning is the determination of a path that a robot must take in order to pass over each point in an environment. Applications include de-mining, floor scrubbing, and inspection. We developed the boustrophedon cellular decomposition, which is an exact cellular decomposition approach, for the purposes of coverage. Essentially, the boustrophedon decomposition is a generalization of the trapezoidal decomposition that could allow for non-polygonalobstacles, but also has the side effect of having more “efficient” coverage paths than the trapezoidal decomposition. Each cell in the boustrophedon decomposition is covered with simple back and forth motions. Once each cell is covered, then the entire environment is covered. Therefore, coverage is reduced to finding an exhaustive path through a graph which represents the adjacency relationships of the cells in the boustrophedon decomposition. This approach is provably complete and experiments on a mobile robot validate this approach.
---
paper_title: Morse Decompositions for Coverage Tasks

paper_content:

Exact cellular decompositions represent a robot's free space by dividing it into regions with simple structure such that the sum of the regions fills the free space. These decompositions have been widely used for path planning between two points, but can be used for mapping and coverage of free spaces. In this paper, we define exact cellular decompositions where critical points of Morse functions indicate the location of cell boundaries. Morse functions are those whose critical points are non-degenerate. Between critical points, the structure of a space is effectively the same, so simple control strategies to achieve tasks, such as coverage, are feasible within each cell. This allows us to introduce a general framework for coverage tasks because varying the Morse function has the effect of changing the pattern by which a robot covers its free space. In this paper, we give examples of different Morse functions and comment on their corresponding tasks. In a companion paper, we describe the sensor-based algo...
---
paper_title: Path Planning for Robotic Demining: Robust Sensor-Based Coverage of Unstructured Environments and Probabilistic Methods

paper_content:

Demining and unexploded ordnance (UXO) clearance are extremely tedious and dangerous tasks. The use of robots bypasses the hazards and potentially increases the efficiency of both tasks. A first cr...
---
paper_title: Path planning and control for AERCam, a free-flying inspection robot in space

paper_content:

This paper describes a prototype robot and the necessary path planning and control for space inspection applications. The robot is the first generation of a free-flying robotic camera that will assist astronauts in constructing and maintaining the Space Station. The robot will provide remote views to astronauts inside the Space Shuttle and future Space Station, and to ground controllers. The paper describes a planar robot prototype autonomously moving about an air bearing table, and introduces a method for determining paths in three-dimensions for efficient fuel use. Finally, the paper describes the software simulation of the path planner with the future Space Station.
---
paper_title: Sensor-Based Exploration: Incremental Construction of the Hierarchical Generalized Voronoi Graph

paper_content:

This paper prescribes an incremental procedure to construct roadmaps of unknown environments. Recall that a roadmap is a geometric structure that a robot uses to plan a path between two points in an environment. If the robot knows the roadmap, then it knows the environment. Likewise, if the robot constructs the roadmap, then it has effectively explored the environment. This paper focuses on the hierarchical generalized Voronoi graph (HGVG), detailed in the companion paper in this issue. The incremental construction procedure of the HGVG requires only local distance sensor measurements, and therefore the method can be used as a basis for sensor-based planning algorithms. Simulations and experiments using a mobile robot with ultrasonic sensors verify this approach.
---
paper_title: Morse Decompositions for Coverage Tasks

paper_content:

Exact cellular decompositions represent a robot's free space by dividing it into regions with simple structure such that the sum of the regions fills the free space. These decompositions have been widely used for path planning between two points, but can be used for mapping and coverage of free spaces. In this paper, we define exact cellular decompositions where critical points of Morse functions indicate the location of cell boundaries. Morse functions are those whose critical points are non-degenerate. Between critical points, the structure of a space is effectively the same, so simple control strategies to achieve tasks, such as coverage, are feasible within each cell. This allows us to introduce a general framework for coverage tasks because varying the Morse function has the effect of changing the pattern by which a robot covers its free space. In this paper, we give examples of different Morse functions and comment on their corresponding tasks. In a companion paper, we describe the sensor-based algo...
---
paper_title: Sensor-based coverage with extended range detectors

paper_content:

Coverage path planning determines a path that passes a robot, a detector, or some type of effector over all points in the environment. Prior work in coverage tends to fall into one of two extremes: coverage with an effector the same size of the robot, and coverage with an effector that has infinite range. In this paper, we consider coverage in the middle of this spectrum: coverage with a detector range that goes beyond the robot, and yet is still finite in range. We achieve coverage in two steps: The first step considers vast, open spaces, where the robot can use the full range of its detector; the robot covers these spaces as if it were as big as its detector range. Here we employ previous work in using Morse cell decompositions to cover unknown spaces. A cell in this decomposition can be covered via simple back-and-forth motions, and coverage of the vast space is then reduced to ensuring that the robot visits each cell in the vast space. The second step considers the narrow or cluttered spaces where obstacles lie within detector range, and thus the detector "fills" the surrounding area. In this case, the robot can cover the cluttered space by simply following the generalized Voronoi diagram (GVD) of that space. In this paper, we introduce a hierarchical decomposition that combines the Morse decompositions and the GVDs to ensure that the robot indeed visits all vast, open, as well as narrow, cluttered, spaces. We show how to construct this decomposition online with sensor data that is accumulated while the robot enters the environment for the first time.
---
paper_title: Contact sensor-based coverage of rectilinear environments

paper_content:

A variety of mobile robot tasks require complete coverage of an initially unknown environment, either as the entire task or as a way to generate a complete map for use during further missions. This is a problem known as sensor-based coverage, in which the robot's sensing is used to plan a path that reaches every point in the environment. A new algorithm, CC/sub R/, is presented here which works for robots with only contact sensing that operate in environments with rectilinear boundaries and obstacles. This algorithm uses a high-level rule-based feedback structure to direct coverage rather than a script in order to facilitate future extensions to a team of independent robots. The outline of a completeness proof of CC/sub R/ is also presented, which shows that it produces coverage of any of a large class of rectilinear environments. Implementation of CC/sub R/ in simulation is discussed, as well as the results of testing in a variety of world geometries and potential extensions to the algorithm.
---
paper_title: Smooth coverage path planning and control of mobile robots based on high-resolution grid map representation

paper_content:

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.
---
paper_title: Learning metric-topological maps for indoor mobile robot navigation

paper_content:

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.
---
paper_title: High resolution maps from wide angle sonar

paper_content:

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.
---
paper_title: Coverage for robotics – A survey of recent results

paper_content:

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.
---
paper_title: Planning Paths of Complete Coverage of an Unstructured Environment by a Mobile Robot

paper_content:

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.
---
paper_title: BSA: A Complete Coverage Algorithm

paper_content:

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.
---
paper_title: Spiral-STC: an on-line coverage algorithm of grid environments by a mobile robot

paper_content:

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.
---
paper_title: Real-Time Planning for Covering an Initially-Unknown Spatial Environment

paper_content:

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.
---
paper_title: Online complete coverage path planning for mobile robots based on linked spiral paths using constrained inverse distance transform

paper_content:

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.
---
paper_title: A neural network approach to complete coverage path planning

paper_content:

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.
---
paper_title: A quantitative description of membrane current and its application to conduction and excitation in nerve

paper_content:

This article concludes a series of papers concerned with the flow of electric current through the surface membrane of a giant nerve fibre (Hodgkinet al., 1952,J. Physiol. 116, 424–448; Hodgkin and Huxley, 1952,J. Physiol. 116, 449–566). Its general object is to discuss the results of the preceding papers (Section 1), to put them into mathematical form (Section 2) and to show that they will account for conduction and excitation in quantitative terms (Sections 3–6).
---
paper_title: A Complete Coverage Path Planning Method for Mobile Robot in Uncertain Environments

paper_content:

In this paper, a novel complete coverage path planning method based on the biologically inspired neural networks, rolling path planning and heuristic searching approach is presented for mobile robot motion planning with obstacles avoidance. The biologically inspired neural network is used to model the environment and calculate the environment information, while the rolling planning technique and the heuristic searching algorithm are utilized for the path planning,. Simulation studies show that the proposed method is very effective for the dynamic uncertain environments.
---
paper_title: A Bioinspired Neural Network for Real-Time Concurrent Map Building and Complete Coverage Robot Navigation in Unknown Environments

paper_content:

Complete coverage navigation (CCN) requires a special type of robot path planning, where the robots should pass every part of the workspace. CCN is an essential issue for cleaning robots and many other robotic applications. When robots work in unknown environments, map building is required for the robots to effectively cover the complete workspace. Real-time concurrent map building and complete coverage robot navigation are desirable for efficient performance in many applications. In this paper, a novel neural-dynamics-based approach is proposed for real-time map building and CCN of autonomous mobile robots in a completely unknown environment. The proposed model is compared with a triangular-cell-map-based complete coverage path planning method (Oh et al., 2004) that combines distance transform path planning, wall-following algorithm, and template-based technique. The proposed method does not need any templates, even in unknown environments. A local map composed of square or rectangular cells is created through the neural dynamics during the CCN with limited sensory information. From the measured sensory information, a map of the robot's immediate limited surroundings is dynamically built for the robot navigation. In addition, square and rectangular cell map representations are proposed for real-time map building and CCN. Comparison studies of the proposed approach with the triangular-cell-map-based complete coverage path planning approach show that the proposed method is capable of planning more reasonable and shorter collision-free complete coverage paths in unknown environments.
---
paper_title: Graph Planning for Environmental Coverage

paper_content:

Tasks such as street mapping and security surveillance seek a route that traverses a given space to perform a function. These task functions may involve mapping the space for accurate modeling, sensing the space for unusual activity, or searching the space for objects. When these tasks are performed autonomously by robots, the constraints of the environment must be considered in order to generate more feasible paths. Additionally, performing these tasks in the real world presents the challenge of operating in dynamic, changing environments. ::: This thesis addresses the problem of effective graph coverage with environmental constraints and incomplete prior map information. Prior information about the environment is assumed to be given in the form of a graph. We seek a solution that effectively covers the graph while accounting for space restrictions and online changes. For real-time applications, we seek a complete but efficient solution that has fast replanning capabilities. ::: For this work, we model the set of coverage problems as arc routing problems. Although these routing problems are generally NP-hard, our approach aims for optimal solutions through the use of low-complexity algorithms in a branch-and-bound framework when time permits and approximations when time restrictions apply. Additionally, we account for environmental constraints by embedding those constraints into the graph. In this thesis, we present algorithms that address the multi-dimensional routing problem and its subproblems and evaluate them on both computer-generated and physical road network data.
---
paper_title: Coverage for robotics – A survey of recent results

paper_content:

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.
---
paper_title: Uniform Coverage of Automotive Surface Patches

paper_content:

In spray painting applications, it is essential to generate a spray gun trajectory such that the entire surface is completely covered and receives an acceptably uniform layer of paint deposition; we call this the “uniform coverage” problem. The uniform coverage problem is challenging because the atomizer emits a non-trivial paint distribution, thus making the relationships between the spray gun trajectory and the deposition uniformity complex. To understand the key issues involved in uniform coverage, we consider surface patches that are geodesically convex and topologically simple as representative of subsets of realistic automotive surfaces. In addition to ensuring uniform paint deposition on the surface, our goal is to also minimize the associated process cycle time and paint waste. Based on the relationships between the spray gun trajectory and the output characteristics (i.e., uniformity, cycle time and paint waste), our approach decomposes the coverage trajectory generation problem into three subpro...
---
paper_title: Coverage path planning on three-dimensional terrain for arable farming

paper_content:

Field operations should be done in a manner that minimizes time and travels over the field surface and is coordinated with topographic land features. Automated path planning can help to find the best coverage path so that the field operation costs can be minimized. Intelligent algorithms are desired for both two-dimensional (2D) and three-dimensional (3D) terrain field coverage path planning. The algorithm of generating an optimized full coverage pattern for a given 2D planar field by using boustrophedon paths has been investigated and reported before. However, a great proportion of farms have rolling terrains, which have a considerable influence on the design of coverage paths. Coverage path planning in 3D space has a great potential to further optimize field operations. This work addressed four critical tasks: terrain modeling and representation, coverage cost analysis, terrain decomposition, and the development of optimized path searching algorithm. The developed algorithms and methods have been successfully implemented and tested using 3D terrain maps of farm fields with various topographic features. Each field was decomposed into subregions based on its terrain features. A recommended “seed curve” based on a customized cost function was searched for each subregion, and parallel coverage paths were generated by offsetting the found “seed curve” toward its two sides until the whole region was completely covered. Compared with the 2D planning results, the experimental results of 3D coverage path planning showed its superiority in reducing both headland turning cost and soil erosion cost. On the tested fields, on average the 3D planning algorithm saved 10.3% on headland turning cost, 24.7% on soil erosion cost, 81.2% on skipped area cost, and 22.0% on the weighted sum of these costs, where their corresponding weights were 1, 1, and 0.5, respectively. © 2011 Wiley Periodicals, Inc. © 2011 Wiley Periodicals, Inc.
---
paper_title: Sampling-based coverage path planning for inspection of complex structures

paper_content:

We present several new contributions in sampling-based coverage path planning, the task of finding feasible paths that give 100% sensor coverage of complex structures in obstacle-filled and visually occluded environments. First, we establish a framework for analyzing the probabilistic completeness of a sampling-based coverage algorithm, and derive results on the completeness and convergence of existing algorithms. Second, we introduce a new algorithm for the iterative improvement of a feasible coverage path; this relies on a sampling-based subroutine that makes asymptotically optimal local improvements to a feasible coverage path based on a strong generalization of the RRT* algorithm. We then apply the algorithm to the real-world task of autonomous in-water ship hull inspection. We use our improvement algorithm in conjunction with redundant roadmap coverage planning algorithm to produce paths that cover complex 3D environments with unprecedented efficiency.
---
paper_title: Asymptotically optimal inspection planning using systems with differential constraints

paper_content:

This paper proposes a new inspection planning algorithm, called Random Inspection Tree Algorithm (RITA). Given a perfect model of a structure, sensor specifications, robot's dynamics, and an initial configuration of a robot, RITA computes the optimal inspection trajectory that observes all points on the structure. Many inspection planning algorithms have been proposed, most of them consist of two sequential steps. In the first step, they compute a small set of observation points such that each point on the structure is visible. In the second step, they compute the shortest trajectory to visit all observation points at least once. The robot's kinematic and dynamic constraints are taken into account only in the second step. Thus, when the robot has differential constraints and operates in cluttered environments, the observation points may be difficult or even infeasible to reach. To alleviate this difficulty, RITA computes both observation points and the trajectory to visit the observation points simultaneously. RITA uses sampling-based techniques to find admissible trajectories with decreasing cost. Simulation results for 2-D environments are promising. Furthermore, we present analysis on the probabilistic completeness and asymptotic optimality of our algorithm.
---
paper_title: Robot Motion Planning

paper_content:

1 Introduction and Overview.- 2 Configuration Space of a Rigid Object.- 3 Obstacles in Configuration Space.- 4 Roadmap Methods.- 5 Exact Cell Decomposition.- 6 Approximate Cell Decomposition.- 7 Potential Field Methods.- 8 Multiple Moving Objects.- 9 Kinematic Constraints.- 10 Dealing with Uncertainty.- 11 Movable Objects.- Prospects.- Appendix A Basic Mathematics.- Appendix B Computational Complexity.- Appendix C Graph Searching.- Appendix D Sweep-Line Algorithm.- References.
---
paper_title: Optimal complete terrain coverage using an Unmanned Aerial Vehicle

paper_content:

We present the adaptation of an optimal terrain coverage algorithm for the aerial robotics domain. The general strategy involves computing a trajectory through a known environment with obstacles that ensures complete coverage of the terrain while minimizing path repetition. We introduce a system that applies and extends this generic algorithm to achieve automated terrain coverage using an aerial vehicle. Extensive experimental results in simulation validate the presented system, along with data from over 100 kilometers of successful coverage flights using a fixed-wing aircraft.
---
paper_title: Optimal Line-sweep-based Decompositions for Coverage Algorithms

paper_content:

Robotic coverage is the problem of moving a sensor or actuator over all points in given region. Ultimately, we want a coverage path that minimizes some cost such as time. We take the approach of decomposing the coverage region into subregions, selecting a sequence of those subregions, and then generating a path that covers each subregion in turn. We focus on generating decompositions based upon the planar line sweep. After a general overview of the coverage problem, we describe how our assumptions lead to the optimality criterion of minimizing the sum of subregion altitudes (which are measured relative to the sweep direction assigned to that subregion). For a line-sweep decomposition, the sweep direction is the same for all subregions. We describe how to find the optimal sweep direction for convex polygonal worlds. We then introduce the minimal sum of altitudes (MSA) decomposition in which we may assign a different sweep direction to each subregion. This decomposition is better for generating an optimal coverage path. We describe a method based on multiple line sweeps and dynamic programming to generate the MSA decomposition.
---
paper_title: Sampling-based coverage path planning for inspection of complex structures

paper_content:

We present several new contributions in sampling-based coverage path planning, the task of finding feasible paths that give 100% sensor coverage of complex structures in obstacle-filled and visually occluded environments. First, we establish a framework for analyzing the probabilistic completeness of a sampling-based coverage algorithm, and derive results on the completeness and convergence of existing algorithms. Second, we introduce a new algorithm for the iterative improvement of a feasible coverage path; this relies on a sampling-based subroutine that makes asymptotically optimal local improvements to a feasible coverage path based on a strong generalization of the RRT* algorithm. We then apply the algorithm to the real-world task of autonomous in-water ship hull inspection. We use our improvement algorithm in conjunction with redundant roadmap coverage planning algorithm to produce paths that cover complex 3D environments with unprecedented efficiency.
---
paper_title: Optimal coverage of a known arbitrary environment

paper_content:

The problem of coverage of known space by a mobile robot has many applications. Of particular interest is providing a solution that guarantees the complete coverage of the free space by traversing an optimal path, in terms of the distance travelled. In this paper we introduce a new algorithm based on the Boustrophedon cellular decomposition. The presented algorithm encodes the areas (cells) to be covered as edges of the Reeb graph. The optimal solution to the Chinese Postman Problem (CPP) is used to calculate an Euler tour, which guarantees complete coverage of the available free space while minimizing the path of the robot. In addition, we extend the classical solution of the CPP to account for the entry point of the robot for cell coverage by changing the weights of the Reeb graph edges. Proof of correctness is provided together with experimental results in different environments.
---
paper_title: Optimal area covering using genetic algorithms

paper_content:

Path planning problems involve computing or finding a collision free path between two positions. A special kind of path planning is complete coverage path planning, where a robot sweeps all area of free space in an environment. There are different methods to cover the complete area; however, they are not designed to optimize the process. This paper proposes a novel method of complete coverage path planning based on genetic algorithms. In order to check the viability of this approach the optimal path is tested in a virtual environment. The simulation results confirm the feasibility of this method.
---
paper_title: Robust coverage by a mobile robot of a planar workspace

paper_content:

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.
---
paper_title: Leap-Frog Path Design for Multi-Robot Cooperative Localization

paper_content:

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.
---
paper_title: Robust Area Coverage using Hybrid Control

paper_content:

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.
---
paper_title: Coverage for robotics – A survey of recent results

paper_content:

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.
---
paper_title: Active Visual SLAM with Exploration for Autonomous Underwater Navigation

paper_content:

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).
---
paper_title: Exploiting critical points to reduce positioning error for sensor-based navigation

paper_content:

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.
---
paper_title: Efficient Boustrophedon Multi-Robot Coverage: an algorithmic approach

paper_content:

This paper presents algorithmic solutions for the complete coverage path planning problem using a team of mobile robots. Multiple robots decrease the time to complete the coverage, but maximal efficiency is only achieved if the number of regions covered multiple times is minimized. A set of multi-robot coverage algorithms is presented that minimize repeat coverage. The algorithms use the same planar cell-based decomposition as the Boustrophedon single robot coverage algorithm, but provide extensions to handle how robots cover a single cell, and how robots are allocated among cells. Specifically, for the coverage task our choice of multi-robot policy strongly depends on the type of communication that exists between the robots. When the robots operate under the line-of-sight communication restriction, keeping them as a team helps to minimize repeat coverage. When communication between the robots is available without any restrictions, the robots are initially distributed through space, and each one is allocated a virtually-bounded area to cover. A greedy auction mechanism is used for task/cell allocation among the robots. Experimental results from different simulated and real environments that illustrate our approach for different communication conditions are presented.
---
paper_title: Graph Planning for Environmental Coverage

paper_content:

Tasks such as street mapping and security surveillance seek a route that traverses a given space to perform a function. These task functions may involve mapping the space for accurate modeling, sensing the space for unusual activity, or searching the space for objects. When these tasks are performed autonomously by robots, the constraints of the environment must be considered in order to generate more feasible paths. Additionally, performing these tasks in the real world presents the challenge of operating in dynamic, changing environments. ::: This thesis addresses the problem of effective graph coverage with environmental constraints and incomplete prior map information. Prior information about the environment is assumed to be given in the form of a graph. We seek a solution that effectively covers the graph while accounting for space restrictions and online changes. For real-time applications, we seek a complete but efficient solution that has fast replanning capabilities. ::: For this work, we model the set of coverage problems as arc routing problems. Although these routing problems are generally NP-hard, our approach aims for optimal solutions through the use of low-complexity algorithms in a branch-and-bound framework when time permits and approximations when time restrictions apply. Additionally, we account for environmental constraints by embedding those constraints into the graph. In this thesis, we present algorithms that address the multi-dimensional routing problem and its subproblems and evaluate them on both computer-generated and physical road network data.
---
paper_title: Cooperative Cleaners: A Study in Ant Robotics

paper_content:

In the world of living creatures, simple-minded animals often cooperate to achieve common goals with amazing performance. One can consider this idea in the context of robotics, and suggest models for programming goal-oriented behavior into the members of a group of simple robots lacking global supervision. This can be done by controlling the local interactions between the robot agents, to have them jointly carry out a given mission. As a test case we analyze the problem of many simple robots cooperating to clean the dirty floor of a non-convex region in Z2, using the dirt on the floor as the main means of inter-robot communication.
---
paper_title: A model for terrain coverage inspired by ant's alarm pheromones

paper_content:

When looking at science and technology today, we find a recurrent problem to many fields: how to cover a search space consistently and uniformly. This problem is encountered in robotics (searching for targets), optimization (searching for solutions), mathematics and computer science (graph traversals), and even in software engineering (the main motivation for this research). In insect societies, and in particular ant colonies, one can find the concept of alarm pheromones used to indicate an important event to the society (e.g. a threat). Alarm pheromones enable the society to have a uniform spread of its individuals, probably as a survival mechanism --- the more uniform the spread the better the changes of survival at the colony level. This paper proposes a model of this ant behavior which can be used to solve the aforementioned problem. The model, called ALARM is inspired primarily by ACO and from observations of ants alarm behavior. We compare the model with a random walk, to demonstrate a significant improvement over this approach.
---
paper_title: Distributed covering by ant-robots using evaporating traces

paper_content:

We investigate the ability of a group of robots, that communicate by leaving traces, to perform the task of cleaning the floor of an un-mapped building, or any task that requires the traversal of an unknown region. More specifically, we consider robots which leave chemical odour traces that evaporate with time, and are able to evaluate the strength of smell at every point they reach, with some measurement error. Our abstract model is a decentralized multi-agent adaptive system with a shared memory, moving on a graph whose vertices are the floor-tiles. We describe three methods of covering a graph in a distributed fashion, using smell traces that gradually vanish with time, and show that they all result in eventual task completion, two of them in a time polynomial in the number of tiles. Our algorithms can complete the traversal of the graph even if some of the agents die or the graph changes during the execution, as long as the graph stays connected. Another advantage of our agent interaction processes is the ability of agents to use noisy information at the cost of longer cover time.
---
paper_title: Aerial remote sensing in agriculture: A practical approach to area coverage and path planning for fleets of mini aerial robots

paper_content:

In this paper, a system that allows applying precision agriculture techniques is described. The application is based on the deployment of a team of unmanned aerial vehicles that are able to take georeferenced pictures in order to create a full map by applying mosaicking procedures for postprocessing. The main contribution of this work is practical experimentation with an integrated tool. Contributions in different fields are also reported. Among them is a new one-phase automatic task partitioning manager, which is based on negotiation among the aerial vehicles, considering their state and capabilities. Once the individual tasks are assigned, an optimal path planning algorithm is in charge of determining the best path for each vehicle to follow. Also, a robust flight control based on the use of a control law that improves the maneuverability of the quadrotors has been designed. A set of field tests was performed in order to analyze all the capabilities of the system, from task negotiations to final performance. These experiments also allowed testing control robustness under different weather conditions. © 2011 Wiley Periodicals, Inc. © 2011 Wiley Periodicals, Inc.
---
paper_title: Contact sensor-based coverage of rectilinear environments

paper_content:

A variety of mobile robot tasks require complete coverage of an initially unknown environment, either as the entire task or as a way to generate a complete map for use during further missions. This is a problem known as sensor-based coverage, in which the robot's sensing is used to plan a path that reaches every point in the environment. A new algorithm, CC/sub R/, is presented here which works for robots with only contact sensing that operate in environments with rectilinear boundaries and obstacles. This algorithm uses a high-level rule-based feedback structure to direct coverage rather than a script in order to facilitate future extensions to a team of independent robots. The outline of a completeness proof of CC/sub R/ is also presented, which shows that it produces coverage of any of a large class of rectilinear environments. Implementation of CC/sub R/ in simulation is discussed, as well as the results of testing in a variety of world geometries and potential extensions to the algorithm.
---
paper_title: A topological coverage algorithm for mobile robots

paper_content:

In applications such as vacuum cleaning, painting, demining and foraging, a mobile robot must cover an unknown surface. The efficiency and completeness of coverage is improved via the construction of a map of covered regions while the robot covers the surface. Existing methods generally use grid maps, which are susceptible to odometry error and may require considerable memory and computation. This paper proposes a topological map and presents a coverage algorithm in which natural landmarks are added as nodes in a partial map. The completeness of the algorithm is argued. Simulation tests show over 99% of the surface is covered; 85% for real (Khepera) robot tests. The path length is about 10% worse than optimal in simulation tests, and about 20% worse than optimal for the real robot, which are within theoretical upper bounds for approximates solutions to traveling salesman based coverage problems. The proposed algorithm generates shorter paths and covers a wider variety of environments than topological coverage based on Morse decompositions.
---
paper_title: Graph Planning for Environmental Coverage

paper_content:

Tasks such as street mapping and security surveillance seek a route that traverses a given space to perform a function. These task functions may involve mapping the space for accurate modeling, sensing the space for unusual activity, or searching the space for objects. When these tasks are performed autonomously by robots, the constraints of the environment must be considered in order to generate more feasible paths. Additionally, performing these tasks in the real world presents the challenge of operating in dynamic, changing environments. ::: This thesis addresses the problem of effective graph coverage with environmental constraints and incomplete prior map information. Prior information about the environment is assumed to be given in the form of a graph. We seek a solution that effectively covers the graph while accounting for space restrictions and online changes. For real-time applications, we seek a complete but efficient solution that has fast replanning capabilities. ::: For this work, we model the set of coverage problems as arc routing problems. Although these routing problems are generally NP-hard, our approach aims for optimal solutions through the use of low-complexity algorithms in a branch-and-bound framework when time permits and approximations when time restrictions apply. Additionally, we account for environmental constraints by embedding those constraints into the graph. In this thesis, we present algorithms that address the multi-dimensional routing problem and its subproblems and evaluate them on both computer-generated and physical road network data.
---
paper_title: A Bioinspired Neural Network for Real-Time Concurrent Map Building and Complete Coverage Robot Navigation in Unknown Environments

paper_content:

Complete coverage navigation (CCN) requires a special type of robot path planning, where the robots should pass every part of the workspace. CCN is an essential issue for cleaning robots and many other robotic applications. When robots work in unknown environments, map building is required for the robots to effectively cover the complete workspace. Real-time concurrent map building and complete coverage robot navigation are desirable for efficient performance in many applications. In this paper, a novel neural-dynamics-based approach is proposed for real-time map building and CCN of autonomous mobile robots in a completely unknown environment. The proposed model is compared with a triangular-cell-map-based complete coverage path planning method (Oh et al., 2004) that combines distance transform path planning, wall-following algorithm, and template-based technique. The proposed method does not need any templates, even in unknown environments. A local map composed of square or rectangular cells is created through the neural dynamics during the CCN with limited sensory information. From the measured sensory information, a map of the robot's immediate limited surroundings is dynamically built for the robot navigation. In addition, square and rectangular cell map representations are proposed for real-time map building and CCN. Comparison studies of the proposed approach with the triangular-cell-map-based complete coverage path planning approach show that the proposed method is capable of planning more reasonable and shorter collision-free complete coverage paths in unknown environments.
---
paper_title: Planning Paths of Complete Coverage of an Unstructured Environment by a Mobile Robot

paper_content:

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.
---
paper_title: Spiral-STC: an on-line coverage algorithm of grid environments by a mobile robot

paper_content:

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.
---
paper_title: A neural network approach to complete coverage path planning

paper_content:

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.
---
paper_title: Sampling-based coverage path planning for inspection of complex structures

paper_content:

We present several new contributions in sampling-based coverage path planning, the task of finding feasible paths that give 100% sensor coverage of complex structures in obstacle-filled and visually occluded environments. First, we establish a framework for analyzing the probabilistic completeness of a sampling-based coverage algorithm, and derive results on the completeness and convergence of existing algorithms. Second, we introduce a new algorithm for the iterative improvement of a feasible coverage path; this relies on a sampling-based subroutine that makes asymptotically optimal local improvements to a feasible coverage path based on a strong generalization of the RRT* algorithm. We then apply the algorithm to the real-world task of autonomous in-water ship hull inspection. We use our improvement algorithm in conjunction with redundant roadmap coverage planning algorithm to produce paths that cover complex 3D environments with unprecedented efficiency.
---
paper_title: Coverage path planning on three-dimensional terrain for arable farming

paper_content:

Field operations should be done in a manner that minimizes time and travels over the field surface and is coordinated with topographic land features. Automated path planning can help to find the best coverage path so that the field operation costs can be minimized. Intelligent algorithms are desired for both two-dimensional (2D) and three-dimensional (3D) terrain field coverage path planning. The algorithm of generating an optimized full coverage pattern for a given 2D planar field by using boustrophedon paths has been investigated and reported before. However, a great proportion of farms have rolling terrains, which have a considerable influence on the design of coverage paths. Coverage path planning in 3D space has a great potential to further optimize field operations. This work addressed four critical tasks: terrain modeling and representation, coverage cost analysis, terrain decomposition, and the development of optimized path searching algorithm. The developed algorithms and methods have been successfully implemented and tested using 3D terrain maps of farm fields with various topographic features. Each field was decomposed into subregions based on its terrain features. A recommended “seed curve” based on a customized cost function was searched for each subregion, and parallel coverage paths were generated by offsetting the found “seed curve” toward its two sides until the whole region was completely covered. Compared with the 2D planning results, the experimental results of 3D coverage path planning showed its superiority in reducing both headland turning cost and soil erosion cost. On the tested fields, on average the 3D planning algorithm saved 10.3% on headland turning cost, 24.7% on soil erosion cost, 81.2% on skipped area cost, and 22.0% on the weighted sum of these costs, where their corresponding weights were 1, 1, and 0.5, respectively. © 2011 Wiley Periodicals, Inc. © 2011 Wiley Periodicals, Inc.
---
paper_title: Asymptotically optimal inspection planning using systems with differential constraints

paper_content:

This paper proposes a new inspection planning algorithm, called Random Inspection Tree Algorithm (RITA). Given a perfect model of a structure, sensor specifications, robot's dynamics, and an initial configuration of a robot, RITA computes the optimal inspection trajectory that observes all points on the structure. Many inspection planning algorithms have been proposed, most of them consist of two sequential steps. In the first step, they compute a small set of observation points such that each point on the structure is visible. In the second step, they compute the shortest trajectory to visit all observation points at least once. The robot's kinematic and dynamic constraints are taken into account only in the second step. Thus, when the robot has differential constraints and operates in cluttered environments, the observation points may be difficult or even infeasible to reach. To alleviate this difficulty, RITA computes both observation points and the trajectory to visit the observation points simultaneously. RITA uses sampling-based techniques to find admissible trajectories with decreasing cost. Simulation results for 2-D environments are promising. Furthermore, we present analysis on the probabilistic completeness and asymptotic optimality of our algorithm.
---
paper_title: Cooperative Cleaners: A Study in Ant Robotics

paper_content:

In the world of living creatures, simple-minded animals often cooperate to achieve common goals with amazing performance. One can consider this idea in the context of robotics, and suggest models for programming goal-oriented behavior into the members of a group of simple robots lacking global supervision. This can be done by controlling the local interactions between the robot agents, to have them jointly carry out a given mission. As a test case we analyze the problem of many simple robots cooperating to clean the dirty floor of a non-convex region in Z2, using the dirt on the floor as the main means of inter-robot communication.
---
paper_title: Efficient Boustrophedon Multi-Robot Coverage: an algorithmic approach

paper_content:

This paper presents algorithmic solutions for the complete coverage path planning problem using a team of mobile robots. Multiple robots decrease the time to complete the coverage, but maximal efficiency is only achieved if the number of regions covered multiple times is minimized. A set of multi-robot coverage algorithms is presented that minimize repeat coverage. The algorithms use the same planar cell-based decomposition as the Boustrophedon single robot coverage algorithm, but provide extensions to handle how robots cover a single cell, and how robots are allocated among cells. Specifically, for the coverage task our choice of multi-robot policy strongly depends on the type of communication that exists between the robots. When the robots operate under the line-of-sight communication restriction, keeping them as a team helps to minimize repeat coverage. When communication between the robots is available without any restrictions, the robots are initially distributed through space, and each one is allocated a virtually-bounded area to cover. A greedy auction mechanism is used for task/cell allocation among the robots. Experimental results from different simulated and real environments that illustrate our approach for different communication conditions are presented.
---

Title: A Survey on Coverage Path Planning for Robotics

Section 1: Introduction
Description 1: This section will provide an overview of Coverage Path Planning (CPP) for robotics, including its importance and applications across various robotic fields.

Section 2: Classical Exact Cellular Decomposition Methods
Description 2: Discusses methods that break the free space into simple, non-overlapping regions called cells and the basics of two notable approaches: Trapezoidal Decomposition and Boustrophedon Decomposition.

Section 3: Morse-based Cellular Decomposition
Description 3: This section covers Morse decomposition, an advanced cellular decomposition technique that includes handling non-polygonal obstacles and the associated on-line method for critical point detection.

Section 4: Landmark-based Topological Coverage
Description 4: Explains a coverage approach for mobile robots based on detecting natural landmarks to create an exact cellular decomposition called slice decomposition. 

Section 5: Contact Sensor-based Coverage of Rectilinear Environments
Description 5: Details the CC R algorithm for robots without range sensing capabilities, focusing on achieving coverage in unknown rectilinear environments.

Section 6: Grid-based Methods
Description 6: Reviews methods utilizing grid representations for the environment, including Wavefront Algorithm, Spiral-STC Algorithm, and neural network-based approaches.

Section 7: Graph-based Coverage
Description 7: Explores coverage algorithms suitable for environments represented as graphs, such as street or road networks, addressing issues like incomplete maps and environmental constraints.

Section 8: 3D Coverage
Description 8: Discusses various methods for 3-dimensional coverage including using planar algorithms in successive horizontal planes, Morse-based decomposition for 3D structures, and specific applications such as bathymetric surfaces.

Section 9: Optimal Coverage
Description 9: Reviews approaches to achieve optimal coverage paths in terms of path length and time to completion, suitable for known or partially known environments.

Section 10: Coverage under Uncertainty
Description 10: Focuses on strategies to reduce the effect of localization error while performing coverage, including SLAM-based approaches.

Section 11: Multi-robot Methods
Description 11: Discusses methods for utilizing multiple robots in CPP tasks, including strategies adapted from single-robot decomposition methods and bio-inspired approaches for multi-robot fleet coordination.

Section 12: Conclusion
Description 12: Summarizes the different CPP methodologies covered, their applications, advantages, and emerging techniques in the field, especially highlighting the potential of probabilistic sampling and SLAM integration in CPP.