You May Split but You Might Work It Out Later: First Steps Toward Merging Nodes in MAPF (Extended Abstract)

Abstract

CBS is a state-of-the-art MAPF algorithm whose performance has been enhanced over the years by the introduction of heuristics that focus the search and reasoning techniques that identify specific types of conflicts that can be resolved faster. To further improve the efficiency of CBS, we present a novel idea based on constraint-reasoning techniques that merges similar high-level nodes close to the root of the constraint tree while preserving CBS' optimality. As a result, some of CBS' duplicate work that occurs when expanding similar high-level nodes is avoided. Our first experimental results using a simple CBS variant (ICBS-h) show a significant reduction in the number of expanded high-level nodes on average.