Generalized 3-Valued Belief States in Conformant Planning

The high complexity of planning with partial observability has motivated to find compact representations of belief state (sets of states) that reduce their size exponentially, including the 3-valued literal-based approximations by Baral et al. and tag-based approximations by Palacios and Geffner. We present a generalization of 3-valued literal-based approximations, and an algorithm that analyzes a succinctly represented planning problem to derive a set of formulas the truth of which accurately represents any reachable belief state. This set is not limited to literals and can contain arbitrary formulas. We demonstrate that a factored representation of belief states based on this analysis enables fully automated reduction of conformant planning problems to classical planning, bypassing some of the limitations of earlier approaches.