Towards an Integration of Golog and Planning

1 Introduction

The action language Golog [Levesque et al., 1997] has been applied successfully to the control of robots [Burgard et al., 1999], among other things. It is based on Reiter's version of the situation calculus [Reiter, 2001], where so-called basic action theories (BATs), which define action preconditions and effects together with an initial situation, are combined with a programming language, which offers imperative programming constructs as well as non-deterministic action choices. Perhaps the greatest advantage of Golog is that a user can write programs which constrain the search for an executable plan in a flexible manner. However, when general planning is needed, Golog supports this only in principle through the use of non-deterministic actions, but does not measure up with state-of-the-art planners.

As a running example, consider a taxi-driver agent in a grid world, whose task it is to deliver passengers to their destinations. Its actions are pickup, dropoff, and moving up, down, left or right one square in the grid. In Golog, the agent's highlevel control program can then be specified like this:

While there are passengers to be served do the following: choose a passenger, plan a route to her location, follow that route, pick up the passenger, plan a route to her destination, follow that route and drop her off.

Planning can easily be specified in Golog as trying out actions nondeterministically in a forward-search manner until a given goal is satisfied [Reiter, 2001]. While possible in principle, this quickly becomes infeasible, in our example even for small grid worlds. Modern planners like FF [Hoffmann and Nebel, 2001] or HSP2 [Bonet and Geffner, 2001], on the other hand, are capable of handling much larger planning problems. So it seems natural to try to combine Golog with a modern planner. Here we focus on planners for the ADL [Pednault, 1989] subset of the plan language PDDL [Fox and Long, 2003].

For the integration, at least two issues arise: differences in expressiveness and the correctness of the embedding. While BATs in the situation calculus can use the full power of firstorder logic, ADL descriptions are more restricted. For example, they assume a finite domain and the initial state consists of literals only. As we will see, it is not very difficult to map ADL into BATs. For the purposes of this paper, it will suffice to simply use a BAT that is the result of such a mapping; a companion paper [Eyerich et al., 2006] discusses the expressiveness issue in more detail.

As for correctness, we need to make sure that a plan returned by an ADL planner for a given goal and state description is also a legal plan in the situation calculus for the corresponding situation. The semantics of PDDL's ADL subset [Fox and Long, 2003] is given in terms of state transitions as an adaptation of Lifschitz' semantics of STRIPS [Lifschitz, 1986]. Roughly, a state consists of a set of literals, and a transition for a plan operator is obtained by adding and deleting literals. By extending earlier work by Lin and Reiter [1997], we are able to show that the ADL semantics is captured precisely by progression in the situation calculus, which refers to updating the description of an initial situation so that conclusions about the future that can be drawn using the updated theory are the same as those drawn from the theory before the update. As a nice side-effect, we obtain a purely declarative semantics of ADL within the situation calculus. 1

1 Pednault's [1989; 1994] original semantics for ADL defined operators similarly by additions and deletions, however of tuples in relations and functions of first-order structures. He also derived sit- To obtain our results, we use a variant of the situation calculus called ES recently proposed by Lakemeyer and Levesque [2004]. Compared to Reiter's situation calculus, this has at least two advantages: for one, the translation of ADL into the new situation calculus is simpler as there are no situation terms to worry about (in ES, situations occur only in the semantics); for another, semantic definitions like progression become simpler as it is no longer necessary to consider arbitrary first-order structures but only certain ones over a fixed universe of discourse. These simplifications do not lead to a loss of expressiveness. In fact, Lakemeyer and Levesque [2005] showed that ES captures precisely the non-epistemic fragment of the situation calculus and Golog.

After establishing that ADL plans are correct for the corresponding BAT, we turn to the embedding of an ADL planner into Golog. In particular, we use the latest version of FF [Hoffmann and Nebel, 2001] together with an implementation of IndiGolog [Sardina et al., 2004], which incorporates on-line execution, Reiter's forward-search planner and progression. We present first experimental results showing the pay-off of using Golog with FF versus pure Golog.

