Project "Multi-Agent Path Planning (MAPF)" (scroll down for publications)
Teams of agents must often assign target locations among themselves and
then plan collision-free paths to their target locations. Examples include
autonomous aircraft towing vehicles, automated warehouse systems, office
robots, 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), thereby reducing pollution, energy consumption,
congestion, and human workload. Today, hundreds of robots already navigate
autonomously in 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). Path planning for these robots is NP-hard, yet
one must find high-quality collision-free paths for them in real-time. Shorter
paths result in higher throughput or lower operating costs (since fewer robots
are required). We therefore study different versions of multi-agent path
finding (aka multi-agent pathfinding or MAPF) problems, their complexities,
algorithms for solving them, and their applications. We have also developed a
hierarchical planning architecture that combines ideas from artificial
intelligence and robotics. It makes use of a simple temporal network to
post-process the output of a multi-robot path-finding algorithm in polynomial
time to create a plan-execution schedule that takes the maximum translational
and rotational velocities of non-holonomic 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.
MAPF Visitors in 2019:
Eli Boyarski, Ben-Gurion University (Israel)
Prof. Daniel Harabor, Monash University (Australia)
MAPF Visitors in 2018:
Prof. Helmut Prendinger and students, National Institute of Informatics (Japan)
Sven spent Summer 2018 at Monash University (Australia) to start a research
collaboration with Dr. Daniel Harabor and Prof. Peter Stuckey on MAPF.
We also had a MAPF research retreat on November 1-2, 2018 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).
MAPF Visitors in 2017:
Prof. Ariel Felner, Ben-Gurion University (Israel)
Prof. Carlos Hernandez Ulloa, Universidad Andres Bello (Chile)
Dr. Masoumeh Mansouri, Orebro Universitet (Sweden)
J. Li, P. Surynek, A. Felner, H. Ma, S. Kumar and S. Koenig. Multi-Agent Path Finding for Large Agents. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), (in print), 2019. [downloadable]
H. Ma, G. Wagner, A. Felner, J. Li, S. Kumar and S. Koenig. Multi-Agent Path Finding with Deadlines. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 417-423, 2018. [downloadable]
L. Cohen, M. Greco, H. Ma, C. Hernandez, A. Felner, S. Kumar and S. Koenig. Anytime Focal Search with Applications. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1434-1441, 2018. [downloadable]
Representative Publications on Collaborative
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.
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.