A generic approach to planning in the presence of incomplete information: Theory and implementation (Extended Abstract)

1 Motivation and RelatedWork

Planning in the presence of incomplete information [Goldman and Boddy 1996; Smith and Weld, 1998] is the problem of generating a plan that can achieve a given goal regardless of what the actual truth value of unknown information about the initial world is. This paper focuses on conformant planning-a special class of planning problems in the presence of incomplete informationthat deals with incomplete information about the initial state and with deterministic and non-sensing actions.

One of the challenges in conformant planning is the problem of reasoning about action effects in the presence of incomplete information. Specifically, consider an action a with a set of conditional effects of the form (a : ψ → η), where ψ and η are a set of literals. Each

∗This paper is based on the journal article [To, Son, and Pontelli, 2015].

Tran Cao Son and Enrico Pontelli

Department of Computer Science New Mexico State University {tson | epontell}@cs.nmsu.edu

effect (a : ψ → η) denotes that the set of literals η will be true in the resulting state after the execution of a in the current state if the e-condition ψ is true in the current state. Due to incomplete information, the current state and, hence, the truth value of ψ in it can be unknown. As a consequence, the fact that η must be true in the successor state can be unknown, making the computation of the successor state particularly challenging. This agrees with the results in [Baral et al., 2000; Haslum and Jonsson, 1999], that conformant planning for domains with conditional effects is at a higher complexity level than that without conditional effects. Since its introduction, conformant planning has attracted the attention of several researchers-leading to the development of several state-of-the-art conformant planners. It is important to observe that most efficient conformant planners are best-first search and progression-based planners, whose development starts with the selection of a representation language for incomplete (partially known) states and the definition of a transition (progression) function that, given a state S and an action, computes the next state S′ of the world, where S and S′ are generally incomplete and encoded in the representation.

To deal with incomplete information about the world, the notion of a belief state-defined as the set of possible states-has been introduced and is widely used in planning in presence of incomplete information [Bonet and Geffner, 2000; Smith and Weld, 1998]. An advantage of this notion lies in its simplicity in representing and reasoning about the effects of actions in presence of incomplete information. Indeed, any formalism for Reasoning about Action and Change (RAC), that assumes completeness of the state, can be straightforwardly generalized to deal with incomplete states, by dealing with each individual possible state in the belief state separately, and by collecting the set of resulting states as the successor belief state. More precisely, let s be a state and a be an action executable in s (s satisfies the precondition of a). The effect of executing a in s is the set of literals that become true in the successor state, defined as

The transition function Φ(a, s) that returns the result of the execution of a in s is defined by

where e(a, s) denotes the set of negations of literals in e(a, s). Then the function ̂Φ(a, S) = {Φ(a, s) | s ∈ S} characterizes the transition between belief states and can be used for reasoning with incomplete information.

The downside of the direct use of belief states lies in its size, which is exponential in the number of unknown fluents. This presents two challenges for the planners employing this representation. First, it can quickly increase the memory usage for maintaining the set of generated belief states to avoid repeated search. This can often lead to the 'Out of memory' situation before the planner finds a solution. Second, it directly influences the time complexity in computing the successor belief states. To address this problem, different approaches have been proposed in state-of-the-art planners, resulting in significant improvement in their performance, both planning time and scalability on the problem size.

In the planner KACMBP [Cimatti, Roveri, and Bertoli, 2004], belief states are represented as OBDDs [Bryant, 1992] with the use of model checking techniques for expanding the search space. The OBDD formula was also used in the planner POND [Bryce et al., 2006] to represent literals and actions in the planning graph for computing heuristics. This BDD-based approach does not require any extra BDD manipulation operations and it can be applied in both directions: progression and regression. However, the transition function defined for OBDDs may require a huge memory consumption in the manipulation of the OBDDs. This is a potential reason why planners employing this formulation, like POND or KACMBP, do not scale well as shown in the experimental evaluation [To, Son, and Pontelli, 2015].

Hoffmann and Brafman (2006) proposed implicit encoding of belief states with the sequence of actions that leads to the belief state from the initial state. To determine whether an unknown proposition holds in a belief state, the resulting conformant planner CFF has to reason about a CNF formula that captures the semantic of the initial belief state and the entire action sequence from it to the current belief state. This representation requires very little memory. However, it incurs excessive repeated computations and checking whether two belief states under this representation are equivalent is challenging and expensive. Furthermore, checking whether a proposition holds after the execution of even one single action in the presence of incomplete information is co-NP complete. We believe those are the main reasons why CFF has difficulties in finding a solution for even small instances of harder problems, where there are unknown propositions in the e-conditions [Palacios and Geffner, 2009; Tran et al., 2009; To, Pontelli, and Son, 2009].

