Multi-robot persistent coverage using branch and bound

Abstract

In this paper we tackle the persistent coverage problem, that aims to maintain a desired coverage level in an environment. The difference with traditional coverage resides in that the coverage decays over time and the robots must keep continuously moving to maintain the desired level. In this context we consider a cost function that quantifies the quality of the coverage in a finite prediction horizon and transform the persistent coverage problem into a discrete optimization problem with constraints. We introduce a branch-and-bound algorithm that allows us to find the optimal solution to the problem, i.e., the set of actions that minimizes the cost function. This algorithm includes a procedure to split the sets of candidate solutions and the calculation of upper and lower bounds on the cost. Additionally, we propose a method to reduce the problem to several smaller subproblems. Finally, we carry out simulations to evaluate the performance of the system.