NSF-BSF: RI: Small: Efficient Bi- and Multi-Objective Search Algorithms
NSF-BSF:RI:小型:高效的双目标和多目标搜索算法
基本信息
- 批准号:2121028
- 负责人:
- 金额:$ 49.97万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2021
- 资助国家:美国
- 起止时间:2021-10-01 至 2025-09-30
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
This project develops faster search algorithms for route-planning problems where multiple cost measures are used to determine the best solutions. For example, when transporting hazardous goods it is important to consider both the duration and safety of a route. Other applications include planning power-transmission lines, inspection and manipulation planning in robotics, scheduling satellites, and routing packets in computer networks. These bi- and multi-objective search algorithms work by maintaining many paths from the given start location to each location encountered during the search. This approach currently prevents them from solving realistically sized problems in real-time. This project both investigates techniques for speeding them up to realistic problem sizes and develops new benchmark instances for evaluating their performance. It is part of an international collaboration that also includes the exchange of personnel and the development of educational material.Bi-objective (and multi-objective) search algorithms allow the cost of every graph edge to be quantified by two (or more) real values. They essentially assume that one wants to find the set of all paths, called the Pareto frontier, such that each path in the set is better than all other paths from a given start vertex to a given goal vertex with respect to the sum of at least one cost component of its edges (or equally good with respect to all cost components). The researchers of this project work on finding synergies between ideas from existing bi-objective search algorithms and recent algorithmic developments in the artificial intelligence search community to develop the next generation of optimal and approximately-optimal bi-objective search algorithms. They are also working on generalizing their bi-objective search algorithms to multi-objective search algorithms and applying them in the context of transportation and robotics.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.
该项目为路线规划问题开发了更快的搜索算法,其中使用多种成本措施来确定最佳解决方案。例如,在运输危险货物时,重要的是要考虑路线的持续时间和安全性。其他应用包括规划输电线路、机器人技术中的检查和操作规划、卫星调度和计算机网络中的数据包路由。这些双目标和多目标搜索算法通过维护从给定起始位置到搜索过程中遇到的每个位置的多条路径来工作。这种方法目前使他们无法实时解决实际规模的问题。该项目研究了将它们加速到实际问题规模的技术,并开发了用于评估其性能的新基准实例。这是一项国际合作的一部分,这项合作还包括人员交流和编写教材。双目标(和多目标)搜索算法允许用两个(或更多)实值来量化每个图边的代价。他们本质上假设人们想要找到所有路径的集合,称为帕累托边界,使得集合中的每条路径都比从给定起始点到给定目标点的所有其他路径,相对于其边的至少一个成本分量的总和(或者相对于所有成本分量的总和)更好。该项目的研究人员致力于在现有双目标搜索算法和人工智能搜索社区的最新算法发展之间寻找协同作用,以开发下一代最优和近似最优双目标搜索算法。他们还致力于将双目标搜索算法推广到多目标搜索算法,并将其应用于交通和机器人领域。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(9)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Cost Splitting for Multi-Objective Conflict-Based Search
基于多目标冲突的搜索的成本分割
- DOI:
- 发表时间:2023
- 期刊:
- 影响因子:0
- 作者:Ge, C.;Zhang, H.;Li, J.;Koenig, S.
- 通讯作者:Koenig, S.
Efficient Multi-Query Bi-Objective Search via Contraction Hierarchies
通过收缩层次结构进行高效的多查询双目标搜索
- DOI:
- 发表时间:2023
- 期刊:
- 影响因子:0
- 作者:Zhang, H.;Salzman, O.;Felner, A.;Kumar, S.;Hernandez, C.;Koenig, S.
- 通讯作者:Koenig, S.
A*pex: Efficient Approximate Multi-Objective Search on Graphs
A*pex:图上的高效近似多目标搜索
- DOI:
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Zhang, H.;Salzman, O.;Kumar, S.;Felner, A.;Hernandez, C.;Koenig, S.
- 通讯作者:Koenig, S.
Simple and efficient bi-objective search algorithms via fast dominance checks
- DOI:10.1016/j.artint.2022.103807
- 发表时间:2022-10
- 期刊:
- 影响因子:0
- 作者:Carlos Hernández;W. Yeoh;Jorge A. Baier;Han Zhang;L. Suazo;Sven Koenig;Oren Salzman
- 通讯作者:Carlos Hernández;W. Yeoh;Jorge A. Baier;Han Zhang;L. Suazo;Sven Koenig;Oren Salzman
Heuristic-Search Approaches for the Multi-Objective Shortest-Path Problem: Progress and Research Opportunities [Survey Track]
多目标最短路径问题的启发式搜索方法:进展和研究机会 [调查轨道]
- DOI:
- 发表时间:2023
- 期刊:
- 影响因子:0
- 作者:Salzman, O.;Felner, A.;Zhang, H.;Chan, S.-H.;Koenig, S.
- 通讯作者:Koenig, S.
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Sven Koenig其他文献
Optimal and Bounded-Suboptimal Multi-Agent Motion Planning
最优和有界次优多智能体运动规划
- DOI:
10.1609/socs.v10i1.18501 - 发表时间:
2021 - 期刊:
- 影响因子:0
- 作者:
L. Cohen;T. Uras;T. K. S. Kumar;Sven Koenig - 通讯作者:
Sven Koenig
Speeding-Up Any-Angle Path-Planning on Grids
加速网格上的任意角度路径规划
- DOI:
10.1609/icaps.v25i1.13724 - 发表时间:
2015 - 期刊:
- 影响因子:0
- 作者:
T. Uras;Sven Koenig - 通讯作者:
Sven Koenig
Map Connectivity and Empirical Hardness of Grid-based Multi-Agent Pathfinding Problem
基于网格的多智能体寻路问题的地图连通性和经验难度
- DOI:
- 发表时间:
2024 - 期刊:
- 影响因子:0
- 作者:
J. Ren;Eric Ewing;T. K. S. Kumar;Sven Koenig;Nora Ayanian - 通讯作者:
Nora Ayanian
Identifying Hierarchies for Fast Optimal Search
识别快速最佳搜索的层次结构
- DOI:
10.1609/socs.v5i1.18307 - 发表时间:
2014 - 期刊:
- 影响因子:0
- 作者:
T. Uras;Sven Koenig - 通讯作者:
Sven Koenig
Multi-objective Search via Lazy and Efficient Dominance Checks
通过惰性和高效的优势检查进行多目标搜索
- DOI:
- 发表时间:
2023 - 期刊:
- 影响因子:0
- 作者:
Carlos Hern´andez;William Yeoh;Jorge A. Baier;Ariel Felner;Oren Salzman;Han Zhang;Shao;Sven Koenig - 通讯作者:
Sven Koenig
Sven Koenig的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Sven Koenig', 18)}}的其他基金
NSF-BSF:RI:Small:Collaborative Research:Next-Generation Multi-Agent Path Finding Algorithms
NSF-BSF:RI:小型:协作研究:下一代多智能体路径查找算法
- 批准号:
1817189 - 财政年份:2018
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
CPS: Small: Novel Algorithmic Techniques for Drone Flight Planning on a Large Scale
CPS:小型:大规模无人机飞行规划的新颖算法技术
- 批准号:
1837779 - 财政年份:2018
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
S&AS: FND: Long-Term Planning and Robust Plan Execution for Multi-Robot Systems
S
- 批准号:
1724392 - 财政年份:2017
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
Support for the ICAPS-15 Doctoral Consortium
支持 ICAPS-15 博士联盟
- 批准号:
1519252 - 财政年份:2015
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
RI: Medium: Collaborative Research: Experience-Based Planning: A Framework for Lifelong Planning
RI:媒介:协作研究:基于经验的规划:终身规划框架
- 批准号:
1409987 - 财政年份:2014
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
CAREER: Artificial Intelligence Planning with Realistic Preference Models
职业:利用现实偏好模型进行人工智能规划
- 批准号:
0536375 - 财政年份:2005
- 资助金额:
$ 49.97万 - 项目类别:
Continuing Grant
CAREER: Artificial Intelligence Planning with Realistic Preference Models
职业:利用现实偏好模型进行人工智能规划
- 批准号:
9984827 - 财政年份:2000
- 资助金额:
$ 49.97万 - 项目类别:
Continuing Grant
相似国自然基金
枯草芽孢杆菌BSF01降解高效氯氰菊酯的种内群体感应机制研究
- 批准号:31871988
- 批准年份:2018
- 资助金额:59.0 万元
- 项目类别:面上项目
基于掺硼直拉单晶硅片的Al-BSF和PERC太阳电池光衰及其抑制的基础研究
- 批准号:61774171
- 批准年份:2017
- 资助金额:63.0 万元
- 项目类别:面上项目
B细胞刺激因子-2(BSF-2)与自身免疫病的关系
- 批准号:38870708
- 批准年份:1988
- 资助金额:3.0 万元
- 项目类别:面上项目
相似海外基金
NSF-BSF: RI: Small: Mechanisms and Algorithms for Improving Peer Selection
NSF-BSF:RI:小型:改进同行选择的机制和算法
- 批准号:
2134857 - 财政年份:2022
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
NSF-BSF: Collaborative Research: RI: Small: Multilingual Language Generation via Understanding of Code Switching
NSF-BSF:协作研究:RI:小型:通过理解代码切换生成多语言
- 批准号:
2203097 - 财政年份:2021
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
NSF-BSF: RI: Small: Efficient Transformers via Formal and Empirical Analysis
NSF-BSF:RI:小型:通过形式和经验分析的高效变压器
- 批准号:
2113530 - 财政年份:2021
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
NSF-BSF: RI: Small: Planning and Acting While Time Passes
NSF-BSF:RI:小型:随着时间的推移进行规划和行动
- 批准号:
2008594 - 财政年份:2020
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
NSF-BSF: RI: Small: Resource-Constrained Multi-hypothesis-aware Perception
NSF-BSF:RI:小型:资源受限的多假设感知感知
- 批准号:
2008279 - 财政年份:2020
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
NSF-BSF: Collaborative Research: RI: Small: Multilingual Language Generation via Understanding of Code Switching
NSF-BSF:协作研究:RI:小型:通过理解代码切换生成多语言
- 批准号:
2007656 - 财政年份:2020
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
NSF-BSF: RI: Small: Structured Distributions in Deep Nets
NSF-BSF:RI:小型:深度网络中的结构化分布
- 批准号:
2008387 - 财政年份:2020
- 资助金额:
$ 49.97万 - 项目类别:
Continuing Grant
NSF-BSF: RI: Small: Provably High-Quality Robot Inspection Planning - Theory and Application
NSF-BSF:RI:小型:可证明的高质量机器人检测规划 - 理论与应用
- 批准号:
2008475 - 财政年份:2020
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
NSF-BSF: Collaborative Research: RI: Small: Multilingual Language Generation via Understanding of Code Switching
NSF-BSF:协作研究:RI:小型:通过理解代码切换生成多语言
- 批准号:
2007960 - 财政年份:2020
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant
NSF-BSF: RI: Small: Learning to plan safely
NSF-BSF:RI:小型:学习安全计划
- 批准号:
1908287 - 财政年份:2019
- 资助金额:
$ 49.97万 - 项目类别:
Standard Grant