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).
Closed fence, one-way, distinct speeds
verifiedWith every robot moving in one direction, the cyclic strategy is optimal for up to four robots but not within any constant factor in general: every set of robots patrols a circle of length \(\sum_i v_i/(33\ln\log_2 k)\).
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Fence: circle
- A closed fence: a circle of length \(\ell\).
- Direction of movement: one-way
- On a closed fence every robot moves only counterclockwise, at any speed between \(0\) and its maximum speed \(v_i\); it never reverses. Czyzowicz et al. require strictly positive speeds, while Dumitrescu, Ghosh and Tóth and Kawamura and Soejima allow robots to stop; the counterexample of Dumitrescu et al. holds under both conventions (Remark after Theorem 1 of Dumitrescu et al. 2014). Schedules are a subset of the two-way schedules, so this is the harder level for the robots.
- 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
- Proposition 2: no schedule has idle time below \(1/(v_1+\dots+v_k)\) on the unit circle, in either direction
Results, in order of publication
The cyclic strategy (the \(r\) fastest robots, equally spaced, all at speed \(v_r\), with \(r\) maximising \(iv_i\)) has idle time \(1/\max_i iv_i\) on the unit circle (Theorem 2); it is optimal for \(k \le 4\) (Theorem 3) and conjectured optimal for every \(k\) (Conjecture 2).
Theorem 1: 32 robots with speeds \(v_i = 1/i\) have a periodic schedule with idle time strictly below \(1\), the idle time of the cyclic strategy; this disproves Conjecture 2 of Czyzowicz et al. 2011, also when speeds must stay positive (Remark). Theorem 2: for every \(\tau \in (0,1]\) and horizon \(t \ge \tau\), \(k \le e^{4t/\tau^2}\) robots with speeds \(1/i\) keep the idle time at most \(\tau\) during \([0,t]\).
Theorem 10: speeds and a schedule that patrol a circle of length \(1.05\max_r rv_r\) with idle time 1. Kawamura and Soejima conjecture that the cyclic strategy is not within any constant factor of optimal.
Theorem 2.4: for large \(k\) and any speeds, a schedule with idle time 1 on a one-way circle of this length. With speeds \(1/i\) the cyclic strategy patrols length 1 and this schedule \(\Theta(\log k/\log\log k)\), so the cyclic strategy is not within a constant factor of optimal, as Kawamura and Soejima conjectured.
Open questions
Close the factor \(O(\log\log k)\) between the schedule of Haeupler et al. 2019 and the bound \(\sum_i v_i\) on the one-way circle.
Notes
Conjecture 2 of Czyzowicz et al. 2011 was disproved by Dumitrescu, Ghosh and Tóth (Theorem 1 of Dumitrescu et al. 2014); Kawamura & Soejima 2020 then gave a quantitative gap of \(21/20\), and Haeupler et al. 2019 an unbounded one. Theorem 2 of Dumitrescu et al. 2014 suggests that the ratio to the cyclic strategy is unbounded, but it holds only over a finite horizon. Theorem 3 of Czyzowicz et al. 2011 (optimality of the cyclic strategy for \(k \le 4\)) is proved for strictly positive speeds; whether it survives when robots may stop was not checked. A lower bound valid for both directions: no schedule has idle time below \(1/(v_1 + \dots + v_k)\) on the unit circle (Proposition 2 of Czyzowicz et al. 2011). Theorem 2.4 of Haeupler et al. 2019 was checked against its arXiv v2.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.