Deadline-Aware Multi-Agent Tour Planning


  • Taoan Huang University of Southern California
  • Vikas Shivashankar Amazon Robotics
  • Michael Caldara Amazon Robotics
  • Joseph Durham Amazon Robotics
  • Jiaoyang Li Carnegie Mellon University
  • Bistra Dilkina University of Southern California
  • Sven Koenig University of Southern California



Planning with time and resources, Robot planning and scheduling


The increasing demand for same-day delivery and the commitment of e-commerce companies to this service raise a number of challenges in logistics. One of these challenges for fulfillment centers is to coordinate hundreds of mobile robots in their automated warehouses efficiently to allow for the retrieval and packing of thousands of ordered items within the promised delivery deadlines. We formulate this challenge as the new problem of deadline-aware multi-agent tour planning, where the objective is to coordinate robots to visit multiple picking stations in congested warehouses to allow as many orders to be packed on time as possible. To solve it, we propose LaRge NeighbOrhood Search for DEadline-Aware MulTi-Agent Tour PlAnning (ROSETTA). We conduct extensive experiments to evaluate ROSETTA with up to 350 robots in simulated warehouses inspired by KIVA systems. We show that it increases the number of orders completed on time by up to 38% compared to several baseline algorithms and also significantly outperforms them in terms of throughput and station utilization.




How to Cite

Huang, T., Shivashankar, V., Caldara, M., Durham, J., Li, J., Dilkina, B., & Koenig, S. (2023). Deadline-Aware Multi-Agent Tour Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 189-197.