Motion planning for multiple autonomous vehicles on a graph

Abstract

I veicoli a guida automatizzata (AGV) vengono utilizzati per spostare le merci tra diverse posizioni in un magazzino. Il coordinamento di una flotta di AGV è un problema molto complesso, che viene generalmente gestito da un software chiamato Traffic Manager nel modo seguente. Il Traffic Manager invia a ciascun AGV un task che prevede l'assegnazione di una posizione target nel magazzino, che deve essere raggiunta per effettuare un'operazione di ritiro o consegna. Quando un AGV riceve un task, sceglie il percorso per raggiungere l'obiettivo, senza tenere conto dei percorsi degli altri AGV. Tuttavia, questa procedura può portare ad una situazione di "deadlock", cioè ad uno scenario in cui un gruppo di veicoli si blocca reciprocamente lungo il percorso loro assegnato, in modo che non possano raggiungere le rispettive posizioni target.

L'obiettivo di questa tesi è studiare un algoritmo che pianifichi i percorsi di tutti gli AGV, al fine di prevenire ed evitare situazioni di "deadlock". Poiché gli AGV seguono percorsi predefiniti che collegano le posizioni in cui gli articoli vengono immagazzinati o elaborati, associamo il layout dell'insieme di percorsi virtuali a un grafo diretto. In particolare si tratta di digrafi fortemente connessi, cioè grafi orientati in cui è possibile raggiungere qualsiasi nodo partendo da qualsiasi altro nodo.

Il problema principale che deve essere risolto dal pianificatore di percorsi è il problema Multi-Agent Path Finding (MAPF) su grafi, che consiste nel calcolare una sequenza di movimenti che riposiziona tutti gli agenti sui nodi target assegnati, evitando collisioni. Poiché il nostro interesse primario è evitare situazioni di "deadlock", ci concentriamo sull'importante compito di trovare una soluzione ammissibile per il MAPF, anche in configurazioni molto affollate. Una volta trovata una soluzione ammissibile, studiamo anche come migliorarla, avvicinandola il più possibile a quella ottimale. Per soluzione ottimale intendiamo la sequenza di movimenti di ciascun agente che consente di raggiungere tutti gli obiettivi nel più breve tempo possibile. Inoltre, studiamo il problema di trovare tali percorsi per gli AGV tenendo conto di alcuni vincoli spaziali, ad esempio dovuti alle dimensioni dei veicoli (questo problema è chiamato C-MAPF), e il problema di trovare il percorso più veloce, considerando la velocità e vincoli di accelerazione, per un singolo agente (chiamato Bounded Acceleration Shortest Path problem).

Automated-Guided Vehicles (AGVs) are used to move items between different locations in a warehouse. The coordination of a fleet of AGVs is a very complex problem, which is generally handled by a software called Traffic Manager in the following way. The Traffic Manager send to each AGVs a task that involves the assignment of a target position in the warehouse, which must be reached to carry out a pick up or delivery operation. When an AGV receives a task, it chooses the path to reach the target, without taking into account the routes of others AGVs. However, this procedure can lead to a "deadlock" situation, i.e., a scenario in which a group of vehicles are mutually blocked along the route assigned to them, so that they are unable to reach their target position.

The objective of this thesis is to study an algorithm that plan the routes of all AGVs, with the aim of preventing and avoiding "deadlock" situations. Since AGVs follow predefined paths that connect the locations in which items are stored or processed, then we associate the layout of the set of virtual paths to a directed graph. In particular, we deal with strongly connected digraphs, directed graphs in which it is possible to reach any node starting from any other node.

The main problem that must be solved by the path planner is the Multi-Agent Path Finding (MAPF) problem on graphs, which consists in computing a sequence of movements that repositions all agents to assigned target nodes, avoiding collisions. Since we are primarily interested in avoiding deadlock situations, we focus on the important task of finding a feasible solution to MAPF, even in crowded configurations. Once we find a feasible solution, we also study how to improve it, bringing it as close as possible to the optimal one. By optimal solution we mean the sequence of movements for each agent, which allows all targets to be reached in the shortest possible time. Moreover, we study the problem of finding such routes for AGVs taking into account spacial constraints, for instance due to the size of the vehicles (this problem is called C-MAPF), and the problem of finding the fastest path, considering velocity and acceleration constraints, for a single agent (called Bounded Acceleration Shortest Path problem).