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
wparameter 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
wEffectiveness: Experiments showed that increasing the sub-optimality boundwconsistently 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