Conjunctive Representations in Contingent Planning: Prime Implicates Versus Minimal CNF Formula

Authors

  • Son To New Mexico State University
  • Tran Son New Mexico State University
  • Enrico Pontelli New Mexico State University

DOI:

https://doi.org/10.1609/aaai.v25i1.8015

Abstract

This paper compares in depth the effectiveness of two conjunctive belief state representations in contingent planning: prime implicates and minimal CNF, a compact form of CNF formulae, which were initially proposed in conformant planning research (To et al. 2010a; 2010b). Similar to the development of the contingent planner CNFct for minimal CNF (To et al. 2011b), the present paper extends the progression function for the prime implicate representation in (To et al. 2010b) for computing successor belief states in the presence of incomplete information to handle non-deterministic and sensing actions required in contingent planning. The idea was instantiated in a new contingent planner, called PIct, using the same AND/OR search algorithm and heuristic function as those for CNFct. The experiments show that, like CNFct, PIct performs very well in a wide range of benchmarks. The study investigates the advantages and disadvantages of the two planners and identifies the properties of each representation method that affect the performance.

Downloads

Published

2011-08-04

How to Cite

To, S., Son, T., & Pontelli, E. (2011). Conjunctive Representations in Contingent Planning: Prime Implicates Versus Minimal CNF Formula. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 1023-1028. https://doi.org/10.1609/aaai.v25i1.8015

Issue

Section

Reasoning about Plans, Processes and Actions