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

Rutgers University Newark, Newark NJ

Investigators

Abstract

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.