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, distinct speeds
verifiedOn a circle, optimal schedules can beat the simple strategies by a factor \(21/20\).
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\).
- 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
Open questions
None recorded for this variant.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.