A First Step into Multi-Robot Patrolling

Soroush Sahraei · September 2026 · Research guide and proof sketches

A traveling salesman can finish a tour and go home. A patrol never finishes. A location visited a moment ago may need attention again before the robot reaches the next distant location. Add several robots and unequal priorities, and the problem becomes as much about timing as about routes.

I spent 62 days in summer 2026 working on this problem with Dr. Shang-En Huang, in the Fast Graph Algorithms Lab at National Taiwan University. Our joint work gives an approximation for weighted patrolling on trees whose guarantee depends only on the number of robots, a hardness result even for a fixed number of robots, and a stronger approximation on paths.

This note starts with the model, builds a map of the literature, and then explains the machinery behind our results. The literature connections come from my patrolling research knowledge graph. The account of our work follows v0 of our manuscript, Constant-Factor Approximation for Weighted Multi-Robot Patrolling on Trees. The manuscript has been submitted; these are manuscript results, not claims of publication or acceptance. Proof sketches below explain the arguments rather than reproduce every technical lemma.

Reading route: start with the model and a small example; use the landscape for orientation; read trees, hardness, and paths for our work. Connections explains how neighboring problems fit together.

1. What exactly are we minimizing?

Let $V$ be a finite set of sites in a metric space, with positive weights $w_v$. There are $k$ robots. Each follows a continuous trajectory $f_r(t)$ with speed at most one. On a tree, robots move along its edges; on a path, positions can be represented by real coordinates.

A visit happens whenever any robot occupies a site. Passing through counts. Robots may wait, meet, or cross; there are no collision constraints. Starting positions are chosen as part of the schedule. The task is to patrol the sites, not every point on every edge.

The latency at site $v$ is its longest visit-free interval:

The initial interval before the first visit counts too. The objective is

A high weight demands a short gap. For a proposed cost $C$, the requirement is $L_v\le C/w_v$. A site of weight $1$ must be revisited within $C$ time units; one of weight $1/16$ may wait sixteen times as long. This is why weights are also interpretable as inverse deadlines or rates at which urgency grows.

Two parameters must remain separate:

• $k$, the number of robots;
• $\rho=w_{\max}/w_{\min}$, the spread of site weights.

Multiplying all weights by the same number scales every schedule's cost but leaves approximation ratios unchanged. Coincident sites can be merged by keeping their largest weight. If there are at most $k$ distinct sites, parking one robot at each gives cost zero. Our nontrivial arguments concern the remaining case.

2. A small schedule worth working through

Consider a star with center $c$ and three leaves $A,B,C$. Each spoke has length $1/2$. Give the center weight $1$ and the leaves weights $1/2,1/4,1/4$ respectively. One robot repeatedly performs these center-to-leaf-to-center excursions:

A, B, A, C, then repeat.

Each excursion lasts one time unit. Leaf visits occur halfway through their slots. The resulting maximum gaps are:

The schedule has cost $1$. It is optimal for this instance: reaching any leaf and returning forces a visit-free interval of at least $1$ at the weight-$1$ center.

By contrast, repeating A, B, C gives every leaf gap $3$. Its cost is $3/2$, because A is underserved. Both schedules visit every site forever. The difference lies in allocating time according to urgency, not merely finding a short route through all sites.

This small example is also a preview of the hardness reduction: a center with a tight deadline can turn continuous movement into discrete unit-length jobs.

3. Why the obvious approaches are not enough

One tour treats unequal priorities alike

For one robot with equal weights in a general metric, the problem has a close relationship to TSP. With unequal weights, repeatedly taking a TSP tour can be $\Theta(n)$ worse than a schedule that revisits important sites more often. The foundational weighted single-robot work develops periodic patrol walks rather than relying on one repeated Hamiltonian tour.3

More robots do not mean equal slices

On an unweighted line, a suitable partition into back-and-forth patrols gives an exact polynomial-time solution. In the weighted case, optimal schedules may need cooperation between robots rather than disjoint territories. Afshani et al. exhibit this distinction in their line-patrolling analysis.1

Our tree algorithm nevertheless assigns one robot per cluster. That is a restriction of the output strategy, not an assumption about the optimum. The proof compares this restricted strategy against arbitrary cooperative schedules.

