Multi-Goal Multi-Agent Pickup and Delivery

In this work, we consider the Multi-Agent Pickup and Delivery (MAPD) problem, where agents constantly engage with new tasks and need to plan collision-free paths to execute them. To execute a task, an agent needs to visit a pair of goal locations, namely the pickup location and the delivery location. To solve an MAPD instance, we need to decide which agent executes which tasks (task-assignment), and plan collision-free paths for agents to execute these tasks (path-finding). Existing MAPD methods either assign an agent's next task only, which can lead to bad schedules of the entire task set, or plan agents' paths segment by segment, which can lead to larger path costs. Therefore, we propose a method that improves the state-of-the-art MAPD methods in both aspects. Our method assigns a sequence of tasks to each agent using the anytime algorithm Large Neighborhood Search (LNS), and plans paths through a sequence of goal locations using the Multi-Agent Path Finding (MAPF) algorithm Priority-Based Search (PBS). Specifically, two variants of this method are proposed: LNS-PBS and LNS-wPBS. Theoretically, we prove that LNS-PBS is complete for well-formed MAPD, a realistic subclass of MAPD instances. Empirically, LNS-PBS produces better solutions than the existing complete method CENTRAL. The second variant LNS-wPBS is more efficient and stable (but has no completeness guarantee). Empirically, LNS-wPBS can scale to thousands of agents and thousands of tasks in a large warehouse, and produce better solutions than the existing scalable methods. Lastly, the proposed method applies to a more generalized variant of MAPD, the Multi-Goal MAPD (MG-MAPD) problem, where tasks can have a various number of goal locations.