An Extension to Conformant Planning Using Logic Programming

1 Introduction

Previous work [Gelfond and Morales, 2004; Son et al., 2005b; 2005a; Tu et al., 2006] have explored the usefulness of approximations of AL actions theories to conformant planning. Among them, [Son et al., 2005a; Tu et al., 2006] define different approximations in terms of logic programs and use these approximations to develop conformant planners in the logic programming paradigm. The choice of logic programming in the implementation of planners in general and conformant planners in particular offers several advantages. First, the correctness of the planner can be formally proved. Second, logic programming allows us to deal with domains with static causal laws (also called constraints). And finally, concurrent planning and domain control knowledge can be implemented in the planner without any difficulty.

The planners in [Son et al., 2005a; 2005b; Tu et al., 2006], however, suffer from two main drawbacks: (i) they work only on planning problems where the initial situation can be characterized by a single set of fluent literals; and (ii) they are in general incomplete, i.e., they might not be able to solve some problems which are solvable by other planners. Since these planners are based on an approximation theory, the latter problem is inevitable. It remained unclear, however, whether or not these planners can be extended to deal with other types of conformant planning problems, e.g. planning problems where the set of possible initial states is given by a disjunction. Furthermore, it is important to characterize conditions for which they are complete. An interesting work on this issue has recently been studied in [Son and Tu, 2006]. Nevertheless, the proposed completeness condition is restricted to action theories without static causal laws.

In this paper we address these limitations by (a) expanding the logic programming implementation of [Son et al., 2005a] to build a new conformant planner, called CPASPm, which Phan Huy Tu and Tran Cao Son New Mexico State University Department of Computer Science {tphan,tson}@cs.nmsu.edu can operate on planning problems with a more complex description of the initial state of the domain; and (b) extending the completeness result in [Son and Tu, 2006] to action theories with static causal laws.

This paper is organized as follows. In the next section, we review the basics of the action description language AL from [Baral and Gelfond, 2000] and the definition of an approximation from [Son et al., 2005a]. In Section 3, we describe an extended logic programming based conformant planner called CPASPm. In Section 4 we state the soundness of the implementation and provide a sufficient condition on action theories for which the planner is complete. Finally, in Section 5, we compare the performance of CPASPm with some other concurrent conformant planners.

2 Background

2.1 ALAction Theories and Transition Diagrams

Dynamic systems can be modeled by transition diagrams whose nodes correspond to possible states of the domain and whose arcs correspond to actions that take the domain from one state to another. We limit our attention to transition diagrams that can be defined by AL action theories.

The signature Σ of an AL action theory consists of two disjoints sets of symbols: a set F of fluents and a set A of elementary actions. An action is a non-empty set of elementary actions. A fluent literal (or literal for short) is either a fluent F or its negation ¬F . An AL action theory is a collection of statements of the forms:e causes l if p (1)

where e is an elementary action, a is an action, and p is a set of fluent literals from the signature Σ. Statement (1), called a dynamic causal law, says that, if e is executed in a state satisfying p then l will hold in any resulting state. Statement (2), called a static causal law, says that any state satisfying p must satisfy l. Statement (3) is an impossibility condition, which says that action a cannot be performed in any state satisfying p. Given an action theory D, a set of literals s is closed under a static causal law (2) if l ∈ s whenever p ⊆ s. For a set of literals s, by Cn(s), we denote the smallest set of literals that includes s and is closed under the set of static causal laws of D. A state σ is a complete and consistent sets of literals closed under the set of static causal laws of D. An action b is said to be prohibited in state σ if D contains an impossibility condition (3) s.t. p ⊆ σ and a ⊆ b. For an action a and a state σ, E(a, σ) stands for the set of all literals l s.t. D contains a law (1) with p ⊆ σ and e ∈ a. Elements of E(a, σ) are called direct effects of the execution of a in σ. An action theory D describes a transition diagram T(D). The nodes of T (D) are states of D and arcs are labeled with actions. The transitions of T (D) are defined as follows.

Definition 1 ([McCain and Turner, 1997]) For an action a and two states σ and σ′ , a transition 〈σ, a, σ′ 〉 ∈ T (D) iff a is not prohibited in σ and