Average service is not a deadline guarantee

A schedule may have the right long-run frequency at every site yet leave one of them unattended for an unacceptable interval. The objective is a worst gap, not average delay or total travel. A frequency argument becomes useful only when it also controls when service occurs.

Infinite schedules need finite descriptions

An algorithm cannot print an infinite trajectory. It must output a rule that generates one. A periodic schedule is one possibility, but even a period may be too long to list explicitly when weights are binary encoded. Our tree algorithm uses a succinct modular description; our path algorithm explicitly describes a period whose size depends on $\rho$.

4. The approximation landscape

Here is the core comparison from the literature used in our manuscript. These are results in stated models, not interchangeable numbers and not an exhaustive claim about every paper available today.

The point of the tree result is independence from weight spread. For one, two, three, and four robots, the factors are $9,22,39,60$. “Constant factor” here means constant for each fixed $k$, not one universal constant independent of robot count.

It is not a uniform numerical improvement over every general-metric bound: a large $k$ and small $h$ can favor a bound proportional to $kh$. Conversely, for fixed $k$, increasing $\rho$ does not worsen our tree guarantee.

The path result improves the earlier factor $12$ in the general fixed-$k$ setting. It does not supersede the PTAS for exactly two robots. Its approximation ratio is independent of $\rho$, but its running time is not.

5. Our tree result: pay for edges, not weight classes

The proof has three parts: cluster sites around heavy depots, construct a one-robot schedule inside each cluster, and show that even an unrestricted optimal team must pay for the cluster's edge load.

Step 1: find at most k clusters

Process sites in nonincreasing weight order. For a trial value $\lambda$, assign a site $v$ to the first existing depot $a$ satisfying

If none works, make $v$ a new depot. The underlying separated-depots lemma says that $k+1$ sites, ordered by decreasing weight and satisfying

force every $k$-robot schedule to have cost at least $2\lambda$.

Why is this stronger than a static pigeonhole argument? Robots can hand off service. The proof must rule out a whole time-dependent team, not a fixed assignment. It keeps one designated robot near the heaviest depot, passes that designation between real robots, then removes it. The remaining visits can be joined into $k-1$ virtual trajectories, with a controlled speed increase. Rescaling time produces a smaller counterexample, giving an induction on robot count.

The algorithm does not know $\operatorname{OPT}_k$. It tests the finitely many critical values $0$ and $w_ud(u,v)/k$, with fixed tie-breaking, and takes the smallest successful value. The separation lemma implies a successful critical value at most $\operatorname{OPT}_k/2$. Every resulting cluster $A$, with depot weight $\bar w$, therefore has radius

These are partitions of the sites. Their spanning subtrees need not be edge-disjoint, which is harmless because robots have no collision constraints.

Step 2: give high and low weights different jobs

Normalize the cluster's weights by $\bar w$, so its depot has weight $1$. Call a site high if its normalized weight is at least $1/3$.

• High sites get the same closed depth-first tour $Q$ in every frame. Write $B$ for its length.
• For each low site $v$, choose the smallest power of two $p_v$ with $p_v\ge1/(3w_v)$. Then $p_v\ge2$ and $w_vp_v<2/3$.
• Low sites receive closed depot tours $P_t$ arranged so that $v$ is served in every $p_v$ consecutive frames.

The power-of-two structure is what makes these frequencies compatible. If an edge is needed by a frequent site, it inherits that site's short period. Less urgent sites can share the travel without forcing a separate payment for every weight class.

Step 3: compress the low-site schedule

The dyadic tree scheduler assigns vertices to residue classes: a vertex of period $2^h$ is due on one congruence class modulo $2^h$. It starts with a depth-first walk, recursively splits its rate-weighted mass into balanced pieces, and contracts edges whose required period has been reached.

A useful invariant is

Here $\mu(W)$ counts edge occurrences with mass $\ell_e/q(e)$, and $q(e)$ is the smallest required turnover time below the edge. On any day, active recursion nodes form a single root-to-leaf chain. Their due vertices can be connected to the depot using contracted edges plus one root path. Doubling that subtree gives a tour of length at most $2(\Psi+R)$.

