Action Language BC: Preliminary Report

1 Introduction

Action description languages are formal languages for describing the effects and executability of actions. "Second generation" action description languages, such as B [Gelfond and Lifschitz, 1998, Section 5], C [Giunchiglia and Lifschitz, 1998], and C+ [Giunchiglia et al., 2004, Section 4], differ from the older languages STRIPS [Fikes and Nilsson, 1971] and ADL [Pednault, 1989] in that they allow us to describe indirect effects of an action-effects explained by interaction between fluents.

The languages B and C have significant common core [Gelfond and Lifschitz, 2012]. Nevertheless, some expressive possibilities of B are difficult or impossible to simulate in C, and the other way around. The main advantage of B is that it allows the user to give Prolog-style recursive definitions. Recursively defined concepts, such as the reachability of a node in a graph, play important role in applications of automated reasoning about actions, including the design of the decision support system for the Space Shuttle [Nogueira et al., 2001]. On the other hand, the language B, like STRIPS and ADL, solves the frame problem by incorporating the commonsense law of inertia in its semantics, which makes it difficult to talk about fluents whose behavior is described by defaults other than inertia. The position of a moving pendulum, for instance, is a non-inertial fluent: it changes by itself, and an action is required to prevent the pendulum frommoving. The amount of liquid in a leaking container changes by itself, and an action is required to prevent it from decreasing. A springloaded door closes by itself, and an action is required to keep it open. Work on the action language C and its extension C+ was partly motivated by examples of this kind. In these languages, the inertia assumption is expressed by axioms that the user is free to include or not to include. Other default assumptions about the relationship between the values of a fluent at different time instants can be postulated as well. On the other hand, some recursive definitions cannot be easily expressed in C and C+.

In this paper we define a new action description language, called BC, that combines the attractive features of B and C+. This language, like B, can be implemented using computational methods of answer set programming [Marek and Truszczynski, 1999; Niemel¨a, 1999; Lifschitz, 2008].

The main difference between B and BC is similar to the difference between inference rules and default rules. Informally speaking, a default rule allows us to derive its conclusion from its premise if its justification can be consistently assumed; default logic [Reiter, 1980] makes this idea precise. In the language B, a static law has the form

<conclusion> if <premise> .

In BC, a static law may include a justification:

<conclusion> if <premise> ifcons <justification>

(if cons is an acronym for "if consistent"). Dynamic laws may include justifications also.

The semantics of BC is defined by transforming action descriptions into logic programs under the stable model semantics. When static and dynamic laws of the language B are translated into the language of logic programming, as in [Balduccini and Gelfond, 2003], the rules that we get do not contain negation as failure. Logic programs corresponding to Bdescriptions do contain negation as failure, but this is because inertia rules are automatically included in them. In the case of BC, on the other hand, negation as failure is used for translating justifications in both static and dynamic laws.

We define here three translations from BC into logic programming. Their target languages use slightly different versions of the stable model semantics, but we show that all three translations give the same meaning to BC-descriptions. The first version uses nested occurrences of negation as failure [Lifschitz et al., 1999]; the second involves strong (classical) negation [Gelfond and Lifschitz, 1991] but does not require nesting; the third produces multi-valued formulas under the stable model semantics [Bartholomew and Lee, 2012]. The third translation is particularly simple, because BC and multivalued formulas have much in common: both languages are designed for talking about non-Boolean fluents. But we start with defining the other two translations, because their target languages are more widely known.

Examples of formalizing commonsense domains discussed in this paper illustrate the expressive capabilities of BC and the use of answer set solvers for the automation of reasoning about actions described in this language. We state also two theorems relating BC to B and to C+.

2 Syntax

An action description in the language BC includes a finite set of symbols of two kinds, fluent constants and action constants. Fluent constants are further divided into regular and statically determined. A finite set of cardinality ≥ 2, called the domain, is assigned to every fluent constant.

An atom is an expression of the form f = v, where f is a fluent constant, and v is an element of its domain. If the domain of f is {f, t} then we say that f is Boolean.

A static law is an expression of the form

(n ≥ m ≥ 0), where each Ai is an atom. It expresses, informally speaking, that every state satisfies A0 if it satisfies A1, . . . ,Am, and Am+1, . . . ,An can be consistently assumed. If m = 0 then we will drop if; if m = n then we will drop ifcons.

A dynamic law is an expression of the form

(n ≥ m ≥ 0), where

