Use este identificador para citar o ir al link de este elemento:
http://hdl.handle.net/1843/SLSS-86YFLH
Tipo: | Dissertação de Mestrado |
Título: | Utilização de ambientes paralelos no processo de aprendizado de algoritmos de busca de caminho em tempo real |
Autor(es): | Vinicius Marques Terra |
primer Tutor: | Luiz Chaimowicz |
primer Co-tutor: | Renato Antonio Celso Ferreira |
primer miembro del tribunal : | Fernando Santos Osório |
Segundo miembro del tribunal: | Wagner Meira Junior |
Resumen: | A constante evolução dos jogos eletrônicos possibilita a criação de ambientes cada vez mais realistas e imersivos, sendo necessário que a interação entre jogo e jogador também avance no sentido do realismo, onde a Inteligência Articial é uma das áreas respons áveis por prover tal interação. Além disso, é notável a evolução dos recursos presentes nos videogames, como a incorporação de processadores multinúcleo nos mesmos, o que muda o paradigma de programação de jogos. Uma das etapas no projeto da Inteligência Articial para jogos é a movimentação das entidades deste, onde a principal técnica utilizada é a busca de caminho. Embora em diversas situações algoritmos tradicionais como o A* resolvam este problema sem comprometimento de performance, o aumento signicativo do tamanho e da complexidade dos mapas, bem como a presença massiva de entidades em um mesmo ambiente faz com que a utilização destes algoritmos afete o desempenho dos jogos. Este problema é resolvido por algoritmos de busca de caminho em tempo real, onde o tempo de busca não aumenta com o tamanho dos ambientes. Tais algoritmos possuem um componente de aprendizado, que evita mínimos locais e aprimora os resultados das futuras buscas, visando chegar ao caminho de custo ótimo, processo que recebe o nome de convergência. Nesse trabalho, apresentamos uma estratégia de paralelização que visa diminuir tempo do processo de convergência, mantendo as restrições de tempo real presentes neste tipo de busca de caminho. A técnica de paralelização criada consiste na utilização de buscas auxiliares sem a restrição de tempo real, onde todas as buscas compartilham o aprendizado adquirido com a busca principal. A avaliação experimental, realizada na arquitetura Cell BE, mostra que,mesmo com o custo adicional necessário para a coordenação das buscas, a redução no tempo total para a convergência é signicativa, ocorrendo ganhos tanto nas buscas em ambientes com menor quantidade de mínimos locais quanto em buscas maiores, onde a melhora do desempenho é ainda melhor. |
Abstract: | The constant evolution of electronic games enables the creation of increasingly realistic and immersive environments. Along with this evolution, it is necessary that the interaction between game and player also go towards realism, where artificial inteligence is one of the areas responsible for providing such interaction. Moreover, the evolution of the hardware present in videogames, such as multi-core processors, is remarkable. The presence of parallel environments changes the paradigm of game programming, with such changes applying to artificial intelligence algorithms. One of the steps in the design of artificial intelligence for games is the movement of entities inside a game. The main technique used to control the movement of these entities is the pathfinding, which consist in finding a best cost path between two points. Although in most cases traditional algorithms such as A* solve this problem without compromising performance, the increase in the size and complexity of the maps and also the presence of massive entities in the same environment makes the use of these algorithms affect the game performance. This problem is solved by the real-time search algorithms, where the search occurs in a limited area and does not scale with the size of problem. Real-time search algorithms have a learning component, which avoids local minima and improve the results for future searches, in order to reach the minimum cost path. This process is named convergence. In this work, we present a parallelization strategy that aims to reduce time of convergence, keeping the real time constraints of this type of search. The parallelization technique consist on the use of auxiliary searches without real-time restrictions, where all the searches share the learning acquired with the main search. The empirical evaluation shows that even with the additional cost required for the coordination of searches, the reduction in the time to convergence is significant, showing gains both in searches occurring in environments with fewer local minima and in bigger searches, where performance improvement is even better. |
Asunto: | Inteligência artificial Computação Programação paralela |
Idioma: | Português |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Institución: | UFMG |
Tipo de acceso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/SLSS-86YFLH |
Fecha del documento: | 30-jun-2010 |
Aparece en las colecciones: | Dissertações de Mestrado |
archivos asociados a este elemento:
archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
viniciusmarquesterra.pdf | 2.23 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.