Distance estimates for planning in the discrete belief space

Abstract

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. To remedy these problems we present a family of admissible, increasingly accurate distance heuristics for planning in the belief space, parameterized by an integer n. We show that the family of heuristics is theoretically robust: it includes the simplest heuristic based on the state space as a special case and as a limit the exact distances in the belief space.