On the Effectiveness of CNF and DNF Representations in Contingent Planning

1 Introduction

Contingent planning [Peot and Smith, 1992] is the task of generating conditional plans in the presence of incomplete information, uncertain action effects, and sensing actions. A contingent plan guides the agent to act conditionally to achieve the goal from every possible initial state of the world and independent from the actual action effects. Contingent planning has been known as one of the hardest problems in planning [Baral et al., 2000; Rintanen 2004].

One of the most common and successful approaches to contingent planning is to transform it into an AND/OR search problem in the belief state space. Significant progress in this direction has been made as state-of-the-art contingent planners (e.g., MBP [Bertoli et al., 2006], POND [Bryce et al., 2006], and contingent-FF [Hoffmann and Brafman, 2005]) can solve problems of large size at different levels of hardness. However, these planners cannot scale up well, mostly due to the underlying belief state representation they employed. For example, the representation using binary decision diagrams (BDDs) [Bryant, 1992], used in MBP and POND, is usually very large and sensitive to the order of the variables; furthermore, computing the successor belief state in BDD representation is expensive as it requires intermediate formulae of exponential size. On the other hand, the implicit representation of belief states used in contingent-FF through the action sequences that lead to them from the initial belief state incurs an excessive amount of repeated computation. Moreover, checking whether a proposition holds after the execution of even one single action is co-NP complete.

Later, [Albore, Palacios, and Geffner, 2009] introduced a new approach, that transforms a contingent problem into a search problem in the state space, whose literals represent the beliefs over the original problem, assuming that the uncertainty lies only in the initial world. This method is more efficient as their planner CLG is capable of solving harder problems of larger size. However, the number of literals in the translated problem can be exponential in the number of unknown literals in the original problem, making the state space extremely large and preventing the planner to scale up. Furthermore, CLG does not consider non-deterministic actions.

Recently, in [To et al., 2011], we introduced a new approach to contingent planning which relies on DNF, the belief state representation developed in [To et al., 2009] for conformant planning. We extended DNF to handle non-deterministic and sensing actions and developed a new AND/OR forward search algorithm, called PrAO, for contingent planning. The resulting planner, called DNFct, outperforms other state-of-the-art contingent planners on most benchmarks in term of both execution time and scalability on the size of problems. However, we observed that the performance of DNFct is not as good on the problems where the size of disjunctive formulae encoding the belief states is too large. In some cases, the planner even hardly starts the search due to large size of the formula encoding the initial belief state. This raises the question of whether a CNF representation of belief states would yield a planner with better scalability.

The goal of this paper is first to address the above question. We begin with the development of a new contingent planner, called CNFct, which employs the CNF representation of belief states for conformant planning [To et al., 2010]. This requires an extension of the transition function developed in that paper to handle non-deterministic and sensing actions for contingent planning. To facilitate the comparisons on belief state representation, we implement CNFct using the same AND/OR forward search algorithm PrAO and propose a new heuristic scheme to use in this paper for both CNFct and DNFct. We also evaluate CNFct against other state-of-the-art contingent planners besides DNFct. The experiments show that CNFct performs reasonably well comparing to DNFct and is better than other planners in many problems. Afterwards, we investigate the effectiveness of the two representations of belief states in contingent planning by identifying their properties and criteria that affect the performance over different classes of problems. The results of this investigation support our empirical evaluation which shows that neither of the two representations dominates the other across all problems.

2 Background: Contingent Planning

A contingent planning problem is a tuple P = 〈F,A,Ω, I,G〉, where F is a set of propositions, A is a set of actions, Ω is a set of observations (sensing actions), I describes the initial state, and G describes the goal. A and Ω are separate, i.e., A ∩ Ω = ∅. A literal is either a proposition p ∈ F or its negation ¬p. ¯ ℓ denotes the complement of a literal ℓ-i.e., ¯ ℓ = ¬ℓ, where ¬¬p=p for p∈F. For a set of literals L, L = { ¯ ℓ | ℓ ∈ L}. We will often use a set of literals to represent a conjunction of literals.

