Simple Strategies Versus Optimal Schedules in Multi-agent Patrolling
From MaRDI portal
Abstract: Suppose that a set of mobile agents, each with a predefined maximum speed, want to patrol a fence together so as to minimize the longest time interval during which a point on the fence is left unvisited. In 2011, Czyzowicz, Gk{a}sieniec, Kosowski and Kranakis studied this problem for the settings where the fence is an interval (a line segment) and a circle, and conjectured that the following simple strategies are always optimal: for Interval Patrolling, the simple strategy partitions the fence into subintervals, one for each agent, and lets each agent move back and forth in the assigned subinterval with its maximum speed; for Circle Patrolling, the simple strategy is to choose a number r, place the r fastest agents equidistantly around the circle, and move them at the speed of the rth agent. Surprisingly, these conjectures were then proved false: schedules were found (for some settings of maximum speeds) that slightly outperform the simple strategies. In this paper, we are interested in the ratio between the performances of optimal schedules and simple strategies. For the two problems, we construct schedules that are 4/3 times (for Interval Patrolling) and 21/20 times (for Circle Patrolling) as good, respectively, as the simple strategies. We also propose a new variant, in which we want to patrol a single point under the constraint that each agent can only visit the point some predefined time after its previous visit. We obtain some similar ratio bounds and NP-hardness results related to this problem.
Recommendations
- Simple strategies versus optimal schedules in multi-agent patrolling
- scientific article; zbMATH DE number 1950764
- Dynamical and Game-Theoretical Approaches to an Optimal Patrol Problem
- Stochastic strategies for patrolling a terrain with a synchronized multi-robot system
- Near-optimal continuous patrolling with teams of mobile information gathering agents
Cites work
- Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- On disjoint residue classes
- On exactly covering systems of arithmetic sequences
- On fence patrolling by mobile agents
- Simple strategies versus optimal schedules in multi-agent patrolling
Cited in
(20)- When patrolmen become corrupted: monitoring a graph using faulty mobile robots
- A distributed ant algorithm for efficiently patrolling a network
- Optimal patrolling of high priority segments while visiting the unit interval with a set of mobile robots
- Simple strategies versus optimal schedules in multi-agent patrolling
- Patrolling on dynamic ring networks
- Utility distribution strategy of the task agents in coalition skill games
- Problems on track runners
- Distributed patrolling with two-speed robots (and an application to transportation)
- Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
- Approximation algorithms for multi-robot patrol-scheduling with min-max latency
- When patrolmen become corrupted: monitoring a graph using faulty mobile robots
- Near-optimal continuous patrolling with teams of mobile information gathering agents
- On fence patrolling by mobile agents
- scientific article; zbMATH DE number 1950764 (Why is no real title available?)
- Optimal strategies for patrolling fences
- Patrolling a path connecting a set of points with unbalanced frequencies of visits
- Patrolling by robots equipped with visibility
- Distance-based solution of patrolling problems with individual waiting times
- Generalised formulations for minimum distance trajectory in patrolling problems
- Computing the \(k\)-resilience of a synchronized multi-robot system
This page was built for publication: Simple Strategies Versus Optimal Schedules in Multi-agent Patrolling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947025)
