---
title: "On the Effectiveness of CNF and DNF Representations in Contingent Planning"
authors:
  - "Son Thanh To"
  - "Enrico Pontelli"
  - "Tran Cao Son"
doi: "10.5591/978-1-57735-516-8/IJCAI11-339"
url: "https://ijcai.org/proceedings/2011/339"
pdf: "https://ijcai.org/proceedings/2011/0339.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "2033-2037"
track: ""
keywords:
---

# On the Effectiveness of CNF and DNF Representations in Contingent Planning

Son Thanh To, Enrico Pontelli, Tran Cao Son

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 2033-2037. DOI: [10.5591/978-1-57735-516-8/IJCAI11-339](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-339)

## 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 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.