Randomized Sensing in Adversarial Environments
Andreas Krause, Alex Roper and Daniel Golovin
How should we manage a sensor network to optimally 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 algorithm which guarantees near-optimal randomized sensing strategies whenever the detection performance for any fixed adversarial strategy satisfies submodularity, an intuitive diminishing returns property. Our approach builds on techniques from game theory and 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 UAVs). We empirically evaluate our algorithms on two real-world sensing problems.