• A0 is an atom containing a regular fluent constant,
• each of A1, . . . ,Am is an atom or an action constant, and
• Am+1, . . . ,An are atoms.

It expresses, informally speaking, that the end state of any transition satisfies A0 if its beginning state and its action satisfy A1, . . . , Am, and Am+1, . . . , An can be consistently assumed about the end state. If m = n then we will drop if cons.

For any action constant a and atom A,

a causes A

stands for A after a.

For any action constant a and atoms A0, . . . , Am (m > 0),

stands for

An action description in the language BC is a finite set consisting of static and dynamic laws.

3 Defaults and Inertia

Static laws of the form

and dynamic laws of the form

will be particularly useful. They are similar to normal defaults in the sense of [Reiter, 1980]. We will write (3) as

and we will drop if when m = 0. We will write (4) as

For any regular fluent constant f, the set of the dynamic laws

for all v in the domain of f expresses the commonsense law of inertia for f. We will denote this set by

4 Semantics

For every action description D, we will define a sequence of logic programs with nested expressions PN0(D), PN1(D), . . . so that the stable models of PNl(D) represent paths of length l in the transition system corresponding to D. The signature σD,l of PNl(D) consists of

• expressions i : A for nonnegative integers i ≤ l and all atoms A, and
• expressions i : a for nonnegative integers i < l and all action constants a.

Thus every element of the signature σD,l is a "time stamp" i followed by an atom in the sense of Section 2 or by an action constant. The program consists of the following rules:

• the translations

(i ≤ l) of all static laws (1) fromD,

• the translations

(i < l) of all dynamic laws (2) fromD,

• the choice rule 1 {0 : A} for every atom A containing a regular fluent constant,

1 A choice rule {E} can be viewed as shorthand for the disjunctive nested expression E; not E [Ferraris and Lifschitz, 2005], or, equivalently, for the rule

E ← not not E.

• the choice rule {i : a} for every action constant a and every i < l,
• the existence of value constraint

for every fluent constant f and every i ≤ l, where v1, . . . , vk are all elements of the domain of f,

• the uniqueness of value constraint

for every fluent constant f, every pair of distinct elements v, w of its domain, and every i ≤ l.

The transition system T(D) represented by an action description D is defined as follows. For every stable model X of PN0(D), the set of atoms A such that 0 : A belongs to X is a state of T(D). In view of the existence of value and uniqueness of value constraints, for every state s and every fluent constant f there exists exactly one v such that f = v belongs to s; this v is considered the value of f in state s. For every stable model X of PN1(D), T(D) includes the transition 〈s0, α, s1〉, where si (i = 0, 1) is the set of atoms A such that i :A belongs to X, and α is the set of action constants a such that 0:a belongs to X.

The soundness of this definition is guaranteed by the following fact:

Theorem 1 For every transition 〈s0, α, s1〉, s0 and s1 are states.

We promised that stable models of PNl(D) would represent paths of length l in the transition system corresponding to D. For l = 0 and l = 1, this is clear from the definition of T(D); for l > 1 this needs to be verified. For every set X of elements of the signature σD,l, let Xi (i < l) be the triple consisting of

• the set of atoms A such that i :A belongs to X,
• the set of action constants a such that i :a belongs to X, and
• the set of atoms A such that (i + 1) :A belongs to X.

Theorem 2 For every l ≥ 1, X is a stable model of PNl(D) iff X0 , . . . ,Xl-1 are transitions.

The rules contributed to PNl(D) by static law (3) have the form

They can be equivalently rewritten as

(see [Lifschitz et al., 2001]). Similarly, the rules contributed to PNl(D) by dynamic law (4) have the form

They can be equivalently rewritten as

In particular, the rules contributed by the commonsense law of inertia (5) can be rewritten as

5 Other Abbreviations

In BC-descriptions that involve Boolean fluent constants we will use abbreviations similar to those established for multivalued formulas in [Giunchiglia et al., 2004, Section 2.1]: if f is Boolean then we will write the atom f =t as f , and the atom f = f as ∼f .

A static constraint is a pair of static laws of the form

where v ̸= w and m > 0. We will write (6) as

The use of this abbreviation depends on the fact that the choice of f, v, and w in (6) is inessential, in the sense of Theorem 3 below. About action descriptions D1 and D2 we say that they are strongly equivalent to each other if, for any action description D (possibly of a larger signature), T(D∪D1) = T(D∪D2). This is similar to the definition of strong equivalence for logic programs [Lifschitz et al., 2001].