Given a state σ and an action a, such σ′ is often referred to as a possible successor state of σ as the result of the execution of a. When σ and a are clear from the context, we simply say that σ′ is a possible successor state.

An action theory D is consistent if for any state σ and action a which is not prohibited in σ there is at least one possible successor state. In this paper, we consider consistent action theories only.

We now introduce some terminology used to describe properties of a transition diagram T(D). By convention, we use letters a and σ (possibly indexed) to denote actions and states respectively. A model M of a chain of events α = 〈a0, . . . , an-1〉 is an alternate sequence of states and actions 〈σ0, a0, σ1, . . . , an-1, σn〉 s.t. 〈σi, ai, σi+1〉 ∈ T (D) for 0 ≤ i < n. σ0 (resp. σn) is referred to as the initial state (resp. final state) of M. We say that M entails a set of literals s, written as M |= s, if s ⊆ σn. Furthermore, we sometimes write 〈σ0, α, σn〉 ∈ T (D) to denote that there is a model of α whose initial state and final state are σ0 and σn, respectively.

An action a is executable in a state σ if there is a state σ′ s.t. 〈σ, a, σ′ 〉 ∈ T (D). A chain of events α = 〈a0, . . . , an-1〉 is executable in σ if either (i) n = 0 (i.e., α is an empty chain of events), or (ii) a0 is executable in σ and for every σ′ s.t. 〈σ, a, σ′ 〉 ∈ T (D), 〈a1, . . . , an-1〉 is executable in σ′ .

2.2 Approximations of T(D) and Conformant Planning Problem

In many of real world applications, an agent may not have complete knowledge of the current state of the domain. Under such circumstances it is not possible for the agent to directly reason about the effects of actions using the transition diagram of the domain. Our approach to reasoning with incomplete information is based on using approximations of action theories [Son and Baral, 2001; Son et al., 2005b; 2005a; Tu et al., 2006]. In this section, we review the definition of approximation from [Son et al., 2005a] and discuss how an approximation can be used to find a solution of a conformant planning problem.

Let D be an action theory. A set s of literals is a partial state if it is a subset of some state and it is closed under the set of static causal laws of D. For a partial state s, a completion of s is a state σ s.t. s ⊆ σ and by comp(s) we denote the set of all completions of s. For a set of partial states S by comp(S) we denote the set ⋃s∈S comp(s).

Definition 2 (Approximation [Son et al., 2005a]) T ′(D) is an approximation of D if:

1. Nodes of T ′(D) are partial states of T(D).
2. If 〈s, a, s′ 〉 ∈ T ′(D) then for every σ ∈ comp(s),
3. (a) a is executable in σ, and
4. (b) s′ ⊆ σ′ for every σ′ s.t. 〈σ, a, σ′ 〉 ∈ T(D).

It is not difficult to see that the following observation holds.

Observation 1 ([Son et al., 2005a]) Let T ′ (D) be an approximation of D. Then, for every chain of events α, if 〈s, α, s′ 〉 ∈ T ′(D) then for every σ ∈ comp(s), (a) α is executable in σ; and (b) s′ ⊆ σ′ for every σ′ s.t. 〈σ, α, σ′ 〉 ∈ T (D).

This observation states that reasoning using approximations is sound wrt reasoning using T (D).

One application of reasoning with partial states is conformant planning. In a conformant planning problem, the task of the agent is to find a chain of events that achieves some given goal provided it may not have complete knowledge of the initial state of the domain. More specifically,

Definition 3 A conformant planning problem P is a tuple 〈D, Γ,G〉 where Γ is a set of possible initial states and G is a set of literals.

Definition 4 A chain of events α = 〈a0, . . . , an-1〉 is a solution or a conformant plan of a conformant planning problem P = 〈D, Γ,G〉 if, for every σ ∈ Γ, α is executable in σ and for every model M of α with initial state σ, M |= G.

The following relationship between conformant plans and paths of an approximation of D follows from Observation 1.

Observation 2 Let T ′ (D) be an approximation. If 〈s, α, s′ 〉 ∈ T ′(D) and G ⊆ s′ then α is a solution of the conformant planning problem 〈D, comp(s), G〉.

