Uso de redes neurais profundas para o aprendizado de funções heurísticas para algoritmos de busca de caminhos

Abstract

Pathfinding is an important area of Artificial Intelligence that has been researched through the use of deep neural networks. More specifically, the research focuses on the development of new path search algorithms guided by heuristic functions, where these functions are implemented by deep neural networks. In essence, heuristic functions are used by various search algorithms to estimate the distance from a current position to an objective position, where the current position (represented as a search space node) that has the best estimate is prioritized in the research process the shortest path between such positions. Traditional heuristic functions such as Euclidean distance and Manhattan distance, for example, optimally guide the search for paths on maps that do not have many obstacles. However, when obstacles are common in the search environment, these heuristic functions begin to lose efficiency as many search space nodes may need to be analyzed. This paper proposes and tests the use of deep neural networks in the learning of heuristic functions that better guide path search algorithms. The objective is to verify if such heuristic functions based on deep neural network results allow to obtain good quality paths in navigation maps represented as regular grids. Developed experiments were performed by performing path searches using traditional heuristic functions, which were compared with functions learned by a deep neural network implemented. The results show that the use of deep neural networks allows to reduce the expansion of the search space nodes maintaining the quality of the paths and, in some situations, reduce the search algorithm execution time.