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

Junkai Jiang, Ruochen Li, Yibin Yang, Yihe Chen, Yuning Wang, Shuai Xu, Jianqiang Wang

TL;DR

This paper introduces CTS-CBS, a novel algorithm for Multi-Agent Collaborative Task Sequencing and Path Finding (CTS-MAPF). It tackles the complex problem of coordinating multiple robots to visit a sequence of tasks and reach their destinations without collisions, offering a theoretically sound approach that balances optimality and efficiency.

What Problem Does This Paper Address?

The paper addresses a challenging extension of the Multi-Agent Pathfinding (MAPF) problem, termed Collaborative Task Sequencing - Multi-Agent Pathfinding (CTS-MAPF). In standard MAPF, agents need to find collision-free paths from their start to their goal. CTS-MAPF adds a crucial layer of complexity: agents must not only navigate collision-free but also visit a series of intermediate "task" locations in a specific, optimized order before reaching their final destinations. This problem is particularly relevant in scenarios like automated warehouses, hazardous material monitoring, or robotic delivery systems where coordinated task execution is paramount. The core challenge lies in simultaneously optimizing both the sequence of tasks for each agent and their collision-free paths, a problem that is computationally demanding due to the NP-hard nature of both the Traveling Salesperson Problem (TSP) for sequencing and MAPF for pathfinding.

Methods

The proposed solution, CTS-CBS, employs a two-level search architecture, building upon the Conflict-Based Search (CBS) framework.

  • High-Level Search: Instead of a single search tree as in standard CBS, CTS-CBS constructs a "search forest." Each tree within this forest corresponds to a specific joint task sequence for all agents. These sequences are generated by solving the joint TSP (jTSP) problem, specifically by finding the K-best solutions for the jTSP. This allows the algorithm to explore multiple task orderings.
  • Low-Level Search: Within each search tree, CTS-CBS performs constrained single-agent path planning. This means each agent plans its path to adhere to the high-level task sequence and any collision constraints imposed by the high-level search.
  • K-Best Joint Task Sequencing: A novel component is the method for generating K-best solutions for the jTSP. This involves a two-layer approach: first, finding K-best sequences for individual agents, and then combining these to find the K-best joint sequences.
  • Necessity Checking for New Root Nodes: To manage the search forest and balance optimality with efficiency, a "necessity checking" mechanism is introduced. This mechanism, controlled by a sub-optimality bound parameter w, determines when to create a new search tree (based on the next best jTSP solution) versus continuing to resolve conflicts within an existing tree. This allows for a trade-off between solution quality and computation time.

Datasets

The paper introduces two new datasets for evaluating CTS-MAPF and related problems:

  • CTS-MAPF Dataset: Adapted from existing MAPF benchmarks (Moving AI [27]), this dataset features scenarios where agents have a predefined order of tasks to visit before reaching their final destinations.
  • MG-MAPF Dataset: This dataset is derived from the CTS-MAPF dataset but treats the final destination as just another task, transforming the problem into a Multi-Goal MAPF (MG-MAPF) scenario where agents don't have a fixed final destination. This allows for comparison with existing MG-MAPF algorithms.

Key Insights and Ideas

  • Decomposing Complexity: The core insight is to decompose the highly complex CTS-MAPF problem into two more manageable sub-problems: task sequencing (jTSP) and collision-free pathfinding (MAPF). By integrating solutions to these, CTS-CBS can tackle the combined problem.
  • Search Forest for Task Exploration: Using a search forest, where each tree represents a different task sequence, is a powerful way to explore the vast combinatorial space of possible task orderings. This is a key departure from traditional single-tree search methods.
  • K-Best Solutions for Robustness: Generating K-best solutions for the jTSP is crucial. It ensures that even if the absolute optimal task sequence leads to difficult pathfinding conflicts, the algorithm can fall back to slightly suboptimal but more feasible sequences, improving success rates.
  • Tunable Sub-optimality: The introduction of the w parameter provides a crucial knob for users to tune the algorithm. This allows for a direct trade-off between finding a guaranteed optimal solution (at higher computational cost) and finding a good-enough solution much faster.

Key Results

  • Significant Performance Gains: The proposed CTS-CBS adaptations for the MG-MAPF problem significantly outperformed baseline algorithms. They achieved up to a 20x larger success rate and were up to 100x faster.
  • Competitive Solution Quality: Despite the speed and success rate improvements, the sacrifice in solution quality was minimal, typically less than 10%.
  • Parameter w Effectiveness: Experiments showed that increasing the sub-optimality bound w consistently improved success rate and reduced runtime, demonstrating the effectiveness of the tunable trade-off mechanism.
  • Practical Applicability: The algorithm was successfully deployed on physical robots, validating its real-world applicability.

Limitations and Future Work

  • Computational Cost of K-Best TSP: While the K-best jTSP approach is effective, generating these solutions can still be computationally intensive, especially for large numbers of agents and tasks.
  • Kinematic Constraints: The current work assumes simplified agent models. Future work will explore incorporating kinematic constraints of agents, which is crucial for real-world robot deployment.
  • Dynamic and Lifelong Scenarios: The algorithm is designed for static environments. Extending it to handle dynamic environments with moving obstacles or to operate in a lifelong learning fashion is a promising direction.
  • Further Efficiency Enhancements: The authors plan to explore additional strategies to further boost the efficiency of CTS-CBS.

Summary updated

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.
BibTeX
@article{jiang2026cts,
  author = {Junkai Jiang and Ruochen Li and Yibin Yang and Yihe Chen and Yuning Wang and Shuai Xu and Jianqiang Wang},
  title = {{CTS-CBS: A New Approach for Multi-Agent Collaborative Task Sequencing and Path Finding}},
  journal = {IEEE Internet of Things Journal},
  year = {2026},
  doi = {10.1109/jiot.2026.3663569},
}
Figure