权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

NSF-BSF：RI：小型：协作研究：下一代多智能体路径查找算法

基本信息

批准号：
1815660
负责人：
Nathan Sturtevant
金额：
$ 19.33万
依托单位：
University of Denver
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-09-01 至 2023-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1815660&HistoricalAwards=false
关键词：
NSF BSF RI Small Collaborative

项目摘要

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.

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

项目成果

期刊论文数量（6）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Conflict-Based Increasing Cost Search

基于冲突的成本递增搜索

DOI：
发表时间：
2021
期刊：
Proceedings of the International Conference on Automated Planning and Scheduling
影响因子：
0
作者：
Walker, Thayne T.;Sturtevant, Nathan R.;Felner, Ariel;Zhang, Han;Li, Jiaoyang;Kumar, T. K.
通讯作者：
Kumar, T. K.

Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks

DOI：
10.1609/socs.v10i1.18510
发表时间：
2019-06
期刊：
ArXiv
影响因子：
0
作者：
Roni Stern;Nathan R Sturtevant;Ariel Felner;Sven Koenig;Hang Ma;Thayne T. Walker;Jiaoyang Li;Dor Atzmon;L. Cohen;T. K. S. Kumar;Eli Boyarski;R. Barták
通讯作者：
Roni Stern;Nathan R Sturtevant;Ariel Felner;Sven Koenig;Hang Ma;Thayne T. Walker;Jiaoyang Li;Dor Atzmon;L. Cohen;T. K. S. Kumar;Eli Boyarski;R. Barták

Multi-Directional Heuristic Search

多向启发式搜索

DOI：
10.24963/ijcai.2020/562
发表时间：
2020
期刊：
International Joint Conference on Artificial Intelligence (IJCAI
影响因子：
0
作者：
Atzmon, Dor;Li, Jiaoyang;Felner, Ariel;Nachmani, Eliran;Shperberg, Shahaf;Sturtevant, Nathan;Koenig, Sven
通讯作者：
Koenig, Sven

Probabilistic Robust Multi-Agent Path Finding

概率鲁棒多智能体路径查找

DOI：
发表时间：
2020
期刊：
Proceedings of the International Conference on Automated Planning and Scheduling
影响因子：
0
作者：
Atzmon, Dor;Li, Jiaoyang;Felner, Ariel;Nachmani, Eliran;Shperberg, Shahaf S.;Sturtevant, Nathan;Koenig, Sven
通讯作者：
Koenig, Sven

Multi-Agent Path Finding with Temporal Jump Point Search

具有时间跳跃点搜索的多智能体路径查找

DOI：
10.1609/icaps.v32i1.19798
发表时间：
2022
期刊：
Proceedings of the International Conference on Automated Planning and Scheduling
影响因子：
0
作者：
Hu, Shuli;Harabor, Daniel;Gange, Graeme;Stuckey, Peter;Sturtevant, Nathan
通讯作者：
Sturtevant, Nathan