The paper proceeds as follows. We first introduce ES and show how BATs are formulated in this logic. Next, we define ADL problem descriptions and provide a formal semantics by mapping them into basic action theories. In Section 4, we define progression and establish the correctness of updating an ADL state with respect to progression. In Section 5, we discuss the integration of Golog and FF. Then we conclude.

2 The logic ES

The language is a first-order modal dialect with equality, predicate and function symbols. For simplicity we assume that all predicates are fluent and that all function symbols are rigid, i.e. predicates may be changed by actions while functions may not. The logical connectives are ∧, ¬, ∀, together with the modal operators ✷ and [r] where r may be any term, including a variable. 2 Other connectives like ∨, ⊃, ≡, and ∃ are used as the usual abbreviations.

Terms and formulas are built from these primitives in the usual way. We let R denote the set of all ground terms. For simplicity, instead of having variables of the action sort distinct from those of the object sort as in the situation calculus, we lump both of these together and allow to use any term as an action or as an object. We read [r]α as "α holds after action r" and ✷α as "α holds after any sequence of actions". We call a formula without free variables a sentence and a formula fluent, when it does not contain ✷ and [r] operators and does not mention the special predicate Poss (which is used to denote executable actions). In addition, we introduce the following special notation: A type τ is a unary predicate; we write ∀x:τ. φ instead of ∀x. τ (x) ⊃ φ.

The semantics: Intuitively, aworldwwill determinewhich fluents are true, but not just initially, also after any sequence of actions. Formally, let P denote the set of all pairs σ:ρ

uation calculus formulas from ADL operators, but did not show the semantic correspondence between the two.

2 The original ES also considers epistemic operators which we do not need here and are left out.

where σ ∈ R∗ is considered a sequence of ground actions, and ρ = F(r1, . . . , rk) is a k-ary ground fluent atom. A world then is a mapping from P to {0, 1}.

First-order variables are interpreted substitutionally over the rigid terms R, i.e. R is treated as being isomorphic to a fixed universe of discourse. This is similar to L [Levesque and Lakemeyer, 2001], where standard names are used as the domain. Given a world w, for any sentence α, we define w |= α as w, 〈 〉 |= α where

w, σ |= (r1 = r2) iff r1 and r2 are identical; w, σ |= (α∧ β) iff w, σ |= α and w, σ |= β; w, σ |= ¬α iff w, σ ̸|= α; w, σ |= ∀x. α iff w, σ |= αxr , for every r ∈ R; w, σ |= [r]α iff w, σ · r |= α; w, σ |= ✷α iff w, σ · σ′ |= α, for every σ′ ∈ R∗ .

The notation αxt means the result of simultaneously replacing all free occurrences of the variable x by the term t.

When Σ is a set of sentences and α is a sentence, we write Σ |= α (read: Σ logically entails α) to mean that for every w, if w |= α′ for every α′ ∈ Σ, then w |= α. Further |= α (read: α is valid) abbreviates {} |= α.

Basic Action Theories: Basic action theories can be defined similar to Reiter's: A set of sentences Σ is a basic action theory iff it only mentions the fluents in a given set F and is of the form Σ = Σ0 ∪ Σpre ∪ Σpost, where

• Σ0 is a finite set of fluent sentences,
• Σpre is a singleton of the form 3 ✷Poss(a) ≡ π, where π is fluent with a being the only free variable;
• Σpost is a finite set of successor state axioms of the form 4 ✷[a]F(⃗x) ≡ γF , one for each fluent F ∈ F \ {Poss}, where γF is a fluent formula whose free variables are among ⃗x and a.

