Dissertação
Sistemas multiagentes para coleta e entrega combinando algoritmos genéticos e planejamento de caminho
Autor
Queiroz, Ana Carolina Ladeira Costa
Institución
Resumen
Distribution centers are increasingly automated with the use of autonomous mobile
robots. These robots perform the function of moving products, increasing productivity
in warehouses. Several works have been studied in the literature that try to capture
these characteristics and the Multi-Agent Pickup and Delivery (MAPD) problem is an
example of problem from this area. In this problem, tasks appear in the system at dierent
times, and each task has two positions, a pickup and a delivery position. Agents attend
to a stream of incoming tasks, moving to pickup position and then to delivery position.
Commonly, this problem has two parts: (i) task allocation, in which the agent receives a
sequence of tasks to be executed, and (ii) path planning, in which it is necessary to find the
best way for the agent to perform its task without colliding with other agents. The problem
of finding multi-agent paths is also known as Multi-Agent Path Finding (MAPF). In this
work, dierent genetic algorithms were proposed to solve the task allocation part of the
MAPD. An analysis of the objectives of the problems was also presented and this problem
was treated with a multi-objective approach, using the Non-dominated Sorting Genetic
Algorithm (NSGA-II) in order to minimize two objective functions, namely, makespan and
service time. For the MAPF sub-problem, path planning algorithms from the literature
were used: Prioritized Planning (PP) and Conflict Based Search (CBS). Another approach
to Prioritized Planning was also proposed, called PP-E. This approach aims to avoid
future collisions between agents, allowing the agent to move to another free position,
after reaching its objective position. Computational experiments were carried out in two
environments, with dierent sizes, number of agents, number of tasks and rate of entry
of tasks in the system. The results were compared with algorithms from the literature
and showed that the proposed approach achieves better results when compared to other
techniques. Centros de distribuição estão cada dia mais automatizados com a utilização de
robôs móveis autônomos. Estes robôs desempenham a função de movimentar produtos,
aumentando a produtividade nos armazéns. Vários trabalhos vêm sendo estudados na
literatura que buscam capturar essas características e o Multi-Agent Pickup and Delivery
(MAPD) é um exemplo de problema desta área. Neste problema, tarefas aparecem no
sistema em diferentes instantes de tempo, e cada tarefa tem duas posições, uma posição de
coleta e uma de entrega. Os agentes devem atender a esse fluxo de tarefas, se deslocando
para a posição de coleta e depois de entrega da tarefa. Comumente, esse problema tem
duas partes: (i) alocação de tarefas, em que o agente recebe uma sequência de tarefas
a serem executadas, e (ii) planejamento de caminho, no qual é necessário encontrar o
melhor caminho para o agente realizar sua tarefa sem colidir com outros agentes. O
problema de encontrar caminhos para multiagentes também é conhecido como Multi-Agent
Path Finding (MAPF). Neste trabalho, foram propostos diferentes algoritmos genéticos
para resolver a parte de alocação de tarefas do MAPD. Também foi apresentado uma
análise dos objetivos dos problemas e este problema foi tratado com uma abordagem
multiobjetivo, utilizando o Non-dominated Sorting Genetic Algorithm (NSGA-II) a fim de
minimizar duas funções objetivo, makespan e service time. Para o sub-problema MAPF,
foram utilizados algoritmos de planejamento de caminhos já conhecidos na literatura:
o Prioritized Planning (PP) e a Conflict Based Search (CBS). Também foi utilizada
outra abordagem para o Prioritized Planning, denominado PP-E. Esta abordagem, PPE, tem como fim evitar futuras colisões entre agentes, possibilitando que o agente se
desloque para outra posição livre após chegar na sua posição de objetivo. Experimentos
computacionais foram realizados em dois ambientes, com diferentes tamanhos, números
de agentes, quantidade de tarefas e taxa de entrada de tarefas no sistema. Os resultados
foram comparados com algoritmos da literatura e mostraram que a abordagem proposta
alcança melhores resultados quando comparada a outras técnicas. CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior