Aug 12, 2026 · cs.ROJ/K move · Enter open · S save
Julian Rau, Jahir Argote-Gerald, Grace McFassel, Genki Miyauchi+2
Department of Computer Science, Technical University of Darmstadt, Germany · School of Electrical and Electronic Engineering, The University of Sheffield, UK · Bristol Robotics Laboratory, University of Bristol, Bristol, UK
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ïve baseline in which all agents independently execute the single-agent solver.