Planning paths for multi-agent pickup and delivery with velocity control

The Multi-Agent Pickup and Delivery (MAPD) problem is the life-long version of Multi-Agent Path Finding (MAPF), where each agent performs path planning to reach pickup and delivery locations without colliding with others. In MAPD numerous aspects must be taken into account in order to provide a consistent solution: the agents characteristics, trajectories, task assignment, the physical environment, and so on. This thesis focuses on an aspect that has not been fully explored in MAPD problems: the impact and influence of velocities. Specifically, since classical MAPD assumes that agents move at constant speed, we investigate how the choice and change of each agent’s velocity during the planning process can affect the performance. To achieve this, a modified version of Safe Interval Path Planning (SIPP) for MAPF problems, is integrated into a broader approach for task assignment and agents coordination, called Token Passing (TP). This integration extends the applicability to the MAPD problem, enabling the control of the agent’s velocity during path planning, while also assessing a proper management of the assigned tasks. In addition to providing an overall good performance, results show the benefits of exploiting this novel approach in relatively crowded environments.

Il problema di Multi-Agent Pickup and Delivery (MAPD) è la versione “life-long” di Multi-Agent Path Finding (MAPF), in cui ogni agente pianifica il proprio cammino per raggiungere una posizione di “pickup” e di “delivery” evitando collisioni con gli altri. In MAPD è necessario considerare numerosi aspetti per fornire una soluzione consistente: le caratteristiche degli agenti, le traiettorie, l’assegnazione dei task, l’ambiente fisico e così via. Questa tesi si concentra su un aspetto che non è stato ancora pienamente esplorato nei problemi MAPD: l’impatto e l’influenza delle velocità. In particolare, poiché MAPD classico presume che gli agenti viaggino a velocità costante, la tesi analizza come la scelta e il cambio di tali velocità per ciascun agente durante il processo di pianificazione del cammino possa influenzare le prestazioni. A tal fine, una versione modificata di Safe Interval Path Planning (SIPP) per problemi MAPF, viene integrata in un approccio più ampio per l’assegnazione dei task e il coordinamento degli agenti, denominato Token Passing (TP). Tale integrazione consente il controllo delle velocità degli agenti durante la pianificazione del percorso in MAPD e, al contempo, gestisce i task da assegnare. Oltre a garantire complessivamente buone prestazioni, i risultati mostrano i benefici derivanti dall’uso di questo nuovo approccio in ambienti relativamente affollati.