Local Guidance for Configuration-Based Multi-Agent Pathfinding

• URL: http://arxiv.org/abs/2510.19072v2
• Date: Thu, 23 Oct 2025 09:44:56 GMT
• Title: Local Guidance for Configuration-Based Multi-Agent Pathfinding
• Authors: Tomoki Arita, Keisuke Okumura,
• Abstract summary: Guidance is an emerging concept that improves the empirical performance of real-time sub-finding multi-agent pathfinding (MAPF) methods.<n>This study explores an alternative approach: providing local guidance in the vicinity of each agent.<n>We demonstrate that supplying informative cues to the planner can significantly improve solution quality without exceeding a moderate time budget.
• Score: 11.193867567895353
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Guidance is an emerging concept that improves the empirical performance of real-time, sub-optimal multi-agent pathfinding (MAPF) methods. It offers additional information to MAPF algorithms to mitigate congestion on a global scale by considering the collective behavior of all agents across the entire workspace. This global perspective helps reduce agents' waiting times, thereby improving overall coordination efficiency. In contrast, this study explores an alternative approach: providing local guidance in the vicinity of each agent. While such localized methods involve recomputation as agents move and may appear computationally demanding, we empirically demonstrate that supplying informative spatiotemporal cues to the planner can significantly improve solution quality without exceeding a moderate time budget. When applied to LaCAM, a leading configuration-based solver, this form of guidance establishes a new performance frontier for MAPF.

Related papers

• PC2P: Multi-Agent Path Finding via Personalized-Enhanced Communication and Crowd Perception [12.114711272142031]
  PC2P is a novel distributed MAPF method derived from a Q-learning-based MARL framework.<n>We introduce a personalized-enhanced communication mechanism based on dynamic graph topology.<n>To resolve extreme deadlock issues, we propose a region-based deadlock-breaking strategy.
  arXiv  Detail & Related papers  (2026-01-06T03:11:26Z)
• Sequence Pathfinder for Multi-Agent Pickup and Delivery in the Warehouse [10.576983033957953]
  Multi-Agent Pickup and Delivery (MAPD) is a challenging extension of Multi-Agent Path Finding (MAPF)<n> Communication learning can alleviate the lack of global information but introduce high computational complexity due to point-to-point communication.<n>We propose the Sequential Pathfinder (SePar) to achieve implicit information exchange, reducing decision-making complexity from exponential to linear.
  arXiv  Detail & Related papers  (2025-09-28T09:48:13Z)
• Scalable spectral representations for multi-agent reinforcement learning in network MDPs [13.782868855372774]
  A popular model for multi-agent control, Network Markov Decision Processes (MDPs) pose a significant challenge to efficient learning. We first derive scalable spectral local representations for network MDPs, which induces a network linear subspace for the local $Q$-function of each agent. We design a scalable algorithmic framework for continuous state-action network MDPs, and provide end-to-end guarantees for the convergence of our algorithm.
  arXiv  Detail & Related papers  (2024-10-22T17:45:45Z)
• Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approach [51.76826149868971]
  Policy evaluation via Monte Carlo simulation is at the core of many MC Reinforcement Learning (RL) algorithms. We propose as a quality index a surrogate of the mean squared error of a return estimator that uses trajectories of different lengths. We present an adaptive algorithm called Robust and Iterative Data collection strategy Optimization (RIDO)
  arXiv  Detail & Related papers  (2024-10-17T11:47:56Z)
• 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)
• Optimistic Multi-Agent Policy Gradient [37.08607405659866]
  Relative overgeneralization (RO) occurs when agents converge towards a suboptimal joint policy.<n>No methods have been proposed for addressing RO in multi-agent policy gradient (MAPG) methods.<n>We propose a general, yet simple, framework to enable optimistic updates in MAPG methods that alleviate the RO problem.
  arXiv  Detail & Related papers  (2023-11-03T14:47:54Z)
• Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning [46.354187895184154]
  Multi-agent Pathfinding (MAPF) problem generally asks to find a set of conflict-free paths for a set of agents confined to a graph. In this work, we investigate the decentralized MAPF setting, when the central controller that posses all the information on the agents' locations and goals is absent. We focus on the practically important lifelong variant of MAPF, which involves continuously assigning new goals to the agents upon arrival to the previous ones.
  arXiv  Detail & Related papers  (2023-10-02T13:51:32Z)
• Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learning [139.53668999720605]
  We present a multi-agent PPO algorithm in which the local policy of each agent is updated similarly to vanilla PPO. We prove that with standard regularity conditions on the Markov game and problem-dependent quantities, our algorithm converges to the globally optimal policy at a sublinear rate.
  arXiv  Detail & Related papers  (2023-05-08T16:20:03Z)
• Locality Matters: A Scalable Value Decomposition Approach for Cooperative Multi-Agent Reinforcement Learning [52.7873574425376]
  Cooperative multi-agent reinforcement learning (MARL) faces significant scalability issues due to state and action spaces that are exponentially large in the number of agents. We propose a novel, value-based multi-agent algorithm called LOMAQ, which incorporates local rewards in the Training Decentralized Execution paradigm.
  arXiv  Detail & Related papers  (2021-09-22T10:08:15Z)
• Distributed Resource Scheduling for Large-Scale MEC Systems: A Multi-Agent Ensemble Deep Reinforcement Learning with Imitation Acceleration [44.40722828581203]
  We propose a distributed intelligent resource scheduling (DIRS) framework, which includes centralized training relying on the global information and distributed decision making by each agent deployed in each MEC server. We first introduce a novel multi-agent ensemble-assisted distributed deep reinforcement learning (DRL) architecture, which can simplify the overall neural network structure of each agent. Secondly, we apply action refinement to enhance the exploration ability of the proposed DIRS framework, where the near-optimal state-action pairs are obtained by a novel L'evy flight search.
  arXiv  Detail & Related papers  (2020-05-21T20:04:40Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  Decentralized multi-agent reinforcement learning algorithms are sometimes unpractical in complicated applications. We propose a flexible fully decentralized actor-critic MARL framework, which can handle large-scale general cooperative multi-agent setting. Our framework can achieve scalability and stability for large-scale environment and reduce information transmission.
  arXiv  Detail & Related papers  (2020-04-17T14:56:29Z)

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.