Scalable Multi-Agent Maze Traversal with Local Communication

• URL: http://arxiv.org/abs/2608.11895v1
• Date: Wed, 12 Aug 2026 10:21:26 GMT
• Title: Scalable Multi-Agent Maze Traversal with Local Communication
• Abstract summary: We propose a distributed algorithm that enables agents to collectively traverse an unknown, possibly cyclic graph.<n>Agents enter sequentially at a designated start node and are tasked to localize and reach an undisclosed goal.<n>At any moment in time, exploration is performed by only one of the agents.
• Score: 1.2875771631391097
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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ïve baseline in which all agents independently execute the single-agent solver.

Related papers

• AgentFugue: Agent Scaling for Long-Horizon Tasks through Collective Reasoning [57.72181998599248]
  AgentFugue is a collective reasoning framework built around a shared reasoning hub.<n>As peer agents explore the same task in parallel, the hub records concise notes on what each agent has established, attempted, or ruled out.<n>Our results suggest that collective reasoning can turn scaling out peer agent systems into a distinct source of capability gains.
  arXiv  Detail & Related papers  (2026-05-23T09:21:51Z)
• GoAgent: Group-of-Agents Communication Topology Generation for LLM-based Multi-Agent Systems [55.12339141172908]
  GoAgent is a communication topology generation method that explicitly treats collaborative groups as the atomic units of MAS construction.<n>Experiments on six benchmarks demonstrate the state-of-the-art performance of GoAgent with 93.84% average accuracy while reducing token consumption by about 17%.
  arXiv  Detail & Related papers  (2026-03-20T06:21:32Z)
• Solving Multi-Agent Multi-Goal Path Finding Problems in Polynomial Time [1.7006003864727406]
  We plan missions for a fleet of agents in undirected graphs, such as grids, with multiple goals.<n>In contrast to regular multi-agent path-finding, the solver finds and updates the assignment of goals to the agents on its own.
  arXiv  Detail & Related papers  (2025-12-17T15:24:20Z)
• Decentralized Multi-Agent Active Search and Tracking when Targets Outnumber Agents [8.692007892160913]
  We propose a decentralized multi-agent, multi-target, simultaneous active search-and-tracking algorithm called DecSTER. Our proposed algorithm uses a sequential monte carlo implementation of the probability hypothesis density filter for posterior inference combined with Thompson sampling for decentralized multi-agent decision making. In simulation, we demonstrate that DecSTER is robust to unreliable inter-agent communication and outperforms information-greedy baselines in terms of the Optimal Sub-Pattern Assignment (OSPA) metric.
  arXiv  Detail & Related papers  (2024-01-06T08:10:58Z)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  Multi-Agent Pathfinding problem involves finding a set of conflict-free paths for a group of agents confined to a graph. In this study, we focus on the decentralized MAPF setting, where the agents may observe the other agents only locally. We propose a decentralized multi-agent Monte Carlo Tree Search (MCTS) method for MAPF tasks.
  arXiv  Detail & Related papers  (2023-12-26T06:57:22Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs [49.71319907864573]
  In this paper, we propose multi-agent skill discovery which enables the ease of decomposition. Our key idea is to approximate the joint state space as a Kronecker graph, based on which we can directly estimate its Fiedler vector. Considering that directly computing the Laplacian spectrum is intractable for tasks with infinite-scale state spaces, we further propose a deep learning extension of our method.
  arXiv  Detail & Related papers  (2023-07-21T14:53:12Z)
• Multi-agent Deep Covering Skill Discovery [50.812414209206054]
  We propose Multi-agent Deep Covering Option Discovery, which constructs the multi-agent options through minimizing the expected cover time of the multiple agents' joint state space. Also, we propose a novel framework to adopt the multi-agent options in the MARL process. We show that the proposed algorithm can effectively capture the agent interactions with the attention mechanism, successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options.
  arXiv  Detail & Related papers  (2022-10-07T00:40:59Z)
• Learning Multi-agent Skills for Tabular Reinforcement Learning using Factor Graphs [41.17714498464354]
  We show that it is possible to directly compute multi-agent options with collaborative exploratory behaviors among the agents. The proposed algorithm can successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options.
  arXiv  Detail & Related papers  (2022-01-20T15:33:08Z)
• MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding [10.354181009277623]
  In multi-agent applications such as surveillance and logistics, fleets of mobile agents are often expected to coordinate and safely visit a large number of goal locations. In this article, we introduce a new algorithm called MS* which computes an optimal solution for this multi-agent problem. Numerical results show that our new algorithm can solve the multi-agent problem with 20 agents and 50 goals in a minute of CPU time on a standard laptop.
  arXiv  Detail & Related papers  (2021-03-18T01:57:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.