Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning

• URL: http://arxiv.org/abs/2506.23793v1
• Date: Mon, 30 Jun 2025 12:34:31 GMT
• Title: Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning
• Authors: Anton Andreychuk, Konstantin Yakovlev, Aleksandr Panov, Alexey Skrynnik,
• Abstract summary: Multi-agent pathfinding (MAPF) is a common abstraction of multi-robot trajectory planning problems.<n>We introduce MAPF-GPT-DDG, a decentralized suboptimal MAPF solvers that leverage machine learning.<n>Our experiments demonstrate that MAPF-GPT-DDG surpasses all existing learning-based MAPF solvers.
• Score: 46.35418789518417
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-agent pathfinding (MAPF) is a common abstraction of multi-robot trajectory planning problems, where multiple homogeneous robots simultaneously move in the shared environment. While solving MAPF optimally has been proven to be NP-hard, scalable, and efficient, solvers are vital for real-world applications like logistics, search-and-rescue, etc. To this end, decentralized suboptimal MAPF solvers that leverage machine learning have come on stage. Building on the success of the recently introduced MAPF-GPT, a pure imitation learning solver, we introduce MAPF-GPT-DDG. This novel approach effectively fine-tunes the pre-trained MAPF model using centralized expert data. Leveraging a novel delta-data generation mechanism, MAPF-GPT-DDG accelerates training while significantly improving performance at test time. Our experiments demonstrate that MAPF-GPT-DDG surpasses all existing learning-based MAPF solvers, including the original MAPF-GPT, regarding solution quality across many testing scenarios. Remarkably, it can work with MAPF instances involving up to 1 million agents in a single environment, setting a new milestone for scalability in MAPF domains.

Related papers

• Enhancing Lifelong Multi-Agent Path-finding by Using Artificial Potential Fields [15.082298617948581]
  We propose methods for incorporating APFs in a range of MAPF algorithms.<n>Using APF is not beneficial for MAPF but yields up to a 7-fold increase in overall system throughput for LMAPF.
  arXiv  Detail & Related papers  (2025-05-28T18:13:10Z)
• Advancing MAPF towards the Real World: A Scalable Multi-Agent Realistic Testbed (SMART) [37.17845947950689]
  Scalable Multi-Agent Realistic Testbed (smart) is a realistic and efficient software tool for evaluating Multi-Agent Path Finding (MAPF) algorithms.<n>We use SMART to explore and demonstrate research questions about the execution of MAPF algorithms in real-world scenarios.
  arXiv  Detail & Related papers  (2025-03-03T05:26:59Z)
• Transient Multi-Agent Path Finding for Lifelong Navigation in Dense Environments [9.000023855628958]
  The Lifelong MAPF (LMAPF) problem is a well-studied online version of MAPF in which an agent receives a new target when it reaches its current target.<n>We propose to solve LMAPF problems by solving a sequence of modified MAPF problems, in which the objective is for each agent to eventually visit its target.<n>We refer to this MAPF variant as Transient MAPF (TMAPF) and propose several algorithms for solving it based on existing MAPF algorithms.
  arXiv  Detail & Related papers  (2024-12-05T15:37:29Z)
• MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale [46.35418789518417]
  Multi-agent pathfinding (MAPF) is a problem that generally requires finding collision-free paths for multiple agents in a shared environment.<n>Recently, learning-based approaches to MAPF have gained attention, particularly those leveraging deep reinforcement learning.<n>We show that MAPF-GPT notably outperforms the current best-performing learnable MAPF solvers on a diverse range of problem instances.
  arXiv  Detail & Related papers  (2024-08-29T12:55:10Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
  arXiv  Detail & Related papers  (2024-01-30T14:26:04Z)
• 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)
• Multi-Agent Automated Machine Learning [54.14038920246645]
  We propose multi-agent automated machine learning (MA2ML) to handle joint optimization of modules in automated machine learning (AutoML) MA2ML explicitly assigns credit to each agent according to its marginal contribution to enhance cooperation among modules, and incorporates off-policy learning to improve search efficiency. Experiments show that MA2ML yields the state-of-the-art top-1 accuracy on ImageNet under constraints of computational cost.
  arXiv  Detail & Related papers  (2022-10-17T13:32:59Z)
• Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learning [56.17603785248675]
  Model-agnostic meta-learning (MAML) has become a popular research area. Existing MAML algorithms rely on the episode' idea by sampling a few tasks and data points to update the meta-model at each iteration. This paper proposes memory-based algorithms for MAML that converge with vanishing error.
  arXiv  Detail & Related papers  (2021-06-09T08:47:58Z)
• Compilation-based Solvers for Multi-Agent Path Finding: a Survey, Discussion, and Future Opportunities [7.766921168069532]
  We show the lessons learned from past developments and current trends in the topic and discuss its wider impact. Two major approaches to optimal MAPF solving include (1) dedicated search-based methods, which solve MAPF directly, and (2) compilation-based methods that reduce a MAPF instance to an instance in a different well established formalism.
  arXiv  Detail & Related papers  (2021-04-23T20:13:12Z)

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.