Sokoban is a grid-world puzzle in which an agent pushes boxes onto target locations. Its multi-agent version additionally requires simultaneous reasoning about which agent should handle which box, how boxes should be ordered, and how agents can move without colliding. The joint-action branching factor grows rapidly with the number of agents, while push-only motion creates severe and often irreversible dead ends. The paper treats this problem as both a challenging planning domain and a testbed for studying whether MAPF techniques can support broader collective automation, such as coordinated warehouse robots.
The main contribution is an adaptation of LaCAM’s configuration-space search to Multi-Agent Sokoban with relatively modest domain-specific changes. The proposed solver combines LaCAM with a box-aware PIBT-based configuration generator, called Sokoban-PIBT, while preserving the overall search structure and its guarantees. The paper reports better scalability than adapting conventional single-agent Sokoban search and demonstrates instances involving tens of agents and boxes. More broadly, it argues that MAPF should be viewed not only as a standalone problem, but also as a reusable 提案手順c primitive for richer multi-agent planning tasks.
Sokoban-LaCAM searches over configurations containing the positions of all agents and boxes. At each expansion, the dedicated PIBT-based generator selects agent actions while accounting for target-to-box and agent-to-box assignments; the resulting box placements are induced by those actions rather than generated independently. Actions causing box-box or box-agent collisions are rejected, and valid transitions require that objects either wait or move to adjacent vertices, that no pair swaps positions, and that every moved box is pushed by exactly one adjacent agent. LaCAM adds lazy constraints and repeatedly generates configurations, allowing it to obtain an initial solution and then refine it. The implementation also uses duplicate detection for configurations that are equivalent when agents and boxes are treated as indistinguishable, dead-end pruning, random restart, and stuck detection. The excerpt states that the search remains exhaustive regardless of the underlying configuration generator, including a random-walk generator, according to prior analysis of LaCAM.
The evaluation has three stated goals: measuring the value of an MAPF-based search backbone on small instances, testing performance across maps and varying numbers of agents and boxes, and assessing the contribution of individual technical components. Instances are generated by randomly placing agents and boxes on specified grid maps, excluding trivially infeasible cases; unsolvable instances may nevertheless remain. The experiments use a desktop with an Apple M1 Ultra CPU and 20 cores, with up to 16 runs in parallel using multithreading. The excerpt does not establish the amount of RAM or the numerical value of every time limit, so those details cannot be inferred. Reported measures include success rate, time to obtain an initial solution, solution cost, initial and final cost improvement, comparison with optimal solutions, search-node counts, and constraint counts.
The results suggest that the combination of LaCAM and PIBT is a promising backbone for the large joint search space of Multi-Agent Sokoban. This setting differs materially from transport-oriented MAPF variants in which an agent and cargo may co-locate or cargo may be repositioned more freely: Sokoban’s push-only dynamics make dead ends particularly severe and frequently irreversible. Consequently, the behavior of the configuration generator is important, not merely the outer search, and the ablation results identify stuck detection and random restart as especially influential. The paper’s goal is not to establish the best possible Sokoban-specific solver, but to test the transfer of MAPF ideas beyond canonical MAPF. The authors therefore frame the result as evidence for a general planning direction rather than as a complete engineering recipe for every manipulation or warehouse setting.
Sokoban is difficult because a box next to a wall cannot be pushed from every direction, creating restricted and sometimes unreachable box configurations. It is a long-standing heuristic-search benchmark and is PSPACE-complete from the computational-complexity perspective. Multi-Agent Sokoban adds inter-agent collision handling and integrated assignment to these already difficult object-manipulation constraints. MAPF computes collision-free paths for multiple agents on a graph, and LaCAM is presented as a recent configuration-based MAPF approach intended to scale to many agents.
The environment is modeled as an undirected graph whose vertices are traversable grid cells and whose edges connect orthogonally adjacent cells. An instance contains agents, boxes, and target locations, with the number of boxes equal to the number of targets. A configuration is an injective assignment of every agent and box to a distinct vertex, and a solution is a finite sequence ending with every target occupied by a box. Between consecutive configurations, each object may wait or move to an adjacent vertex, no ordered pair of objects may swap positions, and every moved box must have exactly one adjacent agent that pushes it. The problem must therefore satisfy object-manipulation, assignment, and multi-agent collision constraints at once.
Sokoban-PIBT generates only agent actions; the box configuration follows implicitly from those actions. The method rejects actions that create box-box or box-agent conflicts while retaining LaCAM’s configuration-based search and lazy constraint mechanism. Duplicate detection treats configurations with the same occupied-location set as identical when agents and boxes are considered indistinguishable, reducing the number of stored states and supporting anytime refinement. The excerpt says that the exhaustive-search property does not depend on using a sophisticated configuration generator, although domain-aware generation is important for practical performance.
The evaluation covers empty, random, and warehouse-style maps with different sizes and different numbers of agents and boxes. The excerpt reports an aggregated time-limited comparison over 1,880 instances and a small-scale comparison on 90 empty-5-5 instances. It also reports an ablation study on random maps, comparing variants on the 274 instances solved by every variant. The listed comparisons include Sokoban-PIBT versus Sokoban-LaCAM and versions removing duplicate detection, dead-end pruning, random restart, or stuck detection.
In the small-scale comparison, both planners solved 27 commonly solved instances; Sokoban-LaCAM reportedly found initial solutions almost instantly and eventually converged to the optimum on all of those instances. The time-limited aggregate success rates shown in the excerpt are 40.2% for Sokoban-PIBT and 68.2% for Sokoban-LaCAM. In the ablation, removing stuck detection reduced the reported success rate, while removing random restart degraded initial and final solution quality and reduced the breadth of exploration. The excerpt further reports that duplicate detection and dead-end pruning add per-node computation but reduce the number of generated search nodes and constraints, suggesting that their pruning benefit outweighs that overhead.
Sokoban-LaCAM demonstrates that a MAPF configuration-search backbone can be extended to a domain combining pushing, assignment, and collision-free coordination. The reported evidence supports the claim that the solver can address instances with tens of agents and boxes while preserving completeness and eventual optimality guarantees. The broader conclusion is that MAPF methods may serve as reusable foundations for collective automation problems whose dynamics are richer than ordinary pathfinding.
The paper explicitly says that it is not intended to provide a complete engineering blueprint, and some implementation details are omitted. Although unsolvable instances may be present, the excerpt does not fully specify the time limits, RAM amount, or every baseline configuration, which limits exact reproducibility from the supplied evidence. The evaluation uses random placements and selected grid maps, so the excerpt does not establish generalization to real warehouses, dynamic obstacles, heterogeneous robots, or learned components. It also does not establish that Sokoban-LaCAM is optimal in practical runtime or solution quality against every relevant Sokoban or MAPF method.
The work connects scalable MAPF search with irreversible object manipulation rather than only movement through a graph. That connection is relevant to warehouse robots and other collective-automation systems in which agents must transport or rearrange objects while coordinating their paths. It provides a concrete argument for reusing MAPF as a planning primitive instead of designing an entirely separate joint-search framework for every new multi-agent domain. The result also motivates future combinations of structured MAPF search with learned heuristics.
This paper is useful for researchers in multi-agent pathfinding, warehouse automation, multi-agent planning, Sokoban, and configuration-space search. It is especially relevant to readers studying LaCAM, PIBT, integrated task assignment and collision avoidance, or the transfer of MAPF methods to object-manipulation domains. Readers seeking a detailed learned heuristic design or validated deployment study in a physical warehouse should note that the supplied excerpt does not provide those details.