Source-linked AI summary
On cooperative patrolling: optimal trajectories, complexity analysis, and approximation algorithms
Fabio Pasqualetti, Antonio Franchi, Francesco Bullo
TL;DR
The paper studies how teams of autonomous robots can patrol graph-modeled environments while minimizing revisit gaps and information-spreading time. It develops exact and distributed methods for chain roadmaps, a conditional polynomial method for trees, and approximation methods for cyclic roadmaps, where the optimization problem is NP-hard.
Problem
The paper addresses the open problem of designing minimum-refresh-time and minimum-latency team trajectories for general environments.
Method
The authors model environments as graph roadmaps and analyze chain, tree, and cyclic cases using optimal partitioning, distributed synchronization, and approximation algorithms.
Results
The paper gives polynomial-time chain methods, a polynomial-time tree method under a constant-robot assumption, and cyclic-roadmap approximations with a factor-8 refresh-time guarantee.
Takeaways & Limitations
Patrolling complexity depends on roadmap structure: chains admit optimal polynomial procedures, trees are tractable under a robot-count restriction, and cyclic environments require approximation.
Abstract
from arXiv · showhide
The subject of this work is the patrolling of an environment with the aid of a team of autonomous agents. We consider both the design of open-loop trajectories with optimal properties, and of distributed control laws converging to optimal trajectories. As performance criteria, the refresh time and the latency are considered, i.e., respectively, time gap between any two visits of the same region, and the time necessary to inform every agent about an event occurred in the environment. We associate a graph with the environment, and we study separately the case of a chain, tree, and cyclic graph. For the case of chain graph, we first describe a minimum refresh time and latency team trajectory, and we propose a polynomial time algorithm for its computation. Then, we describe a distributed procedure that steers the robots toward an optimal trajectory. For the case of tree graph, a polynomial time algorithm is developed for the minimum refresh time problem, under the technical assumption of a constant number of robots involved in the patrolling task. Finally, we show that the design of a minimum refresh time trajectory for a cyclic graph is NP-hard, and we develop a constant factor approximation algorithm.
I. INTRODUCTION
The paper formalizes cooperative patrolling over graph-based roadmaps, optimizing refresh time and latency for autonomous robot teams. It develops exact methods for chains, conditional polynomial methods for trees, and approximation methods for cyclic environments.
- Motivation: The paper addresses continuous surveillance by scheduling trajectories for teams of autonomous robots.The motivation includes monitoring oil spills, detecting forest fires, tracking border changes, and patrolling environments.
- Problem formulation: Refresh time measures the longest gap between visits to a region, while latency measures the time needed to inform all robots about an event.Finite latency requires synchronized motion when communication occurs only at simultaneously occupied adjacent vertices.
- Problem complexity: Minimum refresh-time and latency trajectories are generally difficult to design, motivating specialized algorithms for chain, tree, and cyclic roadmaps.The paper notes that designing optimal trajectories for a general environment is an open problem and that traditional approaches often use space decomposition and traveling-salesperson tours.
- Contributions: For chain roadmaps, the paper characterizes optimal trajectories, computes them through polynomial-time partitioning, and develops distributed procedures for convergence and synchronization.The partitioning procedure is based on bisection and is amenable to distributed implementation.
- Contributions: For cyclic roadmaps, the paper proves NP-hardness and gives a path-covering approximation whose refresh time is within a factor of 8 of minimum.The factor-8 method is presented as the first constant-factor approximation algorithm for this NP-hard problem, to the authors’ knowledge.
- Roadmap model: The environment is represented by a connected weighted roadmap whose vertices provide sensor coverage and whose edges support robot motion and communication.Edge weights correspond to path lengths, and the roadmap can be constructed from strategically selected viewpoints.
C. Refresh time of team trajectories: definitions and a preliminary complexity result
The paper defines team refresh time and formalizes the corresponding optimization problem, then establishes general computational hardness and structural reductions for chain roadmaps. On a chain, optimal trajectories can be represented by ordered, non-overlapping partitions whose cluster dimensions determine minimum refresh time.
- Definitions: Refresh time is the longest interval between consecutive visits to any viewpoint by the team.The team refresh-time problem seeks a trajectory minimizing this worst-case interval.
- Complexity: The Team refresh time problem is NP-hard, by restriction to the single-robot shortest closed-tour case.With one robot, bounded speed makes minimum refresh time equivalent to finding a shortest tour through all viewpoints.
- Chain structure: On a chain, every trajectory has an order-invariant equivalent with the same refresh time, and an optimal trajectory can also be made non-overlapping.These transformations preserve refresh time while simplifying the robots’ visited viewpoint sets.
- Optimal characterization: For a chain, minimum refresh time equals twice the minimum dimension of an m-partition: RT∗ = 2 minΠm dim(Πm).Each robot periodically sweeps its assigned cluster at maximum speed, producing refresh time twice the largest cluster dimension.
- Partition objective: Removing the longest chain edges minimizes average cluster length but generally does not minimize the maximum cluster dimension required for refresh-time optimality.The paper illustrates this distinction with a four-partition example.
B. Optimal m-partition centralized computation
The centralized chain-roadmap algorithm searches over left-induced partitions, whose cardinality decreases monotonically with partition length. Exact optimization requires testing discontinuity points, while bisection yields an ε-accurate solution with near-linear dependence on the number of viewpoints.
- Left-induced partitions: A left-induced partition of length ρ groups consecutive viewpoints into clusters spanning at most ρ.Its clusters are recursively formed from the leftmost remaining viewpoint.
- Partition cardinality: The cardinality |Πρ| is monotone non-increasing and right-continuous, with |Πρ| ≤ k exactly when ρ ≥ ρk.Coincident discontinuities can cause some cardinalities, such as 9 in the example, never to occur.
- Optimality: An optimal left-induced partition of cardinality at most m is also an optimal m-partition.The optimal dimension occurs at a discontinuity point of |Πρ|.
- Exact computation: O(n^2) complexity results from testing lengths associated with pairwise viewpoint distances.Only discontinuity points need to be considered for exact centralized computation.
- Approximate computation: An ε-approximation computed by bisection returns dimension at most ρ∗ + ε and cardinality at most m in O(n log(ε−1)) time.Each evaluation of the partition cardinality takes O(n) operations.
- Trajectory construction: Using the computed partition, the minimum-refresh-time trajectory has refresh time 2dmax and can be designed in O(n log(ε−1)) time.The trajectory is generated by periodically sweeping each assigned cluster.
IV. MINIMUM REFRESH TIME AND LATENCY TEAM TRAJECTORY ON A CHAIN ROADMAP
The paper extends chain-roadmap patrolling from refresh-time optimization to communication latency, where robots must exchange information through synchronized adjacent interactions. It defines directional and overall latency measures and seeks synchronized trajectories that retain an optimal partition while minimizing these communication delays.
- Latency definition: Latency measures the time needed for information to propagate through the robot team along adjacent communication links.On a chain, every adjacent robot pair must communicate for a message to reach the entire team.
- Directional latency: Up-latency is the longest interval between successive communications at the two endpoint robot pairs, accounting for ordered multi-hop propagation.The definition tracks feasible communication times from the first pair through the last pair.
- Latency objective: Overall latency is the maximum of up-latency and down-latency: LT(X) = max{LTup(X), LTdown(X)}.Down-latency is defined analogously for propagation in the reverse direction.
- Trajectory design: The proposed chain trajectories are synchronized, preserve an optimal refresh-time partition, and minimize up-latency, down-latency, or latency.The selected criterion depends on whether communication is assessed from one endpoint or in a fully distributed scenario.
A. Lower bound and optimal team trajectory for up-latency
For a chain roadmap, the paper derives a lower bound on up-latency and constructs a trajectory attaining it while also achieving minimum refresh time. The trajectory is computable in O(n log(ε^-1)) time, with down-latency obtained analogously.
- Lower bound: The up-latency lower bound follows because robots must traverse their assigned clusters to communicate with neighboring robots.The speed bound of 1 yields the traversal-time lower bound.
- Lower bound: Attaining the lower bound requires robot i to communicate with robot i + 1 as soon as xi(t) = ri.This transfers messages across consecutive clusters without waiting at the right extreme.
- Optimal trajectory: A 2dmax-periodic trajectory on an optimal m-partition achieves minimum refresh time 2dmax and minimum up-latency Pm−1 j=2 dj.The trajectory is generated by Trajectory 3.
- Special case: When all clusters have length dmax, opposite-phase trajectories make up-latency and down-latency equal to (m −2)dmax.This is a special simplification for equal-length clusters.
B. Lower bound for latency
The latency analysis restricts attention to 2dmax-periodic trajectories and derives lower bounds from limits on communication frequency. Aggregating consecutive clusters yields the general bound for arbitrary optimal partitions.
- Periodic trajectories: Restricting trajectories to period 2dmax also minimizes refresh time whenever the refresh time is finite.The latency analysis therefore studies periodic trajectories on an optimal partition.
- Communication frequency: When di + di+1 > dmax, at most one communication sequence can occur within any period of length 2dmax.This follows from the bounded robot speed and the distance robots must traverse between communications.
- Simple case: In the simple case, message-transfer constraints impose a latency lower bound of (m −2)dmax.A message can move three robots forward only across the intervening clusters within the periodic communication limits.
- General case: For arbitrary partitions, consecutive clusters are aggregated so adjacent aggregated groups have combined length greater than dmax.The aggregated clusters preserve the relevant latency structure while accounting for short neighboring clusters.
- General case: The general latency lower bound is (m̄ −2)dmax + (d̄1 −d1) + (d̄m̄ −dm).The endpoint correction terms arise because delivery is measured between the original first and last robots rather than the aggregated chain.
C. Optimal team trajectory for latency
Using an optimal partition and aggregated clusters, the paper constructs a chain trajectory that attains both minimum refresh time and the general latency lower bound. Its design has complexity O(n log(ε^-1)).
- Construction: Trajectory 4 synchronizes robots over aggregated clusters whose consecutive lengths sum to more than dmax.This structure enforces the communication-frequency condition used in the latency lower bound.
- Construction: Extreme viewpoints determine alternating communication times, with left and right extremes assigned to complementary phases of the 2dmax period.The trajectory specifies waiting and motion at cluster extremes according to aggregated-cluster position.
- Optimality: The constructed trajectory has minimum refresh time 2dmax and minimum latency (m̄ −2)dmax + d̄1 −d1 + d̄m̄ −dm.It is computed from an optimal m-partition and the associated aggregated clusters.
- Complexity: The trajectory-design complexity is O(n log(ε^-1)).The complexity is inherited from computing the optimal m-partition.
V. DISTRIBUTED SYNCHRONIZATION ALGORITHM ON A CHAIN ROADMAP
The distributed chain-roadmap procedure computes an optimal partition and uses feedback to synchronize robot motion. After finite time, it converges to a trajectory with minimum refresh time and latency, independent of the initial motion directions.
- Distributed partitioning: The distributed procedure first forms an optimal left-induced partition and assigns one cluster to each robot.A leader can compute the partition after the robots gather and elect leadership.
- Feedback synchronization: Feedback synchronization changes velocity at cluster extremes and makes robots wait for neighboring communication before continuing.This reproduces the timing behavior required by the optimal open-loop trajectory.
- Convergence: After finite time, Algorithm 5 produces minimum refresh time and latency.The theorem states convergence to an optimal team trajectory.
- Feedback synchronization: Within a robot group, the feedback rule eventually makes the robots behave as a single robot sweeping the corresponding aggregated segment.Token alternation determines which robot moves after communication, while endpoint timing maintains the required schedule.
- Properties: The convergence is independent of the initial robot configuration and the procedure is robust to a stated class of robot failures.These properties are reported for the distributed algorithm rather than the earlier open-loop trajectories.
VI. A CASE STUDY
Simulations evaluate the distributed synchronization procedure on a two-floor roadmap, including initialization, temporary failure recovery, permanent-failure reconfiguration, and actuation noise. The robots synchronize to optimal refresh-time and latency trajectories after transients, while performance degrades gracefully with noise.
- Simulation setup: The study models holonomic zero-dimensional robots whose communication edges and motion paths follow a prescribed roadmap.The simulations use Matlab and represent the building’s communication and movement structure through the roadmap.
- Initialization: An optimal 10-partition assigns the 10 robots to clusters for minimum refresh time, while random initial positions and velocities test synchronization.Algorithm 5 determines the subsequent motion of each robot.
- Synchronization: After a finite transient, the team synchronizes on a trajectory with minimum refresh time and latency.This behavior is illustrated for the chain roadmap with 30 viewpoints and 10 robots.
- Failure recovery: A temporary stop by robot 7 disrupts synchronization, but the team recovers the desired synchronization when the robot resumes.The remaining robots gather at boundary viewpoints while waiting for communication with robot 7.
- Robustness: 100 noisy simulations show that refresh time and latency degrade gracefully as the speed-noise variance increases.The noise variance is tested over σ2 ∈ {0, 0.02, . . . , 0.5}; permanent failure also triggers detection and computation of a new partition.
VII. APPROXIMATION ALGORITHMS AND HEURISTICS FOR GENERAL ROADMAPS
The paper extends patrolling analysis beyond chains to tree and cyclic roadmaps, characterizing the complexity of optimal trajectory design and introducing approximation methods with guarantees.
- Scope: For general roadmaps, the paper studies tree and cyclic environments after analyzing minimum refresh-time and latency trajectories on chains.The results address computational complexity and approximation methods for teams with more than one robot.
A. Minimum refresh time team trajectory on a tree roadmap
For tree roadmaps, the paper characterizes efficient trajectories through subtree collections and reduces minimum refresh-time design to an optimization over those collections. A minimum-refresh trajectory is computable in O((m −1)!n) time for n vertices and m robots.
- Motivation: Cyclic-based and partition-based trajectory families do not always contain a minimum-refresh trajectory on a tree.The two strategy families fail on different example roadmaps.
- Characterization: For a team trajectory X, efficiency is characterized by RT(X) = max_j DFT(Tj)/mj over its associated subtree collection.The expression follows from the minimum total travel required to visit each subtree’s vertices.
- Efficient trajectories: An efficient trajectory assigns mi robots to each subtree Ti, equally spaces them on a depth-first tour, and moves them at maximum speed.Every vertex is then visited at most every DFT(Ti)/mi.
- Optimization problem: The tree Team refresh time problem is equivalent to finding a subtree collection minimizing max_j DFT(Tj)/mj subject to the robot allocation constraints.Robot counts form a partition of m, and the number of subtrees matches the number of allocation entries.
- Complexity: O((m −1)!n) time suffices to compute a minimum-refresh team trajectory on a tree roadmap.The procedure first computes an optimal subtree collection and then schedules robots using the efficient-trajectory construction.
B. Minimum refresh time team trajectory on a cyclic roadmap
For cyclic roadmaps, the paper develops two approximation approaches by transforming the roadmap into an acyclic one. One has edge-length-dependent performance, while a path-cover method yields an 8-approximation in polynomial time.
- Approximation framework: The cyclic-roadmap methods transform the environment into an acyclic roadmap before constructing refresh-time trajectories.The first method builds a chain from an open tour and applies a chain algorithm.
- First method: The first approximation constructs a chain from an open tour with at most 2n −4 edges, but its performance can degrade as the edge-length ratio γ grows.The chain has at most 2n −3 vertices and 2n −4 edges.
- Computational basis: The path-cover subproblem is NP-hard but admits a 4-approximation polynomial algorithm, enabling the cyclic-roadmap guarantee.The path-cover cost is the maximum path cost in the cover.
- Path-cover method: An 8-approximation polynomial algorithm solves the NP-hard Team refresh time problem on cyclic roadmaps.It combines a 4-approximation min-max path cover with one robot sweeping each path at maximum speed.
- Guarantee: The path-cover construction assigns a different path to each robot and guarantees refresh time within a factor of 8 of optimum for any roadmap and robot count.A campus example illustrates the construction, with shortcutting mentioned as a possible heuristic improvement.
VIII. CONCLUSION AND FUTURE WORK
The work analyzes cooperative patrolling by environment shape, providing polynomial algorithms for chain and bounded-robot tree environments while identifying cyclic environments as computationally harder. Future work targets cyclic latency, more efficient approximations, broader communication and dynamic settings, and hardware validation.
- The study analyzes patrolling design and computational complexity according to whether the environment is a chain, tree, or cyclic graph.
- For chain environments, a polynomial algorithm computes minimum refresh time and latency team trajectories.
- For tree environments, the analysis provides results under the technical assumption of a constant number of robots.
- Further work includes studying latency optimization for cyclic roadmaps and developing more efficient approximation algorithms.
- Future extensions include communication while robots travel roadmap edges, dynamically changing environments, and hardware implementation of the algorithms.