The representation stores residues and a recursion tree, not a list of every day in the potentially enormous period. Given a day number, modular arithmetic identifies which vertices are due. This is why succinct output matters to the polynomial-time theorem.

Step 4: control the worst gap inside a frame

Let $D$ be the upper bound on a low-site tour's duration, and let a frame last $M=B+D$. In frame $t$, traverse $Q$, then $P_t$, then wait at the depot until the frame ends.

A high site has a chosen visit at the same offset in every frame, hence gap at most $M$. A low site's visits need not occur at the same offset. The safe bound is

not merely $p_vM$. Multiplying by its normalized weight gives

That extra within-frame term is exactly why the high/low threshold and period rounding are coordinated. The argument covers the initial wait as well as later gaps.

Step 5: an edge-load bound replaces the logarithmic loss

Set $p_v=1$ for high sites. Root the cluster subtree at its depot and define

An edge costs more when it lies on a route to a site that needs frequent service. A coefficient comparison between the high tour and the low scheduler gives

Now compare $\Phi$ with an arbitrary schedule for the whole instance of cost $L$ arbitrarily close to $\operatorname{OPT}_k$. Put $P=L/\bar w$ and divide time into slabs of length $3P$.

Every site $v$ must appear in every block of $p_v$ slabs. Within one slab, take each robot's portion between its first and last cluster visits and connect both ends to the depot. This costs at most $3P+2R\le(k+3)P$ per robot. Concatenating the at most $k$ walks costs at most $k(k+3)P$.

If a slab visits a site below edge $e$, its depot walk crosses that edge outward and back. Over $N$ slabs, the required crossings imply

Divide by $N$, let $N$ grow, and let $L$ decrease to the infimum. The result is

This charges actual edges at their required rates. There is no summation that pays a fresh approximation loss for every logarithmic weight class.

The final calculation

Returning to original weights, each cluster's cost is at most

Run the cluster schedules simultaneously, one robot per cluster. The global objective is their maximum, so there is no extra factor for the number of clusters.

Source within v0: the separated-depots, greedy-clusters, dyadic-tree-scheduler, frame-latency, structural-frame-bound, and slab-crossing lemmas, followed by the Trees theorem.

6. Why even a tree can encode a hard scheduling problem

The decision question is whether some schedule has cost at most a given threshold. Our manuscript proves it NP-hard on trees for every fixed integer $k\ge1$. This is not a claim that the unrestricted decision problem is NP-complete.

The starting problem is Dense Pinwheel Scheduling: positive integer periods $a_1,\ldots,a_m$ satisfy $\sum_i1/a_i=1$, and task $i$ must occur in every $a_i$ consecutive slots. Kleinberg and Mishra prove this dense version NP-complete in Corollary 5.1 of their 2026 preprint.5

A center becomes a clock

Build a star with spokes of length $1/2$. Its center has weight $1$; leaf $i$ has weight $1/a_i$. Ask for cost at most $1$.

A discrete pinwheel slot becomes an excursion from the center to its task leaf and back. It lasts exactly one unit, and the leaf visit occurs halfway through. Every pinwheel schedule therefore yields a feasible patrol.

Conversely, any useful excursion between consecutive center visits takes at least one unit to reach a leaf and return, but at most one unit because of the center's deadline. It must take exactly one. It cannot serve two distinct leaves. Enumerate these excursions and use their leaf names as a discrete sequence. Waiting between excursions only increases elapsed time, so the leaf gap bound implies that task $i$ appears within every $a_i$ excursion slots. The initial-gap condition also bounds its first occurrence.

The geometry has forced a continuous robot to obey a discrete scheduling clock.

More robots cannot escape the gadget

For a fixed $k$, take $k$ identical stars and connect their centers in a path using edges of length $3$.

Every interval of length $3/2$ must contain a visit to every center. One robot cannot visit two centers in such an interval. All $k$ robots are therefore needed to supply those $k$ visits. A trip between centers would create a length-$3/2$ interval in which the traveling robot visits no center, leaving too few robots. Transfers are impossible; each copy is permanently served by one robot.

This preserves the one-star equivalence while making a connected tree. Hardness comes from recurrent deadlines, not from choosing among many geometric routes. A tree has unique paths and can still contain difficult timing constraints.

7. Our path result: movement already provides coverage

