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:
- 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.
- 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.
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.
Navigation Flexibility
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