Multi-Agent Pickup and Delivery with Task Deadlines


  • Xiaohu Wu Nanyang Technological University
  • Yihao Liu Nanyang Technological University
  • Xueyan Tang Nanyang Technological University
  • Wentong Cai Nanyang Technological University
  • Funing Bai NCS Group
  • Gilbert Khonstantine Nanyang Technological University
  • Guopeng Zhao NCS Group


Search In Robotics, Bounding And Pruning Techniques


We study the multi-agent pickup and delivery problem with task deadlines, where a team of agents execute tasks with individual deadlines to maximize the number of tasks completed by their deadlines. We take an integrated approach that assigns and plans one task at a time taking into account the agent states resulting from all the previous task assignments and path planning. We define metrics to effectively determine which agent ought to execute a given task and which task is most worth assignment next. We leverage the bounding technique to greatly improve the computational efficiency.