On a line, a robot moving from left to right visits every intervening site. That simple fact allows a much tighter representation of a schedule.

For fixed $k$ and $0<\varepsilon\le1$, v0 gives a $(4+\varepsilon)$-approximation. The factor comes from two losses of two, followed by small discretization and search slack.

Two losses of two

First round each weight upward to a power of two:

The rounded optimum is at most twice the original one.

For a candidate value $V$, require a rounded-weight-$w_v'$ site to be visited in every aligned closed window of length $V/w_v'$. Windows are nested because their lengths are dyadic. A schedule of rounded cost at most $V$ satisfies these requirements. Conversely, one visit in every such window guarantees rounded weighted latency at most $2V$.

The second factor two is real: service near the beginning of one window and near the end of the next can leave nearly two window lengths between visits. Visits at a shared endpoint count for both adjacent closed windows.

A whole trajectory becomes a block and two endpoints

Inside a smallest window, record each robot's starting position $u$, ending position $v$, and the contiguous block of sites it is credited with visiting. Put

where $X$ is the credited set. The exact minimum travel time is

To see this, consider the two orders in which a route can reach the extremes: left first or right first. Their lengths are $2(b-a)+(u-v)$ and $2(b-a)-(u-v)$; choose the shorter one. Waiting fills any remaining time budget. If $X$ is empty, the formula reduces to $|u-v|$.

For example, start at $u=1$, end at $v=3$, and require visits to $0$ and $4$. The minimum is $2\cdot4-2=6$, attained by $1,0,4,3$.

This is the band lemma. It turns a continuous feasibility question into one exact inequality. The image of a continuous path over any time interval is itself an interval, so credited blocks can also be required to remain contiguous at every node of the dyadic window tree.

Make a finite dynamic program

A state at a window-tree node stores, for each robot:

• its credited block of site indices, possibly empty;
• entry and exit positions on a finite grid.

At a leaf, the band inequality checks the time budget. At an internal node, child positions must join, child blocks must have a contiguous union, and every site whose window is due at that level must be covered.

Boundary positions are rounded to a site-anchored grid of size $O(n\rho/\varepsilon)$. Changing an endpoint by distance $d$ changes the required travel time by at most $d$: prepend or append that short move. This endpoint-Lipschitz property pays for rounding with a small increase in the window budget.

Repeat by reflection, not by teleportation

Let $P_H$ be the longest window. A feasible root state describes each robot on $[0,P_H]$, but its end need not equal its start. Repeat the motion forward, then backward, with period $2P_H$.

Reflection joins endpoints continuously and preserves all aligned windows, because $P_H$ is an integer multiple of every smaller window. It creates an infinite schedule without adding another constant-factor loss.

Search without assuming the grid is monotone

The grid depends on the candidate value $V$, so the grid-feasibility predicate $Q(V)$ need not be monotone. The proof uses two different guarantees:

1. Soundness: $Q(V)$ yields a schedule of cost at most $2V$.
2. Approximate completeness: continuous canonical data at $V$ imply $Q((1+\eta)V)$.

Continuous canonical feasibility is monotone. If its threshold is $V^\star$, a rejected lower endpoint therefore satisfies $\mathrm{Lo}\le(1+\eta)V^\star$. Bisection keeps an accepted upper endpoint; stopping when $\mathrm{Up}\le(1+\eta)\mathrm{Lo}$ gives the needed approximation, without treating every rejection as an exact feasibility answer.

With $\eta=\varepsilon/16$, the returned cost is at most

The runtime caveat is part of the theorem

A crude explicit runtime bound in v0 is

The output has $O(k\rho)$ breakpoints per period. For fixed $k$, this is polynomial in the numerical value of $\rho$, not merely in the bit length of the weights. A compact binary input can have enormous $\rho$. This is not a polynomial-bit-complexity algorithm for arbitrary weight spread, nor a PTAS for the general fixed-$k$ path problem: its guarantee approaches $4$, not $1$.

The tree algorithm offers a useful contrasting tradeoff: weaker ratio on paths, but polynomial binary-input complexity and a succinct schedule.

8. Connections from the knowledge graph

The graph is useful because the same words conceal different models. These connections transfer ideas; approximation factors transfer only when assumptions match.

