Patrolling on dynamic ring networks

DOI10.1007/978-3-030-10801-4_13MaRDI QIDQ2206223zbMATH OpenOpenAlexFDO

Authors Shantanu Das, Leszek Gąsieniec, Giuseppe Antonio Di Luna

Publication date 22 October 2020

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

Mathematics Subject Classification ID

Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Artificial intelligence for robotics (68T40) Nonnumerical algorithms (68W05)

Abstract: We study the problem of patrolling the nodes of a network collaboratively by a team of mobile agents, such that each node of the network is visited by at least one agent once in every $I(n)$ time units, with the objective of minimizing the idle time $I(n)$. While patrolling has been studied previously for static networks, we investigate the problem on dynamic networks with a fixed set of nodes, but dynamic edges. In particular, we consider 1-interval-connected ring networks and provide various patrolling algorithms for such networks, for $k=2$ or $k>2$ agents. We also show almost matching lower bounds that hold even for the best starting configurations. Thus, our algorithms achieve close to optimal idle time. Further, we show a clear separation in terms of idle time, for agents that have prior knowledge of the dynamic networks compared to agents that do not have such knowledge. This paper provides the first known results for collaborative patrolling on dynamic graphs.

Recommendations

• A distributed ant algorithm for efficiently patrolling a network
• Simple Strategies Versus Optimal Schedules in Multi-agent Patrolling
• When patrolmen become corrupted: monitoring a graph using faulty mobile robots
• When patrolmen become corrupted: monitoring a graph using faulty mobile robots
• Simple strategies versus optimal schedules in multi-agent patrolling

Cited in

(13)

• When patrolmen become corrupted: monitoring a graph using faulty mobile robots
• A distributed ant algorithm for efficiently patrolling a network
• Exploration of dynamic cactuses with sub-logarithmic overhead
• Almost uniform deployment of mobile agents in dynamic rings
• Exploring a dynamic ring without landmark
• When patrolmen become corrupted: monitoring a graph using faulty mobile robots
• Near-optimal continuous patrolling with teams of mobile information gathering agents
• Two Robots Patrolling on a Line: Integer Version and Approximability
• Exploring a Dynamic Ring Without Landmark
• Broadcasting with mobile agents in dynamic networks
• Partial gathering of mobile agents in dynamic rings
• On the broadcast problem for mobile agents in dynamic networks
• Pattern formation of mobile agents in dynamic grids

This page was built for publication: Patrolling on dynamic ring networks

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