A generic approach to planning in the presence of incomplete information: Theory and implementation

This paper proposes a generic approach to planning in the presence of incomplete information. The approach builds on an abstract notion of a belief state representation, along with an associated set of basic operations. These operations facilitate the development of a sound and complete transition function, for reasoning about effects of actions in the presence of incomplete information, and a set of abstract algorithms for planning. The paper demonstrates how the abstract definitions and algorithms can be instantiated in three concrete representations—minimal-DNF, minimal-CNF, and prime implicates—resulting in three highly competitive conformant planners: Dnf, Cnf, and PIP. The paper relates the notion of a representation to that of ordered binary decision diagrams, a well-known belief state representation employed by many conformant planners, and several target compilation languages that have been presented in the literature. The paper also includes an experimental evaluation of the planners Dnf, Cnf, and PIP and proposes a new set of conformant planning benchmarks that are challenging for state-of-the-art conformant planners.