CBTMP: Optimizing Multi-Agent Path Finding in Heterogeneous Cooperative Environments

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.