Robustness in multi-agent pickup and delivery with delays

Multi-Agent Pickup and Delivery (MAPD) is the problem of computing collision-free paths for a group of agents such that they can safely reach delivery locations from pickup ones. These locations are provided at runtime, making MAPD a combination between classical Multi-Agent Path Finding (MAPF) and online task assignment. Current algorithms for MAPD do not consider many of the practical issues encountered in real applications: real agents often do not follow the planned paths perfectly, and may be subject to delays and failures. The objectives of this thesis are to study the problem of MAPD with delays, and to present solution approaches that provide robustness guarantees by planning paths that limit the effects of imperfect execution. In particular, two algorithms are introduced, k-TP and p-TP, both based on a decentralized algorithm typically used to solve MAPD, Token Passing (TP), which offer deterministic and probabilistic guarantees, respectively. Experimentally, these algorithms are compared against a version of TP enriched with recovery routines. k-TP and p-TP, planning robust solutions, are able to significantly reduce the number of replans caused by delays, with little or no increase in solution cost and running time.

Il Multi-Agent Pickup and Delivery (MAPD) è il problema di calcolare percorsi senza collisioni per un gruppo di agenti in modo che possano raggiungere posizioni di consegna da posizioni di raccolta. Queste posizioni vengono determinate a tempo di esecuzione, rendendo il MAPD una combinazione tra il classico Multi-Agent Path Finding (MAPF) e l'assegnazione di compiti in tempo reale. Gli algoritmi attualmente impiegati per risolvere il problema del MAPD non tengono in considerazione molti problemi pratici che si incontrano nelle applicazioni reali: gli agenti spesso non seguono perfettamente i percorsi pianificati, e possono essere soggetti a ritardi e guasti. Gli obiettivi di questa tesi sono studiare il problema MAPD con ritardi, e presentare approcci risolutivi che diano garanzie di robustezza pianificando percorsi in grado di limitare gli effetti dell'esecuzione imperfetta. In particolare, vengono introdotti due algoritmi, k-TP e p-TP, entrambi basati su un algoritmo decentralizzato usato per risolvere il MAPD, detto Token Passing (TP), che offrono rispettivamente garanzie deterministiche e probabilistiche. Sperimentalmente, questi algoritmi sono confrontati con una versione di TP modificata con procedure di recupero. k-TP e p-TP, pianificando soluzioni robuste, sono in grado di ridurre significativamente il numero di ripianificazioni causate da ritardi, con un incremento piccolo o nullo del costo della soluzione e del tempo di esecuzione.