Abstract
This paper investigates the effectiveness of two state representations, CNF and DNF, in contingent planning. To this end, we developed a new contingent planner, called C NFct , using the AND/OR forward search algorithm PrAO [To et al., 2011] and an extension of the CNF representation of [To et al., 2010] for conformant planning to handle nondeterministic and sensing actions for contingent planning. The study uses C NFct and D NFct [To et al., 2011] and proposes a new heuristic function for both planners. The experiments demonstrate that both C NFct and D NFct offer very competitive performance in a large range of benchmarks but neither of the two representations is a clear winner over the other. The paper identi?es properties of the representation schemes that can affect their performance on different problems.