Constraint based coordination algorithm for a fleet of AGVs

Thumbnail Image

Files

master_Amici_Alessandro_2021.pdf (3.58 MB)

URL

Journal Title

Journal ISSN

Volume Title

Sähkötekniikan korkeakoulu | Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2021-01-25

Department

Major/Subject

Autonomous Systems

Mcode

ELEC0007

Degree programme

Master's Programme in ICT Innovation

Language

en

Pages

77

Series

Abstract

With the advent of advanced autonomous cars driving on public roads, the logistic industry is looking forward to deploying new, high-tech fleets of Automated Guided Vehicles. In addition to autonomous driving related problems, the logistic sector needs to consider fleet management issues, including the coordination of the fleet movements in order to prevent the agents to interfere with each other. The work on which this thesis is based is part of a project that aims to design and develop a robotic platform, an integrated fleet management, and a logistic system to handle the transportation of resources among warehouses of an industrial site. The role of this thesis in the project was to design a fleet coordination software component that has to manage the safe navigation of the fleet, ensuring the absence of collisions between agents and infinite waiting times, i.e., deadlocks, while they drive their assigned trajectories. This thesis proposes the design of a constraint based fleet coordination algorithm which can handle tens of robots in a real scenario of an outdoor environment. This algorithm generates a suboptimal navigation plan that is able to satisfy all the demands of the industry and it is, nevertheless, much faster to compute with respect to performing optimal navigation planning, which does not scale to manage a realistic number of agents. Besides, a centralized solution offers more control and predictability which are of great value for the logistic industry. The proposed method leverages spatial and temporal constraints to represent the fleet coordination problem in the form of Simple Temporal Problem (STP). A scheduling algorithm searches for possible conflicts in space and time and modifies the constraints of the problem accordingly. Then, an STP solver evaluates the consistency of the input constraints and forms the most efficient and safe navigation plan that respects those constraints. Experiments evaluate the performance of the proposed coordination algorithm and the results show that this method can handle, under fair assumptions, tens of AGVs without imposing strict limitations on the working environment and the type of robot platform.

Description

Supervisor

Kyrki, Ville

Thesis advisor

Peralta, José Luis

Keywords

AGV, fleet coordination algorithm, constraint satisfaction problem, constraint based representation, simple temporal problem

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202101311782

Collections

[dipl] Sähkötekniikan korkeakoulu / ELEC