Metraipolis › archive › dc_fdcca20eb569
Scalable Multi-Agent Maze Traversal with Local Communication — arXiv:2608.11895
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.11895
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T05:14:48.007Z
- SHA-256 of the archived text
41e616d264ae59b2fe166f7be8fb37f7df935c1c7ab6f5d63be1b37540fed88c- Stable URL of this page
https://metraipolis.com/documento/dc_fdcca20eb569
How to cite
Scalable Multi-Agent Maze Traversal with Local Communication — arXiv:2608.11895 — arXiv (en), https://arxiv.org/abs/2608.11895 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fdcca20eb569 (Metraipolis archive dc_fdcca20eb569, sha256 41e616d264ae59b2fe166f7be8fb37f7df935c1c7ab6f5d63be1b37540fed88c)
BibTeX
@misc{dcfdcca20eb569,
title = {Scalable Multi-Agent Maze Traversal with Local Communication — arXiv:2608.11895},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.11895},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fdcca20eb569; sha256 41e616d264ae59b2fe166f7be8fb37f7df935c1c7ab6f5d63be1b37540fed88c},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.11895. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-13 in cs.MA). Categorie arXiv: Robotics (cs.RO) ; Multiagent Systems (cs.MA). Pagina del lavoro: https://arxiv.org/abs/2608.11895 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-19T05:08:22.842Z dalla pagina https://arxiv.org/catchup/cs.MA/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).