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

随着自动化车辆在制造、仓储和其他环境中的使用越来越多，确保控制这些车辆的自动代理所采取的计划既高效又安全是很重要的。也就是说，我们想要最小化旅行成本，同时保证agent不会相互碰撞或与环境发生碰撞。本项目将特别关注在代理数量有限但失败成本很高的环境中进行规划的方法。例如，在机场，任何时候在停机坪上移动的飞机都相对较少，但碰撞的成本却很大。该项目将开发可用于控制这些环境中的代理的有效和健壮的方法。当这些方法完成后，这将使部署自动化代理的新应用程序能够降低当前系统的成本和污染，同时提高其效率和安全性。现有的智能体集中控制算法存在三个缺陷。首先，他们经常对环境做出限制性假设，例如单位成本行动的轴向运动。其次，最优方法不能扩展到大量代理，并且最快的算法解质量差。第三，这些算法仅在计划形成和执行之间有明确区别的固定场景中定义良好。这个项目将通过开发新的算法来解决这些限制。这些方法将处理更现实的代理模型，比如机器人在状态格上的运动，它们将计算接近最优的解决方案，以确保它们扩展到更大的场景，它们将适应运行在在线问题上，代理可以进入或退出世界，计划执行不精确，必须根据现实世界的限制进行调整。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.