Distance Estimates for Planning in the Discrete Belief Space

We present a general framework for studying heuristics for planning in the belief space. Earlier work has focused on giving implementations of heuristics that work well on benchmarks, without studying them at a more analytical level. Existing heuristics have evaluated belief states in terms of their cardinality or have used distance heuristics directly based on the distances in the underlying state space. Neither of these types of heuristics is very widely applicable: often goal belief state is not approached through a sequence of belief states with a decreasing cardinality, and distances in the state space ignore the main implications of partial observability