Observation 2 shows us a way to solve a conformant planning problem 〈D, Γ,G〉: look for a path in an approximation that leads to a goal partial state (i.e. a partial state satisfying the goal). This approach is adopted in [Son et al., 2005b; 2005a], where the set Γ of possible initial states of a conformant planning problem is modeled as the completions of a single partial state s. It is shown in [Son et al., 2005b; 2005a] that many conformant planning problems in the literature can be successfully solved this way. However, the following is an example of a conformant planning problem that cannot be solved by this method.

Example 1 (Turkey and two guns) There are two guns and a turkey. Initially only one of the guns is loaded and we do not knowwhich one it is. The objective is to kill the turkey by shooting it. Let g1 and g2 be names for the guns and X be a variable for the guns. This planning problem can be modeled as P1 = 〈D1, Γ1, G1〉 where

It is easy to see that by Definition 4 α1 = 〈{shoot(g1)}, {shoot(g2)}〉 is a solution of P1.

Following the approach in [Son et al., 2005b], however, the conformant planning is modeled as P ′1 = 〈D1, Γ′1 , {dead}〉 where Γ′1 = comp({¬dead}). Clearly P ′1 does not have a conformant plan because the state σ = {¬dead, ¬loaded(g1), ¬loaded(g2)} belongs to comp({¬dead}) and there exists no path in the transition diagramT(D) that leads to a goal state fromσ. ✷

In order to address this issue, we have extended the definition of a conformant plan from [Son et al., 2005a], and, with a more careful examination of approximations, conclude the following observation, which can be viewed as a generalization of Observation 2.

Observation 3 Let P = 〈D, Γ,G〉 be a planning problem, T ′(D) be an approximation, and α be a chain of events. Let S be a set of partial states s.t. comp(S) = Γ. If for every s ∈ S, there exists a partial state s′ s.t. 〈s, α, s′ 〉 ∈ T ′(D) and G ⊆ s′ then α is a solution of P.

This observation extends the applicability of approximations to conformant planning problems with a more complex description of the initial state of the domain. In particular, instead of viewing the set of possible initial states Γ as (the completions of) a single initial partial state s as in [Son et al., 2005a], we view it as a set of initial partial states S. Then, to find a conformant plan within an approximation, we look for a chain of events α s.t. every possible path of α starting from a partial state in S always leads to a goal partial state. As an example, the set of possible initial states of the domain in Example 1 can be viewed as the set S1 of two partial states 1 {¬dead, loaded(g1), ¬loaded(g2)} and {¬dead, ¬loaded(g1), loaded(g2)}, i.e., S1 = Γ1. It is easy to verify that, within the approximation in [Son et al., 2005a], the solution α1 = 〈shoot(g1), shoot(g2)〉 can be found by this method because every possible path of α1 in the approximation that starts from a partial state in S1 always leads to a goal partial state.

3 A Logic Programming Implementation

We now describe an answer set planning [Subrahmanian and Zaniolo, 1995] based method for constructing an approximation to action theories of AL. In our method, we define a transition diagram ˜ T(D) in terms of a logic program ˜π(D) called the cautious encoding of D. The work in [Son et al., 2005a] uses a similar construction but the resulting logic program is only able to deal with a single initial partial state. The work in [Tu et al., 2006] does provide a method for constructing conditional plans with several branches but operates from a single initial partial state as well. Our work in this paper can be viewed as a combination of the ideas presented in these works in order to develop a conformant planner which can deal with a more complex description of the initial state;

1 Note that by definition a state is also a partial state.

in particular, the planner can work on domains with disjunctive information in the initial state. In order to achieve this, a distinct label is attached to every partial state considered. Atoms of ˜π(D) are formed by the following (sorted) predicate symbols:

• h(l, t, k) is true if literal l holds at time step t in a path starting from the initial partial state labeled with k;
• o(e, t) is true if e occurs at time step t;
• dc(l, t, k) is true if literal l is a direct effect of an action that occurs at (t - 1, k); and
• ph(l, t, k) is true if literal l possibly holds at time t in a path with the initial partial state labeled with k.