The approach employed in the planners T0 [Palacios and Geffner, 2007; Palacios and Geffner, 2009] and T1 [Albore, Ramirez, and Geffner, 2011] compiles incomplete information away by translating a conformant problem into a classical problem and then using the efficient classical planner FF [Hoffmann and Nebel, 2001] to solve the resulting problem. This approach demonstrates great performance improvements, e.g., T0 and T1 can solve many hard problems of large size. However, the complete translation is exponential in the conformant width of the problem, related to the number of relevant unknown literals, and the number of literals in the resulting problem can be exponential in that of the original problem. To reduce the complexity of the translation, T0 sacrifices the completeness of the translation in certain problems. This explains why T0 is unable to return a solution in several problems, that have solutions, or the translation fails for large instances of several domains, as shown in our experiments.

GC[LAMA] [Nguyen et al., 2012] is another conformant planner that uses a classical planner. This approach is based on the observation that every solution for a conformant problem is also a solution for the classical problem obtained by replacing the initial belief state with a state in it. A tentative plan α for such a subproblem then can be corrected, by inserting an action sequence to produce precondition for the action the plan α violates at that place. If α cannot be fixed to become a plan for the conformant problem, GC[LAMA] continues with another plan of the same or different subproblem. GC[LAMA] is efficient on problems where the action effects are monotonic, i.e., useful actions create useful literals without destroying other useful literals, and the belief state is not large. Otherwise, it is not as efficient, as reported in the experimental evaluation.

Instead of using a complete transition function in the search, the planner CPA [Son et al., 2005] approximates a belief state with the intersection of the states in it [Son and Baral, 2001]. The approximation is polynomial, yet it is incomplete and so are planners employing it. Later, a complete condition for the approximation was identified and corresponding techniques were developed in CPA to make the planner complete [Son and Tu, 2006; Tu et al., 2011]. The computation of successor belief states in this approach is very simple, i.e., it can be performed in the same manner as that for belief states. However, these techniques require the system to deal with sets of approximated states, which-in the worst case-are the same as the actual belief states being represented. Hence, the approximated formula explodes in many problems, as observed in the experiments, preventing the planner to effectively scale. The authors of CPA [Tran et al., 2009] developed preprocessing techniques which help reduce the size of the initial disjunctive formula in certain classes of problems, enabling the planner to perform very well in several benchmarks and to win the conformant planning category in the IPC-08.

2 Our Approach

In this paper, we propose a generic approach to planning with incomplete information. The key idea underlying our approach is the observation that belief states are propositional formulae. Thus, reasoning about effects of actions on belief states can be expressed using suitable operations on formulae, which is usually (possibly exponentially) more compact than the belief states they represent.

As an example, let us consider a domain F = {f, g, h}, an action a with three conditional effects Ca = {f → ¬g, f ∧ ¬g → ¬f, ¬f → f}, pre(a) = {True}, and a belief state S that contains all possible states of the world (i.e., all possible interpretations of propositions in F) except for {¬f, ¬g, ¬h}. Figure 1 shows the belief state S = {s1, . . . , s7} and the computation of the successor belief state S′ after executing a in S using the function Φ (Equation 2).

Let ϕ be a formula and S be a belief state. We say that ϕ represents S or S is the belief state of ϕ, denoted by BS(ϕ), if S is the set of states that satisfy ϕ. In the above example, we observe that S and S′ can be represented by the more compact CNF-formulae ϕ = f ∨ g ∨ h and ϕ′ = f ∨¬g, respectively. Since each formula encodes a unique belief state, we want to use their compact encoding ϕ and ϕ′ instead of the belief states S and S′ of exponential size. To this end, we need to construct a transition function (e.g., ΦµCNF) such that (1) it returns a CNFformula representing the successor belief state given a CNF-formula and an action (e.g., ΦµCNF(a, ϕ) = ϕ′ ) and (2) its computation involves operations over a small set of formulae instead of enumerating each individual in belief states.

