Mobility Matters
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
v1 = 1v2 = 2v3 = 1123Start: piece i has length vi/2Time 1/2: each robot turns at the end of its pieceFinal: back after time 1; every point visited again
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:

  1. Cut the fence into \(k\) pieces, piece \(i\) of length \(v_i/2\).
  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. 2017e

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. 2017e 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\):

  1. The four robots of speed 1 walk end to end, covering most of the fence in a staggered pattern.
  2. The fast robot covers most of what they leave uncovered.
  3. 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
Closed fence, one-way, distinct speeds
With every robot moving in one direction, the cyclic strategy is optimal for up to four robots but not within any constant factor in general: every set of robots patrols a circle of length \(\sum_i v_i/(33\ln\log_2 k)\).
near-optimal \(\frac{1}{33\ln\log_2 k}\sum_i v_i\) vs \(L \le \sum_i v_i\) space-time coverage
Closed fence, two-way, distinct speeds
If 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\).
unknown \(\to\tfrac32\times\text{simple}\) vs —
Open fence, distinct speeds standard
Partitioning the segment among the robots is optimal for 2 and 3 robots but not in general: optimal schedules can patrol a segment almost, but never quite, twice as long.
tight \(\to 2\times\text{partition}\) vs \(\text{partition is not optimal}\) distinct speeds
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 6

Closed fence, one-way, distinct speeds

  1. Close the factor \(O(\log\log k)\) between the schedule of Haeupler et al. 2019 and the bound \(\sum_i v_i\) on the one-way circle.

Closed fence, two-way, distinct speeds

  1. 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).

Open fence, distinct speeds

  1. Is computing an optimal schedule for given speeds on a segment hard?

Graphs with faulty patrollers

  1. 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. 2017e.
  2. Optimal fault-tolerant patrolling of a segment when \(f \ge k/2 - 1\), and for even \(f\) Czyzowicz et al. 2017e.
  3. Approximation algorithms for the optimal idle time on general graphs Czyzowicz et al. 2017e.

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: optimal schedules patrol a segment almost twice as long as partition, and a one-way circle unboundedly longer than the cyclic strategy Haeupler et al. 2019; faults later changed the question to the idle time a graph admits when up to \(f\) patrollers are unreliable Czyzowicz et al. 2017e.

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.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Das et al. 2019c Patrolling on Dynamic Ring Networks. Patrolling 1-interval-connected rings: with visibility limited to the current node the idle time is \(n - \alpha k\), only an additive gain over one agent (Section 4); with a global snapshot, upper and lower bounds that differ by small constant factors for 2 agents and for \(k > 2\) agents, and a separation between agents that know the schedule of the ring and agents that do not. Read (arXiv v1).
  • Chuangpishit et al. 2018a Patrolling a Path Connecting a Set of Points with Unbalanced Frequencies of Visits. Points on a path, each with its own required frequency of visits, patrolled by two robots: approximation algorithms, the best with ratio \(\sqrt 3\). Read (arXiv v1).
  • Morales-Ponce 2022 Optimal patrolling of high priority segments while visiting the unit interval with a set of mobile robots. A unit segment whose high-priority parts must be revisited as often as possible while the rest is visited infinitely often, by \(k\) unit-speed robots: a lower bound on the idle time from lid covers of the high-priority parts, computed in \(O(\max(k, n)\log n)\) time for \(n\) parts, and a schedule that attains it. Read (arXiv v1).
  • Georgiou et al. 2025a The Fagnano Triangle Patrolling Problem. One unit-speed robot patrols the three edges of an acute triangle so that the longest time between two visits of an edge is minimised: the orthic triangle, the classical answer to Fagnano's problem, is optimal, and billiard trajectories solve a related 2-gap problem. Read (arXiv v6).
  • Amir et al. 2023 Patrolling Grids with a Bit of Memory. One agent patrols a \(d\)-dimensional grid graph with little memory: some grids cannot be patrolled with 0 bits whatever the sensing range, an exact characterisation of the grids patrollable with 0 bits and range \(V\), and a 1-bit algorithm with range 1 for every grid. Read (arXiv v2).
  • Afshani et al. 2021 Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. Patrol scheduling with weighted latency: \(k\) robots of equal speed visit \(n\) sites of a metric space to minimise the largest weighted time between visits of a site. A polynomial \(O(k^2\log\frac{w_{\max}}{w_{\min}})\)-approximation; on a line, an exact algorithm for equal weights and a 12-approximation for weights. Read (arXiv v3).
  • Chen et al. 2024 Improved Approximation Algorithms for Patrol-Scheduling with Min-Max Latency Using Multiclass Minimum Spanning Forests. The same patrol scheduling on a weighted metric graph: a \(5h\)-approximation for one robot (Theorem 1) and an \(O(kh)\)-approximation for \(k\) robots (Theorem 2), with \(h = \log_2\frac{w_{\max}}{w_{\min}} + 1\), improving on Afshani et al. 2021. Read (HAL version).
  • Oshrat et al. 2020 Adversarial Fence Patrolling: Non-Uniform Policies for Asymmetric Environments. Adversarial fence patrolling: non-uniform probabilistic policies along an open polyline raise the minimal probability of detecting a penetration above uniform ones (AAAI). Abstract read.
  • Coleman & Morales-Ponce 2023 The Snow Plow Problem: Perpetual Maintenance by Mobile Agents on the Line. The snow plow problem: snow falls continuously on the segment \([0,1]\), and \(k\) robots of equal speed (their \(n\) agents) must plow every point infinitely often and carry what they collect to a dump point. With the dump at an endpoint and uniform snowfall, giving each robot one interval so that all carry the same largest load is optimal and is computed in \(O(k)\) time (Theorem 3.3); for costs given by a travel function and a snowfall function, a \((1+\varepsilon)\)-approximation in \(O(k\log(1/\varepsilon))\) time (Theorems 3.7, 4.1), exact in \(O(k)\) time when both are linear or constant (Theorem 3.8). Read in full.