The program also contains auxiliary predicates: time, fluent, action, and label that are used for enumerating constants of sorts time step, fluent, elementary action and label respectively. In our presentation, we also use some shorthands: if a is an action then o(a, t) = {o(e, t) : e ∈ a}. If p is a set of literals, and F is either h, dc, or ph, then F(p, t, k) = {F(l, t, k) : l ∈ p} and not F(p, t, k) = { not F(l, t, k) : l ∈ p}. For a literal l, by l we denote its complement, i.e. ¯ F = ¬F and ¬F = F. For a set of literal p, p = {l : l ∈ p}. Finally, L, T and K (possibly with indices) are variables for literals, time steps, and labels respectively. For convenience, we often write ˜π(D, n) to denote the restriction of ˜π(D) to time steps between 0 and n. The set of rules 2 of ˜π(D) is listed below.

1. For each dynamic causal law (1) in D, the rules

belong to ˜π(D). The first rule states that l holds at T +1 on path K if e occurs at T and precondition p holds at T on path K. The second rule states that l is a direct effect of e at (T + 1,K) if e occurs at T and precondition p holds at (T,K).

Since the state of the domain at time step T might be incomplete, we add to ˜π(D) the rule

which says that l possibly holds at (T +1, K) if e occurs at T and the precondition p possibly holds at (T,K).

Furthermore, we add to ˜π(D) the following rule

which says that a literal L possibly holds at T + 1 if it possibly holds at T and its negation is not a direct effect of the action that occurs at T .

1. For each static causal law (2) in D, ˜π(D) contains:

These rules state that if p holds (or possibly holds) at (T,K) then so does l.

2 In each rule, predicates defining sorts of variables are omitted for brevity.

1. For each impossibility condition (3) in D, we add to ˜π(D) the following rule:

This rule states that a cannot occur at time step T if precondition p possibly holds at (T, K) for some path K.

1. The inertial law is encoded as follows:

which says that L holds at time step T > 0 if its negation cannot possibly hold at T .

1. Auxiliary rule: ˜π(D) also contains the following rule:

The first rule, as a constraint, states that h(f, t, k) and h(¬f, t, k) cannot hold at the same time 3 . The last two rules are used to define literals.

For an action a and a partial state s, let Π(D, a, s) = ˜π(D, 1) ∪ h(s, 0, 0) ∪ o(a, 0). Note that Π(a, s) is a stratified program, so if it is consistent, then it has a unique answer set [Gelfond and Lifschitz, 1988]. We define an approximation ˜ T (D) based on Π(D, a, s) as follows.

Definition 5 Let s be a partial state and a be an action. Let ˜ T(D) be a transition diagram s.t. 〈s, a, s′ 〉 ∈ ˜ T(D) iff Π(D, a, s) is consistent and s′ = {l : h(l, 1, 0) ∈ A} where A is the answer set of Π(D, a, s).

Theorem 1 If D is consistent then ˜ T (D) is an approximation of D. ✷

The proof of this theorem is similar to the proofs of the soundness of the logic programming encoding of AL action theories in [Son et al., 2006; Turner, 1997].

Let P = 〈D, Γ,G〉 be a conformant planning problem. Since ˜ T(D) is an approximation of D, we can use the program ˜π(D) to find solutions of P. In the remaining part of this section, we describe a logic program ˜π(P, n), where P is the input planning problem and n is the length of a solution we wish to find.

• Let S = {s0, s1, .., sm} be a set of partial states s.t. Γ = comp(S) (hereafter we refer to such S as a set of initial partial states of P). Let the subindex of each element of S act as its label. We construct the program ˜π(P, n) based on S as follows. ˜π(P, n) contains the rules of ˜π(D, n) and the following rules.
• Rules encoding the initial state: For every si ∈ S, ˜π(P, n) contains the rule

1. Rules encoding the goal: To guarantee that the goal is satisfied in the final state of every path, we add to ˜π(P, n) the following rules:

3 Some adjustment to this syntax would be needed if one wants to use an existing answer set solvers. For instance, we may need to replace ¬f with, say, neg(f).

1. Rules to generate actions: To generate action occurrences, we add to ˜π(P, n) the following choice rule [Simons et al., 2002] 4 :

4 Properties of ˜π(P, n)

In this section, we investigate the soundness and completeness of ˜π(P, n).

4.1 Soundness

Using Theorem 1 and Observation 3, we can prove the correctness of the planner ˜π(P, n).

Theorem 2 Let A be an answer set of ˜π(P, n). For 0 ≤ i < n let ai = {e : o(e, i) ∈ A}. Then, α = 〈a0, .., an-1〉 is a solution of P. ✷

