Departmental colloquium 29.12.22
Prof. Sven Koenig
University of Southern California
יר צ ה ע ל
Will lecture on
Multi-Agent Path Finding and Its Applications
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 (and vice versa). Optimal and, in some cases, 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, sorting, multi-arm planning, and pipe routing. 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. Bio:
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 at idm-lab.org.