Multi-Agent Pickup and Delivery with external agents

In a Multi-Agent Pickup and Delivery (MAPD) problem, a team of agents moving in an environment must complete pickup and delivery tasks while avoiding collisions. These tasks appear and are assigned dynamically at runtime, assuming that the environment is static, except for the movements of the agents. This paper introduces a novel MAPD formulation, where team agents must solve their MAPD problem in an environment populated by moving external agents . Team agents do not communicate nor collaborate with external agents and cannot interfere with external agents’ goals and paths, which are unknown. Thus, team agents are in charge of preventing collisions with external agents while fulfilling their pickup and delivery tasks. To address this challenge, we propose an approach where team agents build behavioral models of external agents, and then use these models to anticipate potential conflicts with external agents and plan paths accordingly. We employ two modeling approaches: (1) a probabilistic occupancy model that estimates the likelihood of each location in the environment being occupied by external agents and (2) a Markovian model that captures how external agents transition between locations in the environment. The proposed approach is evaluated under different observational assumptions for team agents, demonstrating that leveraging knowledge of external agents’ behavior reduces collision events and task completion times for team agents.