Theorem 3 Any two static constraints (6) with the same atoms A1, . . . , Am are strongly equivalent to each other.

The rules contributed to PNl(D) by (6) can be equivalently written as

A dynamic constraint is a pair of dynamic laws of the form

where v ̸= w, a1, . . . , ak (k > 0) are action constants, and A1, . . . , Am are atoms. We will write (7) as

and we will drop if in this abbreviation when m = 0. The use of this abbreviation depends on the following fact:

Theorem 4 Any two dynamic constraints (7) with the same action constants a1, . . . , ak and the same atoms A1, . . . , Am are strongly equivalent to each other.

The rules contributed to PNl(D) by (7) can be equivalently written as

6 Example: The Blocks World

The description of the blocks world below ensures that every block belongs to a tower that rests on the table; there are no blocks or groups of blocks "floating in the air."

Let Blocks be a finite non-empty set of symbols (block names) that does not include the symbol Table. The action description below uses the following fluent and action constants:

• for each B ∈ Blocks, regular fluent constant Loc(B) with domain Blocks ∪ {Table}, and statically determined Boolean fluent constant InTower(B);
• for each B ∈ Blocks and each L ∈ Blocks ∪ {Table}, action constant Move(B, L).

In the list of static and dynamic laws, B, B1 and B2 are arbitrary elements of Blocks, and L is an arbitrary element of Blocks ∪ {Table}. Two different blocks cannot rest on the same block:

The definition of InTower(B):

InTower(B) if Loc(B)=Table, InTower(B) if Loc(B)=B1, InTower(B1), default ∼InTower(B).

Blocks don't float in the air:

impossible ∼InTower(B).

The commonsense law of inertia:

The effect of moving a block:

A block cannot be moved unless it is clear:

nonexecutable Move(B, L) if Loc(B1)=B.

Here is a representation of logic programs PNl(D) (Section 4), for this action description D, in the input language of the grounder GRINGO: 2

% declarations of variables for steps, % blocks, and locations step(0..l). #domain step(I). block(b(1..n)). #domain block(B). #domain block(B1). #domain block(B2). location(X) :- block(X). location(table). #domain location(L). % translations of static laws :- loc(B1,B,I), loc(B2,B,I), B1!=B2. intower(B,true,I) :- loc(B,table,I). intower(B,true,I) :- loc(B,B1,I), intower(B1,true,I). {intower(B,false,I)}. :- intower(B,false,I). % translations of dynamic laws {loc(B,L,I+1)} :- loc(B,L,I), I<l. loc(B,L,I+1) :- move(B,L,I), I<l. :- move(B,L,I), loc(B1,B,I), I<l. % standard choice rules {loc(B,L,0)}. {move(B,L,I)} :- I<l. % uniqueness and existence of value :- not 1{loc(B,LL,I) : location(LL)}1. :- not 1{intower(B,false,I), intower(B,true,I)}1.

2 http://potassco.sourceforge.net/

The values of the symbolic constants l (the number of steps) and n (the number of blocks) are supposed to be specified in command line. The stable models generated by an answer set solver for this input file will represent all trajectories of length l in the transition system corresponding to the blocks world with n blocks. For instance, if we ground this program with the GRINGO options -c l=0 -c n=3 then the resulting program will have 13 stable models, corresponding to to all possible configurations of 3 blocks.

The rules involving intower can be written more economically if we use strong (classical) negation and replace

intower(B,true,I), intower(B,false,I) with intower(B,I), -intower(B,I).

That would make the uniqueness of value constraint for intower redundant.

7 Example: A Leaking Container

The example above includes the inertiality assumption for all regular fluents. In some cases, the commonsense law of inertia for a regular fluent is not acceptable and needs to be replaced by a different default.

Consider, for instance, a container of capacity n that has a leak, so that it loses k units of liquid per unit of time, unless more liquid is added. This domain can be described using the regular fluent constants Amt with domain {0, . . . , n}, for the amount of liquid in the container, and the action constant FillUp. There are two dynamic laws:

default Amt=max(a-k, 0) after Amt=a (a = 0, . . . , n), FillUp causes Amt=n.

(When k = 0, the first of them turns into inertial Amt.)

Consider the following temporal projection problem involving this domain, with n = 10 and k = 3: initially the container is full, and it is filled up at time 3; we would like to know how the amount of liquid in the container will change with time. The program below consists of the rules of PNl(D) and rules encoding the temporal projection problem.

