The Common Core of Action Languages B and C
Michael Gelfond and Vladimir Lifschitz · 2012
Action languages B and C are similar to each other in the sense that each of them is capable of describing indirect effects of actions. On the other hand, these languages are not equally expressive: each of them has its own distinctive features that cannot be easily translated into the other language. We clarify the relationship between the expressive capabilities of these languages by describing their common core—a subset of B that can be translated into C by a simple syntactic transformation. Introduction Action languages B (Gelfond & Lifschitz 1998, Section 5) and C (Giunchiglia & Lifschitz 1998), (Gelfond & Lifschitz 1998, Section 6) differ from the previous generation of action description languages in that they allow us to describe ramifications, or indirect effects, of executing an action. This is achieved by introducing constructs that represent relationships between fluents. For instance, walking to a different place affects not only the person’s location but also, indirectly, the location of the cell phone in his pocket, because of a relationship between his own location and the location of the phone. Such relationships can be called static, because they operate within a single time instant. Action descriptions in older languages were limited to dynamic relationships between an action and the values of fluents after its execution. The languages B and C differ from each other in the sense that they are based on different intuitions about causality, and also in the sense that are not equally expressive: each of them has its own distinctive features that cannot be easily translated into the other language. In this note, we clarify the relationship between the expressive capabilities of these languages by describing their common core—a subset of B that can be translated into C by a simple syntactic transformation. This transformation turns a B-description into its “C-image” by appending a standard set of postulates formalizing the commonsense law of inertia (Shanahan 1997). It is STRIPS (Fikes & Nilsson 1971); ADL (Pednault 1989); A (Gelfond & Lifschitz 1993). needed because the commonsense law of intertia is built into the semantics of B; in C, it is easily expressible, but not automatically included. To guarantee the equivalence of a B-description to its C-image we need to assume that its static laws are free of cycles. Conditions of this type have been used in the study of equivalent transformations in the logic of universal causation (Turner 1998, Theorem 5.15) and for the purpose of simplifying logic programming representations of action domains described in C (Lifschitz & Turner 1999, Proposition 2). Review: Languages B and C We begin with a finite set of propositional atoms divided into two groups, fluents and elementary actions. An action is a function from elementary actions to truth values. A transition system T is determined by a set of functions from fluents to truth values, called the states of T , and a set of triples 〈s0, a, s1〉, where s0 and s1 are states of T , and a is an action. These triples are called the transitions of T . A transition system can be visualized as a directed graph that has states as its vertices, with an edge from s0 to s1 labeled a for every transition 〈s0, a, s1〉. Language B Syntax A fluent literal is a literal containing a fluent. A condition is a set of fluent literals. An action description in the language B, or Bdescription, is a set of expressions of the following two forms: • static laws l if c, (1) where l is a fluent literal, and c is a condition; • dynamic laws e causes l if c, (2) where e is an elementary action, l is a fluent literal, and c is a condition. Semantics We will identify a function assigning truth values to atoms with the set of literals that get the value true. In particular, any action can be thought of as a set of elementary actions and their negations, and any state of a transition system can be thought of as a set of fluent literals. About a set X of literals we say that it is closed under a B-description D if, for every static law (1) from D, l ∈ X whenever c ⊆ X. By CnD(X) (“consequences of X under D”) we denote the smallest set of literals that contains X and is closed under D. For any B-description D, the transition system T (D) represented by D is defined as follows: • the states of T (D) are the functions from fluents to truth values that are closed under D; • 〈s0, a, s1〉 is a transition of T (D) iff s1 = CnD(X ∪ (s0 ∩ s1)), (3) where X is the set of all literals l such that, for some dynamic law (2) from D, e ∈ a and c ⊆ s0. Discussion We understand a static law (1) as the inference rule allowing us to derive the new fact l from the facts c established earlier. In the right-hand side of the McCain-Turner equation (3), X is the set of explicit effects of a, s0 ∩ s1 is the set of facts justified by inertia, and the application of CnD generates the indirect effects of a by applying the inference rules expressed by the static laws. Example: D consists of the dynamic law