A set of literals X is consistent (resp. complete) if for every p∈F, {p, ¬p}̸⊆X (resp. {p, ¬p}∩X̸=∅). A state is a consistent and complete set of literals. A belief state is a set of states. We will often use lowercase (resp. uppercase) letter to represent a state (resp. a belief state).

Each action a in A is a tuple 〈pre(a), O(a)〉, where pre(a) is a set of literals indicating the preconditions of action a and O(a) is a set of action outcomes. Each o(a) in O(a) is a set of conditional effect of the form ψ → ℓ (also written as oi : ψ → ℓ), where ψ is a set of literals and ℓ is a literal. If |O(a)| > 1 then a is non-deterministic. O(a) is mutual exclusive, i.e., the execution of a makes one and only one outcome in O(a) occurs. However, which outcome that occurs is uncertain. Each observation ω in Ω is a tuple 〈pre(ω), ℓ(ω)〉, where pre(ω) is the preconditions of ω (a set of literals) and ℓ(ω) is a literal.

A state s satisfies a literal ℓ (s |= ℓ) if ℓ ∈ s. s satisfies a conjunction of literals X (s |= X) if X ⊆ s. The satisfaction of a formula in a state is defined in the usual way. Likewise, a belief state S satisfies a literal ℓ, denoted by S |= ℓ, if s |= ℓ for every s ∈ S. S satisfies a conjunction of literals X, denoted by S |= X, if s |= X for every s ∈ S.

Given a state s, an action a is executable in s if s|=pre(a). The effect of executing a in s w.r.t. an outcome oi is

Let res(oi, s) = s\e(oi, s)∪e(oi, s). The transition function maps an action and a belief state to a belief state, defined as Φ(a, S) = {res(oi, s) | s ∈ S, oi ∈ O(a)} if S ̸= ∅ and S |= pre(a); Φ(a, S) = undefined, otherwise.

Example 1. Consider a domain F = {alive}, a singleton belief state S = {{alive}}, an action shoot with pre(shoot) = {true} and O(shoot) = {o1, o2}, where o1 = {∅ → alive} and o2 = {∅ → ¬alive}. One can easily compute: res(o1, {alive}) = {alive}, and res(o2, {alive}) = {¬alive}. Hence, Φ(shoot, S) = {{alive}, {¬alive}}.

Observe that, in Example 1, the non-deterministic action shoot causes the certain belief state S to become uncertain.

Let ω be an observation in Ω; we define S+ ω = {s | s ∈ S, s |= ℓ(ω)} and Sω = {s | s ∈ S, s |= ℓ(ω)}.

Given a contingent planning problem P , a structure T constructed from the actions and observations of P is said to be a transition tree of P if

• T is empty, denoted by [], or T = a, where a ∈ A; or
• T = a ◦ T ′ , where a ∈ A and T ′ is a non-empty transition tree; or
• T = ω(T +|T -), where ω ∈ Ω and T + and T - are transition trees.

Intuitively, a transition tree represents a conditional plan, as defined in the literature, and can be represented as an AND/OR graph whose nodes are belief states and links are AND/OR-edges. A precise definition is given in the next section. Let us denote undefined by ⊥. The result of the execution of a transition tree T in a belief state S, denoted by ̂Φ(T, S), is a set of belief states defined as follows:

• If S = ⊥ or S = ∅ ∧ T ̸= [] then ̂Φ(T, S) = ⊥; else
• If S ̸= ∅ then ̂Φ([], S) = {S}, else ̂Φ([], ∅) = ∅; else
• If T = a, a ∈ A, then ̂Φ(a, S) = {Φ(a, S)}; else
• If T = a◦T ′ , a ∈ A, then ̂Φ(T, S) = ̂Φ(T ′ , Φ(a, S)); else
• If T = ω(T +|T -) then ̂Φ(T, S) = ̂Φ(T +, S+ ω ) ∪ ̂Φ(T -, Sω ) if S |= pre(ω), and ̂Φ(T, S) = ⊥ otherwise.

Note that the definition of ̂Φ allows the application of an observation ω in a belief state where ℓ(ω) is known, if the subtree of the resulting empty belief state is empty.

