Análise de algoritmos de busca hierárquica com a utilização de redes neurais profundas
Abstract
Algoritmos de pathfinding e redes neurais profundas têm ganhado destaque na área de Inteligência
Artificial (IA). Em geral, estes algoritmos contam com uma heurística que guia a busca a cada nodo
expandido durante a busca do caminho. O problema é que funções heurísticas tradicionalmente usadas por vários algoritmos de pathfinding, a exemplo da distância Euclidiana e a distância de Manhattan, não
consideram as características dos mapas virtuais em que o caminho é computado, tendendo a expandir cada vez mais nodos a medida em que o comprimento do caminho cresce. Tal expansão de nodos acaba gerando tempos de busca elevados quando grandes espaços de busca estão sendo tratados. Para abordar esse problema, este trabalho investiga como usar redes neurais profundas na construção de funções heurísticas para algoritmos de pathfinding hierárquicos, permitindo assim otimizar a busca de caminhos em mapas virtuais de grandes dimensões e diferentes naturezas. Especificamente, este trabalho explora a
implementação de um algoritmo hierárquico de busca, o qual divide os mapas virtuais em sub mapas,
gerando um nível de abstração para acelerar o processo de busca. Uma vez que o caminho abstrato está
pronto, o algoritmo faz um refinamento no nível mais baixo de abstração, empregando o algoritmo de
busca A*. O principal objetivo deste trabalho é, portanto, verificar se o A* empregado em cada sub mapa
pode ser otimizado com a utilização de redes neurais profundas como funções heurísticas. E experimentos
foram realizados com o emprego de três diferentes tipos de mapas virtuais, onde resultados obtidos foram
analisados a partir de técnicas estatísticas de regressão. A partir dos resultados obtidos, o algoritmo
hierárquico explorado neste trabalho foi otimizado em termos de tempo e nodos expandidos
Collections
The following license files are associated with this item: