Project "Multi-Agent Path Planning (MAPF)"
(scroll down for publications)

Teams of agents must often assign locations among themselves and then plan collision-free paths to these locations. Examples include autonomous aircraft towing vehicles, automated warehouse systems, office robots, drones and game characters in video games. For example, soon, autonomous aircraft towing vehicles will tow aircraft all the way from the runways to their gates (and vice versa) to avoid the pollution and excessive energy consumption resulting from planes taxiing with their engines. Today, on the order of one thousand robots already navigate autonomously in some Amazon fulfillment centers to move inventory pods all the way from their storage locations to the inventory stations that need the products they store (and vice versa). Human workers no longer need to move around in such automated warehouses, collecting the right items under time pressure - a physically demanding job. Optimal and, in some cases, even approximately optimal path planning for such robots is NP-hard, yet one must find high-quality collision-free paths for them in real-time since shorter paths result in higher throughput or lower operating costs (since fewer robots are required). Algorithms for such multi-agent path-finding problems have been studied in robotics and theoretical computer science for a long time but are insufficient since they are either fast but result in insufficient solution quality or result in good solution quality but are too slow (especially for highly congested environments), see my educational website mapf.info for more information.

My collaborators and I study different variants of multi-agent path finding (MAPF) problems (including "lifelong" variants), their complexities, algorithms for solving them and their applications. We proved that even approximating optimal solutions can be NP-hard in some cases but also managed to scale up bounded-suboptimal planners to hundreds of agents and high-quality planners without solution guarantees to thousands of agents via a variety of techniques, such as "highway" heuristics, symmetry-breaking techniques, better node-splitting techniques, mutex propagation, more informed heuristics and learning which collision to resolve next as well as more standard techniques, such as rapid random restarts and large neighborhood search. We also studied MAPF solving based on prioritized planning and deep reinforcement learning. Finally, we developed a hierarchical planning architecture that combines ideas from AI, optimization and robotics. It makes use of a simple temporal network to post-process the output of a MAPF algorithm in polynomial time to create a plan-execution schedule that takes the maximum translational and rotational velocities of robots into account, provides a guaranteed safety distance between them and exploits slack to absorb imperfect plan executions and avoid time-intensive re-planning in many cases. Our paper on "Multi-Agent Path Finding with Kinematic Constraints" won the Outstanding Paper Award in the Robotics Track of the International Conference on Automated Planning and Scheduling (ICAPS) 2016, and our paper on "Multi-Agent Path Finding with Mutex Propagation" won the Outstanding Student Paper Award at ICAPS 2020.

We are working with Amazon Robotics on robot navigation in automated warehouses and worked with NASA Ames on coordinating tug robots and scheduling aircraft. We adapted our techniques to pipe routing and applied them to a natural gas plant. We also generalized MAPF to planning domains with additional spatiotemporal constraints (in the context of planning for the Harvard TERMES robots for collective construction), which eventually resulted in a single-agent variant of the domain being used in the International Planning Competition in 2018. More recently, we applied MAPF techniques to railway scheduling, and a team consisting of three of my Ph.D. students and one Ph.D. student from Monash University reached the highest score in both rounds of the NeurIPS-20 Flatland Challenge, a railway scheduling competition with more than 700 participants that was held in partnership with German, Swiss and French railway companies.

News

Our paper "T. Huang, V. Shivashankar, M. Caldara, J. Durham, J. Li, B. Dilkina, and S. Koenig, Deadline-Aware Multi-Agent Tour Planning, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 2023" received the ICAPS-23 Best Student Paper Honorable Mention.

We received funding from Amazon Robotics in 2023 for organizing The League of Robot Runners competition, an automated warehousing competition with a strong MAPF component.

Ph.D. student Han Zhang spent the summer of 2023 as an intern at Amazon Robotics.

Sven spent one month in December 2022/January 2023 at Ben-Gurion University and the Technion in Israel to continue the research collaboration with Profs. Ariel Felner and Oren Salzman.

We co-organized a MAPF workshop at AAAI 2023.

We had the following MAPF visitors in 2022:

Ph.D. student Chris Leet spent the summer of 2022 as an intern at Amazon Robotics.

We received funding from Amazon Robotics in 2022 in form of an Amazon Research Award.

Our paper "E. Boyarski, S.-H. Chan, D. Atzmon, A. Felner and S. Koenig, On Merging Agents in Multi-Agent Pathfinding Algorithms, Proceedings of the Symposium on Combinatorial Search (SoCS), 2022" received the SoCS-22 Best Student Paper Award.

Ph.D. student Jiaoyang Li, whose dissertation topic was on MAPF, graduated and now works as assistant professor at Carnegie Mellon University. Her dissertation received a ICAPS Best Dissertation Award 2023, the Victor Lesser Distinguished Dissertation Award 2023 by the International Foundation for Autonomous Agents and Multiagent System (that runs the AAMAS Conference), and the William F. Ballhaus, Jr. Prize for Excellence in Graduate Engineering Research.

Undergraduate student Shuyang (Jessie) Zhang was a CURVE Symposium winner for her poster on "Machine Learning-Guided Prioritized Planning for Multi-Agent Path Finding" in 2021. She received a Computer Science Award for Outstanding Research for this research in 2022.

Ph.D. student Taoan Huang spent the summer of 2021 as an intern at Amazon Robotics.

We received funding from Amazon Robotics in 2021 in form of an Amazon Research Award.

We co-organized a MAPF workshop at IJCAI 2020.

Team An_Old_Driver, consisting of three of our Ph.D. students plus one student from Monash University, used MAPF technology to reach the highest score in both rounds of the NeurIPS-20 Flatland Challenge, a railway scheduling competition which was held in partnership with German and Swiss railway companies. They outperformed all other entries in both tracks to win overall first place in both rounds. According to the organizers, there were more than 700 participants from 51 countries making more than 2,000 submissions. See here for more information. Our system demonstration of the winning system received the most audience votes for the system demonstration award at the International Conference on Automated Planning and Scheduling (ICAPS) 2021. An updated version of the software won again in the extended Flatland competition in 2021.

Our paper "H. Zhang, J. Li, P. Surynek, S. Koenig and S. Kumar, Multi-Agent Path Finding with Mutex Propagation, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 2020" received the ICAPS-20 Outstanding Student Paper Award.

We received the following press coverage of our research with Amazon Robotics in 2019, which resulted in the publication "J. Li, A. Tinka, S. Kiesel, J. Durham, S. Kumar and S. Koenig, Lifelong Multi-Agent Path Finding in Large-Scale Warehouses, Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2020":

We received funding from Amazon Robotics in 2020 - more than a regular Amazon Research Award.

Ph.D. student Hang Ma, whose dissertation topic was on MAPF, graduated and now works as assistant professor at Simon Fraser University. His dissertation was selected for the ICAPS Best Dissertation Award 2021 and was also a runner-up for the Victor Lesser Distinguished Dissertation Award 2021 by the International Foundation for Autonomous Agents and Multiagent System (that runs the AAMAS Conference).

Ph.D. student Liron Cohen, whose dissertation topic was on MAPF, graduated and now works at Waymo on self-driving cars.

We had the following MAPF visitors in 2019:

We co-organized a MAPF workshop at IJCAI 2019.

Our MAPF team received a Technology Commercialization Award from the USC Stevens Center for Innovation Technology in 2019.

Ph.D. student Jiaoyang Li spent the summer of 2019 as an intern at Amazon Robotics.

We have created a class project on MAPF for undergraduate and graduate students in "Introduction to Artificial Intelligence" and more advanced artificial intelligence classes (as well as for self study). This project was chosen as Model AI Assignment by the Symposium on Educational Advances in Artificial Intelligence in 2020.

We now maintain a MAPF information page (at mapf.info) with a listing of MAPF research groups, their publications and software, tutorials, a mailing list, and so on, for the MAPF research community.

Sven spent part of Summer 2019 at Monash University (Australia) to continue the research collaboration with Dr. Daniel Harabor and Prof. Peter Stuckey.

We had a MAPF research retreat on November 25-28, 2019 at Ben-Gurion University (Israel) with representatives from the University of Southern California, Ben-Gurion University, the University of Alberta and the University of Denver in the context of a joint research project funded by the US National Science Foundation (NSF) and the US-Israel Binational Science Foundation (BSF).

We received funding from Amazon Robotics in 2019 in form of an Amazon Research Award.

We had the following MAPF visitors in 2018:

Sven spent part of Summer 2018 at Monash University (Australia) to start a research collaboration with Dr. Daniel Harabor and Prof. Peter Stuckey on MAPF.

We had a MAPF research retreat on November 1-2, 2018 at the University of Southern California with representatives from the University of Southern California, Ben-Gurion University, the University of Alberta and the University of Denver in the context of a joint research project funded by the US National Science Foundation (NSF) and the US-Israel Binational Science Foundation (BSF).

We received funding from Amazon Robotics in 2018 in form of an Amazon Research Award.

We had the following MAPF visitors in 2017:

Our paper "W. Hoenig, S. Kumar, L. Cohen, H. Ma, H. Xu, N. Ayanian and S. Koenig, Multi-Agent Path Finding with Kinematic Constraints, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 2016" received the ICAPS-16 Outstanding Paper Award in the Robotics Track.

Tutorial

Overview Publications

Representative Publications

Representative Publications on Railway Scheduling

Representative Publications on Intersection Coordination for Self-Driving Cars

Representative Publications on Pipe Routing

Representative Publications on Virtual Network Embedding

Representative Publications on Moving in Formation

Representative Publications on Collaborative Construction

The TERMES domain is a multi-agent path finding domain with additional temporal and spatial constraints. We submitted the TERMES domain for a single robot as a benchmark domain to the International Planning Competition (IPC), and it was used in the IPC 2018. You can download its PDDL description or use it in an online planning system.

Representative Publications on Navigation in Human Environments

Dissertations

Part of this material is based upon research supported by the National Aeronautics and Space Administration via Stinger Ghaffarian Technologies (in form of a Ph.D. internship), a gift by Amazon, and the National Science Foundation under grant numbers 1409987, 1724392, 1817189 and 1837779. Any opinions, findings, and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the sponsoring organizations. Please also visit our NSF project website for more information on multi-agent path finding.

If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.

Home Page of Sven Koenig