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).
Open fence, distinct speeds
standard settingverifiedPartitioning the segment among the robots is optimal for 2 and 3 robots but not in general: optimal schedules can patrol a segment almost, but never quite, twice as long.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Fence: segment
- An open fence: the segment \([0,\ell]\); robots may reverse direction anywhere.
- Direction of movement: two-way
- Every robot moves along the fence in either direction at any speed between \(0\) and \(v_i\), and may reverse at any point and any time. On a segment and on a graph this is the only meaningful choice.
- Faults: no faults
- Every robot detects and reports the target.
- Speeds: distinct speeds
- Each robot \(i\) has its own maximum speed \(v_i\), known to all.
- Communication: face-to-face
- Face-to-face: two robots exchange information only when they are at the same point at the same time.
- Randomness: deterministic
- Trajectories are fixed functions of the information received.
What is known
- counterexample with \(k = 6\) agents
- Theorem 2.1: the longest segment patrolled with idle time 1, where \(v_{\max}\) is the largest speed
- with equal speeds it gives the partition's \(\sum_i v_i/2\); for \(k\) robots the efficiency \(L/\sum_i v_i\) is at most \(1 - 1/\sqrt{k+1}\) (Lemma 2.2)
Results, in order of publication
Introduces patrolling by robots with distinct speeds; shows the partition strategy optimal for \(k=2\) (Theorem 1) and conjectures it optimal for every \(k\) (Conjecture 1); Kawamura & Kobayashi 2015 disproved the conjecture.
Theorem 3: for every integer \(x \ge 2\), \(k = 4x+1\) robots with \(v_1 + \dots + v_k = 16x+1\) patrol a segment of length \(25x/3\) with idle time 1, against \((16x+1)/2\) for the partition; this improved the counterexample of Kawamura & Kobayashi 2015 and is superseded by the \(4/3\) of Kawamura & Soejima 2020.
Schedules that patrol a segment \(4/3\) times longer than partition (efficiency approaching \(2/3\)); Kawamura and Soejima conjectured that \(2/3\) is the best efficiency, which Haeupler et al. 2019 disproved.
Theorem 2.3: for large \(k\), \(k-1\) robots of speed 1 and one of speed \(\Theta(\sqrt k)\) patrol a segment with efficiency \(1 - 3.5/\sqrt k\), where partition has efficiency \(1/2\). By Theorem 2.1 and Lemma 2.2, efficiency \(1-\varepsilon\) needs \(\Omega(\varepsilon^{-2})\) robots and a speed ratio \(\Omega(\varepsilon^{-1})\), so the construction is asymptotically optimal.
Open questions
Is computing an optimal schedule for given speeds on a segment hard?
Notes
Czyzowicz et al. asked how much better than partition an optimal schedule can be Czyzowicz et al. 2011; Haeupler, Kuhn, Martinsson, Petrova and Pfister answered it Haeupler et al. 2019. Their bound of Theorem 2.1 is attained by the constructions of Dumitrescu et al. 2014 and Kawamura & Soejima 2020. Checked against the full text of Haeupler et al. 2019 (arXiv v2).
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.