Multi-Robot Path Planning for Persistent Coverage Tasks with Performance Guarantees

Abstract

Recent advances on the design of autonomous mobile agents have motivated the use of the latter in persistent surveillance tasks with applications in agriculture, information gathering and search and rescue missions. In these tasks the goal is to design agents’ paths so as every point in the area of interest is covered more than once. In literature the persistent surveillance problem has been addressed under two different frameworks: 1) the visitation frequency of a finite set of points (discrete spaces) and 2) the amount of coverage offered by the agents over the area of interest. In the first category agents aim at visiting a finite set of points in the area so as the time elapsed since a point was last visited is minimized over the set. Here, the environment is considered static and no information on the coverage condition of the points is available. In the second category the environment is characterized by a property that changes over time, called coverage level and the goal is to design agents’ paths so as the coverage level is maintained at a desired level over the area. In this approach the error between the actual and desired coverage level of the area is bounded. However, locally no information is available on the frequency at which each point gets covered. The novelty of this thesis lies in the integration of the aforementioned solution approaches so as complete coverage information is provided for a finite set of points. Here, the goal is to design the agents’ paths so as the coverage level of each point is bounded from below by a desired level. The paths are planned over a finite optimization horizon and found as a solution to a Mixed Integer Linear Program (MILP). Two formulations of the problem are proposed and their efficiency is validated in simulation. The recursive feasibility of the centralized problem is also guaranteed when a set of time-varying terminal constraints is introduced to the problem. These constraints force agents to move along a pre-defined set of closed paths designed in a way that the coverage level boundness constraint is always satisfied. A two-step method is proposed for their design that relies on the solution of a Linear Program (LP) when a set of closed paths violating the objective is given, found as a solution to a modified version of the proposed MILP at step 1. Finally, two distributed formulations of the problem are introduced in which agents solve in parallel a local path planning problem. The difference on these methods lies in the accuracy of the information available to the agents for planning. Despite this difference simulation tests show a difference of only 1.5% in the coverage level performance when various sized teams of agents are employed for the task.