November 5, 2021
11:00am - 12:00pm

The coordination of robots and other agents becomes more and more important for industry. For example, on the order of one thousand robots already navigate autonomously in Amazon fulfillment centers to move inventory pods all the way from their storage locations to the picking stations that need the products they store (and vice versa). Optimal and even some approximately optimal path planning for these robots is NP-hard, yet one must find high-quality collision-free paths for them in real-time. Algorithms for such multi-agent path-finding problems have been studied in robotics and theoretical computer science for a longer time but are insufficient since they are either fast but of insufficient solution quality or of good solution quality but too slow. In this talk, I will discuss different variants of multi-agent path-finding problems, cool ideas for both solving them and executing the resulting plans robustly, and several of their applications, including warehousing, manufacturing, and autonomous driving. I will also discuss how three Ph.D. students from my research group and one Ph.D. student from a collaborating research group at Monash University used multi-agent path-finding technology to win the NeurIPS-20 Flatland train scheduling competition.
Our research on this topic has been funded by both NSF and Amazon Robotics.

Sven Koenig is a professor of computer science at the University of Southern California. Most of his current research focuses on planning for single agents (such as robots) or multi-agent systems. Additional information about him can be found on his webpages: idm-lab.org.