The Multi-Agent Pickup and Delivery Problem: MAPF, MARL and Its Warehouse Applications

Tim Tsz-Kit Lau, Biswa SenguptaarXiv 2022 · DOI · arXiv

Abstract

This paper presents a comparative study between traditional Multi-Agent Path-Finding (MAPF) and Multi-Agent Reinforcement Learning (MARL) in the context of the Multi-Agent Pickup and Delivery (MAPD) problem. Using the RWARE warehouse environment, the authors evaluate Conflict-Based Search (CBS) and Shared Experience Actor-Critic (SEAC). While CBS demonstrates superior efficiency in small-scale scenarios, SEAC exhibits significantly better scalability and real-time execution capabilities as agent density increases.

Introduction

In modern automated logistics, fleets of robots are tasked with the continuous pickup and delivery of items. This "lifelong" operational requirement, known as the Multi-Agent Pickup and Delivery (MAPD) problem, presents significant challenges in path planning and conflict resolution. Traditionally, this has been addressed via Multi-Agent Path-Finding (MAPF) algorithms like Conflict-Based Search (CBS). However, the rise of Multi-Agent Reinforcement Learning (MARL) offers a decentralized alternative. This study benchmarks these two paradigms to identify their respective strengths and scaling limits.

Experimental Methodology

The researchers compared two representative approaches:

  1. Lifelong Conflict-Based Search (CBS): A search-based algorithm that resolves collisions by imposing spatio-temporal constraints. To adapt it for lifelong tasks, the system triggers a full replan whenever an agent receives a new assignment.
  2. Shared Experience Actor-Critic (SEAC): A MARL framework where agents learn navigation policies through trial and error, sharing experiences to accelerate convergence.

Environment and Datasets

The benchmarks were conducted using a modified Multi-Robot Warehouse Environment (RWARE). The grid-based layouts include shelves (obstacles) and corridors, categorized into small, medium, and large sizes.

Warehouse layouts (small, medium, large) with 5 agents illustrating the grid-based environment.

Results and Analysis

Efficiency vs. Scalability

The results reveal a clear trade-off between optimality and scalability. At a small scale (5 agents), CBS significantly outperformed SEAC, achieving lower mean flow times and higher throughput (delivering ~27 items per episode vs. SEAC's ~10-14). However, CBS hit a "computational wall" beyond 8 agents, failing to provide real-time solutions due to the exponential growth of the search space in dense environments.

In contrast, SEAC demonstrated robust scalability. As shown in the performance table below, SEAC successfully managed up to 15 agents while maintaining consistent episodic times. The authors noted that a dense reward structure (points for both pickup and delivery) was vital for effective learning.

Performance metrics for the SEAC (MARL) algorithm, showing its ability to scale to 15 agents.

A key qualitative difference emerged in how agents interact with the environment. In the CBS implementation, unrequested shelves were treated as static obstacles, restricting movement. MARL agents, however, learned to navigate under empty shelves, effectively increasing the available "road" capacity and reducing congestion.

Real-Time Execution

A critical advantage of the MARL approach is the shift of computational load. While CBS requires intensive replanning during execution (leading to robot idle time), SEAC performs heavy computation during training. At test time, agents execute learned policies nearly instantaneously, making them better suited for dynamic, real-time warehouse operations.

Conclusion

The study concludes that while traditional MAPF solvers like CBS are ideal for small, sparse fleets where path optimality is paramount, MARL approaches like SEAC are superior for large-scale, dense warehouse environments. Future work points toward hybrid systems, potentially using imitation learning to combine the precision of search-based methods with the scalability of neural networks.

Summary updated

Abstract

We study two state-of-the-art solutions to the multi-agent pickup and delivery (MAPD) problem based on different principles -- multi-agent path-finding (MAPF) and multi-agent reinforcement learning (MARL). Specifically, a recent MAPF algorithm called conflict-based search (CBS) and a current MARL algorithm called shared experience actor-critic (SEAC) are studied. While the performance of these algorithms is measured using quite different metrics in their separate lines of work, we aim to benchmark these two methods comprehensively in a simulated warehouse automation environment.
BibTeX
@misc{lau2022multi,
  author = {Tim Tsz-Kit Lau and Biswa Sengupta},
  title = {{The Multi-Agent Pickup and Delivery Problem: MAPF, MARL and Its Warehouse Applications}},
  year = {2022},
  eprint = {2203.07092},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2203.07092},
}
Figure