  Decision making under uncertainty is at the heart of any autonomous system
acting with imperfect information. The cost of solving the decision making
problem is exponential in the action and observation spaces, thus rendering it
unfeasible for many online systems. This paper introduces a novel approach to
efficient decision-making, by partitioning the high-dimensional observation
space. Using the partitioned observation space, we formulate analytical bounds
on the expected information-theoretic reward, for general belief distributions.
These bounds are then used to plan efficiently while keeping performance
guarantees. We show that the bounds are adaptive, computationally efficient,
and that they converge to the original solution. We extend the partitioning
paradigm and present a hierarchy of partitioned spaces that allows greater
efficiency in planning. We then propose a specific variant of these bounds for
Gaussian beliefs and show a theoretical performance improvement of at least a
factor of 4. Finally, we compare our novel method to other state of the art
algorithms in active SLAM scenarios, in simulation and in real experiments. In
both cases we show a significant speed-up in planning with performance
guarantees.
