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

NSF-BSF: RI: Small: Efficient Bi- and Multi-Objective Search Algorithms

NSF-BSF：RI：小型：高效的双目标和多目标搜索算法

基本信息

批准号：
2121028
负责人：
Sven Koenig
金额：
$ 49.97万
依托单位：
University of Southern California
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-10-01 至 2025-09-30
项目状态：
未结题

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

项目摘要

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

基于多目标冲突的搜索的成本分割

DOI：
发表时间：
2023
期刊：
International Conference on Automated Planning and Scheduling (ICAPS
影响因子：
0
作者：
Ge, C.;Zhang, H.;Li, J.;Koenig, S.
通讯作者：
Koenig, S.

Efficient Multi-Query Bi-Objective Search via Contraction Hierarchies

通过收缩层次结构进行高效的多查询双目标搜索

DOI：
发表时间：
2023
期刊：
International Conference on Automated Planning and Scheduling (ICAPS
影响因子：
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
期刊：
Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS
影响因子：
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
期刊：
Artif. Intell.
影响因子：
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]

多目标最短路径问题的启发式搜索方法：进展和研究机会 [调查轨道]