MAX-MIN ANT SYSTEM NO PLANEJAMENTO DE CAMINHOS ÓTIMOS EM GRAFO VISANDO A NAVEGAÇÃO AUTÔNOMA DE ROBÔS MÓVEIS

XXXVII Encontro de Iniciação Científica

Claudio Cesar Martins Magalhaes Filho, THIAGO AZEVEDO CAMPOS COSTA, Arthur Plinio de Souza Braga

Neste trabalho utiliza-se um grafo para representar o ambiente em que um robô móvel, desenvolvido pelo Grupo de Pesquisa em Automação e Robótica (GPAR) do Departamento de Engenharia Elétrica / CT / UFC, deve navegar de forma autônoma. Na pesquisa, o foco está em implementar algoritmos que planejem trajetórias ótimas para o robô navegar a partir do mapa criado (grafo) com uma Rede Neural Artificial do tipo &quot;Growing Neural Gas&quot; (GNG). Neste planejamento, a trajetória deve desviar de obstáculos e é avaliada por critérios como o tamanho final da trajetória e a distância entre a posição final desejada e a posição final atingida pelo robô. Para isto, foi implementada a meta-heurística de Otimização por Colônia de Formigas (&quot;Ant Colony Optimization&quot; – ACO) que é baseada em uma modelagem do comportamento coletivo de formigas. Essas formigas se movem, obedecendo a distribuições de probabilidade, entre os nós e através das bordas de um grafo. Nestas transições entre os nós, as formigas artificiais atualizam variáveis relacionadas à qualidade das trajetórias geradas (análogas às concentrações de feromônio depositadas por formigas reais na natureza), influenciando no processo decisório da colônia. O algoritmo de formigas utilizado foi o &quot;MAX-MIN Ant System&quot; (MMAS) com adaptações para melhorar o desempenho da tarefa de encontrar caminhos curtos em um grafo, o MMAS insere limites máximos para os valores de feromônio, evitando uma convergência para um caminho abaixo do ideal. Para fins comparativos, foi implementada outra estratégia, conhecida como &quot;Artificial Potential Field&quot; (APF), que é uma técnica de planejamento de caminho muito utilizada por apresentar ótimos resultados. A técnica APF é baseada no comportamento de uma partícula carregada em um campo magnético, e suas ações dependem da combinação dos campos de atração (criados pelos pontos de destino) e de repulsão (criados pelos obstáculos no mapa). A continuação do trabalho é inspirada pelos resultados promissores do ACO.

Palavras-chave: Robótica Móvel. Metaheurística. Colônia de Formigas. Planejamento de Trajetória.

Encontros Universitários da UFC, Fortaleza, v. 3, 2018

1597