Title: Randomized sensing in adversarial environment

Authors: A. Krause, A. Roper, and D. Golovin


How should we manage a sensor network to opti- mally guard security-critical infrastructure? How should we coordinate search and rescue helicopters to best locate survivors after a major disaster? In both applications, we would like to control sensing resources in uncertain, adversarial environments. In this paper, we introduce RSENSE, an efficient algo- rithm which guarantees near-optimal randomized sensing strategies whenever the detection perfor- mance satisfies submodularity, a natural diminishing returns property, for any fixed adversarial scenario. Our approach combines techniques from game the- ory with submodular optimization. The RSENSE algorithm applies to settings where the goal is to manage a deployed sensor network or to coordinate mobile sensing resources (such as unmanned aerial vehicles). We evaluate our algorithms on two real– world sensing problems.

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale