Multi-Load Agent Path Finding for Online Pickup and Delivery Problem

The Multi-Agent Pickup and Delivery (MAPD) problem, a variant of the lifelong Multi-Agent Path Finding (MAPF) problem, allows agents to move from their initial locations via the pickup locations of tasks to the delivery locations. In general MAPD problem, the agent is single-load and completes only one task at a time. However, many commercial platforms, e.g., Amazon and JD, have recently deployed multi-load agents to improve efficiency in their automated warehouses. As the multi-load agents can complete multiple tasks at once instead of just one, existing solutions for the general MAPD are unsuitable for the multi-load agent scenario. Meanwhile, a few works focus on the schedule of multi-load agents because it is hard to assign tasks to suitable multi-load agents and find conflict-free paths in real-time for multi-load agents. Therefore, in this paper, we formally define the Multi-Load Agent Pickup and Delivery (MLAPD) problem, in which the multi-load agents complete the real-time pickup-and-delivery tasks and avoid conflicts with each other to minimize the sum of the travel costs and the delay costs. For solving the MLAPD problem, we propose an efficient task assignment algorithm and a novel dynamic multi-agent path finding algorithm. Extensive experiments show that compared with the state-of-the-art, our solution can complete an additional 4.31% ∼ 138.33% of tasks and save 0.38% ∼ 12.41% of total costs while meeting real-time requirements.