The idea is that Σ0 represents the initial database, Σpre is one large precondition axiom and Σpost the set of successor state axioms for all fluents in F (incorporating Reiter's solution [Reiter, 2001] to the frame problem).

3 ADL

PDDL's ADL subset goes beyond STRIPS by supporting equality, conditional effects and typing. Also, preconditions may contain negation, disjunction and quantifiers.

ADL Problems: These are defined by

1. a finite list of types τ1, . . . , τl and Object; along with this a finite list of statements of the form

defining τi as the union of the τij ; a primitive type is one that does not appear on the left-hand side of such a definition and is distinct fromObject;

3 Free variables are understood as universally quantified from the outside; ✷ has lower syntactic precedence than the logical connectives, i.e. ✷Poss(a) ≡ π stands for ∀a.✷(Poss(a) ≡ π).

4 The [t] construct has higher precedence than the logical connectives. So ✷[a]F (⃗x) ≡ γF abbreviates ∀a.✷([a]F (⃗x) ≡ γF ).

1. a finite list of fluent predicates F1, . . . , Fn; associated with each Fj a list of types τj1 , . . . , τjkj (one for each argument of Fj , abbreviated as ⃗ τFj )
2. a finite list of objects with associated primitive types o1:τo1 , . . . , ok:τok (object symbols are constants);
3. a finite list of ADL operators A1, . . . ,Am (see below);
4. an initial state I (see below) and
5. a goal description G in form of a precondition formula.

I and G may only contain the symbols from items 1 to 3. We further require that all the symbols are distinct. In particular, this forbids using a type also as an Fj and using an object also as an Ai. All objects are implicitly of type Object, which is a supertype of all other types. In the case of closed-world planning, the initial state I is simply given by a finite set of ground fluent atoms F(⃗r), otherwise it is a set of ground literals.

An ADL operator A is a triple (⃗y:⃗τ, πA, ϵA), where ⃗y:⃗τ is a list of variables with associated types, 5 πA is a precondition formula and ϵA an effect formula, both with free variables among ⃗y. Both πA and ϵA have to be constructed using only the ⃗y and the symbols from items 1 to 3 of the problem description. The name of the operator A has to be a p-ary function symbol, where p is the number of parameters of A.

Precondition formulas are the following: Every atomic formula F(⃗t) and every equality atom (t1 = t2), where each of the ti is either a variable or a constant, is a precondition formula. If φ1 and φ2 are precondition formulas, then so are φ1 ∧φ2, ¬φ1 and ∀x:τ.φ1. Without loss of generality, we assume that an effect formula is a conjunction of effects of the following forms, at most one of each kind for each fluent Fj :

The notation γ ⇒ ψ stands for a conditional effect: if the precondition formula γ holds before performing the action, then ψ will become true afterwards.

An Example: Let us consider the taxi domain. For reasons of space we only consider the operators, initial state, and goal description:

1. Operators:

It is always possible to move a taxi into one of the four main cardinal directions; a move that would lead out of the grid has no effect. After moving, the location of the taxi and every passenger in it has changed accordingly. pickup = (〈y1:Taxi, y2:Passenger〉,

5 ⃗y:⃗τ is to be understood as a list of pairs yi:τi.

Picking someone up is only possible when the taxi is at the same location as the passenger and there is noone already in the taxi (we assume it can only hold one person at a time).

Finally, it is always possible to drop the taxi's occupant (if any) at its current location.

1. Initial State (in a closed world):
2. Goal description:

I = {At(taxi1, 5, 7), At(passenger1, 3, 1), Destination(passenger1, 1, 1), Connects(1, 1, east, 2, 1), . . . Connects(10, 10, north, 10, 9)}

In [Fox and Long, 2003] a state-transition semantics is defined for applying ADL operators in the closed-world case. The idea is roughly this: given any closed state I, represented as a set of ground atoms, and an operator A(⃗ p) whose precondition is satisfied in I, then the application of A(⃗ p) results in a new state I ′ which is obtained from I by deleting all those Fj(⃗o) where γFj ,A(⃗o, ⃗ p) holds in I and adding all those where γ+ Fj ,A(⃗o, ⃗p) holds.

4 Mapping ADL to ES

In this section, we generalize the approach of [Lin and Reiter, 1997] and show that applying ADL operators corresponds to a certain form of first-order progression in ES. We begin by constructing, given an ADL problem description, a corresponding basic action theory Σ.

The Successor State Axioms Σpost: It is not a coincidence that the normal form (2) resembles the effect axioms used by Reiter to construct his successor state axioms as a solution to the frame problem. Generalizing his approach (also applied in [Pednault, 1994]), we transform a set of operator descriptions to a set of successor state axioms as follows. Let

By "γ+ Fj ,Ai ∈ NF (Ai)" we mean that there only is a disjunct for those Ai for which 6 there is some γ+ Fj,Ai in the effect of Ai. Using a similar definition for γFj , we get the successor state axiom for Fj :

The additional conjunct 7 ⃗ τFj ( ⃗ xj) ensures that Fj can only become true for instantiations of the ⃗ xj that are consistent with the type definitions for Fj 's arguments.

6 Recall that (2) does not require a conjunct for each Fj and Ai. 7⃗τ (⃗t) abbreviates τ1(t1) ∧ · · · ∧ τk(tk).

Since our semantics defines predicates to be fluent and types have to be situation-independent, we additionally include for each type τi a successor state axiom

Applying all of the above to the example, we get

Notice that, as stated above, not all operators are mentioned in γ+ At , but only those that possibly cause a positive truth value for At. Therefore, the construction presented here still incorporates a solution to the frame problem. Our Σpost now consists of the following sentences (among others 8 ):

The Precondition Axiom Σpre: A precondition axiom can be obtained by a similar case distinction; in the example:

The Initial Description Σ0: We finally not only have to encode the information about the initial world state, but also about the typing of objects:

Σ0 contains one sentence (7) for each "either" statement (1). We further have one sentence of the form (8) for each type declaration of predicate arguments. For each primitive type τi such that oj1 , . . . , ojki are all objects declared to be of that type, we include a sentence of the form (9). (10) finally declares Object to be the union of all other types. Although the above sentences in themselves only establish type consistency in the initial situation (there are no ✷ operators here), the special form of Σpost defined earlier ensures that these facts will remain true in successor situations.

8 Here and in the following we omit axioms concerning the nonchanging predicates Connects and Destination as well as the types Xcoord, Ycoord and Direction which encode the grid structure.

To encode the actual initial state, we include for each Fj 9

in case of a closed world, assuming that Fj( ⃗ o1), . . . , Fj( ⃗ oko ) are all atoms in I mentioning Fj. In an open-world problem, we instead include

if the ⃗ oi are all the objects in positive literals Fj(⃗ oi) and the ⃗ pi are all the objects in negative literals ¬Fj(⃗ pi) in I. In our closed-world example, we end up with a Σ0 consisting of:

Correctness: First we note some simple consequences of the above construction:

Lemma 1 Let A(⃗ p) be an action (i.e. an operator and object symbols as instantiations for A's parameters) and ⃗o be object parameters (i.e. constants) for the fluent Fj. Then

1. Σ0∧ ⃗ τFj (⃗o) is satisfiable iff the ⃗o are of the correct types (according to the ADL problem description).
2. Σ0 |= γ ∗Fj ⃗ xj a ⃗o A(⃗ p) iff γ ∗Fj,A(⃗o, ⃗ p) is satisfied in the original ADL state I, where ∗ ∈ {+, -}.
3. Σ0 |= Poss(A(⃗ p)) iff πA(⃗ p) is satisfied in the original ADL state I and the ⃗ p are of the correct types.

We are now ready to show the correspondence between ADL's state-transition semantics of adding and deleting literals and first-order progression in ES. The definition below is derived from Lin and Reiter's original proposal of progression, but it is simpler due to the fact that we need not consider arbitrary first-order structures.

A set of sentences Σr is a progression of Σ0 through a ground term r (wrt Σpre and Σpost) iff:

1. all sentences in Σr are fluent in 〈r〉 (i.e. equivalent to [r]φ for some fluent formula φ);
2. Σ0 ∪Σpre ∪Σpost |= Σr;
3. for every world wr with wr |= Σr ∪Σpre ∪Σpost, there is a world w with w |= Σ0 ∪ Σpre ∪ Σpost such that:

for all σ ∈ R∗ and all primitive formulas F(⃗t) such that F ∈ F (including Poss).

9 If ⃗r abbreviates r1, . . . , rk and⃗t stands for t1, . . . , tk, then (⃗r = ⃗t) means (r1 = t1) ∧ · · · ∧ (rk = tk).

Intuitively, for an observer in the situation after r was performed (and only looking "forward" in time), it is impossible to distinguish between a world satisfying the original theory Σ and one that satisfies Σr ∪ Σpre ∪ Σpost.

For a basic action theory that is the translation from an ADL problem, it is quite easy to obtain such a progression given an action A(⃗ p) and an ADL state description I. Provided that Σ0∪Σpre |= Poss(A(⃗ p)), we do the following for all (finitely many) ⃗o and Fj such that Fj(⃗o) is type-consistent: 10

For open worlds, additionally delete ¬Fj(⃗o) in the first case and add ¬Fj(⃗o) in the second case. If we then denote the set of literals to be added by Adds and the ones to be deleted by Dels, the new state description is

In the closed-world case, I ′ corresponds precisely to the ADL state which results from applying the A(⃗ p) to I according to the state-transition semantics of [Fox and Long, 2003].

Theorem 2 Let I ′ be obtained as described above, given an ADL problem and a ground action r = A(⃗ p). Further let Σr = {[r]ψ | ψ ∈ Σ0(I ′ )}, where Σ0(I ′ ) is the result of applying the constructions in (7)-(12) to I ′ instead of I. For all Fj, let the consistency condition |= ¬(γ+ Fj ∧ γFj )ar hold. Then Σr is a progression of Σ0 through r in the closed-world case.

In the open-world case, this holds under the additional condition that whenever for some γ ∗Fj (with ∗ ∈ {+,-}) it is the case that Σ0∪{γ ∗Fj ⃗ xj a ⃗o r } is satisfiable, thenΣ0 |= γ ∗Fj ⃗ xj a ⃗o r .

Let us consider progression in our closed-world example. Suppose we want to progress through move(taxi1, south) (m, for short). First note that Σ0 ∪ Σpre |= Poss(m). The reader may verify (assuming an appropriate axiomatization of Connects) that

Σ0 |= γ+ At a x1 x2 x3 m taxi1 5 8 , Σ0 |= γAt a x1 x2 x3 m taxi1 5 7

and that these are all type-consistent instantiations for x1, x2, x3 such that γ+ At am respectively γAt am are entailed by Σ0. Because there are no disjuncts for move in γ+ In and γIn , γ+ In am and γIn am are not entailed for any instantiation of x1, x2. The new state description then is

I ′ = {At(taxi1, 5, 8), At(passenger1, 3, 1), Destination(passenger1, 1, 1), Connects(1, 1, east, 2, 1), . . . Connects(10, 10, north, 10, 9)} We obtain the progression Σm consisting of [m](At(x1, x2, x3) ⊃ (Object(x1) ∧ Xcoord(x2) ∧ Ycoord(x3))), [m](In(x1, x2)⊃(Taxi(x1) ∧ Passenger(x2))), [m](Taxi(x)≡(x = taxi1)), [m](Passenger(x)≡(x = passenger1)), [m](Object(x)≡(Taxi(x) ∨ · · · ∨ Passenger(x))),

10 i.e. those Fj(⃗o) such that Σ0 ∧ ⃗ τFj (⃗o) is satisfiable

Theorem 2 tells us that, for a closed initial state, the application of an ADL operator under the state-transition semantics is the same as progressing the initial situation of the corresponding BAT. In the open-world case, it prescribes what the result of applying the ADL operator should be. It is easy to show that the theorem extends to arbitrary sequences of actions and hence that legal plans under ADL are also legal plans in the BAT. 11

5 Golog with FF

Golog is a programming language completely defined within the situation calculus. As shown in [Lakemeyer and Levesque, 2005], it can be as well defined directly within ES. At its core, Golog uses a basic action theory to define the meaning of its (primitive) actions and the initial situation. Based on these primitives, complex actions can be formed using constructs from imperative programming such as sequence (;), if-then-else, while-loops and procedures. In addition, non-deterministic action choices and the nondeterministic choice of arguments (πx) offer some flexibility when executing a program, including full planning over the primitive actions.

For our experimental results, we are using an Eclipse Prolog implementation of IndiGolog, courtesy of Hector Levesque; see [Sardina et al., 2004] for details of the semantics. IndiGolog features on-line execution, where a program is executed step-by-step, and progression in the sense of the previous section, that is, the initial state is updated after each execution of a primitive action. IndiGolog also includes an implementation of Reiter's forward-search planner (specified as a Golog procedure), which can be called as achieve(G) for a given goal formula G, and which returns as a plan a sequence of actions P , if one is found. P then takes the place of achieve(G) in the program, and step-wise execution resumes, starting with the execution of P .

The underlying BAT is the translation of the ADL problem description for the taxi domain. The following program is used throughout our tests:

while ∃p:Passenger. ¬atDest(p) do (πp:Passenger) pickup(taxi1, p); achieve(atDest(p)); drop passenger(taxi1)

¬atDest(p)?; achieve(atSamePos(taxi1, p)); endWhile Here, atDest(p) stands for ∃x:Xcoord. ∃y:Ycoord. At(p, x, y) ∧ Destination(p, x, y) and atSamePos(t, p) abbreviates ∃x:Xcoord. ∃y:Ycoord. At(p, x, y) ∧ At(t, x, y).

The following table summarizes, for varying grid sizes and number of passengers, the run-time behavior (in seconds) of the original IndiGolog versus IndiGolog where achieve is replaced by a call to the ADL planner FF [Hoffmann and The table clearly shows that the built-in Golog planner cannot compete for all but the smallest problem instances. (Missing entries are tests which did not return a result after 10 minutes and were aborted.)

11 Legal means that all actions are executable and that the goal is satisfied in the final state or progressed situation.

We want to emphasize that our approach does not aim at competing with existing planning systems on solving classical planning problems. 12 Instead, we envision that the combined system pays off in scenarios where each approach by itself would be either inefficient or fail completely. In particular, this is the case when the problem is very large and information has to be gathered at run-time. To illustrate the idea, instead of the toy example above, consider a robot constantly transporting items in a warehouse: The robot would execute thousands of actions, including sensing its environment and servicing new transportation requests. While it does not seem feasible to solve the whole problem by an offline planner, it is certainly possible to write an IndiGolog program to solve such a task. The role of the planner is then to solve certain sequential subtasks (e.g. finding an optimal schedule for currently pending requests) at which Golog by itself would be too slow. We believe that the results in this paper lay the necessary ground work for such scenarios.

6 Conclusion

In this paper we showed that it pays off to combine the action language Golog with modern planners. In doing so, we developed a declarative semantics for ADL as progression in the situation calculus. Currently we are also considering larger fragments of PDDL [Fox and Long, 2003] with features such as time and preferences. It would be interesting to also consider other action formalisms like Flux [Thielscher, 2002] or the family of A languages [Gelfond and Lifschitz, 1998]. Our hope is that this will lead to a convergence of the planning and action-language communities, which have been largely separated since the inception of STRIPS.

Acknowledgments

This work has partly been supported by the EC under contract number FP6-004250-CoSy and DFG grants La 747/13-2 and Ne 623/10-1.

12 In additional experiments we gave FF the overall task of finding a plan to deliver all passengers to their destinations. It was usually faster than the combination of Golog and FF; e.g. finding a plan for the 7x7 grid with 5 passengers took 29.74 seconds.