Randomized sensing in adversarial environments
Andreas Krause, Alex Roper, Daniel Golovin · 2011
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. 1