Minimum-Cost Strategies for Sequential Search and Evaluation

Many problems in intelligent systems involve an agent carrying out sequential tasks. For example, a robot may have the objective of locating an improvised explosive device (IED) hidden in one of many locations. A machine might perform tests on a computer chip to classify the chip as working or faulty. It is often important for the agent to have the capability to use real time data to adapt their behavior. 

This project addresses fundamental search and evaluation problems aimed at reducing incurred cost or time. Surprisingly little is known about some of these problems. The search problems are concerned with locating targets hidden within some finite set of locations, possibly in a network environment. The evaluation problems concern the ordering of a sequence of tests (queries) with binary outcomes, used to perform classification or diagnosis. The problems are addressed in two settings. In the first, uncertainty about the location of targets (test outcomes) is modeled by a known probability distribution, and the goal is to minimize expected cost for the distribution. In the second, the targets are assumed to be placed 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. 

Project Participants

Faculty:  Lisa Hellerstein, Thomas Lidbetter



This material is based upon work supported in part by the National Science Foundation under Grants 1909335 and 1909446. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.