Dissertação

{en_GB=Application and Design of GPU Parallel RRT for Racing Car Simulation} {} EVALUATED

{pt=As Graphical Processing Units (GPUs) têm evoluído rapidamente, mantendo um poder de processamento ordens de magnitude superior ao dos Central Processing Units (CPUs). Como resultado, o interesse em usar o paradigma de programação General-Purpose computing on Graphics Processing Units (GPGPU) tem aumentado. Hoje em dia tem sido revelado empenho no estudo de algoritmos de procura probabilísticos tais como os Randomized Search Algorithms (RSA) que têm uma boa complexidade temporal e consequentemente podem ser utilizados em grandes espaços de estados. Um desses algoritmos é o Rapidly-Exploring Random Tree (RRT), que revela obter bons resultados quando aplicado a espaços de estados dinâmicos com grande dimensionalidade. Este trabalho consiste no desenvolvimento, estudo e exploração de técnicas de parallelização baseadas no GPGPUs de modo a melhorar a aplicação do RRT a videojogos de corridas. De modo a executar este estudo, foi criada uma variante do RRT chamada Iterative Parallel Sampling RRT (IPS-RRT) e um agente foi construído para o jogo open source TORCS. Os resultados mostram que, embora os acessos às memórias pelo GPU apresentem latências altas, o uso de abordagens melhoradas pelo GPGPU como a apresentada neste trabalho conseguem não só melhorar a eficiência computacional mas também a qualidade das soluções retornadas, dado que o GPU IPS-RRT conseguiu melhorias a nível temporal para problemas de grandes dimensões (gerando 6400 estados) e reduções nos tempos de volta na ordem dos 19%., en=Graphical Processing Units (GPUs) have evolved at a large pace, maintaining a processing power orders of magnitude higher than Central Processing Units (CPUs). As a result, the interest of using the General-Purpose computing on Graphics Processing Units (GPGPU) paradigm has grown. Nowadays, effort is being put to study probabilistic search algorithms like the Randomized Search Algorithms (RSA) family, which have good time complexity, and thus can be adapted to massive search spaces. One of those algorithms is Rapidly-Exploring Random Tree (RRT) which reveals good results when applied to high dimensional dynamical search spaces. This work consists in the design, exploration and study of the use of GPGPU-based parallelization techniques in order to improve the application of RRT to racing videogames. To approach such study, a new variant of the RRT algorithm called Iterative Parallel Sampling RRT (IPS-RRT) was developed and a bot for the TORCS open source racing game was built. The results show that, although accesses to the GPU’s memory present high latency, the use of GPGPU-based techniques like the one of this work can still improve not only the planning computational efficiency but also the quality of the returned solutions, as GPU IPS-RRT achieved temporal improvements in big problem sizes (when generating 6400 states) and lap time reductions of around 19%.}
{pt=Programação Geral para GPUs,  Algorítmos de Procura com Aleatoriedade, Iterative Parallel Sampling RRT, The Open Racing Car Simulator, Planeamento, en=General-Purpose computing on GPUs, Randomized Search Algorithms, Iterative Parallel Sampling RRT, The Open Racing Car Simulator, Planning}

Julho 26, 2017, 10:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

João Miguel De Sousa de Assis Dias

Departamento de Engenharia Informática (DEI)

Professor Auxiliar

ORIENTADOR

Carlos António Roque Martinho

Departamento de Engenharia Informática (DEI)

Professor Auxiliar