Parallel multi-speed pursuit-evasion game algorithms

Abstract

Pursuit-Evasion Game (PEG) consiste de um time de perseguidores tentando capturar um ou mais fugitivos. PEG é importante devido à sua aplicação em vigilância, busca e salvamento, robótica de desastres, defesa de fronteiras e assim por diante. Em geral, PEG requer tempo exponencial para calcular o número mínimo de perseguidores para capturar um fugitivo. Para mitigar isso, criamos um algoritmo paralelo ótimo para minimizar o tempo de captura no PEG. Dada uma topologia discreta, esse algoritmo também gera o número mínimo de perseguidores para capturar um fugitivo. Também foi estendido o algoritmo paralelo para outras versões como: heterogênea/jogadores multi-velocidade; a técnica pac-dot para aumentar a longevidade do evader em um jogo, e; uma estratégia de poda para a técnica pac-dot, para aumentar a sua escalabilidade. Além disso, descrevemos um algoritmo para alocação de recursos entre redes de agentes heterogêneos, para disponibilizar todos os recursos para cada agente heterogêneo da equipe, por meio do compartilhamento de recursos na vizinhança do nó. Cada equipe de agentes com todos os recursos disponíveis é associada a um fugitivo no jogo de perseguição e fuga. A abordagem é tolerante a falhas nos casos em que um recurso/agente quebra, sendo capaz de alocar um recurso compatível quando disponível. As principais contribuições desta tese são: Primeiro, foi descrito um algoritmo para alocação de recursos para múltiplas equipes de agentes com todos os recursos disponíveis. Em segundo lugar, aplicamos nossa abordagem de alocação de recursos para substituir um agente em tempo real se ele falhar. Em terceiro lugar, avaliamos nossa técnica aplicando-a ao PEG, desde a composição das equipes até a introdução e correção de falhas ao longo das simulações da instância. O desempenho do algoritmo paralelo foi avaliado pela métrica speedup. O algoritmo e suas extensões foram simulados e avaliados em diversas topologias, para validar a sua viabilidade a partir da discussão e avaliação de um conjunto de resultados. O algoritmo paralelo nos permite escalar até 8,13 vezes com 32 núcleos em comparação com o estado da arte. Considerando a complexidade do espaço de estados, a técnica de poda para o algoritmo pac-dot minimiza o espaço de estados e transições geradas, podendo lidar com um grande número de estados (≈830Mi) e transições (≈11Bi). Em geral, nossos algoritmos aumentam a escalabilidade e tornam viável o cálculo da estratégia ótima PEG para casos mais realistas. As simulações para estratégia de alocação de recursos foram realizadas para treze jogadores, simultaneamente. A partir da avaliação das simulações, a abordagem se mostrou eficiente para manter uma trajetória ótima até a captura dos fugitivos nos casos em que ocorre falha. Além disso, a abordagem escala para que muitos jogos ocorrerem simultaneamente.