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

Resumo

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 "Growing Neural Gas" (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 ("Ant Colony Optimization" – 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 "MAX-MIN Ant System" (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 "Artificial Potential Field" (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.