4.2 A Sufficient Condition for the Completeness

Although Theorem 2 tells us that ˜π(P, n) is sound, the program is not complete in the sense that there are planning problems that have solutions for which ˜π(P) returns no answer set. This is illustrated in the following example.

Example 2 Consider the action description

and the planning problemP2 = 〈D2, Γ2, {g}〉 where Γ2 is the set of all possible states. Obviously 〈a〉 is a solution of this problem because either f or ¬f is true in any state belonging to Γ2 and thus either one of the above dynamic causal laws would take effect when a is executed.

Let S1 = {∅}. Then, it is easy to see that comp(S1) = Γ2. If we construct ˜π(P2, 1) based on S1 then ˜π(P2, 1) is inconsistent, which means that no conformant plan of length one can be found by ˜π(P2, 1). In fact, it can be shown that for every n, ˜π(P2, n) is inconsistent. Thus, ˜π(P2, n) cannot solve the planning problemP2. However, if ˜π(P2, 1) is constructed based on the set of initial partial states S2 = {{f}, {¬f}} then ˜π(P2, 1) would return an answer set corresponding to the solution 〈a〉. ✷

The above example shows that choosing a set of initial partial states S plays an important role in the completeness of ˜π(P, n). To characterize the situation in Example 2, we define a notion of dependencies among literals and between literals and actions (adapted from [Son and Tu, 2006]).

Definition 6 A literal l depends on a literal g, written as l ◁g, whenever one of the following conditions holds.

1. l = g.
2. D contains a law [a causes l if p] s.t. g ∈ p.
3. D contains a law [l if p] s.t. g ∈ p.
4. There exists a literal h s.t. l ◁ h and h ◁ g.
5. l ◁ g.

4 If we wish to find a sequential plan, the only thing needed to do is to change the left side of the rule to 1{o(E, T) : action(E)}1.

Definition 7 An action b depends on a literal l, written as b◁l, if either

1. D contains an impossibility condition (3) s.t. a ⊆ b and ¯l ∈ ψ, or
2. there exists a literal g s.t. b ◁ g and g ◁ l.

For a set of literals w, we write l ◁ w to denote that l ◁ g for some g ∈ w, and l ⋪ w to denote that there exists no g ∈ w s.t. l ◁ g.

Observe that according to Definition 6, for the domain D2 in Example 2, we have that g ◁ f and g ◁ ¬f. This implies that for each state σ in Γ2, we can find some literal l such that g ◁ l. In this case, we say that Γ2 is not reducible to ∅ wrt {g}. The precise definition of reducibility is given below.

Definition 8 Let Δ be a set of states, s be a partial state, and w be a set of literals. We say that Δ is reducible to s wrt w, denoted by Δ ≫w s if

1. s is a subset of every state σ in Δ,
2. for each l ∈ w, Δ contains a state σ s.t. l ⋪ (σ \s), and
3. for each action a, Δ contains a state s s.t. a ⋪ (σ \ s).

We say that a set of states Δ is reducible to a set of partial states S wrt a set of literals w, written as Δ ≫w S iff Δ = comp(S) and comp(s) ≫w s for every s ∈ S. Back to Example 2, according to this definition, we do not have Γ2 ≫{g} S1 = {∅} but we do have Γ2 ≫{g} S2 = {{f }, {¬f }}.

We define a class of action theories as follows.

Definition 9 A static causal law is simple if its precondition contains at most one literal. An action theory D is simple if each of its static causal laws is simple.

We notice that if D is simple then Δ≫w S implies that reasoning with ˜ T (D) from the set of partial states S would agree with reasoning about w with T(D) from the set of possible initial states Δ on the set of literals w. Base on this observation, we have the following result about the completeness of ˜π(P, n).

Theorem 3 Let α = 〈a1, . . . , an-1〉 be a solution of P = 〈D, Γ,G〉. If D is simple and ˜π(P, n) is constructed based on a set of initial partial states S s.t. Γ ≫G S then ˜π(P, n) is consistent and has an answer set A s.t. ai = {e : o(e, i) ∈ A}. ✷