Let SI be the set of all possible states satisfying the initial description I. A transition tree T is said to be a solution of P if every belief state in ̂Φ(T, SI) satisfies the goal G.

Example 2. We have an agent A and a bomb B, whose location is unknown in a house with two rooms. A can move around and disarm B if they are in the same room. A can sense whether B is in the same room. The problem P is given as F = {sameR(A, B), safe}, A = {move, disarm(B)}, Ω = {sense(B)}, I = ¬safe, and G = safe; where move = (true, {sameR(A,B)→¬sameR(A,B), ¬sameR(A,B)→sameR(A,B)}), disarm(B) = (sameR(A,B), {true→safe}), and ℓ(sense(B)) = sameR(A,B). A solution tree for the problem is "sense(B)(disarm(B) | move ◦ disarm(B))". (Fig. 1).

3 CNF/DNF Representations of Belief States

We will first review several notions of the CNF representation for conformant planning in [To et al., 2010]. We then extend it to deal with non-deterministic actions and observations for contingent planning, in addition to incomplete information.

A clause is a set of fluent literals. A clause is trivial if it contains the set {f, ¬f} for some fluent f. A CNF formula is a set of clauses. A literal ℓ is in a CNF formula ϕ, denoted by ℓ ∈ ϕ, if there exists a clause α ∈ ϕ such that ℓ ∈ α. A unit clause is a singleton set, i.e. it contains only one literal which is called unit literal. A clause α subsumes a clause β if α ⊂ β. A clause is subsumed by a CNF formula if it is subsumed by some clause in the formula. A CNF formula can be simplified by removing the subsumed clauses from it.

A CNF-formula ϕ is called a CNF-state if

• ϕ does not contain a trivial clause;
• ϕ does not contain two clauses γ and δ such that γ subsumes δ; and
• for every unit clause {ℓ} in ϕ, ℓ ̸∈ ϕ.

A set of CNF-states is called a CNF-belief state.

In this paper, by r(.), we denote a function that maps a CNF-formula to an equivalent CNF-state. A literal ℓ (resp. a set of literals γ) is true in a CNF-state ϕ if ϕ |= ℓ (resp. ϕ |= ℓ for every ℓ ∈ γ), where |= denotes the standard entailment relation. Also, by ϕℓ (resp. ϕ¯ ℓ) we denote the set of clauses in ϕ which contain ℓ (resp. ¯ ℓ). Let ϕ be a CNF formula and ℓ be a literal. By ϕ - ℓ we denote the CNF formula obtained by removing every occurrence of ℓ from ϕ.

For two CNF formulae ϕ = {α1, . . . , αn} and ψ = {β1, . . . , βm}, the cross-product of ϕ and ψ, denoted by ϕ×ψ, is the CNF-formula defined by {αi∪βj | αi ∈ ϕ, βj ∈ ψ}. The reduced-cross-product of ϕ and ψ, denoted by ϕ⊗ψ, is the CNF-state defined by ϕ⊗ψ = r(ϕ×ψ). If either ϕ or ψ is empty then ϕ × ψ = ϕ ⊗ ψ = ∅.

Note that ϕ ⊗ ψ = ψ ⊗ ϕ ≡ ϕ ∨ ψ. For a set of CNF formulae Ψ = {ϕ1, . . . , ϕn}, ⊗[Ψ] denotes ϕ1 ⊗ ϕ2 ⊗ . . . ⊗ ϕn, a CNF-state equivalent to ∨ni=1 ϕi.

Given a CNF-state ϕ, we define the function Update which encodes the CNF-state after the execution of an action, that causes a literal ℓ to be true, in ϕ as follows.

Let ϕ be a CNF-state and ℓ a literal. The update of ϕ by ℓ, denoted by Update(ϕ, ℓ), is defined by:

• If ℓ is a unit clause in ϕ then Update(ϕ, ℓ) = ϕ. ¯

¯

• If ℓ is a unit clause in ϕ, then Update(ϕ, ℓ) = (ϕℓ) ∧ ℓ.
• Otherwise

¯

