Multi-agent path finding in configurable environments

Multi-Agent Path Finding (MAPF) plays an important role in many real-life applications where autonomous agents must coordinate to reach their goals without collisions. MAPF problems often take place in structured environments that are usually assumed to be static and known in advance. In this thesis, we introduce C-MAPF, i.e., MAPF in configurable environments, a novel variant of the MAPF problem in which the environment is configurable, namely its structure and topology can be controlled within some given constraints. Consider, for instance, a warehouse logistics application: the environment can be changed (at least to some degree) by the managers of the warehouse, for example by re-arranging the positions of the shelves or by removing or adding temporary walls. We study the properties of the C-MAPF problem and we devise two algorithms for solving it, both based on Conflict-Based Search (CBS), a state-of-the-art MAPF algorithm. First, we present Parallel CBS (P-CBS), that searches for a solution by simultaneously considering all the possible configurations of the environment. We then present Abstract CBS (A-CBS), an extended version of the CBS algorithm that solves C-MAPF problems by introducing a new type of conflict on the allowable configurations of the environment. We prove that our solvers are both complete and optimal and we experimentally assess their performance in different settings.

Multi-Agent Path Finding (MAPF) svolge un ruolo importante in molte applicazioni del mondo reale in cui agenti autonomi devono coordinarsi per raggiungere i propri obiettivi senza collisioni. I problemi MAPF hanno spesso luogo in ambienti strutturati solitamente considerati statici e noti in anticipo. In questa tesi, introduciamo C-MAPF, ovvero MAPF in ambienti configurabili, una nuova variante del problema MAPF in cui l'ambiente è configurabile, vale a dire la sua struttura e la sua topologia possono essere controllate sotto determinati vincoli. Si consideri, ad esempio, un'applicazione riguardante la logistica di magazzino: l'ambiente può essere modificato (almeno in una certa misura) dai gestori del magazzino, ad esempio riorganizzando le posizioni degli scaffali o rimuovendo o aggiungendo muri temporanei. Analizziamo quindi le proprietà del problema C-MAPF e introduciamo due algoritmi per risolverlo, entrambi basati su Conflict-Based Search (CBS), un noto algoritmo per MAPF. Presentiamo Parallel CBS (P-CBS), che cerca una soluzione considerando contemporaneamente tutte le possibili configurazioni dell'ambiente. Presentiamo poi Abstract CBS (A-CBS), una versione estesa dell'algoritmo CBS che risolve i problemi C-MAPF introducendo un nuovo tipo di conflitto sulle configurazioni consentite dell'ambiente. Dimostriamo che i nostri algoritmi sono completi e ottimi e valutiamo sperimentalmente le loro prestazioni in diversi contesti.