On the Effectiveness of CNF and DNF Representations in Contingent Planning
Son To, Enrico Pontelli and Son Tran
This paper investigates the effectiveness of alternative state representations in contingent planning. The work builds on the recently proposed ideas, from conformant planning research, of encoding belief states using compact representations in disjunctive and conjunctive normal form formulae. The conformant planning research defined complete transition functions for computing successor belief states in the presence of incomplete information for these state representations. The present paper extends such functions to handle non-deterministic and sensing actions in the AND/OR forward search paradigm for contingent planning solutions. The ideas have been deployed in two contingent planners, CNFct and DNFct, using the same heuristic functions. The important role of representations in contingent planning is confirmed by the fact that both CNFct and DNFct offer competitive performance in a large range of benchmarks, even with a simple heuristic function. Furthermore, our experiments demonstrate that 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 classes of problems.