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 agents is optimal for 2 and 3 agents but not in general; optimal schedules can be up to \(4/3\) better.
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.
- 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
Results, in order of publication
Introduces patrolling by agents with distinct speeds; shows the partition strategy optimal for \(k=2\) and conjectures it optimal for every \(k\), as stated by Kawamura & Kobayashi 2015, who disproved the conjecture.
Schedules that patrol a segment \(4/3\) times longer than partition.
Open questions
How much better than partition can an optimal schedule be on a segment, and is the problem of computing an optimal schedule hard?
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.