Multi-agent Sokoban solving improves with pathfinding advances
Solving Multi-Agent Sokoban via LaCAM
Multiagent Systems
Summary
Sokoban is a puzzle where you push boxes on a grid to reach target spots, but it gets much harder when many agents push boxes at once. The authors show that by using new techniques for multi-agent pathfinding, they can solve complex versions of this puzzle efficiently with many agents and boxes. Their method, Sokoban-LaCAM, not only finds solutions reliably but also can find the best solutions over time. This work suggests that advances in multi-agent path planning can help solve harder coordination problems in automated systems.
What this means in practice
- •For warehouse automation teams: Coordinate multiple autonomous forklifts to assign tasks and navigate without collisions in complex warehouse layouts.
- •For robotics system integrators: Integrate multi-agent pathfinding techniques for coordinating robot fleets in environments requiring simultaneous manipulation and navigation.
Authors
Keisuke Okumura
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.