A deadlock-free solution for Multi-Agent Pickup and delivery in the presence of external agents

This thesis addresses a variation of the Multi-Agent Pickup and Delivery (MAPD) problem in environments shared with higher-priority External Agents. MAPD involves coordinating a team of agents that plan collision-free paths to complete pickup and delivery tasks. However, in the presence of External Agents that move through the environment without communicating with the Team Agents, the responsibility for avoiding collisions must be taken on completely by the Team Agents. While Team Agents can use limited-range sensing channels to reactively avoid collisions, this reactive approach is insufficient in certain scenarios, leading to deadlocks—situations where Team Agents cannot proceed without causing a collision. Since deadlocks are unsolvable in the presence of high-priority External Agents, they must be prevented proactively. We demonstrate that by limiting the number of agents—both Team and External—within portions of the environment, Team Agents can prevent deadlocks entirely. Compared to state of the art solutions, our method broadens the range of environments that can be traversed deadlock-free and reduces the restrictions on task placement. Experimental results support our claims, showing that our approach eliminates deadlocks at the cost of approximately doubling the time required to solve the MAPD problem of the Team Agents, compared to baseline solutions that assume perfect communication or that allow deadlocks.

Questa tesi affronta una variante del problema Multi-Agent Pickup and Delivery (MAPD) in ambienti condivisi con agenti esterni con priorità superiore. MAPD coinvolge un team coordinato di agenti che pianificano percorsi privi di collisioni per completare compiti di pickup e delivery. Tuttavia, in presenza di agenti esterni che si muovono nell'ambiente senza comunicare con gli agenti del team, la responsabilità di evitare le collisioni deve essere interamente a carico degli agenti del team. Sebbene gli agenti del team possano utilizzare sistemi osservazione limitati per evitare collisioni in modo reattivo, questo approccio reattivo non è sufficiente in determinati scenari, portando a situazioni di stallo (deadlock) —dove gli agenti del team non possono procedere senza causare una collisione. Poiché gli stalli sono irrisolvibili in presenza di agenti esterni con alta priorità, devono essere prevenuti in modo proattivo. Dimostriamo che limitando il numero di agenti—sia del team che esterni—Nell'ambiente, gli agenti del team possono allo prevenire completamente gli stalli. Rispetto alle soluzioni stato dell'arte, il nostro metodo amplia la gamma di ambienti che possono essere percorsi senza deadlock e riduce le restrizioni sul posizionamento dei compiti. I risultati sperimentali supportano le nostre affermazioni, mostrando che il nostro approccio elimina gli stalli a fronte di un tempo necessario per risolvere il problema MAPD che è approssimativamente il doppio rispetto a soluzioni che assumono comunicazioni perfette o che consentono stalli.