Conformant Planning at KLAP, CS, NMSU
Overview: This page contains information about several conformant planning systems developed by members of the Knowledge representation, Logic, and Advanced Programming Laboratory (KLAP) at the Computer Science Department, New Mexico State University, since 2005.
Conformant Planning Systems Based on Approximation
 |
Description: The basic idea of the approach lies in the use of approximation reasoning, in particular the so called 0-approximation, in the search for a conformant plan. This reduces the size of the state-space from 2^{2^n} to 3^n. The original paper, "Conformant Planning for Domains with Constraints - A New Approach," describes this approach is authored by Tran Cao Son, Phan Huy Tu, Michael Gelfond, and Ricardo Morales and was presented at the AAAI conference, 2005. The paper can be downloaded in PDF format. The name CpA stands for "Conformant Planning using Approximantion." CpA differs from other conformant planners in that it can work with domain constraints (also known as static causal laws in the literature). Due to its use of approximation, CpA is incomplete. A counterpart of CpA in logic programming is described in the paper "An Approximation of Action Theories and Its Application to Conformant Planning," and is presented at LPNMR 2005 (see PDF). The AIJ paper "Approximation of Action Theories and Its Application to Conformant Planning," by Phan Huy Tu, Tran Cao Son, Michael Gelfond, and A. Ricardo Morales (Artificial Intelligence, Volume 175, Issue 1, January 2011, Pages 79-119) ScienceDirect Link provides a complete description about the technical and implementation details of CpA. |
| Because CpA is incomplete and would have memory issue when the initial belief state is large and cannot be approximated (to be precise, approximation renders the problem unsolvable), we investigate different methods for improving performance and scalability of CpA. |
Reduction and Goal Splitting Techniques
Because the size of the initial belief state is (quite often) very large and the 0-approximation does not consider the interactions between system variables (or fluents), CpA does not perform well in several conformant planning benchmarks proposed in the International Planning Competition. CpA also employs a very simple heuristic (the number of satisfied subgoals). We developed CpA(C) and CpA(H) to address this issue. Both planners differ from CpA in the following: |
Both are complete for domains without static causal laws (a.k.a. domain constraints). |
|
Both implement the oneof-combination to reduce the size of the initial belief state whenever it is possible. |
|
Both use goal splitting to solve large problems whenever the technique is applicable. |
|
CpA(H) won the Best Non-Observable Non-Determinicstic Planner award at the IPC 2008 |
|
Vien Tran, Khoi Nguyen, Tran Cao Son, Enrico Pontelli: A conformant planner based on approximation: CpA(H). ACM TIST 4(2): 36 (2013) |
|
Dang-Vien Tran, Hoang-Khoi Nguyen, Enrico Pontelli, Tran Cao Son. Improving Performance of Conformant Planners: Static Analysis of Declarative Planning Domain Specifications. PADL 2009: 239-253. (The ACM TIST paper is a revised and extended version of this paper) |
|
Download code: CpA(H) binary and scripts. To run the system with PDDL inputs, you will need to have Sicstus- or SWI-Prolog. The input files for all planners (CpA, CFF, KACMBP, POND, T0) mentioned in the paper can be downloaded here (big tar file). |
Incremental Computation of Belief States
The second method that we developed to achieve the completeness of CpA relies on the observation that belief states can, in most cases, be represented by compact formulae and processed efficiently. We therefore investigated several representations of belief states (DNF, CNF, Prime Implicate) and developed several conformant planners that perform extremely well. The results of this research direction are published in the following papers: |
Son Thanh To, Tran Cao Son, Enrico Pontelli: A generic approach to planning in the presence of incomplete information: Theory and implementation. Artif. Intell. 227: 1-51 (2015). The system DNF-Conformant Planner is used in the experiments described in this paper. In this paper, we proposed an abstract notion of a representation for belief states and defined the basic operators over a representation that can be used as the building blocks for the definition of a transition function in domains with incomplete information. |
|
Son Thanh To, Tran Cao Son, and Enrico Pontelli. Conjunctive Representations in Contingent Planning: Prime Implicates vs. Minimal CNF Formula. Proc. of the 25th AAAI Conference on Artificial Intelligence (AAAI), 2011. The two systems CNF/PI-Contingent Planner and benchmarks are used in the experiments described in this paper. |
|
Son Thanh To, Enrico Pontelli, and Tran Cao Son. On the Effectiveness of CNF and DNF Representations in Contingent Planning. In Proc. of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), 2011. The code for the planner described in this paper is DNF-Contingent Planner. |
|
Son Thanh To, Tran Cao Son, and Enrico Pontelli. Contingent Planning as And/Or forward Search with Disjunctive Representation. In Proc. of the 21th International Conference on Automated Planning and Scheduling (ICAPS), 2011. The code for the system used in the experiment of this paper is the DNF-Contingent Planner. |
|
Son Thanh To, Enrico Pontelli, and Tran Cao Son. A Conformant Planner with Explicit Disjunctive Representation of Belief States. In Proc. of ICAPS-2009. This system is the first developed in this research direction and used in the paper submitted to AIJ. |
Conformant Planning using Classical Planners
Parallel to the exploration of the conformant planners using approximation and incremental computation, we developed conformant planners using classical planners. It turns out that by combining our reduction technique with classical planners, we can create a conformant planner with exceptional coverage and efficiency. The results of this research direction are published in the following papers. |
Khoi Nguyen, Vien Tran, Tran Cao Son, Enrico Pontelli. On Improving Conformant Planners by Exploiting Domain-Structures. AAAI, 2011. |
|
Khoi Nguyen, Vien Tran, Tran Cao Son, Enrico Pontelli. On Computing Conformant Plans Using Classical Planners: A Generate-And-Complete Approach. ICAPS 2012. (Best Student Paper Award) |
|
System: GC-LAMA - described in the ICAPS 2012 paper and also used in the AAAI 2011 paper Source Code. |