Trabalho de Conclusão de Curso de Graduação
Análise de algoritmos de busca hierárquica com a utilização de redes neurais profundas
Fecha
2021-02-09Autor
Gez, Jairo Ferreira
Institución
Resumen
Pathfinding algorithms and deep neural networks have gained prominence in the area of Artificial
Intelligence (AI). In general, these algorithms have a heuristic that guides the search for each expanded
node during the p ath search. The problem is that heuristic functions traditionally used by various
pathfinding algorithms, such as the Euclidean distance and the Manhattan distance, do not consider the
characteristics of the virtual maps in which the path is computed, ten d ing to expand more and more nodes
as the path length grows. Such expansion of nodes ends up generating long search times when large search
spaces are being treated. To solve this problem, this work investigates how to use deep neural networks in
the constr uction of heuristic functions for hierarchical pathfinding algorithms, thus allowing to optimize the
search for paths in large virtual maps and different natures. Specifical ly, this work explores the
implementation of a hierarchical search algorithm, which divides virtual maps into sub maps, generating a
level of abstraction to speed up the search process. Once the abstract path is ready, the algorithm makes a
refinement at t he lowest level of abstraction, using the search algorithm A *. The main objective of this
work is, therefore, to verify if the A * used in each sub map can be optimized with the use of deep neural
networks as heuristic functions. Experiments were carried out using three different types of virtual maps,
where results obtained were analyz ed using statistical regression techniques. From the results obtained, the
hierarchical algorithm explored in this work was optimized in terms of time and expanded nodes.