Multi-Agent Pickup and Delivery in Dynamic Environments

In a Multi-Agent Pickup and Delivery (MAPD) problem, a group of agents has to accomplish subsequent pickup and delivery tasks while avoiding collisions. Tasks are provided at runtime, making MAPD a combination of Multi-Agent Path Finding (MAPF) and online task assignment. In this paper, we consider a new formulation of MAPD, in which a team of agents has to solve a MAPD problem without interfering or communicating with other agents not belonging to the team that are operating in the same environment. We address the problem from the point of view of the team of agents, and we propose that they build a model of the behavior of the agents external to the team and exploit this information in planning their paths. We consider different levels of knowledge that the team of agents can have about the other agents, and propose different solutions accordingly. Experimental results show that the inclusion of information about the behavior of external agents in the team's planning phase reduces the number of potential collisions and decreases tasks' completion time for the team.