Persistent monitoring and growing urgency

Imagine each site's urgency increasing at rate $w_v$ and resetting upon a visit. Its largest urgency between resets is weighted latency. This is the continuous-travel version of Bamboo Garden Trimming. The discrete version instead spends one slot servicing one item without metric travel. Höhne and van Stee's $10/7$ approximation belongs to that discrete model, not arbitrary weighted tree patrol.7

A constructive connection also runs in the other direction: converting urgency requirements into suitable pinwheel periods can produce schedules. Pinwheel is not only a hardness source.

Gąsieniec et al. develop this urgency viewpoint in both discrete and continuous settings. Their continuous metric guarantees include $O(\log\rho)$ and $O(\log n)$; the discrete rates and service model lead to different bounds.11

Unweighted cyclic schedules

Afshani et al. study a specific cyclic strategy class: partition sites into groups, give each group a tour, and space its robots evenly along that tour. For unweighted instances with $k\ge2$, they prove a cyclic solution within $2(1-1/k)$ of unrestricted optimum. Combining the structural result with TSP approximation gives $3(1-1/k)+\varepsilon$ in general metrics and $2(1-1/k)+\varepsilon$ in fixed-dimensional Euclidean space.9

Neither expression should be substituted at $k=1$, and neither is a theorem for arbitrary weights. Also, “cyclic” in this result is more specific than “some periodic trajectory.” The connection to our work is the search for a tractable strategy class with a provable comparison to unrestricted motion.

Stars: easy geometry, different service models

For unweighted sites at the leaves of a star, Chen et al. give an $O(n\log n)$ exact algorithm that combines stationing robots at selected long-spoke leaves with a shared patrol of the rest. Their conference abstract sketches the proofs. This does not solve our weighted setting: the center in our hardness construction is itself a site with a deadline.13

For continuous Bamboo Garden Trimming on stars, Kusano obtains a $3$-approximation through a duration-aware scheduling formulation. The same paper shows that duration-aware pinwheel feasibility can remain strongly NP-hard even at arbitrarily small density. Long individual jobs create blocking that a global load statistic misses.12

The special two-robot line

Chuangpishit et al. obtain a $\sqrt3$-approximation for two unit-speed robots with unbalanced waiting-time requirements; Damaschke later gives a PTAS for two-robot line patrol. These are reasons to keep robot-count assumptions visible, rather than advertise $4+\varepsilon$ as the best bound for every line instance.10 4

Replenishment: similar constraints, different objective

In replenishment with fixed turnover times, each location must be visited sufficiently often, but the objective concerns the cost of daily depot tours. Bosman et al. obtain tree approximations of $2$ for minimum average tour cost and $6$ for minimum maximum tour cost. Those are not latency ratios for our problem.6

What transfers is the machinery: powers of two, synchronized recurring work, and balancing tree-tour load. Our dyadic scheduler likewise uses nested periods to decide which subtrees need service on a given day.

Simple strategy versus unrestricted optimum

Fence and circle patrolling often require service at every point of a continuous boundary and allow unequal robot speeds. Kawamura and Soejima show that natural partition and runner strategies can be suboptimal in those settings.8

The lesson is methodological: do not infer optimality from an appealing picture of independent patrol territories. Prove a comparison against unrestricted schedules. That is the role of our separated-depots and slab-crossing arguments.

Local geometry and global frequency

A frequency budget captures average workload. A spatial bottleneck captures where that workload must pass. Our tree proof combines both in $\ell_e/p_e$: the length of a necessary edge divided by its required service period. Our path proof instead exploits contiguous coverage. Different geometry calls for a different finite representation.

A warning about old open-problem lists

A knowledge graph is a reading aid, not a timeless authority. In particular, older discussions described ordinary Pinwheel NP-hardness as unresolved. Kleinberg and Mishra's 2026 preprint establishes NP-hardness, and its dense NP-completeness result supplies the source problem for our reduction.5

Likewise, a claim about an optimal cyclic strategy must specify the schedule class and whether weights are uniform. Our ability to output periodic approximate schedules does not prove that every unrestricted optimum is periodic, nor establish polynomial-size certificates for exact feasibility.

9. What remains open in our work?

