[3P5-OS-17a] OS-17

[3P5-OS-17a-01] DA-MAPD: Deadline-Aware Multi-Agent Pickup and Delivery

〇Hiroya Makino¹, Seigo Ito¹ (1. Toyota Central R&D Labs., Inc.)

Keywords:Multi-agent path finding, Multi-agent pickup and delivery, Shortest path problem, Mathematical optimization

This paper first introduces the Deadline-Aware Multi-Agent Pickup and Delivery (DA-MAPD) problem, an advanced version of MAPD that integrates delivery deadlines. Deadlines are critical in automated warehouses and factories. Subsequently, we propose a novel algorithm, Deadline-Aware Token Passing (DA-TP), to address DA-MAPD. DA-TP enhances traditional Token Passing by calculating pickup deadlines based on delivery deadlines and strategically assigning tasks to balance execution costs with deadline adherence. It aims to minimize the delay by reducing each task's tardiness. We validate DA-TP's effectiveness in reducing delays through numerical experiments in a simulated warehouse environment.