Sistemas multiagentes para coleta e entrega combinando algoritmos genéticos e planejamento de caminho
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Universidade Federal de Juiz de Fora (UFJF)
Abstract
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.
Description
Citation
Endorsement
Review
Supplemented By
Referenced By
Creative Commons license
Except where otherwise noted, this item's license is described as Acesso Aberto

