On fence patrolling by mobile agents (Q405281)

Summary: Suppose that a fence needs to be protected (perpetually) by \(k\) mobile agents with maximum speeds \(v_1,\dots,v_k\) so that no point on the fence is left unattended for more than a given amount of time. The problem is to determine if this requirement can be met, and if so, to design a suitable patrolling schedule for the agents. Alternatively, one would like to find a schedule that minimizes the \textit{idle time}, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by \textit{J. Czyzowicz} et al. [ESA 2012, Lect. Notes Comput. Sci. 6942, 701--712 (2011; Zbl 1260.68397)], and discuss several strategies for the cases where the fence is an open and a closed curve, respectively.{ } In particular: (i) we disprove a conjecture by Czyzowicz et al. (loc. cit.) regarding the optimality of their algorithm \({\mathcal A}_2\) for unidirectional patrolling of a closed fence; (ii) we present a schedule with a lower idle time for patrolling~an open fence, improving an earlier result of \textit{A. Kawamura} and \textit{Y. Kobayashi} [ISAAC 2012, Lect. Notes Comput. Sci. 7676, 598--608 (2012; Zbl 1260.90141)].