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, two-way, distinct speeds
draftIf robots may reverse, two robots gain nothing over the cyclic strategy, but for suitable speeds a train of slow robots with one fast robot shuttling along it beats both simple strategies by a factor approaching \(3/2\).
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: 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
Results, in order of publication
For \(k = 2\) no schedule moving in both directions beats the cyclic strategy (Theorem 4). For three robots with speeds \(1, \tfrac12, \tfrac13\) a schedule in which some robots reverse has idle time \(\tfrac{35}{36}\), below the idle time \(1\) of the cyclic strategy and of the partition (Theorem 5; the conference version omits the analysis and gives the schedule as a figure). Dumitrescu, Ghosh and Tóth restate these idle times (35/36 against 12/11 for the partition and 1 for the cyclic strategy) Dumitrescu et al. 2014.
Proposition 1 (train algorithm \(A_3\)): robots \(a_2,\dots,a_k\) equally spaced move one way at speed \(v_k\), and the fastest robot \(a_1\) shuttles back and forth along the arc between the end and the start of the train. With \(v_1 = 1\) and \(v_2 = \dots = v_k = 1/k\) its idle time tends to \(2/3\), against \(1\) for the partition and the cyclic strategy; for every \(k \ge 4\) some speeds make it beat both. Proposition 2: for every \(k \ge 2\) some speeds have an optimal schedule that leaves up to \(k-1\) robots unused (on a segment every robot is needed).
Open questions
What is the largest ratio between optimal schedules and the best simple strategy on the two-way circle? It lies between \(3/2\) Dumitrescu et al. 2014 and 2, since partition patrols \(\sum_i v_i/2\) and no schedule patrols more than \(\sum_i v_i\) (Proposition 2 of Czyzowicz et al. 2011).
Notes
The analysis of Theorem 5 of Czyzowicz et al. 2011 is omitted in the conference version, so its \(35/36\) is not checked; the best result, Proposition 1 of Dumitrescu et al. 2014, was checked with its proof. The setting stays a draft only because of Theorem 5.
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
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.