A dynamic programming algorithm for finding an optimal sequence of
  informative measurements
  An informative measurement is the most efficient way to gain information
about an unknown state. We give a first-principles derivation of a
general-purpose dynamic programming algorithm that returns an optimal sequence
of informative measurements by sequentially maximizing the entropy of possible
measurement outcomes. This algorithm can be used by an autonomous agent or
robot to decide where best to measure next, planning a path corresponding to an
optimal sequence of informative measurements. The algorithm is applicable to
states and controls that are continuous or discrete, and agent dynamics that is
either stochastic or deterministic; including Markov decision processes and
Gaussian processes. Recent results from approximate dynamic programming and
reinforcement learning, including on-line approximations such as rollout and
Monte Carlo tree search, allow the measurement task to be solved in real-time.
The resulting solutions include non-myopic paths and measurement sequences that
can generally outperform, sometimes substantially, commonly used greedy
approaches. This is demonstrated for a global search problem, where on-line
planning with an extended local search is found to reduce the number of
measurements in the search by approximately half. A variant of the algorithm is
derived for Gaussian processes for active sensing.
