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

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

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.