Update(ϕ, ℓ) = r((ϕ\(ϕℓ ∪ϕ¯ ℓ)) ∧ ℓ ∧ (ϕℓ -ℓ)×(ϕ¯ ℓ - ℓ)) Given a consistent set of literals L, we denote Update(ϕ, ∅) = ϕ and Update(ϕ, L) = Update(Update(ϕ, ℓ), L \ {ℓ}) for any ℓ ∈ L if L ̸= ∅.

Let ϕ be a CNF-state and γ a consistent set of literals. The enabling form of ϕ w.r.t. γ, denoted by ϕ+γ, is a set of CNF formulae and is defined as

where ¬γ is the clause γ = {¯l | l ∈ γ}, ϕ∧¬γ = ϕ∪{γ}, and ϕ∧ γ = ϕ∪ {{l} | l ∈ γ}.

For a CNF-belief state Ψ, let Ψ + γ = ⋃ϕ∈Ψ(ϕ + γ).

The extension starts from this point as follows:

Definition 1. Let oi be an outcome of action a. A CNF formula ϕ is called enabling for oi if for every conditional effect oi : ψ → ℓ, either ϕ |= ψ or ϕ |= ¬ψ holds.

A set of CNF formulae Ψ is enabling for oi if every CNF formula in Ψ is enabling for oi.

For an outcome oi of action a and a CNF-state ϕ, let enboi (ϕ) = ((ϕ + ψ1) + . . .) + ψk where oi = {ψ1 → ℓ1, . . . , ψk → ℓk}. The effect of a in ϕ if the outcome oi occurs, denoted by e(oi, ϕ), is defined as follows:

Definition 2. Let ϕ be a CNF-state and a be an action. The transition function between CNF-states, denoted by ΦCNF (a, ϕ), is defined as follows:

• ΦCNF (a, ϕ) = ⊗[⋃oi∈O(a) {Update(φ, e(oi, φ)) | φ ∈ enboi (ϕ)}] if ϕ |= pre(a); and
• ΦCNF (a, ϕ) = ⊥ otherwise.

Given a CNF-state ϕ, by BS(ϕ) we denote the belief state represented by ϕ. By definition, for a sensing action ω, the execution of ω in BS(ϕ) results in two disjoint belief states S1 and S2 such that S1 ∪ S2 = BS(ϕ), S1 |= ℓ(ω), and S2 |= ℓ(ω). It is easy to see that S1 ≡ r(ϕ ∧ ℓ(ω)) and S2 ≡ r(ϕ ∧ ℓ(ω)). Thus, the execution of ω in ϕ results in two CNF-states: ϕ+ω = r(ϕ ∧ ℓ(ω)) and ϕ-ω = r(ϕ ∧ ℓ(ω)).

Similarly to the definition of ̂Φ, we can extend ΦCNF to define ̂ ΦCNF , an extended transition function that maps a transition tree and a CNF-state to a set of CNF-states, by replacing each belief state S with its encoding CNF-state ϕ, where, for each observation ω in Ω (last item), ϕ+ω and ϕ-ω play the role of S+ ω and Sω , respectively.

Theorem 1. Let ϕ be a CNF-state and T be a transition tree. Then each belief state in ̂Φ(T,BS(ϕ)) is equivalent to a CNF-state in ̂ ΦCNF(T, ϕ), and each CNF-state in ̂ ΦCNF (T, ϕ) represents a belief state in ̂Φ(T , BS(ϕ)).

̂

The above theorem shows that ΦCNF is equivalent to the complete semantics defined by ̂Φ. Thus, any planner using ̂ ΦCNF in its search for solutions will be sound and complete, provided that the search algorithm is sound and complete.

Instead of using CNF-states to represent belief states, [To et al., 2011] uses DNF-states in the development of DNFct. A partial state is a consistent set of literals. A DNF-state is a set of partial states that does not contain a pair of δ1 and δ2 such that δ1 ⊂ δ2. In developing DNFct, we define the function ΦDNF which is similar to ΦCNF . The definitions leading to the definition of ΦDNF are similar to Definitions 1-2 and are omitted to save space (details are in [To et al., 2011]).

