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