An MILP approach for persistent coverage tasks with multiple robots and performance guarantees

Maria Charitidou*, Tamás Keviczky

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

18 Downloads (Pure)


Multiple robots are increasingly being considered in a variety of tasks requiring continuous surveillance of a dynamic area, examples of which are environmental monitoring, and search and rescue missions. Motivated by these applications, in this paper we consider the multi-robot persistent coverage control problem over a grid environment. The goal is to ensure a desired lower bound on the coverage level of each cell in the grid, that is decreasing at a given rate for unoccupied cells. We consider a finite set of candidate poses for the agents and introduce a directed graph with nodes representing their admissible poses. We formulate a persistent coverage control problem as a MILP problem that aims to maximize the coverage level of the cells over a finite horizon. To solve the problem, we design a receding horizon scheme (RHS) and prove its recursive feasibility property by introducing a set of time-varying terminal constraints to the problem. These terminal constraints ensure that the agents are always able to terminate their plans in pre-determined closed trajectories. A two-step method is proposed for the construction of the closed trajectories, guaranteeing the satisfaction of the coverage level lower bound constraint, when the resulting closed trajectories are followed repeatedly. Due to the special structure of the problem, agents are able to visit every cell in the grid repeatedly within a worst-case visitation period. Finally, we provide a computational time analysis of the problem for different simulated scenarios and demonstrate the performance of the RHS problem by an illustrative example.

Original languageEnglish
Article number100610
Number of pages10
JournalEuropean Journal of Control
Publication statusPublished - 2022

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.


  • MILP Planning
  • Multi-robot systems
  • Persistent coverage
  • Receding horizon scheme


Dive into the research topics of 'An MILP approach for persistent coverage tasks with multiple robots and performance guarantees'. Together they form a unique fingerprint.

Cite this