Solving Multi-Agent Sokoban via LaCAM

Keisuke Okumura

cs.MASep 30, 2026

Solving Multi-Agent Sokoban via LaCAM

Authors: Keisuke Okumura

Organizations: National Institute of Advanced Industrial Science and Technology (AIST), Japan

Abstract

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 underdeveloped. This is because Multi-Agent Sokoban is substantially more difficult due to factors specific to multi-agent planning, such as the rapidly growing branching factor as the number of agents grows and the need to handle integrated task assignment and collision-free pathfinding. In this paper, we show that a scalable planner for Multi-Agent Sokoban can be designed by leveraging recent advances in multi-agent pathfinding (MAPF). Specifically, our Sokoban-LaCAM efficiently solves instances involving tens of agents and boxes while preserving both completeness and eventual optimality guarantees. This provides evidence that MAPF can serve as a powerful primitive for solving broader collective automation problems.

Figures & tables

success (% $\uparrow$ )		time ( $\mathrm{ms}$ $\downarrow$ )		sub-opt of $\text{LaCAM}^{\ast}$
$\text{IDA}^{\ast}$	$\text{LaCAM}^{\ast}$	$\text{IDA}^{\ast}$	$\text{LaCAM}^{\ast}$	init	$30\text{\,}\mathrm{s}$	opt-proven
30.0	93.3	3117 $\pm$ 2663	< $0.1\text{\,}\mathrm{ms}$	1.44	1.00	24/27 ${=}$ 89%

Table 1: Performance of

\text{Sokoban-LaCAM}^{\ast}

against

\text{IDA}^{\ast}

on the 90 instances of empty-5-5 from Fig. 1 under a

30\text{\,}\mathrm{s}

time limit. Among them, both planners solve 27 instances. For these commonly solved instances, we report the time required by

\text{Sokoban-LaCAM}^{\ast}

to obtain its initial solutions, together with the suboptimality factors for initial and final solutions using the optimal

\text{IDA}^{\ast}

solutions as references. Notably,

\text{Sokoban-LaCAM}^{\ast}

finds initial solutions for all 27 instances almost instantly, and all of them eventually converge to the optimum. Furthermore,

\text{Sokoban-LaCAM}^{\ast}

proves optimality for most of these instances (see opt-proven ).

Figure 2 : Ablation study and anytime performance of

\text{Sokoban-LaCAM}^{\ast}

on the random-* maps from Fig. 1 . Except for the success rate under the

10\text{\,}\mathrm{s}

time limit, the left table reports averages over the 274 instances solved by all variants for a fair comparison, together with 95% confidence intervals. init time denotes the time required to find the first feasible solution. init cost impr reports the makespan improvement relative to Sokoban-LaCAM upon finding the initial solution. Similarly,

10\text{\,}\mathrm{s}

cost impr reports the relative makespan improvement at the time limit. We additionally report the number of search nodes generated by LaCAM ( #search nodes ) and the number of generated constraints ( #constraints ). The right plot focuses on the average makespan over planning time on random-8-8-10 , computed from the 72 instances solved by all variants.

Explore similar work

Alternating Target-Path Planning for Scalable Multi-Agent Coordination
May 8, 2026Yu Kumagai, Keisuke OkumuraMulti-Agent Path Finding Multi-Agent Coordination
1Hitotsubashi University, Japan · 2National Institute of Advanced Industrial Science and Technology (AIST), Japan
AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding
Aug 8, 2026Alvin Combrink, Sabino Francesco Roselli, Martin FabianMulti-Agent Path Finding Path Planning
Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden.
Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding
May 8, 2026Valeriy Vyaltsev, Alsu Sagirova, Anton Andreychuk +5Multi-Agent Path Finding Multi-Robot Motion Planning
CogAI Lab, Moscow, Russia

May 8, 2026, cs.AIJ/K move · Enter open · S save

Alternating Target-Path Planning for Scalable Multi-Agent Coordination

Yu Kumagai, Keisuke Okumura

1Hitotsubashi University, Japan · 2National Institute of Advanced Industrial Science and Technology (AIST), Japan

Multi-Agent Path Finding Multi-Agent Coordination Path Planning Repair-Assignment Problem Planning Solvers

Open paper AskPDF arXiv

The concurrent target assignment and pathfinding (TAPF) problem extends multi-agent pathfinding (MAPF) by asking planners to allocate distinct targets and collision-free paths to agents. Prior work on TAPF has relied exclusively on Conflict-Based Search (CBS), which tightly couples target assignment and pathfinding, resulting in compute-intensive, non-scalable solutions. In contrast, we propose an iterative refinement framework that decouples target assignment from pathfinding. Our framework builds on modern, fast, suboptimal MAPF solvers, such as LaCAM. Specifically, within a given time budget, it repeatedly solves MAPF for the current target assignment, identifies bottleneck agents via MAPF feedback, and refines the assignment. Empirical results show that feedback-driven reassignment loop is effective, enabling our framework to scale well beyond the reach of the state-of-the-art CBS-based solver while maintaining decent solution quality. This represents a solid step toward practical, large scale TAPF suitable for real-world setups.

Abstract

Explore similar work

Alternating Target-Path Planning for Scalable Multi-Agent Coordination

AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding

Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding