Yaakov Sherma, Eyal Weiss, Oren Salzman

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

Introduction

From agent centric to obstacle centric planning: a makespan-optimal algorithm for the multi-agent warehouse rearrangement problem. Achieve minimal makespan for Multi-Agent Warehouse Rearrangement with our obstacle-centric algorithm. The first fully-coupled, search-based optimal approach for complex warehouse automation.

Abstract

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.

Review

This paper tackles the Multi-Agent Warehouse Rearrangement (MAWR) problem, a complex and practical variant of Multi-Agent Path Finding (MAPF) and Multi-Agent Pickup and Delivery (MAPD). The MAWR problem requires a fleet of agents to collectively reconfigure a warehouse layout, moving obstacles from an initial state to a goal state. The abstract effectively highlights the computational hardness of this problem and, crucially, points out a significant gap in existing literature: current solutions typically forgo any guarantees of optimality. This context sets a clear motivation for the presented work, which aims to address this lack of optimality. The core contribution of this research lies in presenting the first fully-coupled search-based algorithm that guarantees makespan-optimal solutions for the MAWR problem. This is achieved through an innovative shift in perspective from the conventional "agent-centric" planning, where tasks are assigned to agents, to an "obstacle-centric" approach. The proposed algorithm operates in two distinct phases: Phase 1 focuses on planning optimal paths for the movable obstacles themselves, leveraging an adaptation of the well-regarded CBS (Conflict-Based Search) algorithm, while Phase 2 employs a network-flow algorithm to ensure these obstacle paths can be realized by the agents. This architectural design is a novel and elegant way to decompose the problem, allowing for the rigorous proof of minimal-makespan solutions. The makespan-optimal guarantee represents a significant advancement for the MAWR problem, which has direct implications for the efficiency of warehouse automation and logistics. The abstract further strengthens its claim by stating empirical demonstrations of the algorithm's ability to achieve better plans than existing state-of-the-art approaches. This work not only provides a theoretical breakthrough by proving optimality but also validates its practical utility. This paradigm shift to obstacle-centric planning, coupled with the makespan-optimality guarantee and empirical validation, positions this research as a highly impactful contribution to the field of multi-agent systems and robotics.

Full Text

Comments

You need to be logged in to post a comment.