Key points are not available for this paper at this time.
A Busca de Caminhos Multiagentes (MAPF) envolve a determinação de caminhos para múltiplos agentes viajarem simultaneamente e sem colisões através de uma área compartilhada em direção a locais-alvo específicos. Este problema é computacionalmente complexo, especialmente ao lidar com grandes números de agentes, como é comum em aplicações realistas como a coordenação de veículos autônomos. Encontrar uma solução ótima é frequentemente computacionalmente inviável, tornando o uso de algoritmos aproximados e sub-otimais essencial. Aumentando a complexidade, os agentes podem agir de maneira auto-interessada e estratégica, possivelmente distorcendo seus objetivos para o algoritmo MAPF se isso lhes for benéfico. Embora o campo do design de mecanismos ofereça ferramentas para alinhar incentivos, usar essas ferramentas sem uma consideração cuidadosa pode falhar quando há apenas acesso a resultados aproximadamente ótimos. Neste trabalho, introduzimos o problema do design de mecanismos escaláveis para MAPF e propomos três mecanismos à prova de estratégias, dois dos quais até utilizam algoritmos MAPF aproximados. Testamos nossos mecanismos em domínios MAPF realistas com tamanhos de problemas variando de dezenas a centenas de agentes. Descobrimos que eles melhoram o bem-estar além de uma linha de base simples.
Friedrich et al. (Fri,) estudaram esta questão.