Multi-Agent Monte Carlo Tree Search for Makespan-Efficient Object Rearrangement in Cluttered Spaces
Hanwen Ren, Junyoung Kim, Aathman Tharmasanthiran, Ahmed H. Qureshi
AI summary
Problem
Real-world object rearrangement often involves non-monotone tasks where objects block each other, but existing multi-agent planners are limited to monotone cases, rely on costly learning, or force synchronous execution that wastes time.
Approach
The method uses a centralized Monte Carlo Tree Search to assign tasks while allowing robots to start new tasks immediately upon finishing current ones, guided by a one-step look-ahead cost estimate to avoid idle waiting.
Key results
- Centralized task assignment reduces combinatorial search space
- Asynchronous execution with one-step look-ahead minimizes robot idle time
- Consistent makespan reduction over strong baselines in simulation
- Successful real-world multi-robot validation across diverse configurations
Why it matters
Provides a scalable, non-learning-based planning framework that enables faster, more efficient multi-robot collaboration for logistics, warehouse automation, and disaster response.
Abstract
Object rearrangement planning in complex, clut- tered environments is a common challenge in warehouses, households, and rescue sites. Prior studies largely address monotone instances, whereas real-world tasks are often non- monotone—objects block one another and must be temporarily relocated to intermediate positions before reaching their final goals. In such settings, effective multi-agent collaboration can substantially reduce the time required to complete tasks. This paper introduces Centralized, Asynchronous, Multi-agent Monte Carlo Tree Search (CAM-MCTS), a novel framework for general-purpose makespan-efficient object rearrangement planning in challenging environments. CAM-MCTS combines centralized task assignment—where agents remain aware of each other’s intended actions to facilitate globally optimized planning—with an asynchronous task execution strategy that enables agents to take on new tasks at appropriate time steps, rather than waiting for others, guided by a one-step look- ahead cost estimate. This design minimizes idle time, prevents unnecessary synchronization delays, and enhances overall sys- tem efficiency. We evaluate CAM-MCTS across a diverse set of monotone and non-monotone tasks in cluttered environments, demonstrating consistent reductions in makespan compared to strong baselines. Finally, we validate our approach on a real-world multi-agent system under different configurations, further confirming its effectiveness and robustness. Videos can be found at https://www.youtube.com/watch?v=kNRg2kNnFxg.