4 Implementation of CNFct

This section describes the implementation of the CNFct. For our comparison, we include a description of the implementation of DNFct. We focus on aspects that help understand better the effectiveness of the CNF and DNF representations employed in CNFct and DNFct respectively. Moreover, DNFct is modified to use the heuristic function implemented in CNFct.

Search Algorithm: As mentioned earlier, CNFct employs the same AND/OR forward search algorithm PrAO [To et al., 2011] as DNFct does. We built CNFct on top of CNF [To et al., 2010]. We modified the implementation of the representation in CNF for non-deterministic and sensing actions.

Heuristics: Both planners employs the same new heuristic function which is based on the number of satisfied subgoals and the number of known literals in the belief state. Let us note that the second component of the heuristic function helps select nodes (CNF-states/DNF-states) of less uncertainty and smaller size in both representations for expansion.

Observe that the use of the same search algorithm and the same heuristic function allows both planners to expand/generate the same sets of nodes (belief states) in the search graph, making the comparison and evaluation of the two representations more accurate.

Data Structure: In DNFct, a partial state is encoded as a dynamic bitset available in the standard library of C++. The size of the bitset is the number of literals in the domain. This encoding usually requires less memory for storing partial states and DNF-states, since each literal in a partial state is represented by one bit. Furthermore, the library contains several efficient bitwise operators necessary for the computation of ΦDNF . DNFct also reduces memory consumption by creating each distinct partial state, needed during the search for solutions, only once, i.e., all identical partial states in different DNF-states are represented by the same dynamic bitset stored in the memory.

In CNFct, since most non-unit clauses contain only two literals as observed in the experiments, each non-unit clause is encoded by a set of integers each of which represents a literal. However, the set of unit literals in each CNF-state is still represented as a bitset. As for DNFct, only distinct clauses (resp. set of unit literals) are created and stored in the memory.

We believe that this data structure scheme is optimal for each representation, making the comparison of the two methods meaningful.

5 Experimental Evaluation

Planners: We compare CNFct with DNFct, CLG, contingentFF, and POND 2.2 on a broad set of benchmarks. These planners are known to be among the best available contingent planners. We also considered MBP planner but it does not perform better than the other planners on most benchmarks. Moreover, due to the limit of the column width of the paper, we do not use MBP in this paper. We executed contingent-FF with both available options (with and without helpful actions) and report the best result for each instance. POND was executed with AO* search algorithm (aostar option). The experiments show that the translation time of CLG can vary in a very wide range (from few to hundreds of seconds) for a same instance. Hence, for CLG, we report the best result from several executions of the planner for each instance.

Benchmarks: Among the benchmarks, btcs, btnd, ebtcs, ebtnd, ebts, elogistic, grid, logistics, and unix come from the contingent-FF distribution, while cball, doors, localize, and wumpus are from the CLG distribution. The other domains, including e1d, ecc, edisp, and epush, are variants of the challenging conformant domains 1-dispose, cornercube, dispose, and push, respectively. These domains are modified by us to force planners to generate conditional plans as they do not have a conformant plan.

All the experiments have been performed on a Linux Intel Core 2 Dual 9400 2.66GHz workstation with 4GB of memory. The time-out limit was set to two hours.

Overall Evaluation: The performance of CNFct in comparison with the other state-of-the-art contingent planners is summarized in Table 1. Because of their implementation, CNFct and DNFct return the same solution. We therefore report their performance in a single column (2nd column). This column-in the format t1/t2(s/d)-reports the total runtime in seconds for CNFct (t1), DNFct (t2), the number of actions in the solution (s), and the depth of the solution tree (d). The other columns--written as t(s/d)-report the total run-time in seconds (t), the number of actions in the solution (s), and the depth of the solution tree (d) for the other planners, whenever this information is available. Observe that s and d are the same for CNFct and DNFct, as they use the same search algorithm and the same heuristic function. POND does not report the depth information. Usually, d and s are criteria to evaluate the quality of a solution. However, we consider d to be more important, as it is the maximum number of actions the agent needs to execute to achieve the goal.

