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

RI: Small: Collaborative Research: Minimum-Cost Strategies for Sequential Search and Evaluation

RI：小型：协作研究：顺序搜索和评估的最低成本策略

基本信息

批准号：
1909446
负责人：
Thomas Lidbetter
金额：
$ 14.18万
依托单位：
Rutgers University Newark
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-08-01 至 2023-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909446&HistoricalAwards=false
关键词：
RI Small Collaborative Research Minimum

项目摘要

In many situations, tasks are performed sequentially. For example, a robot searching a building for a hidden bomb will search room by room, in some order, until the bomb is found. An automated medical diagnosis procedure might first perform one medical test, observe its outcome, then perform another test, and so forth, until the diagnosis becomes clear. It is becoming increasingly important to improve the way intelligent systems operate in these types of situations. This project will develop algorithms and software that systems can use to determine the order in which to perform tasks, so as to minimize costs incurred or time spent. Because the outcomes of tasks are often unknown until the tasks are performed, the algorithms will be designed to enable systems to quickly make dynamic decisions, based on new information obtained as tasks are performed. In addition to the robot search and medical diagnosis applications described above, this project has applications to many other areas, including determining network connectivity, quality testing of manufactured products, and evaluating database queries. The project will provide research opportunities to graduate and talented undergraduate students, and the researchers will engage in outreach activities, both at the college and K-12 levels, to students in groups that are under-represented in computer science.The project research will focus on fundamental sequential ordering problems for search and evaluation in two settings. In the first setting, uncertainty about outcomes is modeled by a known probability distribution, and the goal is to minimize expected cost for the distribution. In the second, outcomes are determined by an adversary. Here a robust solution is desired, which minimizes expected cost in the worst case. This is equivalent to regarding the problem as a zero-sum game. In either setting, the search environment could be a discrete set of locations or it could have a more complex network structure. The project will bring together approaches from algorithms, machine learning and game theory. Central goals are as follows: (1) Developing intelligent and adaptable search and evaluation policies that have good theoretical guarantees and can be easily implemented and deployed in practice, (2) Developing algorithmic techniques that will constitute an algorithmic toolkit for researchers working on search and evaluation problems, and (3) Integrating insights and techniques from different areas to give unified approaches to solving broad classes of related problems.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.

在许多情况下，任务是按顺序执行的。例如，在建筑物中搜索隐藏炸弹的机器人将按一定顺序逐个房间搜索，直到找到炸弹。自动医疗诊断程序可能首先执行一项医疗测试，观察其结果，然后执行另一项测试，以此类推，直到诊断变得清晰。改进智能系统在此类情况下的运行方式正变得越来越重要。该项目将开发算法和软件，系统可以使用它们来确定执行任务的顺序，从而将所产生的成本或花费的时间降至最低。由于在执行任务之前，任务的结果通常是未知的，因此算法的设计将使系统能够根据执行任务时获得的新信息，快速做出动态决策。除了上述机器人搜索和医疗诊断应用程序外，该项目还应用于许多其他领域，包括确定网络连接、制造产品的质量测试和评估数据库查询。该项目将为研究生和有才华的本科生提供研究机会，研究人员将在大学和K-12水平上向计算机科学中代表性不足的群体的学生开展外联活动。该项目研究将集中在两个背景下用于搜索和评估的基本顺序排序问题。在第一个设置中，结果的不确定性由已知的概率分布建模，目标是最小化分布的预期成本。在第二种情况下，结果由对手决定。这里需要一个健壮的解决方案，在最坏的情况下将预期成本降到最低。这相当于将问题视为零和博弈。在任一设置中，搜索环境可以是一组离散的位置，也可以具有更复杂的网络结构。该项目将汇集算法、机器学习和博弈论的方法。中心目标如下：(1)开发具有良好理论保证且易于在实践中实施和部署的智能和适应性搜索和评估政策；(2)开发算法技术，为致力于搜索和评估问题的研究人员提供算法工具包；以及(3)整合不同领域的见解和技术，给出统一的方法来解决广泛类别的相关问题。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。