k-Robust Conflict-Based Search with Continuous time for Multi-robot Coordination

Abstract

Coordinating multiple robots is crucial for various real-life applications. Many Multi-Agent Path Finding (MAPF) algorithms have been proven to be successful in addressing this challenge. Nevertheless, some problems, such as unexpected delays during navigation, commonly arise when handling highlevel abstractions, potentially leading to failures or collisions in live executions. This paper proposes k-Robust Continuoustime Conflict-Based Search (kR-CCBS), a novel algorithm that overcomes some of these limitations. Our approach offers path planning with continuous time, leading to more precise routes than discrete time approaches. Additionally, we increase safety by incorporating k-robustness, enabling the system to adapt to agent failures due to delays and minimize collision risks. Comparative evaluations demonstrate that kR-CCBS outperforms similar works in effectiveness while maintaining reasonable costs, making it a promising solution for real-world multi-agent coordination scenarios.