A framework for distributed discrete evacuation strategies
This work provides a foundational framework for distributed evacuation on arbitrary graphs, with provably optimal performance on grid-like networks, benefiting multi-agent coordination in emergency scenarios.
The paper introduces a general algorithmic framework for distributed discrete evacuation in networks where agents lack global knowledge, achieving asymptotically optimal (constant competitive ratio) strategies for grid networks.
In this paper, we study discrete evacuation in networks, where agents know the network topology and designated exit nodes but do not know the number and initial positions of other agents. Each agent initially occupies a distinct node and must reach any exit node. Operating in a synchronous distributed model with local communication, the agents aim to minimize the time when the last agent reaches an exit. We introduce a general algorithmic framework for constructing evacuation strategies on arbitrary graphs. As a key application, we demonstrate that the framework yields asymptotically optimal evacuation strategies -- achieving a constant competitive ratio -- for grid networks, with natural extensions to triangular and hexagonal grids.