Luiz Fernando Yuan Gouvea
Resumo
A interceptação de alvos móveis consiste em determinar a rota que o veículo interceptador deve assumir a fim de alcançar um alvo móvel numa posição futura estimada. Grandezas como distância e tempo são dois fatores que desempenham papéis importantes e devem ser minimizados a fim de evitar a reação e fuga do alvo. Em algumas situações, como a interceptação marítima, os atuais algoritmos de interceptação consideram o ambiente livre e desimpedido, sendo, portanto, inúteis em várias situações do mundo real onde o cenário apresenta obstáculos interpostos entre o interceptador e o alvo. Este trabalho apresenta três novos algoritmos para o problema de caminho mais curto inspirados nos modelos de Dijkstra, A* e Otimização por Colônia de Formigas, aplicados na interceptação de alvos móveis em um cenário com obstáculos poligonais bidimensionais. Foi desenvolvida uma ferramenta de avaliação e teste voltada para interceptação marítima de alvos em cenários com obstáculos geográficos. Os resultados obtidos demonstram que os algoritmos são capazes de resolver o problema proposto com destaque para os modelos baseados no A* e na Otimização por Colônia de Formigas, que se mostraram bastante competitivos.
Abstract
The purpose of interception of moving targets is to determine the route that the interceptor vehicle must take in order to reach a moving target in a estimated future position. Quantities such as distance and time are two factors that play important roles and should be minimized to prevent the reaction and escape of the target. In some situations, like maritime interception, interception algorithms consider the environment without obstacles, which are useless in many situations where the real-world scenario presents obstacles interposed between the interceptor and the target. This work presents three algorithms for the shortest path problem inspired by Dijkstra, A* and Ant Colony Optimization models, applied to the interception of moving targets in two-dimensional polygonal obstacles environment. An evaluation and test tool was developed focused on maritime interception of targets in scenarios with geographical obstacles. The results show that the algorithms are able to solve the proposed problem with emphasis on models based on A* and by Ant Colony Optimization, which have proved to be very competitive.
