k-robust CBS with continuous time for multi-robot coordination

Abstract

Coordinating multiple robots is crucial for various real-life applications. Many MultiAgent Path Finding (MAPF) algorithms have been proven to be successful in addressing this challenge. Nevertheless, some MAPF algorithms exhibit shortcomings when handling high-level abstractions, neglecting real-life aspects, consequently leading to failures in live executions. In this paper, we propose k-Robust CCBS, a novel algorithm that overcomes some of these limitations. Our approach offers path planning with continuous time, leading to more precise routes. Additionally, we ensure safety through the incorporation of k-robustness, enabling the system to adapt to agent failures and minimize collision risks. Comparative evaluations demonstrate that k-Robust CCBS outperforms similar works in terms of effectiveness while maintaining reasonable costs, making it a promising solution for real-world multi-agent coordination scenarios.

Coordenar múltiplos robôs é crucial em várias aplicações na vida real. Muitos algoritmos de Planejamento de Caminhos Multi-Agente (MAPF) provaram-se bem-sucedidos abordando este desafio. No entanto, alguns algoritmos MAPF possuem limitações quando precisam lidar abstrações de alto-nível, negligenciando aspectos da realidade, consequentemente levando a falhas em execuções reais. Nesta dissertação, proponho o k-Robust CCBS, um algoritmo novo que supera algumas destas limitações. Esta abordagem possui um planejamento de caminhos com tempo contínuo, gerando rotas mais precisas. Adicionalmente, enforça-se segurança através da incorporação de k-Robustez, habilitando a adaptação do sistema a falhas de agentes e minimizando os riscos de colisões. Avaliações comparativas demonstram que o k-Robust CCBS supera trabalhos similares em termos de efetividade, enquanto mantém custos razoáveis, fazendo com que seja uma solução promissora para cenários reais de coordenação de múltiplos agentes.