dc.contributor.advisor | Pozzer, Cesar Tadeu | |
dc.creator | Santos, Adrian Kaminski dos | |
dc.date.accessioned | 2021-02-10T18:13:32Z | |
dc.date.available | 2021-02-10T18:13:32Z | |
dc.date.issued | 2019-12-11 | |
dc.date.submitted | 2019 | |
dc.identifier.uri | http://repositorio.ufsm.br/handle/1/20311 | |
dc.description | Trabalho de conclusão de curso (graduação) - Universidade Federal de Santa
Maria, Centro de Tecnologia, Bacharelado em Ciência da Computação, RS, 2019. | por |
dc.description.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*. | eng |
dc.language | por | por |
dc.publisher | Universidade Federal de Santa Maria | por |
dc.rights | Acesso Aberto | por |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 International | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | A* Híbrido | por |
dc.subject | Otimização | por |
dc.subject | SIS-ASTROS | por |
dc.subject | Hash | por |
dc.subject | Polígono | por |
dc.title | Análise do desempenho de técnicas de otimização aplicadas ao algortimo A* híbrido para busca de rotas de veículos | por |
dc.type | Trabalho de Conclusão de Curso de Graduação | por |
dc.degree.local | Santa Maria, RS, Brasil. | por |
dc.degree.graduation | Bacharelado em Ciência da Computação | por |
dc.description.resumo | Este trabalho de graduação propõe o desenvolvimento de técnicas de otimização,
aplicadas ao algoritmo A* Híbrido para busca de caminhos para veículos, baseado na
implementação utilizada na navegação local de viaturas no sistema de simulação
SIS-ASTROS. Durante o trabalho foi implementado, utilizando a linguagem C#, uma
adaptação do algoritmo. Foram desenvolvidas duas técnicas: para otimização de cálculos de
intersecção com polígonos (obstáculos para os veículos) foi implementada uma hash de
aproximação de polígono, com tempo de avaliação de complexidade O(1), e para otimização
da heurística do algoritmo foi utilizada o algoritmo de Dijkstra sobre um grafo de visibilidade.
Ambas técnicas foram avaliadas em diferentes cenários de teste, e apresentaram desempenho
superior aos algoritmos utilizados como comparação neste trabalho no que tange o tempo de
execução de uma busca de caminhos. | por |
dc.publisher.country | Brasil | por |
dc.publisher.initials | UFSM | por |
dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | por |
dc.publisher.unidade | Centro de Tecnologia | por |