Análise do desempenho de técnicas de otimização aplicadas ao algortimo A* híbrido para busca de rotas de veículos

Abstract

This undergraduate final work proposes the development of optimization techniques applied to the Hybrid A* pathfinding algorithm, based on the implementation currently present in the military simulation system SIS-ASTROS. An adaptation of that same algorithm was developed using C# language. Then, two different techniques were developed: a polygon approximation hash for optimization of intersection calculation between points and polygons, with O(1) complexity. It was also developed a technique for optimization of Euclidean distance heuristics using Dijkstra’s algorithm over a visibility graph. Both techniques were evaluated in different test scenarios and presented superior performance when compared to other techniques used in the work, with respect to their execution time for pathfinding using the implemented Hybrid A*.