Online Multi-Agent Pickup and Delivery with Task Deadlines

Managing delivery deadlines in automated ware- houses and factories is crucial for maintaining customer satis- faction and ensuring seamless production. This study introduces the problem of online multi-agent pickup and delivery with task deadlines (MAPD-D), an advanced variant of the online MAPD problem incorporating delivery deadlines. In the MAPD problem, agents must manage a continuous stream of delivery tasks online. Tasks are added at any time. Agents must complete their tasks while avoiding collisions with each other. MAPD-D introduces a dynamic, deadline-driven approach that incorpo- rates task deadlines, challenging the conventional MAPD frame- works. To tackle MAPD-D, we propose a novel algorithm named deadline-aware token passing (D-TP). The D-TP algorithm cal- culates pickup deadlines and assigns tasks while balancing exe- cution cost and deadline proximity. Additionally, we introduce the D-TP with task swaps (D-TPTS) method to further reduce task tardiness, enhancing flexibility and efficiency through task- swapping strategies. Numerical experiments were conducted in simulated warehouse environments to showcase the effectiveness of the proposed methods. Both D-TP and D-TPTS demonstrated significant reductions in task tardiness compared to existing methods. Our methods contribute to efficient operations in automated warehouses and factories with delivery deadlines.