Multi-robot surveillance: An improved algorithm for the GRAPH-CLEAR problem

Abstract

The main contribution of this paper is an improved algorithm for the GRAPH-CLEAR problem, a novel NP-complete graph theoretic problem we recently introduced as a tool to model multi-robot surveillance tasks. The proposed algorithm combines two previously developed solving techniques and produces strategies that require less robots to be executed. We provide a theoretical framework useful to identify the conditions for the existence of an optimal solution under special circumstances, and a set of mathematical tools characterizing the problem being studied. Finally we also identify a set of open questions deserving more investigations.