Project "Multi-Agent Path Planning"
(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 (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 2017:


Overview Publications

Representative Publications

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.

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 number 1724392. 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.

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