Por favor, use este identificador para citar o enlazar este ítem: https://repositorio.ufjf.br/jspui/handle/ufjf/14167
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
anacarolinaladeiracostaqueiroz.pdfPDF/A2.21 MBAdobe PDFVista previa
Visualizar/Abrir
Clase: Dissertação
Título : Sistemas multiagentes para coleta e entrega combinando algoritmos genéticos e planejamento de caminho
Autor(es): Queiroz, Ana Carolina Ladeira Costa
Orientador: Bernardino, Heder Soares
Co-orientador: Vieira, Alex Borges
Miembros Examinadores: Gonçalves, Luciana Brugiolo
Miembros Examinadores: Silva, Eduardo Krempser da
Resumo: 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.
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.
Palabras clave : Sistemas multiagentes
Alocação de tarefas
Planejamento de caminho
Algoritmo genético
Otimização multiobjetivo
Multiagent systems
Task allocation
Path planning
Genetic algorithm
Multi-objective optimization
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma: por
País: Brasil
Editorial : Universidade Federal de Juiz de Fora (UFJF)
Sigla de la Instituición: UFJF
Departamento: ICE – Instituto de Ciências Exatas
Programa: Programa de Pós-graduação em Ciência da Computação
Clase de Acesso: Acesso Aberto
Attribution-NonCommercial-NoDerivs 3.0 Brazil
Licenças Creative Commons: http://creativecommons.org/licenses/by-nc-nd/3.0/br/
DOI: https://doi.org/10.34019/ufjf/di/2022/00078
URI : https://repositorio.ufjf.br/jspui/handle/ufjf/14167
Fecha de publicación : 4-mar-2022
Aparece en las colecciones: Mestrado em Ciência da Computação (Dissertações)



Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons