We investigate state-space abstraction methods for computing approximate probabilities with Bayesian networks. These methods approximate Bayesian networks by aggregating the states of variables. We implement an iterative approximation procedure based on this idea, and the procedure demonstrates the desirable anytime property in experiments. Further theoretical analysis reveals special properties of the approximations, and we exploit these properties to design heuristics for improving performance profiles of the iterative procedure.
