CBTMP: Optimizing Multi-Agent Path Finding in Heterogeneous Cooperative Environments
Jianqi Gao, Yanjie Li, Yongjin Mu, Qi Liu, Haoyao Chen, Yunjiang Lou
Abstract
This paper introduces the Conflict-Based Three-agent Meeting with Pickup (CBTMP), a near-optimal algorithm tailored for cooperative multi-agent path finding in heterogeneous environments, specifically to boost the operational efficiency of intelligent warehouses. CBTMP is a two-level algorithm. The high-level policy identifies the meeting positions for heterogeneous agents by reformulating the cooperative multi-agent path finding problem as a multi-group, three-agent meeting with pickup problem. Using the meeting positions and predefined task positions, the low-level policy utilizes the proposed conflict-based search with time-step alignment algorithm to plan conflict-free paths for all heterogeneous agents. Extensive evaluations on six two-dimensional grid benchmark maps reveal that CBTMP not only significantly bolsters solution success rates but also attains near-optimal sum-of-costs and makespan values. To confirm its real-world applicability, we also validate CBTMP through experiments with physical Turtlebot3 robots.
BibTeX
@inproceedings{ral2025_cbtmpoptimizingm,
title = {CBTMP: Optimizing Multi-Agent Path Finding in Heterogeneous Cooperative Environments},
author = {Jianqi Gao and Yanjie Li and Yongjin Mu and Qi Liu and Haoyao Chen and Yunjiang Lou},
booktitle = {RA-L 2025},
year = {2025}
}