We observe that there are several problems for which the experimental results differ from those reported in the literature. We suspect that the discrepancy occurs due to the different versions of the other planners and/or the environments for conducting the experiments are different (e.g., different hardware/OS).

As observed from Table 1, CNFct and DNFct perform better than other planners

From the experimental results in Table 1 one can observe that CNFct, like DNFct, outperforms the other planners while CLG is better than the rest planners in the tested domains. The quality of the solutions found by CNFct, which is the same as that of DNFct, is in general not as good as contingentFF but is better than CLG or Pond in some cases. We believe that the heuristic scheme used in CNFct plays an important role in this issue. The simplicity of the heuristic function could also be the reason that CNFct and DNFct are not as competitive in the domains elogistics, logistics, and wumpus.

6 Effectiveness of CNF/DNF Representations

In this section, we analyze the effectiveness of the CNF and DNF representations on the performance of the respective planners. In particular, we are interested in what features affect the scalability and performance of a planner. From Table 1 one can observe that CNFct scales best, as it can solve most problem instances on the table, while DNFct is the fastest planner that solves most instances with shortest time.

Before we get into the details, let us discuss the strength and weakness of each method using the following domains.

Consider cball-n-m, e1d-n-m, edis-n-m, and epush-nm, where n denotes the number of locations and m is the number of objects. Initially, the location of each object oi (i = 1, . . . ,m) is unknown among n given locations pj (j = 1, . . . , n), and described by the literal at(oi, pj). Thus, the number of states in the initial belief state is linear in nm, i.e., exponential in m. On the other hand, the size of the initial CNF-state is linear in m×n2 . This, we believe, explains why CNFct scales best when m increases, provided that n is not too large. On the other hand, DNFct can outperform CNFct if n ≥ 9 and m ≤ 2, e.g., e1d-9-1, e1d-9-2, epush-10-1, etc... The reason is that the CNF-states in these cases is not much smaller or even larger in comparison with the DNF-states, whereas ΦDNF can be computed much faster than ΦCNF due to the difference in their complexity, as analyzed later. Furthermore, the nature of the DNF representation allows to use the bitset encoding compactly along with bitwise operations for computing ΦDNF efficiently.

The above discussion shows that two important issues that can affect a planner's performance and scalability are: (i) the size of the formula representing the initial belief state and (ii) the efficiency of computing the transition function. For a better understanding of the second factor, let us analyze the complexity of the two transition functions in the worst case.

Let S be a belief state and a be an action. For simplicity, assume that a contains only one outcome oi.

Complexity of ΦCNF: Let ϕ be the CNF-state representing S, n be the number of clauses in ϕ, and m be the length of the largest clause in ϕ. For simplicity, we assume that n and m are the same for the intermediate CNF-states in the computation of ΦCNF . Let k be the number of non-unit literals in the antecedents of the conditional effects of a and u be the number of the antecedents of the conditional effects of a which are unknown in ϕ. The computation of ΦCNF incurs the following costs:

1. Satisfaction checking: k × f(n,m), where f(n,m) is the cost of checking satisfaction of a literal in ϕ. Note that f(n,m) is exponential in n.
2. Enabling conversion enboi : 2u × f1(n,m). Let ψ be one of those antecedents; the conversion of ϕ to enabling form splits it into ϕ∧ψ and ϕ∧¬ψ. f1(n,m) is the cost of conversion of ϕ ∧ ψ or ϕ ∧ ¬ψ to a CNF-state (r(.)), which is polynomial in n and m. There are u of such antecedents, so there will be at most 2u CNF-states at the end of this process.
3. Update: 2u × f2(n,m, e), where e = max{|e(oi, φ)| | φ ∈ enboi (ϕ)} and f2 is polynomial in n, m, and e.
4. Reduced-cross-product: 2u × f3(n,m), where f3 is polynomial in n and m.

The complexity of ΦCNF is k×f(n,m)+2u ×(f1(n,m)+ f2(n, m, e) + f3(n, m)) which is exponential in n and u.

