Multi-agent pickup and delivery in dynamic environments

Classical Multi-Agent Pickup and Delivery (MAPD) problems focus on coordinating a team of autonomous agents to efficiently transport items from pickup to delivery locations within a static and fully known environment. Applications of this setting can be found in logistics, automated warehouses, urban delivery systems, and autonomous vehicle coordination. The MAPD framework usually assumes homogeneous agents with identical capabilities and tasks that can be addressed sequentially. While classical MAPD provides a foundation for solving coordination and planning problems, its underlying assumptions limit its applicability to real-world scenarios, which are often dynamic, unpredictable, and constrained by environmental and operational complexities. To contribute to bridging the gap between theory and practice, this thesis explores two novel MAPD variants: MAPD with External Agents (MAPD-EA) and MAPD with Mobile Pickups (MAPD-MP). MAPD-EA introduces the challenge of operating in environments shared with independent external agents, such as humans or robots, whose behavior and goals are unknown to the agents performing MAPD. The key contribution of this thesis in MAPD-EA is the development of behavioral models of external agents, specifically probabilistic occupancy and Markovian approaches, which allow task-performing agents to anticipate and adapt to the movements of the external agents. These models are integrated into the proposed Token Passing with Collision Avoidance and Replanning + Model (TP-CA-M) algorithm, enabling agents to plan proactively and respond to environmental changes in real time. Moreover, the thesis investigates MAPD-EA in human-populated environments, testing TP-CA-M on a real-world human motion dataset. To prevent deadlock situations caused by interactions between team agents and external entities, the thesis proposes a novel deadlock prevention strategy that segments the environment into discrete tiles and imposes constraints on the number of agents allowed per tile. This method effectively avoids deadlocks, ensuring task completion even in crowded and unpredictable settings. The second variant, MAPD-MP, considers a team of heterogeneous agents assigned to complementary roles, divided into suppliers, that transport items, and deliverers, that complete deliveries but have to retrieve items from the suppliers. Deliverers are able to move everywhere in the environment, while suppliers are bound to specific zones. This framework necessitates real-time coordination, adaptive task allocation, and optimized meeting point determination to balance the constraints imposed by agent mobility and environmental structure. A new algorithm, Token Passing with Exchange Locations (TP-EL), addresses these challenges by synchronizing the movement and tasks of suppliers and deliverers, enhancing system efficiency.

I problemi classici di Multi-Agent Pickup and Delivery (MAPD) si concentrano sul coordinamento di un team di agenti autonomi per trasportare in modo efficiente oggetti da punti di prelievo (pickup) a punti di consegna (delivery) in un ambiente statico e completamente noto. Le applicazioni più importanti si trovano in settori come la logistica, i magazzini automatizzati, i sistemi di consegna urbana e la coordinazione dei veicoli autonomi. L'approccio MAPD classico presuppone agenti omogenei con capacità identiche e compiti che possono essere affrontati in modo sequenziale. Sebbene il MAPD classico costituisca una base per risolvere problemi di coordinamento e pianificazione, le sue assunzioni limitano l'applicabilità a scenari reali, spesso dinamici, imprevedibili e caratterizzati da complessità ambientali e operative. Per colmare il divario tra teoria e pratica, questa tesi esplora due varianti innovative del MAPD: MAPD con Agenti Esterni (MAPD-EA) e MAPD con Pickups Mobili (MAPD-MP). MAPD-EA introduce la sfida di operare in ambienti condivisi con agenti esterni indipendenti, come esseri umani o robot, i cui comportamenti e obiettivi non sono noti agli agenti che svolgono problemi MAPD. Il principale contributo di questa tesi nel MAPD-EA è lo sviluppo di modelli comportamentali degli agenti esterni, in particolare approcci basati sull'occupazione probabilistica e modelli markoviani, che permettono agli agenti incaricati dei compiti di anticipare e adattarsi ai movimenti degli agenti esterni. Questi modelli sono integrati in un algoritmo, chiamato Token Passing with Collision Avoidance and Replanning + Model (TP-CA-M), che consente agli agenti di pianificare in modo proattivo e di rispondere in tempo reale ai cambiamenti ambientali. Inoltre, la tesi esplora il MAPD-EA in ambienti popolati da esseri umani, testando TP-CA-M su un dataset reale. Per prevenire situazioni di deadlock causate dalle interazioni tra gli agenti del team e le entità esterne, la tesi propone una strategia innovativa di prevenzione dei deadlock, che piastrella l'ambiente in quadrati di 2 x 2 celle discrete e impone vincoli sul numero di agenti ammessi per piastrella. Questo metodo evita efficacemente i deadlock, garantendo il completamento dei compiti anche in ambienti affollati e imprevedibili. La seconda variante, MAPD-MP, considera un team di agenti eterogenei con ruoli complementari, divisi in fornitori, che trasportano oggetti, e distributori, che completano le consegne ma devono prima ritirare gli oggetti dai fornitori. I distributori possono muoversi liberamente in tutto l'ambiente, mentre i fornitori sono limitati a zone specifiche. Questo contesto richiede coordinamento in tempo reale, assegnazione dei compiti adattiva e l'individuazione ottimizzata dei punti di incontro per bilanciare i vincoli imposti dalla mobilità degli agenti e dalla struttura dell'ambiente. Un nuovo algoritmo, Token Passing with Exchange Locations (TP-EL), affronta queste sfide sincronizzando i movimenti e i compiti di fornitori e distributori, migliorando l'efficienza del sistema.