Motion planning for multiple autonomous vehicles on a graph

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).