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

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

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.