Riassunto analitico
La risoluzione del problema di coordinamento di un sistema multi-robot composto da carrelli industriali a guida automatica (AGV) rappresenta, ad oggi, una sfida di fondamentale importanza per l’automazione dei moderni magazzini e nell’ottimizzazione della logistica dei trasporti. I sistemi di movimentazione tramite AGV attualmente presenti a livello industriale prevedono l’utilizzo di un controllore centralizzato, che si occupa sia della suddivisione dei task tra i carrelli, che del loro coordinamento. I così detti metodi “Accoppiati” prevedono la risoluzione simultanea dei due problemi precedentemente accennati al fine di ottenere percorsi ottimi e privi di conflitti. Il tempo risoluzione di questo problema cresce, tuttavia, in modo esponenziale con il numero di carrelli presenti nel sistema, rendendolo poco scalabile e poco flessibile. I metodi “Disaccoppiati” prevedono invece la suddivisione del path-planning dal motion co-ordination, introducendo tuttavia un rischio rilevante di indurre il sistema in condizione così dette di “Deadlock”, le quali causano il blocco di gruppi di AGV e il successivo fallimento del sistema complessivo. L’obiettivo della tesi di Laurea qui esposta riguarda lo sviluppo e l’implementazione di un algoritmo di controllo centralizzato e disaccoppiato che sia in grado di prevedere il verificarsi delle condizioni di DeadLock, al fine di generare percorsi DeadLock -free. A tale fine viene proposto un metodo basato su un approccio a più livelli. Nel livello superiore viene risolto il problema di assegnazione delle precedenze tra i veicoli utilizzando il concetto di Time-Window, il livello centrale si occupa dell’identificazione temporale di eventuali condizioni di DeadLock sfruttando un Time-Expanded Graph ed il livello inferiore ha il compito di risolvere preventivamente tali situazioni al fine di evitare arresti del sistema. Nella prima parte dell’elaborato vengono descritte le componenti standard di un sistema multi-AGV e i metodi che vengono comunemente utilizzati per rappresentarlo. Vengono poi analizzate in modo approfondito le strategie di controllo di tali sistemi presenti in letteratura, mettendo in evidenza le criticità che subentrano nella loro applicazione ai sistemi reali. Nella fase successiva viene poi introdotto e descritto l’algoritmo di controllo elaborato, il quale è stato implementato e simulato interamente utilizzando il linguaggio di programmazione Python 3. Nell’ultima fase vengono esposti i risultati raggiunti confrontando le performance del sistema in precedenza e a seguito dell’introduzione dell’algoritmo elaborato.
|
Abstract
Controlling a multi-Robot system, composed of industrial automatic guided vehicles (AGV), represents a critical problem for the automation of modern warehouses and the optimization of the logistics.
Currently, the vast majority of AGV systems adopted in the industrial field are supervised by a centralized controller, which solves the problem of task allocation and coordination of the AGVs.
The so called "Coupled" methods enable simultaneous resolution of the two previously mentioned problems, in order to obtain optimal and conflict-free paths. The time required to compute the solution of the Coupled coordination problem, anyways, grows exponentially with the number of AGV in the system, making it less scalable and less flexible.
"Decoupled" methods try to solve path planning and motion coordination separately, introducing however a risk related to the so called DeadLock situations.
The objective of the thesis concerns the ideation, the developement and the implementation of a centralized decoupled control algorithm thet is able to forecast DeadLock situations in multi-AGV systems.
In order to do that, a multi-layered approach is proposed. In the upper layer the coordination problem is solved using a Time Windows based approach.The middle layer is used to identify any possible DeadLock Condition in a temporal way using a Time-Expanded Graph. The lower has the objective to prevent the occurence of those situations, thus avoiding system failures.
The first part of the thesis consists in the description of both the standard components of a multi-AGV system and the methods which are commonly used to represent it.
In the second part there is a state of the art analysis of common control strategies, followed by an identification of the problems that may arise when those methods are applied in the real environment.
In the third part, the new control method is introduced, described, implemented and simulated using Python 3 programming lenguage.
In the last part, the results of the simulations are discussed and the performance of the system is evaluated before and after the introduction of the proposed algorithm.
|