Suppose that a fence needs to be protected (perpetually) by $k$ mobile agents with maximum speeds $v_1,\ldots,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 idle time, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by Czyzowicz et al. (2011), 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. 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 Kawamura and Kobayashi.
@article{10_37236_4063,
author = {Adrian Dumitrescu and Anirban Ghosh and Csaba D. T\'oth},
title = {On fence patrolling by mobile agents},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {3},
doi = {10.37236/4063},
zbl = {1307.90149},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4063/}
}
TY - JOUR
AU - Adrian Dumitrescu
AU - Anirban Ghosh
AU - Csaba D. Tóth
TI - On fence patrolling by mobile agents
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/4063/
DO - 10.37236/4063
ID - 10_37236_4063
ER -
%0 Journal Article
%A Adrian Dumitrescu
%A Anirban Ghosh
%A Csaba D. Tóth
%T On fence patrolling by mobile agents
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/4063/
%R 10.37236/4063
%F 10_37236_4063
Adrian Dumitrescu; Anirban Ghosh; Csaba D. Tóth. On fence patrolling by mobile agents. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/4063
