Multi-Agent Pickup and Delivery with Mobile Pickups

In Multi-Agent Pickup and Delivery (MAPD), a team of agents must find collision-free paths to service an online stream of tasks, which are composed of pickup and delivery locations that have to be visited sequentially. This paper addresses the novel problem of MAPD with mobile pickups, which involves two types of agents, the suppliers and the deliverers. Suppliers are large robots that can transport many items, but cannot navigate tight spaces or manipulate objects, while deliverers can navigate to rooms to deliver items, but can only carry one item at a time. Deliverers have to collect items from the suppliers, and bring them to the assigned delivery locations. This introduces a new challenge which is not tackled in classical MAPD: deciding where and when the exchange of items should happen. We propose Token Passing with Exchange Locations (TP-EL), an extension of the widely used Token Passing (TP) algorithm with a task allocation mechanism that considers which supplier to pick items from, and when and where to do so. We experiment in several simulated domains, demonstrating the superiority of TP-EL over baselines that do not consider mobile pickups or use alternative methods to decide pickup locations.