We can verify that for the planning problem P2 in Example 2, if we construct ˜π(P, n) based on S1 = {∅} then we would miss the solution 〈a〉. However, if we construct it based on the set of partial states S2 = {{f}, {¬f}} then ˜π(P, 1) would return an answer set corresponding to the solution 〈a〉.

5 Experiments

Theorem 2 suggests a simple algorithm for finding minimal plans (wrt the number of steps) of a planning problemP: sequentially run program ˜π(P, n) with n = 1, 2, . . . , until it returns an answer set (we assume that P does not have a trivial solution 〈〉). We have implemented this algorithm in a planning system called CPASPm and use CMODELS [Lierler and Maratea, 2004] as the underlying answer set solver.

CPASPm takes as input a logic program representation of P and produces concurrent conformant plans. We have compared CPASPm with other conformant planning systems. Due to space limit we only consider planners capable of generating concurrent plans. As aforementioned, only a small modification to the logic program can make the planner act as a sequential planner.

We compare CPASPm with the concurrent conformant planners DLV K [Eiter et al., 2003] and C-PLAN [Castellini et al., 2003]. C-PLAN is a SAT-based conformant planner where a planning problem is translated into a satisfiability problem and satisfying assignments of variables correspond to solutions of the original planning problem. DLV K is somewhat similar to CPASPm as both run on top of an answer set solver. However, unlike CPASPm DLV K does not use approximations. Its algorithm has two phases: looking for candidate plans first and then checking if they are conformant.

We prepared a test suite of problems which involves both concurrency and complex initial situations. Some of this problems are simple modifications to conformant benchmarks in the literature. The test suite consists of the problems Conformant Turkey and Lost Cleaner. Conformant Turkey is a modification of the classic Yale shooting problem. In our problem, there are n guns, but only one of which is loaded. Guns can be shot concurrently, with the exception of gun #1 and #2. The objective is to kill the turkey. Lost Cleaner is a modification of the ring [Cimatti et al., 2004]. The agent is in one of n rooms arranged in a ring fashion. Each room has m objects that must be cleaned by the agent. The agent can move to the next room in a clockwise or counter-clockwise fashion and at a time it can clean objects in a room concurrently. Initially, the agent does not know its initial location nor the current status (cleaned or dirty) of the objects.

Experiments were conducted in a 1.4GHz Pentium 4 machine running Linux, and each planner was given 30 minutes to complete each instance of each problem. The results are shown in Tables 1 and 2. In each table, times are in seconds, and PL is the number of steps of a shortest solution of the corresponding problem.

As we can see from Table 1, CPASPm outperforms both DLV K and C-PLAN in the Conformant Turkey domain. Solutions for these domain all involve 3 steps, with one step consisting of firing multiple guns concurrently. In this domain, exploiting concurrency is key to obtaining a short plan.

In the Lost Cleaner domain, shown in Table 2, only CPASPm is able to solve all problem instances within the time limit. In this domain, the length of a solution ranges from 3 to 19 steps and it is determined by the number of rooms in the ring. As the number of rooms in the problem increases, the number of possible initial situations increases. One of the advantages of using approximations is that it is possible to reason about the domain without having to consider all possible worlds. As the complexity of the problem increases, only CPASPm is able to scale. In this problem C-PLAN behaved erratically, failing some simple problem instances and then solving more complicated ones. In general, the use of approximations allows CPASPm to exploit concurrent actions when searching for a solution, and to scale better than the other concurrent planners as the number of possible initial states and the length of the solution increases.

6 Conclusion and Future Work

In this paper, we extend the logic programming based approach to conformant planning in [Son et al., 2005a; Tu et al., 2006] to develop a conformant planner, called CPASPm, which can solve planning problems with a more complex description of the initial states. The planner inherits several key properties of the planner CPASP in [Son et al., 2005a]. In particular, it can deal with static causal laws and is capable of finding minimal and concurrent plans. It is sound and sometimes complete wrt the full semantics of AL action theories. Our experimental results show that the planner is comparable with some other concurrent conformant planners.

As future work, one of our goals is to strengthen the condition for the completeness of the planner. Also, we would like to develop a method for including domain knowledge so that we can obtain better performance from the planner.

Acknowledgment: We will like to thank Dr. Michael Gelfond for his collaboration, help, and useful discussions on the topic.