Multi-agent pickup and delivery with task probability distribution

Multi-Agent Pickup and Delivery (MAPD) is a problem in the field of multi-robot systems that consists in completing a set of tasks by making an agent move to the pickup location and then to the delivery location of each task. Since in MAPD new tasks are dynamically added to the system throughout its lifetime, existing algorithms assume complete ignorance about the position and the time at which future tasks will appear until they are actually added to the system. The objectives of this thesis are to define a variant of the MAPD problem in which a spatial and temporal probability distribution of future tasks is known and to define algorithms that take advantage of this task probability distribution to reduce the average time required to execute tasks. We define some modifications to an existing MAPD algorithm, Token Passing (TP). These modifications are both adopted in isolation and then combined in different variants of the algorithms. Experiments are run to compare new algorithms to TP and they show that the use of the task probability distribution can have a significant positive impact on the average time required to complete tasks. However, the algorithms that provide the best average completion times can require a significantly high cost in terms of number of actions performed by agents and of runtime cost of the algorithm, while some other algorithms provide a more balanced trade-off among different evaluation metrics.

Multi-Agent Pickup and Delivery (MAPD) è un problema nel campo dei sistemi multi-robot che consiste nel completare un gruppo di task facendo spostare un agente fino alla posizione di partenza del task e poi fino alla sua destinazione. Dal momento che nel problema MAPD nuovi task possono essere aggiunti al sistema in qualsiasi momento, gli algoritmi sviluppati fino a oggi ipotizzano che qualsiasi informazione in merito alla posizione e al momento in cui i futuri task appariranno non sia disponibile finché i task non sono realmente aggiunti al sistema. L'obiettivo di questa tesi è quello di definire una variante del problema MAPD in cui è nota una distribuzione di probabilità spaziale e temporale dei task e di sviluppare degli algoritmi che sfruttino tale distribuzione di probabilità per ridurre il tempo mediamente richiesto per eseguire i task. Un algoritmo MAPD, Token Passing (TP), è utilizzato come punto di partenza per la definizione degli algoritmi e su di esso sono apportate diverse modifiche. Queste modifiche sono adottate singolarmente e quindi combinate in diverse varianti dell'algoritmo. Per confrontare i nuovi algoritmi con TP, vengono condotti degli esperimenti che mostrano un notevole impatto positivo degli algoritmi proposti sul tempo medio di completamento dei task. Tuttavia, gli algoritmi che garantiscono i migliori risultati per il tempo di completamento dei task sono significativamente più costosi in termini di numero di azioni eseguite dagli agenti e di tempo di esecuzione, mentre altri algoritmi garantiscono un compromesso più bilanciato fra le diverse metriche considerate.