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).
Graphs with faulty patrollers
verifiedWith at most \(f\) unreliable robots among \(k\), the optimal idle time lies between \((f+1)|E|/k\) and \((f+1)\,\mathrm{CPT}(G)/k\), which coincide on Eulerian graphs; computing it is NP-hard.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Fence: graph
- Every point of every edge of a graph \(G\) must be visited; robots move along edges.
- Faults: crash faults
- Up to \(f\) robots may fail to detect or to report the target when they pass over it.
- Speeds: equal speeds
- All robots move at most at unit speed.
- 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.
Statement for this variant
\(k\) unit-speed robots move perpetually along the edges of a connected graph \(G\) whose edges are curves of given lengths; \(|E|\) is the total length. Knowing the strategy, an adversary chooses a set of \(f\) faulty robots, whose visits do not count, a point \(p\) and a time \(t\). The idle time of a strategy is the supremum, over these choices, of the length of an interval starting at \(t\) during which no reliable robot visits \(p\); the goal is to minimise it.
What is known
- any connected graph, \(k \ge 2\), \(f \le k-1\)
- every point must be passed by at least \(f+1\) robots within each idle window, else the adversary makes them all faulty
- \(k = 3\) robots, at most one faulty
- graphs with unit-length edges
- reduction from 3-edge-colouring of cubic graphs
Results, in order of publication
Introductory and current best: robots equally spaced along a Chinese Postman Tour (Theorem 3); equals \((f+1)|E|/k\) on Eulerian graphs (Corollary 1). For a segment with \(f < k/2 - 1\) the paper gives a three-group strategy that is optimal for odd \(f\) and almost optimal for even \(f\) (Theorems 1 and 2).
Open questions
Is the decision version of fault-tolerant patrolling in NP? With \(k\) part of the input and integer edge lengths it is in PSPACE Czyzowicz et al. 2017.
Optimal fault-tolerant patrolling of a segment when \(f \ge k/2 - 1\), and for even \(f\) Czyzowicz et al. 2017.
Approximation algorithms for the optimal idle time on general graphs Czyzowicz et al. 2017.
Notes
Faulty here means a robot whose visits do not count; the adversary chooses the faulty set knowing the strategy. \(\mathrm{CPT}(G)\) is the length of a Chinese Postman Tour of \(G\). Kotzig graphs (cubic graphs whose three perfect matchings pairwise form Hamiltonian cycles) attain the minimum idle time \(\tfrac23|E|\), the number of their vertices, for \(k = 3\), \(f = 1\) (Corollary 2). The problem was posed at a MITACS workshop in 2012. Checked against the full text of Czyzowicz et al. 2017.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.