Patrolling
Robots move forever so that no point of a fence (a segment, a circle, or the edges of a graph) stays unvisited for long.
Problem statement and measuresexpand
\(k\) robots with maximum speeds \(v_1,\dots,v_k\) move forever along a fence: a segment, a circle, or the edges of a graph. The idle time is the largest time interval during which some point is not visited. The aim is to minimise it, or, equivalently, to find the longest fence that can be patrolled with idle time 1.
Measures: Idle time, worst idle time, or the longest fence patrollable with idle time 1 (stated per variant).
Progress map
tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Idle time
Direction of movement + circle
—
near-optimal
\(\frac{1}{33\ln\log_2 k}\sum_i v_i\) vs \(L \le \sum_i v_i\)
space-time coverage
unknown
\(\to\tfrac32\times\text{simple}\) vs —
tight
\(\to 2\times\text{partition}\) vs \(\text{partition is not optimal}\)
distinct speeds
tight
\((f+1)\,\mathrm{CPT}(G)/k\) vs \((f+1)|E|/k\)
faulty reports
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.