Unassigned Agents in Compilation-based Multi-agent Path Finding

• URL: http://arxiv.org/abs/2606.15797v1
• Date: Sun, 14 Jun 2026 13:04:03 GMT
• Title: Unassigned Agents in Compilation-based Multi-agent Path Finding
• Abstract summary: We show in this paper that UA-MAPF can be expressed in recent compilation-based techniques for MAPF.<n>We adapt SMT-CBS and NRF-SAT, the recent solvers based on counterexample guided abstraction refinement and non-refined abstractions.
• Score: 7.766921168069531
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Compilation-based techniques represent an important stream of solvers for multi-agent path finding (MAPF) due to their modularity and adaptability for non-standard variants of the problem. While in the standard MAPF the task is to navigate all agents from their initial positions to given individual goal positions without any collision, variants where a different requirement for agents is used are also relevant. Such a variant is MAPF with unassigned agents (UA-MAPF) where some agents have the same setting as in the standard MAPF with initial positions and goals while the remaining agents have the initial position but have no goal - unassigned agents. Despite unassigned agent do not need to reach any goal position they have to be moved out of the way of the standard agents if needed which represent a specific challenge. We show in this paper that UA-MAPF can be expressed in recent compilation-based techniques for MAPF based on formulating the problem as Boolean satisfiability, namely we adapt SMT-CBS and NRF-SAT, the recent solvers based on counterexample guided abstraction refinement and non-refined abstractions.

Related papers

• Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding [48.1609560841622]
  We present a learnable communication module tailored to enhance cooperation between agents via efficient feature sharing.<n>Our experiments show that the introduced method outperforms the existing learning-based MAPF solvers.
  arXiv  Detail & Related papers  (2026-05-08T12:05:08Z)
• Behavior Knowledge Merge in Reinforced Agentic Models [48.89546963456286]
  Reinforcement learning is central to post-training, particularly for agentic models that require specialized reasoning behaviors.<n>Existing merging methods are designed for supervised fine-tuning (SFT), and they are suboptimal to preserve task-specific capabilities on RL-trained agentic models.<n>We propose Reinforced Agent Merging (RAM), a distribution-aware merging framework explicitly designed for RL-trained agentic models.
  arXiv  Detail & Related papers  (2026-01-20T03:56:53Z)
• Vulnerable Agent Identification in Large-Scale Multi-Agent Reinforcement Learning [49.31650627835956]
  Partial agent failure becomes inevitable when systems scale up, making it crucial to identify the subset of agents whose compromise would most severely degrade overall performance.<n>In this paper, we study this Vulnerable Agent Identification (VAI) problem in large-scale multi-agent reinforcement learning (MARL)<n> Experiments show our method effectively identifies more vulnerable agents in large-scale MARL and the rule-based system, fooling system into worse failures, and learning a value function that reveals the vulnerability of each agent.
  arXiv  Detail & Related papers  (2025-09-18T16:03:50Z)
• 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)
• 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)
• Counterexample Guided Abstraction Refinement with Non-Refined Abstractions for Multi-Agent Path Finding [15.99072005190786]
  We propose a novel CEGAR-style solver for MAPF based on SAT in which some abstractions are deliberately left non-refined. Non-refining however yields order-of-magnitude smaller SAT encodings than those of the previous approach.
  arXiv  Detail & Related papers  (2023-01-20T17:18:49Z)
• Heuristically Guided Compilation for Multi-Agent Path Finding [15.99072005190786]
  We focus on compilation-based solvers in which the MAPF problem is expressed in a different well established formalism. We show in this work how the build a MAPF encoding for the target SAT solver in which domain specific knowledge is reflected. The conducted experiments show that guided compilation outperforms the vanilla variants of the SAT-based MAPF solver.
  arXiv  Detail & Related papers  (2022-12-13T23:19:15Z)
• META: Mimicking Embedding via oThers' Aggregation for Generalizable Person Re-identification [68.39849081353704]
  Domain generalizable (DG) person re-identification (ReID) aims to test across unseen domains without access to the target domain data at training time. This paper presents a new approach called Mimicking Embedding via oThers' Aggregation (META) for DG ReID.
  arXiv  Detail & Related papers  (2021-12-16T08:06:50Z)
• DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving Technologies [7.766921168069532]
  In multi-agent path finding (MAPF), the task is to find non-conflicting paths for multiple agents. We present a novel compilation scheme called DPLL(MAPF) in which the consistency checking of partial assignments of decision variables is integrated directly into the SAT solver.
  arXiv  Detail & Related papers  (2021-11-11T23:06:00Z)

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.