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.

Faculty: Lisa Hellerstein, Thomas Lidbetter

**Publications**** **

**A Tight Bound for Stochastic Submodular Cover**

L. Hellerstein, D. Kletenik, S. Parthasarathy

Journal of Artificial Intelligence Research 71:347-370, 2021.**A****Polyhedral Approach to Some Max-Min Problems**

L. Hellerstein, T. Lidbetter

CoRR Technical Report arXiv:2104.10236, 2021.**A General Framework for Approximating****Min-Sum Ordering Problems**

F. Happach, L. Hellerstein, T. Lidbetter

CoRR Technical Report arXiv:2004.05954, 2020.**The Largest-Z-ratio-First algorithm is 0.8531-Approximate for Scheduling Unreliable Jobs on Parallel Machines**

A. Agnetis and T. Lidbetter

Operations Research Letters, 48(4):405-409, 2020.**A Search Game on a Hypergraph with Booby Traps**

T. Lidbetter and K.Y. Lin

Theoretical Computer Science, 821:57-70, 2020.**Search and Rescue in the Face of Uncertain Threats**

T. Lidbetter

European Journal of Operational Research, 285(3):1153-1160, 2020.

**Acknowledgments**** **

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.