On fence patrolling by mobile agents

zbMATH Open1307.90149arXiv1401.6070MaRDI QIDQ405281FDOQ405281

Authors: Adrian Dumitrescu, Anirban Ghosh, Csaba D. Tóth 

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Suppose that a fence needs to be protected (perpetually) by $k$ mobile agents with maximum speeds $v_1,ldots,v_k$ so that no point on the fence is left unattended for more than a given amount of time. The problem is to determine if this requirement can be met, and if so, to design a suitable patrolling schedule for the agents. Alternatively, one would like to find a schedule that minimizes the emph{idle time}, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by Czyzowicz et al.(2011), and discuss several strategies for the cases where the fence is an open and a closed curve, respectively. In particular: (i) we disprove a conjecture by Czyzowicz et al. regarding the optimality of their Algorithm $mathcal{A}_2$ for unidirectional patrolling of a closed fence; (ii) we present an algorithm with a lower idle time for patrolling an open fence, improving an earlier result of Kawamura and Kobayashi.

Full work available at URL: https://arxiv.org/abs/1401.6070

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Fence patrolling by mobile agents with distinct speeds
• Fence patrolling by mobile agents with distinct speeds
• Simple Strategies Versus Optimal Schedules in Multi-agent Patrolling
• Simple strategies versus optimal schedules in multi-agent patrolling
• Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds

zbMATH Keywords

approximation algorithmidle timemulti-agent patrolling

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Agent technology and artificial intelligence (68T42)

Cited In (11)

• Title not available (Why is that?)
• Computing the \(k\)-resilience of a synchronized multi-robot system
• Rowmotion on fences
• Distributed Patrolling with Two-Speed Robots (and an Application to Transportation)
• Fence patrolling by mobile agents with distinct speeds
• When patrolmen become corrupted: monitoring a graph using faulty mobile robots
• Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
• Patrolling a perimeter
• Simple Strategies Versus Optimal Schedules in Multi-agent Patrolling
• Problems on track runners
• Simple strategies versus optimal schedules in multi-agent patrolling

This page was built for publication: On fence patrolling by mobile agents

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405281)