Learning Markov models to predict the behavior of a team of agents

Multi Agent Pickup and Delivery (MAPD) is the life-long version of Multi Agent Path Finding (MAPF) in which agents execute an incoming stream of tasks that require them to reach a pickup location, where the task is started, and then move to a delivery location, completing the task. An extension to this problem, called MAPD for a guest team (MAPD-g), sees the presence of two teams of agents in the same shared environment, each one executing its own MAPD instance. The two teams have different priorities; the highest-priority one is called home team, and the presence of a lower-priority team, called guest team, should not impact on its operations. Moreover, no communication is expected between the teams. For this reason, an effective approach for solving MAPD-g requires the guest team to reason on the future position of home agents. The work of this thesis adds to the literature on the field, by introducing Markovian models for the prediction of the future position of home agents. These models are learned from past observations of the movements of the home team, collected via an initial time period of full observation on the environment, or from encounters with home agents that enter the field of view of a guest agent. The results show the ability of these models to be employed in the path planning process for reducing the number of episodes of potential collision, and constitute an improvement upon existing algorithms for the problem. The overall performance highlights a trade-off with the reduction in the expected number of conflicts, requiring additional work in this direction.

Multi Agent Pickup and Delivery (MAPD) è la versione continuativa nel tempo del problema di Multi Agent Path Finding (MAPF), in cui degli agenti eseguono un flusso di compiti in arrivo i quali richiedono loro di raggiungere un punto di prelievo, dove il loro compito ha inizio, e successivamente di raggiungere il punto di consegna, completando il compito. Un’estensione di questo problema, chiamata Multi Agent Pickup and Delivery for a guest team (MAPD-g), prevede la presenza di due squadre di agenti nel medesimo ambiente condiviso, ognuna delle quali esegue una propria istanza di MAPD. Le due squadre hanno una diversa priorità: il gruppo a più alta priorità è chiamato squadra di casa, e la presenza di un secondo gruppo a più bassa priorità, detto squadra ospite, non deve impattare sulle operazioni dei primi. Inoltre, non è prevista nessuna comunicazione tra le due squadre. Per questo motivo, un approccio efficace alla soluzione di un problema MAPD-g richiede che la squadra ospite ragioni sulla possibile posizione futura degli agenti della squadra di casa. Il lavoro di questa tesi va ad aggiungersi alla letteratura presente in questo ambito, introducendo modelli Markoviani per effettuare predizioni sulla posizione degli agenti della squadra di casa. I parametri di questi modelli sono stimati a partire da passate osservazioni sul il movimento degli agenti, acquisite tramite un periodo iniziale di osservazione completa sull’ambiente, oppure da incontri con agenti della squadra di casa che entrano nel campo visivo di un agente ospite. I risultati mostrano l’efficacia di questi modelli nel ridurre il numero di episodi di potenziale conflitto quando sono impiegati nel processo di pianificazione dei percorsi degli agenti ospiti, inoltre costituiscono un miglioramento rispetto ad algoritmi preesistenti che risolvono il medesimo problema. Le prestazioni complessive, in termini di rapidità nel completare ciascun compito, sono legate a un compromesso con la riduzione del valore atteso sul numero di conflitti, pertanto si prevede la necessità di lavoro aggiuntivo su questo fronte.