% declarations of variables for steps % and amounts step(0..l). #domain step(I). amount(0..n). #domain amount(A). % translations of dynamic laws {amt(AA,I+1)} :- amt(A,I), AA=(|A-k|+(A-k))/2, I<l. amt(n,I+1) :- fillup(I), I<l. % standard choice rules {amt(A,0)}. {fillup(I)} :- I<l. % uniqueness and existence of value :- not 1 {amt(AA,I) : amount(AA)} 1.

% temporal projection amt(n,0). fillup(3). -fillup(0..2;4..l).

#hide. #show amt/2.

The solver CLINGO produces the following output:

amt(10,0) amt(10,4) amt(7,5) amt(7,1) amt(4,2) amt(4,6) amt(1,7) amt(1,3) amt(0,9) amt(0,8)

8 Translation into the Language of Programs with Strong Negation

In the definition of the semantics of BC in Section 4 the programs PNl(D) can be replaced by the programs with strong negation PSl(D) that consist of the following rules:

• the translations

(i ≤ l) of all static laws (1) fromD,

• the translations

(i < l) of all dynamic laws (2) fromD,

• the disjunctive rules 0 : A ∨ ¬ 0 : A for every atom A containing a regular fluent constant,
• the disjunctive rules i : a ∨ ¬ i : a for every action constant a and every i < l,
• the existence of value constraint

for every fluent constant f and every i ≤ l, where v1, . . . , vk are all elements of the domain of f,

• the uniqueness of value rule

for every fluent constant f, every pair of distinct elements v, w of its domain, and every i ≤ l.

The stable models of the program PNl(D) from Section 4 can be obtained from the (complete) answer sets of PSl(D) by removing all negative literals:

Theorem 5 A set X of atoms of the signature σD,l is a stable model of PNl(D) iff X ∪ {¬A | A ∈ σD,l \ X} is an answer set of PSl(D).

It follows that the translation PN in the definition of T(D) can be replaced with the translation PS.

9 Translation into the Language of Multi-Valued Formulas

Multi-valued formulas are defined in [Giunchiglia et al., 2004, Section 2.1], and the stable model semantics is extended to such formulas in [Bartholomew and Lee, 2012].

A multi-valued signature is a set σ of symbols, called constants, along with a nonempty finite set Dom(c) of symbols, disjoint from σ, assigned to each constant c, called the domain of c. An atom of the signature σ is an expression of the form c = v ("the value of c is v"), where c ∈ σ and v ∈ Dom(c). If Dom(c) is {f, t} then we say that the constant c is Boolean. A multi-valued formula is a propositional combination of atoms. (Note that the symbol ¬ in multivalued formulas corresponds to negation as failure in logic programs.)

A multi-valued interpretation of σ is a function that maps every element of σ to an element of its domain. An interpretation I satisfies an atom c = v if I(c) = v. The satisfaction relation is extended from atoms to arbitrary formulas according to the usual truth tables for the propositional connectives.

The reduct F I of a multi-valued formula F relative to a multi-valued interpretation I is the formula obtained from F by replacing each maximal subformula that is not satisfied by I with ⊥. We say that I is a stable model of F if I is the only interpretation satisfying F I . 3

Consider the multi-valued signature consisting of

• the constants i : f for nonnegative integers i ≤ l and all fluent constants f, with the same domain as f, and
• the Boolean constants i :a for nonnegative integers i < l and all action constants a.

If F is a propositional combination of atoms f =v and action constants then i : F stands for the formula of this signature obtained from F by prepending i : to every fluent constant and to every action constant.

For any action description D, by MVl(D) we denote the conjunction of the following multi-valued formulas:

• the translations

(i ≤ l) of all static laws (1) fromD,

• the translations

(i < l) of all dynamic laws (2) fromD,

• the formula 0 : (f =v ∨ f ̸=v) for every regular fluent constant f and every element v of its domain,
• the formula i : (a=t ∨ a=f) for every action constant a and every i < l.

By σA we denote the set of all action constants.

Theorem 6 A set X of atoms of the signature σD,l is a stable model of PNl(D) iff X ∪{i :a=f | a ∈ σA, i < l, i :a ̸∈ X} is a stable model of MVl(D).

It follows that the translation PN in the definition of T(D) can be replaced with the translation MV.

