Exploiting Submodular Value Functions for Faster Dynamic Sensor Selection

A key challenge in the design of multi-sensor systems is the efficient allocation of scarce resources such as bandwidth, CPU cycles, and energy, leading to the dynamic sensor se-lection problem in which a subset of the available sensors must be selected at each timestep. While partially observ-able Markov decision processes (POMDPs) provide a natural decision-theoretic model for this problem, the computational cost of POMDP planning grows exponentially in the num-ber of sensors, making it feasible only for small problems. We propose a new POMDP planning method that uses greedy maximization to greatly improve scalability in the number of sensors. We show that, under certain conditions, the value function of a dynamic sensor selection POMDP is submod-ular and use this result to bound the error introduced by per-forming greedy maximization. Experimental results on a real-world dataset from a multi-camera tracking system in a shop-ping mall show it achieves similar performance to existing methods but incurs only a fraction of the computational cost, leading to much better scalability in the number of cameras