A neural network model for modeling external agents in multi-agents pickup and delivery

Multi-agent Pickup and Delivery (MAPD) problem involves a team of agents that has to complete tasks by planning collision-free paths from their current locations to pickup points and then to delivery points. MAPD problems have a dynamic nature, since new tasks can be added at any time, and agents have to assign and complete them in an online manner. Multi-Agent Pickup and Delivery for a guest team (MAPD-g) is an extension of MAPD, in which two teams of agents, namely guest team and home team, have to solve MAPD tasks in a shared environment. In MAPD-g, guest agents must compute collision-free paths to safely complete MAPD tasks assigned at runtime without interfering or communicating with the home team. The assumption of non-communicative teams brings the necessity for the guest team to compute a model of the home agents to try to avoid conflict in the path planning phase. The objective of this thesis is to propose a new approach to model home agents. Existing solutions utilize data from the past positions of the home team to construct a static model of its behavior, which is then employed in guests' planning phase. In our approach, assuming to know home agents' positions in real time, we devise a method that recursively updates such a behavioral model, providing guest agents with recent information regarding the home team during the planning phase. The model is updated using predictions of the potential future positions of the home team, generated at each time step using a Convolutional Neural Network (CNN) trained to predict the future positions of the home team agents. This approach is particularly well-suited for scenarios in which the behavior of the home team is not consistent over time, making the usage of a static model inadequate. Experimental results conducted in various scenarios demonstrate that our approach is a competitive alternative to existing ones.

Il problema di Multi-agent Pickup and Delivery (MAPD) coinvolge un team di agenti che deve completare compiti pianificando percorsi privi di collisioni dai loro attuali punti di posizione ai punti di ritiro e poi ai punti di consegna. I problemi MAPD hanno una natura dinamica, poiché nuovi compiti possono essere aggiunti in qualsiasi momento e gli agenti devono assegnarli e completarli in modo online. Multi-Agent Pickup and Delivery for a guest team (MAPD-g) è un'estensione di MAPD, in cui due team di agenti, ossia il team ospite e il team di casa, devono risolvere compiti MAPD in un ambiente condiviso. In MAPD-g, gli agenti ospiti devono calcolare percorsi privi di collisioni per completare in modo sicuro i compiti MAPD assegnati durante l'esecuzione senza interferire o comunicare con il team di casa. L'assunzione di team non comunicanti porta alla necessità per il team ospite di calcolare un modello degli agenti di casa per cercare di evitare conflitti nella fase di pianificazione del percorso. L'obiettivo di questa tesi è proporre un nuovo approccio per modellare gli agenti di casa. Le soluzioni esistenti utilizzano dati dalle posizioni passate del team di casa per costruire un modello statico del suo comportamento, che viene quindi utilizzato nella fase di pianificazione degli ospiti. Nel nostro approccio, assumendo di conoscere le posizioni degli agenti di casa in tempo reale, progettiamo un metodo che aggiorna ricorsivamente tale modello comportamentale, fornendo agli agenti ospiti informazioni recenti riguardanti il team di casa durante la fase di pianificazione. Il modello viene aggiornato utilizzando previsioni delle potenziali posizioni future del team di casa, generate ad ogni passo temporale utilizzando una Rete Neurale Convoluzionale (Convolutional Neural Network) addestrata a prevedere le posizioni future degli agenti del team di casa. Questo approccio è particolarmente adatto per scenari in cui il comportamento del team di casa non è coerente nel tempo, rendendo inadeguato l'uso di un modello statico. I risultati sperimentali condotti in vari scenari dimostrano che il nostro approccio è un'alternativa competitiva alle soluzioni esistenti.