All settings

The assumption tree (4 settings, 2 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 › Direction of movement › Faults › Speeds › Communication › Randomness.

tight near-optimal polynomial gap unknown impossible no variant

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: partition on the segment, and on the circle the cyclic strategy for robots that all move in one direction; on the circle the same paper shows that for three robots moving in both directions neither simple strategy is optimal Czyzowicz et al. 2011. Kawamura and Kobayashi disproved the segment conjecture Kawamura & Kobayashi 2015, Dumitrescu, Ghosh and Tóth disproved the one-way circle conjecture and showed that on the two-way circle a new strategy beats both simple ones by a factor approaching \(3/2\) Dumitrescu et al. 2014, 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 with every robot moving in one direction 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. 2017e.

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

Direction of movement

0one-way: every robot moves in the same fixed direction1two-way: robots may reverse direction at any time

Czyzowicz, Gąsieniec, Kosowski and Kranakis first studied the circle with every robot moving in the same direction, since "in order to profit from the circle topology it may seem natural to try to traverse the cycle always in the same direction", and then asked whether allowing both directions helps: it does not for two robots, but it does for some speeds of three Czyzowicz et al. 2011. Dumitrescu, Ghosh and Tóth studied both versions, as the unidirectional and the bidirectional unit circle Dumitrescu et al. 2014, and Kawamura and Soejima call the first the (unidirectional) circle patrolling problem Kawamura & Soejima 2020. The scale is one-way < two-way: a one-way schedule is also a two-way schedule.

Formal definitions
0one-way
On a closed fence every robot moves only counterclockwise, at any speed between \(0\) and its maximum speed \(v_i\); it never reverses. Czyzowicz et al. require strictly positive speeds, while Dumitrescu, Ghosh and Tóth and Kawamura and Soejima allow robots to stop; the counterexample of Dumitrescu et al. holds under both conventions (Remark after Theorem 1 of Dumitrescu et al. 2014). Schedules are a subset of the two-way schedules, so this is the harder level for the robots.
1two-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.

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