Parallel Multi-speed Pursuit-Evasion Game Algorithms - Santos, Renato Fernando dos; Vieira, Marcos Augusto Menezes (Anais Estendidos do Simpósio Brasileiro de Robótica e Simpósio Latino-Americano de Robótica (SBR/LARS), 2024)
O Jogo de Perseguição-Fuga (PEG) é importante no campo da robótica. Determinar a estratégia ótima, como o número mínimo de perseguidores necessário, frequentemente exigindo tempo exponencial. Propomos um novo algoritmo paralelo que reduz significativamente o tempo de computação para PEG, tornando possível analisar jogos com um grande número de estados e transições. O algoritmo também se estende aos jogadores heterogêneos/multi-velocidade e incorpora estratégias avançadas Além disso, introduzimos um algoritmo de alocação de recursos para equipes multi-agentes heterogêneas, garantindo o compartilhamento eficiente de recursos e a substituição em tempo real de agentes para manter a tolerância a falhas. Nossas simulações demonstram que nosso algoritmo paralelo supera significativamente as abordagens existentes, alcançando até 8,13 vezes mais velocidade em comparação com o estado da arte. Além disso, nossos algoritmos melhoram a escalabilidade e a aplicabilidade prática na resolução de PEGs.