Algoritmos de busca de caminhos voltados para informações de altura e inclinação representadas em mapas de navegação

Abstract

Artificial Intelligence is an area of research in evidence nowadays, which covers several fields of study. Among its ramifications, it is understood the area that seeks to solve path finding problems. This work addresses the problem of searching for paths in navigation maps, prioritizing the computation of paths when height and slope information in the terrain are considered. When it comes to mountainous environments, agent performance can be compromised as uneven in their movement. In simulation systems, the system context to which the work algorithm is directed, it is sought to simulate events as closely as possible to reality, so a failure could compromise the execution of the system. Thus, the treatment of possible risks during the movement, provided by the unevenness of the terrain, is paramount for the good functioning and integrity of the system. After the implementation of the proposed algorithm, the experiments to test its efficiency were conducted in two virtual terrains (with real terrains), with different relief characteristics. Furthermore, the algorithm was compared to three other algorithms with similar characteristics to perform its evaluation. As input, this paper provides as contributions the development of an algorithm that plan routes using a technique called "line of sight" while it treats height, an approach not found in the literature. Thus, the algorithm provides smoothed paths that avoid mountainous regions, whose inclinations may provide risks to the movement of the agents involved in the simulation. Also, the algorithm uses hierarchical search technique, using preprocessing of paths between important nodes in the hierarchy composition of the virtual terrain representation structure, which results in an optimization of execution time.