Online Multi-Agent Pickup and Delivery with Task Deadlines
<|reference_start|>Online Multi-Agent Pickup and Delivery with Task Deadlines: Managing delivery deadlines in automated warehouses and factories is crucial for maintaining customer satisfaction 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 incorporates task deadlines, challenging the conventional MAPD frameworks. To tackle MAPD-D, we propose a novel algorithm named deadline-aware token passing (D-TP). The D-TP algorithm calculates pickup deadlines and assigns tasks while balancing execution 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.<|reference_end|>
@article{makino2024online,
    title={Online Multi-Agent Pickup and Delivery with Task Deadlines},
    author={Hiroya Makino and Seigo Ito},
    journal={arXiv preprint arXiv:2403.12377},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.12377},
    primaryClass={cs.MA cs.RO}
}