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.
A problem more closely related to ours is that of patrolling @cite_21 @cite_25 , where an environment must be continually surveyed by a group of robots such that each point is visited with equal frequency. Similarly, in @cite_34 vehicles must repeatedly visit the cells of a gridded environment. Also, continual perimeter patrolling is addressed in @cite_19 . In another related work, a region is persistently covered in @cite_37 by controlling robots to move at constant speed along predefined paths. Our work is different from these, however, in that we treat the situation in which different parts of the environment may require different levels of attention. This is a significant difference as it induces a difficult resource trade-off problem as one typically finds in queuing theory @cite_31 , or dynamic vehicle routing @cite_33 @cite_6 . @cite_32 , the authors consider unequal frequency of visits in a gridded environment, but they control the robots using a greedy method that does not have performance guarantees.
@cite_37 @cite_33 @cite_21 @cite_32 @cite_6 @cite_19 @cite_31 @cite_34 @cite_25
2025291543 1971739135 1603050797 2140903796 2006275224 2161128818 2165298539 2148926063
In this paper we address the problem of persistent coverage of a given convex polygonal region in the plane. We present an algorithmic solution for this problem that takes into account the limitations in the communication and sensing ranges of the agents. We show that our algorithm provides a persistent coverage period that is bounded away by a constant factor from a minimal tour among the centers of an optimal static cover, which is comprised of circles having the same radius as the sensing radius of the agents. A simulation is provided that illustrates the algorithm. In 1991, D. J. Bertsimas and G. van Ryzin introduced and analyzed a model for stochastic and dynamic vehicle routing in which a single, uncapacitated vehicle traveling at a constant velocity in a Euclidean region must service demands whose time of arrival, location and on-site service are stochastic. The objective is to find a policy to service demands over an infinite horizon that minimizes the expected system time (wait plus service) of the demands. This paper extends our analysis in several directions. First, we analyze the problem of m identical vehicles with unlimited capacity and show that in heavy traffic the system time is reduced by a factor of 1 m2 over the single-server case. One of these policies improves by a factor of two on the best known system time for the single-server case. We then consider the case in which each vehicle can serve at most q customers before returning to a depot. We show that the stability condition in this case depends strongly on the geometry of the region. Several pol... A group of agents can be used to perform patrolling tasks in a variety of domains ranging from computer network administration to computer wargame simulations. The multi-agent patrolling problem has recently received growing attention from the multi-agent community, due to the wide range of potential applications. Many algorithms based on reactive and cognitive architectures have been developed, giving encouraging results. However, no theoretical analysis of this problem has been conducted. In this paper, various classes of patrolling strategies are proposed and compared. More precisely, these classes are compared to the optimal strategy by means of a standard complexity analysis. As mobile robots become increasingly autonomous over extended periods of time, opportunities arise for their use on repetitive tasks. We define and implement behaviors for a class of such tasks that we call continuous area sweeping tasks. A continuous area sweeping task is one in which a group of robots must repeatedly visit all points in a fixed area, possibly with nonuniform frequency, as specified by a task-dependent cost function. Examples of problems that need continuous area sweeping are trash removal in a large building and routine surveillance. In our previous work we have introduced a single-robot approach to this problem. In this paper, we extend that approach to multi-robot scenarios. The focus of this paper is adaptive and decentralized task assignment in continuous area sweeping problems, with the aim of ensuring stability in environments with dynamic factors, such as robot malfunctions or the addition of new robots to the team. Our proposed negotiation-based approach is fully implemented and tested both in simulation and on physical robots In this paper we introduce a dynamic vehicle routing problem in which there are multiple vehicles and multiple priority classes of service demands. Service demands of each priority class arrive in the environment randomly over time and require a random amount of on-site service that is characteristic of the class. To service a demand, one of the vehicles must travel to the demand location and remain there for the required on-site service time. The quality of service provided to each class is given by the expected delay between the arrival of a demand in the class and that demand's service completion. The goal is to design a routing policy for the service vehicles which minimizes a convex combination of the delays for each class. First, we provide a lower bound on the achievable values of the convex combination of delays. Then, we propose a novel routing policy and analyze its performance under heavy-load conditions (i.e., when the fraction of time the service vehicles spend performing on-site service approaches one). The policy performs within a constant factor of the lower bound, where the constant depends only on the number of classes, and is independent of the number of vehicles, the arrival rates of demands, the on-site service times, and the convex combination coefficients. This paper poses the cooperative perimeter-surveillance problem and offers a decentralized solution that accounts for perimeter growth (expanding or contracting) and insertion deletion of team members. By identifying and sharing the critical coordination information and by exploiting the known communication topology, only a small communication range is required for accurate performance. Simulation and hardware results are presented that demonstrate the applicability of the solution. Search and exploration using multiple autonomous sensing platforms has been extensively studied in the fields of controls and artificial intelligence. The task of persistent surveillance is different from a coverage or exploration problem, in that the target area needs to be continuously searched, minimizing the time between visitations to the same region. This difference does not allow a straightforward application of most exploration techniques to the problem, although ideas from these methods can still be used. In this research we investigate techniques that are scalable, reliable, efficient, and robust to problem dynamics. These are tested in a multiple unmanned air vehicle (UAV) simulation environment, developed for this program. A semi-heuristic control policy for a single UAV is extended to the case of multiple UAVs using two methods. One is an extension of a reactive policy for a single UAV and the other involves allocation of sub-regions to individual UAVs for parallel exploration. An optimal assignment procedure (based on auction algorithms) has also been developed for this purpose. A comparison is made between the two approaches and a simplified optimal result. The reactive policy is found to exhibit an interesting emergent behavior as the number of UAVs becomes large. The control policy derived for a single UAV is modified to account for actual aircraft dynamics (a 3 degree-of-freedom nonlinear dynamics simulation is used for this purpose) and improvements in performance are observed. Finally, we draw conclusions about the utility and efficiency of these techniques. This paper discusses the problem of generating patrol paths for a team of mobile robots inside a designated target area. Patrolling requires an area to be visited repeatedly by the robot(s) in order to monitor its current state. First, we present frequency optimization criteria used for evaluation of patrol algorithms. We then present a patrol algorithm that guarantees maximal uniform frequency, i.e., each point in the target area is covered at the same optimal frequency. This solution is based on finding a circular path that visits all points in the area, while taking into account terrain directionality and velocity constraints. Robots are positioned uniformly along this path, using a second algorithm. Moreover, the solution is guaranteed to be robust in the sense that uniform frequency of the patrol is achieved as long as at least one robot works properly.