3 This formulation is based on the characterization of the stable model semantics of multi-valued formulas given by [Bartholomew and Lee, 2012, Theorem 5].

10 Relation to B

The version of the action language B referred to in this section is defined in [Gelfond and Lifschitz, 2012]. For any action description D in the language B, by D¬∼ we denote the result of replacing each negative literal ¬f in D with the atom ∼f (that is, f = f). The abbreviations introduced in Sections 2 and 5 above allow us to view D¬∼ as an action description in the sense of BC, provided that all fluent constants are treated as regular Boolean. We define the translation of D into BC as the result of extending D¬∼ by adding the inertiality assumptions (5) for all fluent constants f.

We will loosely refer to states and transitions of the transition system represented by D as states and transitions of D.

To state the claim that this translation preserves the meaning of D, we need to relate states and transitions in the sense of the semantics of B to states and transitions in the sense of Section 4. In B, a state is a consistent and complete set of literals f, ¬f for fluent constants f. For any set s of atoms f, ∼f, by s∼¬ we denote the set of literals obtained from s by replacing each atom ∼f with the negative literal ¬f. Furthermore, an action in B is a consistent and complete set of literals a, ¬a for action constants a.

Theorem 7 For any action description D in the language B,

• (a) a set s of atoms is a state of the translation of D into the language BC iff s∼¬ is a state of D;
• (b) for any sets s0, s1 of atoms and any set α of action constants, 〈s0, α, s1〉 is a transition of the translation of D into the language BC iff

is a transition of D.

The description of the blocks world from Section 6 does not correspond to any B-description, in the sense of this translation, for two reasons. First, some fluent constants in it are not regular: it uses statically determined fluents InTower(B), defined recursively in terms of Loc(B). They are similar to "defined fluents" allowed in the extension of B introduced in [Gelfond and Inclezan, 2009]. Second, some fluent constants in it are not Boolean: the values of Loc(B) are locations.

The leaking container example (Section 7) does not correspond to any B-description either: the regular fluent Amt is not Boolean, and the default describing how the value of this fluent changes is different from the commonsense law of inertia. An alternative approach to describing the leaking container is based on an extension of B by "process fluents," called H [Chintabathina et al., 2005].

11 Relation to C+

The semantics of C+ is based on the idea of universal causation [McCain and Turner, 1997]. Formal relationships between universal causation and stable models are investigated in [McCain, 1997; Ferraris et al., 2012], and it is not surprising that a large fragment of BC is equivalent to a large fragment of C+.

In C+, just as in BC, some fluent symbols can be designated as "statically determined." (Other fluents are called

"simple" in C+; they correspond to regular fluents in our terminology.) Fluent symbols in C+may be non-exogenous; in our first version of BC such fluents are not allowed. Action symbols in C+may be non-Boolean; in this respect, that language is more general than the version of BC defined above.

Consider a BC-description such that, in each of its static laws (1), m = 0. In other words, we assume that every static law has the form

Such a description can be translated into C+ as follows:

• all action constants are treated as Boolean;
• every static law (8) is replaced with

• every dynamic law (2) is replaced with caused A0 if Am+1 ∧ · · · ∧ An after A1 ∧ · · · ∧ Am;
• for every action constant a,

exogenous a

is added.

Theorem 8 For any action description D in the language BC such that in each of its static laws (1) m = 0,

• (a) the states of the translation of D into the language C+ are identical to the states of D;
• (b) the transitions of the translation of D into the language C+ can be characterized as the triples

This translation is applicable, for instance, to the leaking container example. The description of the blocks world from Section 6 cannot be translated into C+ in this way, because the static laws in the recursive definition of InTower(B) violate the condition m = 0.

12 FutureWork

The version of BC described in this preliminary report is propositional; expressions with variables, as in the examples from Sections 6 and 7, need to be grounded before they become syntactically correct in the sense of BC. We plan to define the syntax and semantics of BC with variables, in the sprit of [Lifschitz and Ren, 2007], using the generalization of stable models proposed in [Ferraris et al., 2011].

The version of the Causal Calculator described in [Casolary and Lee, 2011] will be extended to cover the expressive capabilities of BC.

Acknowledgements

Joohyung Lee was partially supported by the National Science Foundation under Grant IIS-0916116 and by the South Korea IT R&D program MKE/KIAT 2010-TD-300404-001. Many thanks to Michael Gelfond and to the anonymous referees for valuable advice.