To compute the result s′ of execution of an action a in a state s, we need to compute the effect e(a, s) of executing a in s, the set of literals that must be true in the successor state s′ . Observe from Figure 1 that, the effects of executing a in s1, s3, and s5 are all different. However, e(a, s1) = e(a, s2) = {¬g}, e(a, s3) = e(a, s4) = {¬f, ¬g}, and e(a, s5) = e(a, s6) = e(a, s7) = {f}. Hence, if we divide BS(ϕ) into three sets of states S1 = {s1, s2}, S2 = {s3, s4}, and S3 = {s5, s6, s7} (Figure 2) then for each i ∈ {1, 2, 3} and u, v ∈ Si, we have that e(a, u) = e(a, v). This is because the truth value of each e-condition of a in all the states in each subset Si is the same and it can be different in states from different subsets (e.g., the e-condition f in (a : {f} → {¬g}) is true in all states s1 and s2 in S1 and it is false in all states s5, s6, and s7 in S3.) Observe also that S1, S2, and S3 can be represented by the formulae ϕ1 = f ∧ g, ϕ2 = f ∧ ¬g, and ϕ3 = ¬f ∧ (g ∨ h) respectively. Since the effects of a in all states in BS(ϕi), for each ϕi, are the same, we define e(a, ϕi) = e(a, s) for s ∈ BS(ϕi) and i ∈ {1, 2, 3}. Let s′j = Φ(a, sj) (for j = 1, . . . , 7) and S′ i = Φ(a, Si). Let ϕ′i be the formula obtained by updating ϕi with the minimum change such that the literals in e(a, ϕi) become true in the new formula ϕ′i . Intuitively, BS(ϕ′i ) = S′ i and, hence, BS(ϕ′1 )∪BS(ϕ′2 )∪BS(ϕ′3 ) = BS(ϕ′ ) (= S′ ). Indeed, it is easy to see that ϕ′1 = f ∧¬g, ϕ′2 = ¬f ∧¬g, ϕ′3 = f ∧ (g ∨ h) and the disjunction ϕ′1 ∨ ϕ′2 ∨ ϕ′3 can be simplified to the formula ϕ′ . On the other hand, S = S1 ∪ S2 ∪ S3 and ϕ ≡ ϕ1 ∨ ϕ2 ∨ ϕ3. In summary, the computation of ϕ′ includes three major steps as described in Figure 2.

As shown in our analysis and experiments [To, Son, and Pontelli, 2010a; To, Son, and Pontelli, 2010b; To, Son, and Pontelli, 2011c; To, Son, and Pontelli, 2015], the size of formulae representing belief states and, hence, the performance of a corresponding planner depend substantially on both the type of the formulae being used and the specific problem. For this reason, we propose a generic approach based on the abstract notion representation, instead of limiting to some specific types of formulae, aimed at the use of any type of propositional formulae to represent belief states.

Specifically, a collection R of formulae is a representation of belief states (or representation, for short) if for every belief state S there exists a formula ϕ ∈ R that represents S (BS(ϕ) = S). A formula ϕ in R is called an R-state. A function ΦR that maps pairs composed of an action a and R-state ϕ into R-states is a transition function for R if ΦR(a, ϕ) represents the belief state Φ(a, BS(ϕ)), i.e., BS(ΦR(a, ϕ)) = Φ(a, BS(ϕ)).

As shown in the above example (Figure 2), a transition function ΦR for R will be developed based on three computation steps as follows:

• Step 1: Compute the set of R-states {ϕi | i = 1, . . . , n} such that BS(ϕ1) ∪ . . . ∪ BS(ϕn) = BS(ϕ) and ∀i.∀s, s′ ∈ BS(ϕi). e(a, s) = e(a, s′ ). Compute e(a, ϕi) for i = 1, . . . , n;
• Step 2: For each R-state ϕi, compute ϕ′i by updating ϕi such that e(a, ϕi) is true in ϕ′i and nothing else changes;
• Step 3: Convert the disjunction ϕ′1 ∨ . . . ∨ ϕ′n into an equivalent R-state ϕ′ , i.e., BS(ϕ′ ) = BS(ϕ′1 ∨ . . . ∨ ϕ′n ).

To realize the above computation steps, we then specify a set of abstract operations on a representation R and use these operations in defining the abstract transition function ΦR. We devise a set of abstract algorithms for computing the transition function that can be instantiated in each concrete representation and used in the implementation of conformant planners.

We illustrate the generic framework by instantiating it in three concrete representations of belief states:

• minimal-DNF, a compact form of disjunctive normal form formulae,
• minimal-CNF, a compact form of conjunctive normal form formulae, and
• prime implicates, a well-known, special form of minimal-CNF.

For each representation, we define its set of operations, provide a concrete implementation of these operations, and instantiate the abstract algorithms to create a conformant planner. This results in three conformant planning systems, called DNF, CNF, and PIP, that employ the minimal-DNF, minimal-CNF, and prime implicates as the belief state representation, respectively.

We evaluate these systems using benchmarks available in the literature as well as new benchmarks, that appear to be particularly challenging for other planners. The experimental evaluation shows that the three systems are very competitive with other planners. In addition, the two systems using conjunctive representations (CNF and PIP) are particularly effective on the new problems.

Acknowledgements

Thanks to Knexus Research Corporation for sponsoring this article.