Uma abordagem evolucionária para o planejamento online de rotas para múltiplos robôs móveis em ambiente multiagente

Abstract

O problema de planejamento de rotas de robôs móveis consiste em determinar a melhor rota para um robô, em um ambiente estático e/ou dinâmico, que seja capaz de deslocá-lo de um ponto inicial até e um ponto final, também em conhecido como estado objetivo. O presente trabalho emprega o uso de uma abordagem baseada em Algoritmos Genéticos para o planejamento de rotas de múltiplos robôs em um ambiente complexo composto por obstáculos fixos e obstáculos moveis. Através da implementação do modelo no software do NetLogo, uma ferramenta utilizada em simulações de aplicações multiagentes, possibilitou-se a modelagem de robôs e obstáculos presentes no ambiente como agentes interativos, viabilizando assim o desenvolvimento de processos de detecção e desvio de obstáculos. A abordagem empregada busca pela melhor rota para robôs e apresenta um modelo composto pelos operadores básicos de reprodução e mutação, acrescido de um novo operador duplo de refinamento capaz de aperfeiçoar as melhores soluções encontradas através da eliminação de movimentos inúteis. Além disso, o calculo da rota de cada robô adota um método de geração de subtrechos, ou seja, não calcula apenas uma unica rota que conecta os pontos inicial e final do cenário, mas sim várias pequenas subrotas que conectadas formam um caminho único capaz de levar o robô ao estado objetivo. Neste trabalho foram desenvolvidos dois cenários, para avaliação da sua escalabilidade: o primeiro consiste em um cenário simples composto apenas por um robô, um obstáculo movel e alguns obstáculos fixos; já o segundo, apresenta um cenário mais robusto, mais amplo, composto por múltiplos robôs e diversos obstáculos fixos e moveis. Ao final, testes de desempenho comparativos foram efetuados entre a abordagem baseada em Algoritmos Genéticos e o Algoritmo A*. Como critério de comparação foi utilizado o tamanho das rotas obtidas nas vinte simulações executadas em cada abordagem. A analise dos resultados foi especificada através do Teste t de Student.

The problem of path planning of mobile robots is to determine the best path for a robot in a static and/or dynamic environment , that is capable of moving a robot from a start point to a final point, also know as goal state. This study employs the use of an approach based on Genetic Algorithms for path planning of multiple robots in an complex environment composed by fixed and mobile obstacles. Through the implementation of the model in NetLogo software, a tool used in simulations of multi-agent applications, robots and obstacles in the environment could be modeled as interactive agents, thus enabling the development of process of detection and obstacle avoidance. The approach was employed in search of the best path to robots and presents a model composed by basic operators of reproduction and mutation, plus a new dual refinement operator that can improve the best solutions found by eliminating unnecessary movements. In addition, the path calculation of each robot adopts a method of generating mini-paths, i.e., does not calculate only one route that connects the starting and ending points of the scenario, but several small mini-paths that connected form a only path able to take the robot to the goal state. In this work were developed two scenarios for evaluation of its scalability: the first consists of a simple scenario composed by only one robot, one mobile obstacle and some fixed obstacles, whereas the second presents a scenario more robust, broader, composed by multiple robots and various fixed and mobile obstacles. Finally, comparative performance tests were carried out between the Genetic Algorithm approach and the A* Algorithm. As comparison criteria was used the size of the obtained paths in the twenty simulations performed on each approach. The analysis of the results was specified through the Student’s t test.