Reduce the robot-count loss on trees. Can the $O(k^2)$ guarantee become $O(k)$ while staying independent of weight spread? In our proof, the quadratic term is visible in closing up to $k$ robot traces through a cluster whose radius already carries a factor $k$.

Keep the path factor without numerical dependence on weight spread. The dyadic window tree has $O(\rho)$ nodes. Can it be compressed while retaining the stronger path guarantee? A constant-factor polynomial-bit-time algorithm already follows from the tree result for fixed $k$; the challenge is to keep a factor near $4$, rather than to obtain any constant at all.

Understand exact certificates. Hardness does not settle NP membership. Succinct modular schedules certify the approximation algorithm's output, not the existence of a polynomial-size witness for every exactly feasible input.

Separate theorem from implementation. These are worst-case approximation algorithms and proof constructions. This note does not report a benchmarked robot controller or experimental speedup. Efficient implementations, useful constants on practical instances, and richer motion constraints are separate questions.

10. A reading route into the area

1. Start with weighted latency. Alamdari, Fata and Smith explain why shortest repeated tours are not enough.3
2. Add robots and compare metrics. Afshani et al. develop general-metric and line algorithms, with very different behavior in weighted and unweighted cases.1
3. Study the logarithmic baseline. Chen, Hung and Klasing show how multiclass minimum spanning forests improve dependence on robot count.2
4. Read our tree proof as a chain of certificates. Clustering certifies radius; the dyadic scheduler certifies visit frequency and tour length; slab crossings certify that an unrestricted optimum pays for the load.
5. Read the path proof as a representation theorem. Interval coverage, band traversal, boundary states, and reflection matter more than memorizing the final constant. Compare the separate two-robot PTAS.4
6. Follow the scheduling links. Pinwheel supplies hardness; replenishment and Bamboo Garden Trimming supply recurring-service techniques.5 6 7

The central question is not “which route should each robot take?” It is which movement must happen, how often, and how can those obligations share travel without creating a long unattended gap? Trees let us charge that obligation to edges. Paths let us encode it as intervals. That distinction drives our two algorithms.

Sources

1 https://arxiv.org/abs/2005.02530 · Afshani et al. · Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency (WAFR 2020; proceedings 2021)

2 https://hal.science/hal-04728521v1 · Chen, Hung and Klasing · Multiclass Minimum Spanning Forests (AAIM 2024)

3 https://arxiv.org/abs/1202.5619 · Alamdari, Fata and Smith · Persistent Monitoring in Discrete Environments (IJRR 2014)

4 https://doi.org/10.1007/978-3-030-48966-3_16 · Damaschke · Two Robots Patrolling on a Line (IWOCA 2020)

5 https://arxiv.org/abs/2604.13974 · Kleinberg and Mishra · NP-Hardness and a PTAS for the Pinwheel Problem (2026 preprint)

6 https://arxiv.org/abs/1712.05218 · Bosman et al. · Replenishment Problems with Fixed Turnover Times (Algorithmica 2022)

7 https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.16 · Höhne and van Stee · Discrete Bamboo Garden Trimming and Continuous Trimming on Star Graphs (2023)

8 https://arxiv.org/abs/1411.6853 · Kawamura and Soejima · Simple Strategies versus Optimal Schedules in Multi-Agent Patrolling (CIAC 2015; TCS 2020)

9 https://arxiv.org/abs/2203.07280 · Afshani et al.: On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem (SoCG 2022)

10 https://arxiv.org/abs/1710.00466 · Chuangpishit et al.: Patrolling a Path Connecting a Set of Points with Unbalanced Frequencies of Visits (SOFSEM 2018)

11 https://arxiv.org/abs/2202.01567 · Gąsieniec et al.: Perpetual Maintenance of Machines with Different Urgency Requirements (2024 version)

12 https://doi.org/10.1007/978-3-032-17801-5_46 · Kusano: Limitations of Density-Based Heuristics and an Alternative Approach for Pinwheel Scheduling with Durations (SOFSEM 2026)

13 https://doi.org/10.1049/icp.2026.1985 · Chen et al.: Multi-Robot Patrol-Scheduling with Min-Max Latency on Stars (ICETA 2025)

Back to notes · Research experience