Abstract
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 RS ENSE, an ef?cient algorithm which guarantees near-optimal randomized sensing strategies whenever the detection performance satis?es submodularity, a natural diminishing returns property, for any ?xed adversarial scenario. Our approach combines techniques from game theory with submodular optimization. The RS ENSE 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.