Scalable Multi-Agent Maze Traversal with Local Communication
TL;DR
This work proposes a distributed algorithm that enables agents to collectively traverse an unknown, possibly cyclic graph and proves that the algorithm is complete, that its makespan is asymptotically equivalent to that of an optimal full-knowledge strategy, and derive its time and space complexity.
Abstract
Cave networks, pipe systems, and similar maze-like environments pose significant challenges for multi-agent navigation in unknown settings with limited communication. We propose a distributed algorithm that enables agents to collectively traverse an unknown, possibly cyclic graph. Agents enter sequentially at a designated start node and are tasked to localize and reach an undisclosed goal while avoiding collisions. They coordinate via local communication using leader-follower relationships and leader switching. At any moment in time, exploration is performed by only one of the agents, which runs a single-agent maze solver. We prove that the algorithm is complete, that its makespan is asymptotically equivalent (in the number of agents) to that of an optimal full-knowledge strategy, and derive its time and space complexity. Simulations with up to $625$ agents show a decreasing average sum-of-fuels as the number of agents increases and demonstrate that the proposed approach outperforms a na\"ive baseline in which all agents independently execute the single-agent solver.