  In this paper, we focus on activating only a few sensors, among many
available, to estimate the state of a stochastic process of interest. This
problem is important in applications such as target tracking and simultaneous
localization and mapping (SLAM). It is challenging since it involves stochastic
systems whose evolution is largely unknown, sensors with nonlinear
measurements, and limited operational resources that constrain the number of
active sensors at each measurement step. We provide an algorithm applicable to
general stochastic processes and nonlinear measurements whose time complexity
is linear in the planning horizon and whose performance is a multiplicative
factor 1/2 away from the optimal performance. This is notable because the
algorithm offers a significant computational advantage over the polynomial-time
algorithm that achieves the best approximation factor 1/e. In addition, for
important classes of Gaussian processes and nonlinear measurements corrupted
with Gaussian noise, our algorithm enjoys the same time complexity as even the
state-of-the-art algorithms for linear systems and measurements. We achieve our
results by proving two properties for the entropy of the batch state vector
conditioned on the measurements: a) it is supermodular in the choice of the
sensors; b) it has a sparsity pattern (involves block tri-diagonal matrices)
that facilitates its evaluation at each sensor set.
