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

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

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.