Skip to content
Open access

Maximizing Throughput in Lifelong Multi-Agent Path Finding with Unassigned Agents

Aug 2026 · Proceedings of the International Symposium on Combinatorial Search · Vol 19, pp. 121-128 · 0 citations

TL;DR

This paper provides a new variant of Lacam for MAPFUA and a general framework for LMAPFUA and focuses on the best balance between the total number of agents available and how many of them should be assigned for achieving high throughput.

Abstract

The Multi-agent Path Finding with Unassigned Agents (MAPFUA) is a recently introduced practical variant of MAPF. In MAPFUA there are two types of agents: assigned agents that have targets to go to and unassigned agents}that do not have targets but are allowed to move to clear the way for the assigned agents. In this paper we deal with the lifelong variant LMAPFUA where new tasks arrive over time and the aim is to maximize the throughput. We first provide a new variant of Lacam for MAPFUA and a general framework for LMAPFUA. We then focus on the best balance between the total number of agents available and how many of them should be assigned for achieving high throughput. Our experiments show that usually a higher throughput is achieved if some assigned agents are transferred to be unassigned agents that may be better positioned to perform future tasks.

Read PDF

Similar papers

Preprint Oct 2026

The Cost of Classical Multi-Agent Path Finding

Insight is provided on when classical MAPF is a reasonable simplification, and when MAPF$_R$ unlocks significantly higher-quality solutions.

Alvin Combrink, S. Roselli, Martin Fabian · 0 citations
Sep 2026

Solving Multi-Agent Sokoban via LaCAM

Sokoban, a puzzle game in which an agent pushes boxes onto unlabelled target locations in a grid world, is a long-standing benchmark planning problem. While it is easy to see the connection to practical applications such as warehouse logistics with autonomous forklifts, its multi-agent counterpart has remained underdev...

Keisuke Okumura · 0 citations
#artificial intelligence Open access Jul 2025

LSRP*: Scalable and Anytime Planning for Multi-Agent Path Finding with Asynchronous Actions (Extended Abstract)

Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed, most of them rely on a common assumption on synchronized actions, where the actions of all...

Da-Chuan Liu, Shuai Zhou, Shi-Zhe Zhao et al. · 3 citations
#artificial intelligence Preprint Oct 2026

Goal-Aware Dynamic Multi-Agent Collaboration for Long-Horizon Tasks

A preliminary study shows that verification has the strongest association with task success, but often occurs late, leaving limited opportunities for correction, and that the proportion of duty-relevant information decreases as records from different duties accumulate in a shared context.

Xue-Xin Shen, Lingyong Yan, Shuai-Qiang Wang et al. · 0 citations
Preprint Oct 2026

IF-MAP: Influence-Function-Inspired Agent Prioritization in Multi-Agent Systems

IF-MAP is introduced, an influence-function-inspired method for identifying agents with high potential for system-level improvement and direct improvement effort toward greater end-to-end performance gains.

Jie Mao, Ping-Chen Lu, Zi-Kun Qu et al. · 0 citations
Open access 2026

LYCO: Learning to Yield for Decentralized Multi-Agent Path Finding in Congested Environments

In grid-world settings, LYCO consistently outperformed representative decentralized RL baselines in high-density environments, achieving a success rate above 0.7 at an agent density of 0.3 on a $20\times 20$ map with obstacle density 0.1 while maintaining a competitive makespan.

Hiroya Makino, Koji Noshiro, K. Hasebe et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.