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.

" "

Tutorial

Overview Publications

Representative Publications


Part of this material is based upon research supported by the National Aeronautics and Space Administration via Stinger Ghaffarian Technologies and the National Science Foundation under grant numbers IIS-1409987 and IIS-1319966. 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