EXECUTION-DRIVEN DYNAMIC MULTI-ROBOT TASK ALLOCATION MODEL EASILY APPLICABLE TO REAL CASES

Abstract

Many modern warehouses and factories use autonomous mobile robots for their internal logistics operations. Due to the workload of these facilities, it is impractical to manually assign transport tasks to fleet robots. Frequent changes in planned orders and unexpected events during their execution, such as robot malfunctions or traffic jams, increase the complexity of the task assignment problem. Taking all this into account, exhaustive searches for solutions must be limited in computing time and their results become suboptimal. Practical solutions use less computationally intensive allocation mechanisms that may not provide optimal results but are well suited to dynamic environments such as those described. One of these mechanisms consists in auctioning the tasks between the robots so that those who make the best offer end up doing the assigned transport. This work proposes a model of a multi-agent system to make allocations through auctions that improves the quality of the solutions of a system with simple auctions while incorporating repetition mechanisms. Unlike other task assignment applications, which use estimates to determine robot availability, the one we developed uses a physical simulator, allowing the effect of traffic or other factors to be considered. To make this possible, in addition to the models of the deliberative part of the agents of the system, the models of the reactive part of the robots have also been created. These models are formally described with a specific type of state machine that, in addition to guaranteeing predictability and facilitating the verification and implementation of the system, makes it possible to express the deliberative behavior of the agents. The proposed system includes a synchronization mechanism with the physical part so that it makes the assignments and controls the robots while evolving the set of machines until it requires time to pass, such as to let the robots move. The experiments that have been done show reductions in the time and distance traveled by the robots when the auction parameters are adjusted, and repetitions are used. The results obtained suggest that the allocations are close to the optimal ones. Since the task assignment system that has been developed controls the simulated robots during the execution of tasks, the integration with a plant with real robots would be straightforward.

Date of Award	8 Feb 2023
Original language	English
Supervisor	Lluis Ribas Xirgo (Director)