Use este identificador para citar o ir al link de este elemento:
http://hdl.handle.net/1843/58297| Tipo: | Tese |
| Título: | Parallel multi-speed pursuit-evasion game algorithms |
| Título(s) alternativo(s): | Algoritmos paralelos para pursuit-evasion game de velocidades variadas |
| Autor(es): | Renato Fernando dos Santos |
| primer Tutor: | Marcos Augusto Menezes Vieira |
| primer miembro del tribunal : | Luiz Chaimowicz |
| Segundo miembro del tribunal: | Douglas Guimarães Macharet |
| Tercer miembro del tribunal: | Leandro Soriano Marcolino |
| Cuarto miembro del tribunal: | Denis Fernando Wolf |
| Resumen: | Pursuit-Evasion Game (PEG) consists of a team of pursuers trying to capture one or more evaders. PEG is important due to its application in surveillance, search and rescue, disaster robotics, boundary defense, and so on. In general, PEG requires exponential time to compute the minimum number of pursuers to capture an evader. To mitigate this, we have designed a parallel optimal algorithm to minimize the capture time in PEG. Given a discrete topology, this algorithm also outputs the minimum number of pursuers to capture an evader. We also extended the parallel algorithm to consider other versions as: heterogeneous/multi-speed players; the pacdot technique to increase evader lifetime in a game; and a pruning strategy for pac-dot technique to increase the scalability. Additionally, We describe an algorithm for resource allocation between networks of heterogeneous agents to make all resources available to each heterogeneous agent of the team via resource sharing in the node neighborhood. Each team of agents with all resources available is associated with an evader to play pursuit-evasion games. Our approach is fault tolerant in cases where a resource/agent breaks, being able to allocate a compatible resource when available. The main contributions of this thesis are as follows. First, we describe an algorithm for resource allocation for multi-teams of agents with all resources available. Second, we apply our resource allocation approach to replace an agent in real time if it fails. Third, we evaluate our technique by applying it to the PEG, from the composition of the teams to the introduction and fixing of failures throughout the instance simulations. The parallel algorithm performance was evaluated by speedup metric and this algorithm and its extensions were simulated and evaluated on many different topologies to validate the viability of our algorithms by discussing and evaluating a set of simulation results. The parallel algorithm enables us to scale up to 8.13 times with 32 cores compared to the state-of-the-art. Considering the complexity of the state space growing up, the pruning technique to the pac-dot algorithm minimizes the state space and generated transition and can handle a large number of states (≈830 M) and transitions (≈11 G) generated. In general, our algorithms increase the scalability and make it feasible to compute the PEG optimal strategy for more realistic cases. The simulations for allocation resources strategy were carried out for thirteen players, simultaneously. From the evaluation of the simulations, the approach proved to be efficient to maintain an optimal trajectory until the capture of evaders in cases in which failure occurs. Furthermore, the approach scales for many games being played simultaneously. |
| 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. |
| Asunto: | Computação – Teses Jogo de perseguição e fuga – Teses Sistemas Multi-agentes – Teses Robôs heterogêneos |
| Idioma: | eng |
| País: | Brasil |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Institución: | UFMG |
| Departamento: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
| Curso: | Programa de Pós-Graduação em Ciência da Computação |
| Tipo de acceso: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/58297 |
| Fecha del documento: | 2-jun-2023 |
| Aparece en las colecciones: | Teses de Doutorado |
archivos asociados a este elemento:
| archivo | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| Thesis Final - Renato Fernando dos Santos.pdf | 8.11 MB | Adobe PDF | Visualizar/Abrir |
Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.