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.
该项目为路径规划问题开发了更快的搜索算法,其中使用多个成本衡量标准来确定最佳解决方案。例如,在运输危险货物时,重要的是要考虑路线的持续时间和安全。其他应用包括规划输电线路、机器人中的检查和操作规划、卫星调度以及计算机网络中的数据包路由。这些双目标和多目标搜索算法通过维护从给定起始位置到搜索期间遇到的每个位置的许多路径来工作。这种方法目前阻碍了他们实时解决实际规模的问题。这个项目既研究了将它们加速到实际问题大小的技术,又开发了新的基准实例来评估它们的性能。它是国际合作的一部分,国际合作还包括人员交流和教育材料的开发。双目标(和多目标)搜索算法允许用两个(或更多)实际值来量化每条图形边的成本。它们本质上假设人们想要找到所有路径的集合,称为帕累托前线,使得集合中的每条路径相对于其边的至少一个成本分量的总和(或者相对于所有成本分量相同地好)比从给定起点顶点到给定目标顶点的所有其他路径更好。该项目的研究人员致力于从现有的双目标搜索算法中寻找想法与人工智能搜索界最近的算法发展之间的协同效应,以开发下一代最优和近似最优的双目标搜索算法。他们还致力于将他们的双目标搜索算法推广到多目标搜索算法,并将其应用于交通和机器人领域。这一奖项反映了NSF的法定使命,并通过使用基金会的智力优势和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(9)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Cost Splitting for Multi-Objective Conflict-Based Search
基于多目标冲突的搜索的成本分割
Efficient Multi-Query Bi-Objective Search via Contraction Hierarchies
通过收缩层次结构进行高效的多查询双目标搜索
A*pex: Efficient Approximate Multi-Objective Search on Graphs
A*pex:图上的高效近似多目标搜索
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]
多目标最短路径问题的启发式搜索方法:进展和研究机会 [调查轨道]
{{ 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
加速网格上的任意角度路径规划
Map Connectivity and Empirical Hardness of Grid-based Multi-Agent Pathfinding Problem
基于网格的多智能体寻路问题的地图连通性和经验难度
Identifying Hierarchies for Fast Optimal Search
识别快速最佳搜索的层次结构
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
RI: Small: Any-Angle Search
RI:小:任意角度搜索
  • 批准号:
    1319966
  • 财政年份:
    2013
  • 资助金额:
    $ 49.97万
  • 项目类别:
    Standard Grant
CAREER: Artificial Intelligence Planning with Realistic Preference Models
职业:利用现实偏好模型进行人工智能规划
  • 批准号:
    0536375
  • 财政年份:
    2005
  • 资助金额:
    $ 49.97万
  • 项目类别:
    Continuing Grant
Incremental Heuristic Search
增量启发式搜索
  • 批准号:
    0350584
  • 财政年份:
    2003
  • 资助金额:
    $ 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
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了