  Multi-robot patrolling represents a fundamental problem for many monitoring
and surveillance applications and has gained significant interest in recent
years. In patrolling, mobile robots repeatedly travel through an environment,
capture sensor data at certain sensing locations and deliver this data to the
base station in a way that maximizes the changes of detection. Robots move on
tours, exchange data when they meet with robots on neighboring tours and so
eventually deliver data to the base station.
  In this paper we jointly consider two important optimization criteria of
multi-robot patrolling: (i) idleness, i.e. the time between consecutive visits
of sensing locations, and (ii) delay, i.e. the time between capturing data at
the sensing location and its arrival at the base station. We systematically
investigate the effect of the robots' moving directions along their tours and
the selection of meeting points for data exchange. We prove that the problem of
determining the movement directions and meeting points such that the data delay
is minimized is NP-hard. We propose heuristics and provide a simulation study
which shows that the cooperative approach can outperform an uncooperative
approach where every robot delivers the captured data individually to the base
station.
