In this paper, we present controllers that enable mobile robots to persistently monitor or sweep a changing environment. The environment is modeled as a field that is defined over a finite set of locations. The field grows linearly at locations that are not within the range of a robot and decreases linearly at locations that are within range of a robot. We assume that the robots travel on given closed paths. The speed of each robot along its path is controlled to prevent the field from growing unbounded at any location. We consider the space of speed controllers that are parametrized by a finite set of basis functions. For a single robot, we develop a linear program that computes a speed controller in this space to keep the field bounded, if such a controller exists. Another linear program is derived to compute the speed controller that minimizes the maximum field value over the environment. We extend our linear program formulation to develop a multirobot controller that keeps the field bounded. We characterize, both theoretically and in simulation, the robustness of the controllers to modeling errors and to stochasticity in the environment.
Our problem in this paper is also related to sweep coverage, or lawn mowing and milling problems, in which robots with finite sensor footprints move over an environment so that every point in the environment is visited at least once by a robot. Lawn mowing and milling has been treated in @cite_27 and other works. Sweep coverage has recently been studied in @cite_9 , and in @cite_12 efficient sweep coverage algorithms are proposed for ant robots. A survey of sweep coverage is given in @cite_3 . Our problem is significantly different from these because our environment is dynamic, thereby requiring continual re-milling or re-sweeping. A different notion of persistent surveillance has been considered in @cite_35 and @cite_28 , where a persistent task is defined as one whose completion takes much longer than the life of a robot. While the terminology is similar, our problem is more concerned with the task (sweeping or monitoring) itself than with power requirements of individual robots.
@cite_35 @cite_28 @cite_9 @cite_3 @cite_27 @cite_12
2141154005 2092297192 2022750663 1544032329 1535557537 1584030176
Unmanned aerial vehicles (UAVs) are well-suited to a wide range of mission scenarios, such as search and rescue, border patrol, and military surveillance. The complex and distributed nature of these missions often requires teams of UAVs to work together. Furthermore, overall mission performance can be strongly influenced by vehicle failures or degradations, so an autonomous mission system must account for the possibility of these anomalies if it is to maximize performance. This paper presents a general health management methodology for designing mission systems that can anticipate the negative effects of various types of anomalies on the future mission state and choose actions that mitigate those effects. The formulation is then specialized to the problem of providing persistent surveillance coverage using a group of UAVs, where uncertain fuel usage dynamics and strong interdependence effects between vehicles must be considered. Finally, the paper presents results showing that the health-aware persistent surveillance planner based on this formulation exhibits excellent performance in both simulated and real flight test experiments. This paper presents an extension of our previous work on the persistent surveillance problem. An extended problem formulation incorporates real-time changes in agent capabilities as estimated by an onboard health monitoring system in addition to the existing communication constraints, stochastic sensor failure and fuel flow models, and the basic constraints of providing surveillance coverage using a team of autonomous agents. An approximate policy for the persistent surveillance problem is computed using a parallel, distributed implementation of the approximate dynamic programming algorithm known as Bellman Residual Elimination. This paper also presents flight test results which demonstrate that this approximate policy correctly coordinates the team to simultaneously provide reliable surveillance coverage and a communications link for the duration of the mission and appropriately retasks agents to maintain these services in the event of agent capability degradation. This paper presents an algorithm for the complete coverage of free space by a team of mobile robots. Our approach is based on a single robot coverage algorithm, which divides the target two-dimensional space into regions called cells, each of which can be covered with simple back-and-forth motions; the decomposition of free space in a collection of such cells is known as Boustrophedon decomposition. Single robot coverage is achieved by ensuring that the robot visits every cell. The new multi-robot coverage algorithm uses the same planar cell-based decomposition as the single robot approach, but provides extensions to handle how teams of robots cover a single cell and how teams are allocated among cells. This method allows planning to occur in a two-dimensional configuration space for a team of N robots. The robots operate under the restriction that communication between two robots is available only when they are within line of sight of each other. 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. 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. Ant robots are simple creatures with limited sensing and computational capabilities. They have the advantage that they are easy to program and cheap to build. This makes it feasible to deploy groups of ant robots and take advantage of the resulting fault tolerance and parallelism. We study, both theoretically and in simulation, the behavior of ant robots for one-time or repeated coverage of terrain, as required for lawn mowing, mine sweeping, and surveillance. Ant robots cannot use conventional planning methods due to their limited sensing and computational capabilities. To overcome these limitations, we study navigation methods that are based on real-time (heuristic) search and leave markings in the terrain, similar to what real ants do. These markings can be sensed by all ant robots and allow them to cover terrain even if they do not communicate with each other except via the markings, do not have any kind of memory, do not know the terrain, cannot maintain maps of the terrain, nor plan complete paths. The ant robots do not even need to be localized, which completely eliminates solving difficult and time-consuming localization problems. We study two simple real-time search methods that differ only in how the markings are updated. We show experimentally that both real-time search methods robustly cover terrain even if the ant robots are moved without realizing this (say, by people running into them), some ant robots fail, and some markings get destroyed. Both real-time search methods are algorithmically similar, and our experimental results indicate that their cover time is similar in some terrains. Our analysis is therefore surprising. We show that the cover time of ant robots that use one of the real-time search methods is guaranteed to be polynomial in the number of locations, whereas the cover time of ant robots that use the other real-time search method can be exponential in (the square root of) the number of locations even in simple terrains that correspond to (planar) undirected trees.