Optimal Sensor Selection for Binary Detection based on Stochastic Submodular Optimization

We address the problem of selecting sensors for the estimation of binary random variables, so as to minimize the probability of error. This problem arises when a large number of sensors are potentially available, but only a few can actually be used for estimation purposes. While sensor selection is a combinatorial problem, we show that the optimization of an upper bound on the probability of error can be formulated as a submodular maximization for which computationally efficient algorithms can provide solutions with guaranteed performance. The submodular optimization that needs to be solved involves the computation of an expected value that generally cannot be computed in closed form, but we show that replacing the expected value by a Monte Carlo empirical mean can result in negligible loss of performance with high probability. We illustrate the use of these results in the context of detecting illegal unreported and unregulated (IUU) fishing.