Home›Search in geometric domains›Search, evacuation and patrolling›Patrolling

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 measurescollapse

Fence patrolling: robots with maximum speeds \(v_1, \dots, v_k\) move forever along a segment so as to minimise the idle time, the longest interval during which some point is not visited. The animation runs the partition strategy Czyzowicz et al. 2011 with speeds \(1, 2, 1\): robot \(i\) sweeps its own piece, of length \(v_i/2\), back and forth at full speed (bars: the part swept on the way out, then on the way back), so every point is visited again within time 1 and a fence of length \((v_1 + \dots + v_k)/2\) is patrolled; this is not always optimal Kawamura & Kobayashi 2015.

\(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).

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Security guards with different walking speeds must watch a long straight fence so that no point is left unvisited for too long. In fence patrolling the guards are \(k\) robots with maximum speeds \(v_1, \dots, v_k\) that move forever along the fence, here a segment; a point is visited when some robot is at it. The idle time is the longest stretch of time during which some point of the fence is not visited by any robot. Equivalently, fixing the idle time to 1, we ask for the longest fence, of length \(\ell\), that the robots can patrol. Robots may pass each other, and the schedule, the motion of every robot over time, is planned in advance.

1AlgorithmPartition: give each robot its own piece Open fence, distinct speeds → Czyzowicz et al. 2011

The partition strategy:

Cut the fence into \(k\) pieces, piece \(i\) of length \(v_i/2\).
Robot \(i\) walks back and forth over its own piece at full speed, forever.

Why it works and what it costs. A round trip over piece \(i\) takes \(2 \cdot (v_i/2)/v_i = 1\), so every point of the piece is visited at least once in every unit of time, and the fence has length \(\ell = (v_1 + \dots + v_k)/2\). On the other hand, in any unit of time robot \(i\) visits a stretch of at most \(v_i\), so no schedule patrols more than \(v_1 + \dots + v_k\): partition is within a factor 2 of optimal. Czyzowicz et al. 2011 proved it optimal for \(k = 2\) and conjectured it optimal for all \(k\); Kawamura & Kobayashi 2015 confirmed \(k = 3\).

Why it matters. Partition is the natural first answer, and it is used as a building block in most patrolling strategies.

2Lower boundEvery point needs \(f+1\) visitors: a counting bound Graphs with faulty patrollers → Czyzowicz et al. 2017

Now patrol a graph: nodes joined by edges, where each edge is a segment with a length; the fence is the union of the edges, of total length \(|E|\). There are \(k\) robots of speed 1, of which up to \(f\) are unreliable: their visits do not count, and the adversary, an opponent who knows the schedule, picks them. Take any window, an interval of time of length \(T\) equal to the idle time. If some point is visited in that window by only \(f\) distinct robots or fewer, the adversary declares those robots unreliable and the point counts as not visited. So every point must be visited by at least \(f+1\) different robots in the window.

Why it holds. Together the robots walk at most \(kT\) in the window, and they must cover every point of every edge \(f+1\) times, which needs at least \((f+1)|E|\). Hence \(T \ge (f+1)|E|/k\). Czyzowicz et al. 2017 match it on graphs where a closed walk (a route along edges that ends where it starts) uses every edge exactly once: spread the robots evenly along that walk, \(|E|/k\) apart, so every point is visited by a new robot every \(|E|/k\) time units; in general they use a shortest closed walk through all edges and show that finding the optimum is NP-hard.

Why it matters. Counting total work against what must be covered is the simplest lower-bound technique in patrolling, and it is tight here.

3AlgorithmSix robots beat the partition Open fence, distinct speeds → Kawamura & Kobayashi 2015

Take six robots with speeds \(1, 1, 1, 1, 7/3, 1/2\). Partition patrols a fence of length \((1+1+1+1+7/3+1/2)/2 = 41/12\). Kawamura & Kobayashi 2015 patrol a longer fence, of length \(7/2\):

The four robots of speed 1 walk end to end, covering most of the fence in a staggered pattern.
The fast robot covers most of what they leave uncovered.
The slowest robot fills the last small gaps.

Why it works and what it costs. Since \(7/2 = 42/12 > 41/12\), the conjecture that partition is always optimal is false; adding further robots shows it fails for every \(k \ge 6\). Later schedules patrol fences up to \(4/3\) times longer than partition Kawamura & Soejima 2020, and on a circle simple strategies can be beaten by a factor \(21/20\). The optimal schedule for general speeds is unknown.

Why it matters. It shows that sharing pieces of the fence can beat dividing it, which is why even this one-dimensional problem is still open.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Idle time

Open fence, distinct speeds standard

Partitioning 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.

unknown \(\tfrac43\times\text{partition}\) vs \(\text{partition is not optimal}\) distinct speeds

Closed fence, distinct speeds

On a circle, optimal schedules can beat the simple strategies by a factor \(21/20\).

unknown \(\tfrac{21}{20}\times\text{simple}\) vs —

Graphs with faulty patrollers

With 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.

tight \((f+1)\,\mathrm{CPT}(G)/k\) vs \((f+1)|E|/k\) faulty reports

Open questions 4

Open fence, distinct speeds

How much better than partition can an optimal schedule be on a segment, and is the problem of computing an optimal schedule hard?

Graphs with faulty patrollers

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.

What the community started looking at

Patrolling asked first for optimal strategies and whether the simple ones, partitioning the fence or cycling around it, are optimal Czyzowicz et al. 2011. They are not in general Kawamura & Kobayashi 2015 Kawamura & Soejima 2020; faults later changed the question to the idle time a graph admits when up to \(f\) patrollers are unreliable Czyzowicz et al. 2017.

Perspectives

From the cow path to evacuation The line of work from Bellman's and Beck's linear search problem to group search with faulty robots, evacuation of disks and polygons, priority evacuation, and patrolling by robots with distinct speeds.

All settings

The assumption tree (3 settings, 1 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Idle time); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Fence › Faults › Speeds › Communication › Randomness.

tight near-optimal polynomial gap unknown impossible no variant

No assumptions · 3 branches by fence Nothing is assumed on any axis.

Assumptions specific to this problem

Fence

0the edges of a graph1a segment (open fence)1a circle (closed fence)

Patrolling asks agents to visit every point of a terrain often enough; the measure is the idle time, the longest time a point is left unvisited Kawamura & Kobayashi 2015. Czyzowicz, Gąsieniec, Kosowski and Kranakis proposed the open fence (a segment) and the closed fence (a circle) for agents with distinct speeds at ESA 2011, and conjectured that simple strategies are optimal on both Czyzowicz et al. 2011 (as reported by Kawamura & Soejima 2020). Kawamura and Kobayashi disproved the segment conjecture Kawamura & Kobayashi 2015, and Kawamura and Soejima showed that optimal schedules can beat the simple strategies by factors \(4/3\) on the segment and \(21/20\) on the circle Kawamura & Soejima 2020. They note that "finding an optimal strategy is not at all straightforward, even when the terrain is as simple as it could be" Kawamura & Soejima 2020. Graphs, the most general domain, were studied by Czyzowicz et al. with unreliable robots: the domain is "represented by all points belonging to the graph edges", and edges are rectifiable curves whose lengths are their weights Czyzowicz et al. 2017.

Formal definitions

0graph: Every point of every edge of a graph \(G\) must be visited; robots move along edges.
1segment: An open fence: the segment \([0,\ell]\); robots may reverse direction anywhere.
1circle: A closed fence: a circle of length \(\ell\).

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.