On the Effectiveness of CNF and DNF Representations in Contingent Planning
Son Thanh To, Enrico Pontelli, Tran Cao Son
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 CNFct, 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 CNFct and DNFct [To et al., 2011] and proposes a new heuristic function for both planners. The experiments demonstrate that both CNFct and DNFct 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 identifies properties of the representation schemes that can affect their performance on different problems.