A distributed ant algorithm for efficiently patrolling a network

DOI10.1007/s00453-003-1030-9zbMath1102.68728OpenAlexW2014474286MaRDI QIDQ1879364

Israel A. Wagner, Vladimir Yanovski, Alfred Marcel Bruckstein

Publication date: 22 September 2004

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-003-1030-9

zbMATH Keywords

blanket timeextended Eulerian cycle

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Learning and adaptive systems in artificial intelligence (68T05) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (27)

Bounds on the cover time of parallel rotor walks ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Coalescing Walks on Rotor-Router Systems ⋮ Time and space optimality of rotor-router graph exploration ⋮ The robot crawler graph process ⋮ The Range of a Rotor Walk ⋮ The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks ⋮ Robustness of the rotor-router mechanism ⋮ Total variation discrepancy of deterministic random walks for ergodic Markov chains ⋮ When patrolmen become corrupted: monitoring a graph using faulty mobile robots ⋮ Deterministic Random Walks for Rapidly Mixing Chains ⋮ Exploration of Time-Varying Connected Graphs with Silent Agents ⋮ Simple strategies versus optimal schedules in multi-agent patrolling ⋮ Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles ⋮ Distributed Patrolling with Two-Speed Robots (and an Application to Transportation) ⋮ Derandomizing random walks in undirected graphs using locally fair exploration strategies ⋮ Exploration of dynamic networks: tight bounds on the number of agents ⋮ Unbounded Discrepancy of Deterministic Random Walks on Grids ⋮ Multi-robot area patrol under frequency constraints ⋮ Patrolling security games: definition and algorithms for solving large instances with single patroller and single intruder ⋮ Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time ⋮ Fast two-robot disk evacuation with wireless communication ⋮ Lower Bounds for Graph Exploration Using Local Policies ⋮ The cover time of deterministic random walks for general transition probabilities ⋮ Does adding more agents make a difference? A case study of cover time for the rotor-router ⋮ Monitoring the plane with rotating radars ⋮ Fence patrolling by mobile agents with distinct speeds

Cites Work

• Unnamed Item
• Efficiently searching a graph by a smell-oriented vertex process
• Real-time heuristic search
• How to reuse a “write-once≓ memory
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: A distributed ant algorithm for efficiently patrolling a network