ICBSS: An Improved Algorithm for Multi-Agent Combinatorial Path Finding

The Multi-Agent Combinatorial Path Finding (MCPF) problem is a generalized version of the Multi-Agent Path Finding (MAPF) problem, in which each agent must collectively visit multiple intermediate target locations on the way to its final destination. The state-of-the-art approach for addressing MCPF, known as Conflict-Based Steiner Search (CBSS) [1], leverages K-best joint sequences to create multiple search trees, and employs a CBS-like search to resolve collisions for each tree. Despite its optimality guarantee, CBSS is computationally burdensome due to the duplicated collision resolutions across multiple trees and the computation of the K best joint sequences. To address these challenges, we propose a novel algorithm called Improved Conflict-Based Steiner Search (ICBSS), aiming at expediting CBSS by replacing the multi trees with a single constraint tree (CT), which can be implemented by interleaving the time-dependent traveling salesman algorithm to compute the optimal joint path for agents under the newly generated constraints in each CT vertex. Additionally, we introduce a sub-optimal variant of ICBSS, which improves computational efficiency at the expense of solution optimality. Empirical results show that ICBSS outperforms state-of-the-art MCPF algorithms on a variety of MAPF instances.

Authors

• Zheng Chen
• Changlin Chen
• Yiran Ni

Keywords

• Machine learning algorithms
• Costs
• Heuristic algorithms
• Merging
• Transforms
• Machine learning
• Traveling salesman problems
• Computational efficiency
• Robotics and automation
• Pathfinding
• Single Tree
• Final Destination
• Multiple Trees
• Tree Search
• Time Step
• Target Sequence
• Undirected
• Workspace
• Shortest Path
• Root Node
• Spending Time
• Number Of Agents
• Root Of The Tree
• Child Nodes
• Graph Construction
• Set Of Agents
• Pair Of Vertices
• Types Of Edges
• Agency Costs
• Cost Path
• Target Copies
• Start Location
• Dynamic Obstacles
• Voter Preferences
• Cost Matrix
• Path Planning