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).