Complexity of ΦDNF : Let Δ be the DNF-state representing S. The main difference in the complexity of ΦDNF is that checking satisfaction of a literal in Δ is linear in |Δ| and there is no reduced-cross-product phase, which is often expensive. Moreover, conversion of a DNF-formula to the DNF-state is much simpler than that of a CNF-formula to the CNF-state. In summary, ΦDNF is exponential only in u with much smaller hidden cost compared with ΦCNF .

Empirical Comparison and Discussion: Table 2 presents several features of CNFct and DNFct obtained from our experiments. In all columns, cls and p-states stand for clauses (in CNFct) and partial states (in DNFct) respectively. The table contains, beside the size of the formulae representing the initial belief state (3rd column); the average number of clauses, partial states, and unknown antecedents (u) in an expanded CNF-state or DNF-state respectively (4th column); the average size of all clauses/partial states appearing in the expanded CNF-states/DNF-states (5th column); and the number of distinct clauses, partial states and nodes generated by the planners (6th column). We believe that these numbers help explain the scalability and performance of both planners in different domains. Note that, since all the unit literals in a CNF-state are encoded in a bitset and the experiments show that the computation cost of ΦCNF depends mostly on the non-unit clauses in the CNF-state, only non-unit clauses are accounted for in Table 2.

As analyzed earlier, the cost of ΦCNF depends on the number of unknown antecedents u and (non-unit) clauses in the CNF-state and the size of the clauses. The last column reveals that most non-unit clauses in the expanded CNF-states have size two. Hence, the cost of ΦCNF depends mainly on u and the number of clauses in each CNF-state. Observe that (the average of) u is very small (< 10-10 ) in most domains, partly due to the heuristic scheme used in the planners, except btcs, btnd, and localize in which DNFct performs much better than CNFct. The reason is that although both ΦCNF and ΦDNF are exponential in u but ΦDNF does not incur the computation of the reduced-cross-product phase, which is exponential in u, while ΦCNF does; and the enabling conversion of ΦDNF is also much simpler.

The performance of the planners also depends on the memory consumption, which is reflected in the last column. Consider the cases of ebtcs and ebts, where DNFct performs much better than CNFct. The reasons are not only that the average number of clauses of the expanded CNF-states is much bigger than the average number of partial states in an expanded DNF-state, but also the number of distinct clauses generated by CNFct is much larger than the number of distinct partial states generated by DNFct for each instance. Now consider the case of cball-3-4: even though the average number of partial states of the expanded DNF-states (48.34) is not much larger than the number of clauses (9.71) (remember that ΦCNF is exponential in this number), DNFct performs much worse than CNFct, because it generates a very large number of distinct partial states (3,643,961), while CNFct generates only 132 distinct clauses. Observe also that both planners fail to find a solution for wumpus-10. While the reason for the failure of CNFct is only the unsuitable heuristic function, as it generates successor CNF-states quite fast, the failure of DNFct is mainly due to the large size of the initial DNFstate-DNFct spends 3230 seconds for the computation of the initial DNF-state from the description of the initial information and produces out of memory during the expansion of the first node. If a better heuristic function for this domain was used, DNFct would still fail but CNFct would probably find a solution for wumpus-10.

7 Summary

This paper presented a new approach to contingent planning using CNF representations of belief states and implemented it in the planner CNFct. It investigated the effectiveness of CNF and DNF representations by means of CNFct and DNFct [To et al., 2011] using a same new heuristic function. The empirical study showed that both methods are very efficient but neither of them dominates the other and their performance can vary significantly on different classes of problems. The paper identified key aspects of each representation that affect the performance of the corresponding planner.

In summary, CNFct scales better with the size of the problem and requires less memory, while DNFct can find a solution faster. In addition, we showed that the performance is significantly affected by the total amount of consumed memory, which is determined mainly by the number of distinct clauses/partial states generated, rather than the number of generated CNF-states/DNF-states and the total number of clauses/partial states contained in them.

Acknowledgments

We are grateful to the reviewers for their helpful comments. We also thank Alexandre Albore (one of the authors of CLG planner) for his assistance with the experiments.

The authors are partially supported by NSF grant IIS0812267.