Análise de algoritmos de busca hierárquica com a utilização de redes neurais profundas

Abstract

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.