From Agent Centric to Obstacle Centric Planning: A Makespan-Optimal Algorithm for the Multi-Agent Warehouse Rearrangement Problem

The Multi-Agent Warehouse Rearrangement (MAWR) problem calls for computing agents plans such that they collectively rearrange a warehouse environment from a given layout which species the location of every movable obstacle in the environment, to a goal layout. It is a natural variant of the well-studied Multi-Agent Path Finding (MAPF) and Multi-Agent Pickup and Delivery (MAPD) problems, which have numerous applications in warehouse automation. Similar to MAPF and MAPD, the problem is computationally hard and existing methods forgo any optimality guarantees while computing solutions to the problem. In contrast, in this work we present the first fully-coupled search-based makespan-optimal approach for solving the MAWR problem. This is done by shifting the algorithmic viewpoint from being agent centric to obstacle centric: Common MAPF and MAPD algorithms are agent-centric wherein tasks are assigned to agents, and the agents’ paths are planned to fulfill these tasks. In contrast, the approach we present here is obstacle-centric: Our algorithm iterates between two phases: Ph1 planning optimal paths for the movable obstacles using an adaptation of the celebrated CBS MAPF algorithm and Ph2 attempting to realize the movable obstacles paths using a network-flow algorithm. We prove that our approach guarantees minimal-makespan solutions and empirically demonstrate that it achieves better plans than state-of-the-art approaches for MAWR.