Multi-Agent Path Finding (MAPF) is an algorithm designed to identify collision-free paths for multiple agents, commonly used in fields like robotics and drone navigation. Conflict-Based Search with Continuous Time (CCBS) is particularly beneficial for real-world applications due to its capability to find paths in continuous time; however, it often experiences lengthy computation times. Although techniques such as prioritizing conflicts (PC), disjoint splitting (DS), and high-level heuristics have been implemented to reduce these times, challenges remain. To address these issues, this paper introduces methods to improve space utilization by calculating agent congestion. By optimizing space usage, we can identify paths that avoid potential collisions, even when those paths share the same cost. We propose enhancements to high-level heuristics, conflict prioritization, and low-level heuristics, as well as a method for calculating congestion in continuous time. These improvements lead to a reduction in agent collisions and a decrease in high-level expansions, resulting in a 30% increase in computational success rates compared to the existing CCBS. Incorporating space utilization into the search process significantly enhances MAPF performance.
Im et al. (Wed,) studied this question.