权益分类	功能权益	普通用户	{{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.

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

项目成果

期刊论文数量（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]

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