On cooperative patrolling: optimal trajectories, complexity analysis, and approximation algorithms

Abstract

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.

Preprint submitted to IEEE Transaction on Robotics

Cited by in corpus (19)

• Persistent Multi-UAV Surveillance with Data Latency Constraints
• Decentralized Simultaneous Multi-target Exploration using a Connected Network of Multiple Robots
• Multi-robot persistent surveillance with connectivity constraints
• Connectivity Maintenance: Global and Optimized approach through Control Barrier Functions
• Multi-Robot Patrolling with Sensing Idleness and Data Delay Objectives
• Perimeter-defense Game on Arbitrary Convex Shapes
• Simple strategies versus optimal schedules in multi-agent patrolling
• Resilience of a synchronized multi-agent system
• The Meeting Time of Multiple Random Walks
• Lightweight Decentralized Neural Network-Based Strategies for Multi-Robot Patrolling
• The Deformed Consensus Protocol: Extended Version
• Point Sweep Coverage on Path
• Markov Chain-Based Stochastic Strategies for Robotic Surveillance
• Stochastic Strategies for Robotic Surveillance as Stackelberg Games
• Energy-Aware Stochastic UAV-Assisted Surveillance
• Persistent Monitoring in Discrete Environments: Minimizing the Maximum Weighted Latency Between Observations
• A framework for synchronizing a team of aerial robots in communication-limited environments
• Changeable Sweep Coverage Problem
• Stochastic Surveillance Strategies for Spatial Quickest Detection