CTS-CBS: A New Approach for Multiagent Collaborative Task Sequencing and Path Finding

Abstract

This paper addresses a generalization problem of Multi-Agent Pathfinding (MAPF), called Collaborative Task Sequencing - Multi-Agent Pathfinding (CTS-MAPF), where agents must plan collision-free paths and visit a series of intermediate task locations in an optimized order before reaching their final destinations. To address this problem, we propose a new approach, Collaborative Task Sequencing - Conflict-Based Search (CTS-CBS), which conducts a two-level search. In the high level, it generates a search forest, where each tree corresponds to a joint task sequence derived from the jTSP solution. In the low level, CTS-CBS performs constrained single-agent path planning to generate paths for each agent while adhering to high-level constraints. Furthermore, we integrate Explicit Estimation Search into CTS-CBS to enhance the search efficiency. We also provide theoretical guarantees of its solution completeness and optimality (or sub-optimality with a bounded parameter). To evaluate the performance of CTS-CBS, we utilize three datasets with different map sizes, map difficulty and agent/task numbers, and conduct comprehensive experiments. The results show that our algorithms demonstrate significant improvements in success rate and runtime, while maintaining competitive solution quality. Finally, practical robot simulation and tests demonstrate the algorithm’s applicability in real-world scenarios.