NSF-BSF:RI:Small:Collaborative Research:Next-Generation Multi-Agent Path Finding Algorithms

University Of Denver, Denver CO

Investigators

Abstract

With the increased use of automated vehicles in manufacturing, warehousing, and other environments, it is important to ensure that the plans taken by the automated agents controlling these vehicles are both efficient and safe. That is, we want to minimize the cost of travel while ensuring that agents will not collide with each other or the environment. This project will focus particularly on approaches for planning in environments where the number of agents is limited, but the cost of failure is high. For instance, in an airport there are relatively few airplanes moving on the tarmac at any one time, but the cost of collisions is large. The project will develop efficient and robust approaches that can be used to control agents in these environments. When these approaches are complete, this will enable new applications for the deployment of automated agents that can reduce the cost and pollution of current systems while increasing their efficiency and safety. Existing algorithms for centralized control of agents have three drawbacks. First, they often make restrictive assumptions about the environment, such as axis-aligned movement with unit-cost actions. Second, the optimal approaches do not scale to large numbers of agents and the fastest algorithms have poor solution quality. Third, these algorithms are only well-defined in fixed scenarios where there is a clear distinction between plan formation and execution. This project will address these limitations by developing new algorithms. These approaches will handle more realistic agent models, such as robotic movement on a state lattice, they will compute near-optimal solutions to ensure that they scale to significantly larger scenarios, and they will be adapted to run on online problems where agents can enter or exit the world and where plan execution is imprecise and must be adapted based on real-world restrictions. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.