On the Effectiveness of CNF and DNF Representations in Contingent Planning

To, Son Thanh; Pontelli, Enrico; Son, Tran Cao

doi:10.5591/978-1-57735-516-8/IJCAI11-339

On the Effectiveness of CNF and DNF Representations in Contingent Planning

Son Thanh To, Enrico Pontelli, Tran Cao Son

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2033-2037.

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.

Son Thanh To, Enrico Pontelli, and Tran Cao Son. 2011. On the Effectiveness of CNF and DNF Representations in Contingent Planning. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2033–2037. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-339

@inproceedings{ijcai2011p339,
  title     = {On the Effectiveness of CNF and DNF Representations in Contingent Planning},
  author    = {To, Son Thanh and Pontelli, Enrico and Son, Tran Cao},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2033--2037},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-339},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-339},
}

TY  - CPAPER
TI  - On the Effectiveness of CNF and DNF Representations in Contingent Planning
AU  - To, Son Thanh
AU  - Pontelli, Enrico
AU  - Son, Tran Cao
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2033
EP  - 2037
DO  - 10.5591/978-1-57735-516-8/IJCAI11-339
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-339
ER  -