Source-linked AI summary
Solving Multi-Agent Sokoban via LaCAM
Keisuke Okumura
TL;DR
Multi-Agent Sokoban remains underdeveloped despite its relevance to warehouse logistics, and it combines a growing joint search space with task assignment and collision-free pathfinding. The paper extends MAPF configuration search in Sokoban-LaCAM; it efficiently solves large-scale instances, supporting MAPF search as a foundation for broader multi-agent planning.
Problem
Multi-Agent Sokoban is an underdeveloped planning problem that combines a rapidly growing branching factor with integrated task assignment and collision-free pathfinding.
Source: §1 · p. 1, §2.1 · p. 2Method
Sokoban-LaCAM searches configurations with constrained PIBT joint actions, supplemented by problem-specific heuristics and pruning.
Source: §1 · p. 2Results
Sokoban-LaCAM integrates task assignment, object manipulation, and coordinated path planning, and experiments show it efficiently solves large-scale instances.
Source: §5 · p. 10Takeaways & Limitations
The results suggest configuration-based MAPF search can provide a foundation for more general multi-agent planning beyond canonical MAPF.
Source: §5 · p. 10The paper omits several implementation details and assumes the number of boxes equals the number of targets.
Source: §2.1 · p. 2, §3 · p. 4
Abstract
from arXiv · showhide
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.
1 Introduction
Multi-Agent Sokoban combines box manipulation with integrated task assignment and collision-free path planning, but has received little attention despite its warehouse-logistics connection. The paper presents Sokoban-LaCAM as a scalable MAPF-based planner and uses the problem to test whether MAPF search can extend to broader collective automation tasks.
1 Introduction
- Multi-Agent Sokoban requires integrated box-to-agent and box-to-target assignment alongside collision-free paths that avoid agent–agent, agent–box, and box–box collisions.The paper connects this structure to warehouse logistics, where robots transport goods while coordinating to avoid interference.Source: §1 · p. 1
- The paper asks whether multi-agent pathfinding techniques can provide scalable, real-time planning beyond canonical MAPF.MAPF computes collision-free paths for multiple agents on a graph, and LaCAM(∗) demonstrates reliable sub-second planning for hundreds of agents [8] [9] [10].Source: §1 · p. 1
- Sokoban-LaCAM solves instances with tens of agents and boxes within seconds, with completeness and eventual optimality guarantees.The paper reports substantially better scalability than adapting IDA∗, traditionally used for single-agent Sokoban.Source: §1 · p. 2
- Sokoban-LaCAM searches configurations, generates joint actions via constrained PIBT, and adds problem-specific heuristics and pruning rules.The paper presents this as a test of whether search-based MAPF algorithms, at least LaCAM, can serve as general multi-agent combinatorial search frameworks for collective automation.Source: §1 · p. 2
2 Preliminaries
The preliminaries formalize the multi-agent puzzle and its makespan objective, then position it within MAPF search, task assignment, and object-manipulation planning. They explain why configuration-based search is relevant and how pushing boxes makes this setting distinct from related transport problems.
2.1 Problem Definition
- The model places agents and boxes at distinct traversable cells, requires every target to hold a box in the final configuration, and minimizes solution makespan.The formulation assumes the number of boxes equals the number of targets and defines valid transitions through movement, collision, and pushing rules.Source: §2.1 · p. 2
2.2 MAPF, LaCAM, and PIBT
- LaCAM lazily refines action constraints to generate one successor configuration at a time, postponing exponential branching while preserving exhaustive search and completeness.PIBT can generate a collision-free successor in time linear in the number of agents; configuration-based search is extended here to coupled task planning and box manipulation.Source: §2.2 · p. 3
2.3 Integrated Task and Path Planning
- Integrated assignment-and-pathfinding formulations include unlabelled MAPF, MAPF-UA, and TAPF, with scalable algorithms for several formulations building on LaCAM.Canonical MAPF is a special case of Multi-Agent Sokoban when there are no boxes and agents have assigned goal configurations.Source: §2.3 · pp. 3–4, §2.2 · p. 3
2.4 Planning with Object Manipulation
- Sokoban couples path planning with manipulation because box movements alter the traversable workspace for agents and other objects.Its push-only dynamics make dead ends particularly severe and often irreversible compared with formulations that allow carrying, co-location, or freer repositioning.Source: §2.4 · p. 4
3 Sokoban-LaCAM
Sokoban-LaCAM extends configuration-space search to Multi-Agent Sokoban with a PIBT-based generator and task-assignment preferences. Its design combines target–box and agent–stand assignments with search improvements, while retaining completeness and eventual optimality guarantees.
3 Sokoban-LaCAM
- The configuration-space search is complete, and its eventual-optimal variant handles cumulative-cost objectives such as makespan.The section presents the planner as a MAPF-based framework extended with modest modifications, rather than a complete engineering blueprint.Source: §3.1 · p. 4, §3 · p. 4
3.1 Minimal Adaptation
- Sokoban-PIBT generates agent actions and checks collisions after simulating any pushed box movement.If the resulting action is infeasible under a constraint, LaCAM continues searching over alternative constraints.Source: §3.1 · p. 4
3.2 Preference Construction
- Target–box and agent–stand assignments shape agent preferences toward box pushes, reachable stands, or proximity to potential tasks.Assigned agents prioritize the push action when at their stand; otherwise, action order favors reaching the stand, while unassigned agents are guided toward stands.Source: §3.2 · p. 5
3.3 Target–Box Assignment
- A distance-aware target–box matching is refined by pairwise swaps that reduce the maximum push-aware distance.The assignment is a heuristic rather than an optimal bottleneck assignment because makespan also depends on agent–stand assignment and collision-free pathfinding.Source: §3.3 · pp. 5–6
3.4 Agent–Stand Assignment
- Agent–stand assignment excludes stands blocked by boxes or dead-end pushes, then greedily assigns agents to distinct boxes and refines the result with pairwise swaps.The objective is to reduce the maximum assigned box-aware distance.Source: §3.4 · p. 6
3.5 Search Improvements
- Search improvements include probabilistic restarts, an admissible movement lower bound for branch-and-bound, and restarts after heuristic progress stalls.Stuck detection uses a fixed threshold of 64 iterations in the experiments, although the text says the threshold should gradually increase to preserve completeness in theory.Source: §3.5 · pp. 6–7
- Dead-end pruning rejects infeasible configurations, while unlabelled duplicate detection treats configurations as identical when their agent and box location sets match.The proposed dead-end criteria include 2 × 2 box blocks unless all cells are targets and comparisons of boxes and targets adjacent to outer walls; set-based duplicate detection reduces stored configurations for anytime refinement.Source: §3.5 · p. 7
4 Evaluation
The evaluation compares Sokoban-LaCAM with an IDA* baseline, tests its performance across varied maps and agent/box counts, and ablates its search techniques. Results show that the search framework scales beyond 100 agents or boxes, while the ablation highlights the value of stuck detection and random restarts.
4 Evaluation
- The evaluation uses randomly generated instances on a desktop PC and examines baseline comparison, varied map settings, and component contributions.Instances exclude trivially infeasible cases, but may still be unsolvable.Source: §4 · p. 7
4.1 Comparison with IDA∗
- On the 90 empty-5-5 instances under a 30 s limit, both planners solve 27; Sokoban-LaCAM* finds initial solutions almost instantly, and all commonly solved instances eventually reach the optimum.Sokoban-LaCAM* proves optimality for most commonly solved instances.Source: Table 1 · p. 8
4.2 Stress Test
- Sokoban-LaCAM solves instances with more than 100 agents or more than 100 boxes, and substantially improves overall planning performance over Sokoban-PIBT alone.It struggles more with many boxes than with many agents; random preference construction solves only 2.8% of instances.Source: §4.2 · p. 8, Figure 1 · p. 9
4.3 Ablation Study
- Search stuck detection is the most important proposed technique for solving difficult instances, while random restart substantially improves solution quality.Without restart, depth-first search tends to pursue a single branch, producing longer makespans and fewer generated search nodes and constraints.Source: §4.3 · pp. 8–9, Figure 2 · p. 10
5 Discussion
The discussion presents Multi-Agent Sokoban as a testbed for transferring MAPF search beyond canonical MAPF. It argues that configuration-based search offers a promising foundation for broader multi-agent planning, with learned heuristics as a future direction.
5 Discussion
- The experiments show that Sokoban-LaCAM can efficiently solve large-scale instances of a problem integrating task assignment, object manipulation, and coordinated path planning.Source: §5 · p. 10
- The paper uses Multi-Agent Sokoban to investigate whether MAPF advances transfer beyond canonical MAPF, rather than to solve Sokoban itself.The authors identify learned heuristics for Sokoban-LaCAM as a future direction [13].Source: §5 · p. 10