Sistemas multiagentes para coleta e entrega combinando algoritmos genéticos e planejamento de caminho

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.