Il Milione: A Journey in the Computational Logic in Italy Evolving Reactive Logic Programs Programmi Logici Reattivi Evolutivi Jose Julio Alferes Federico Banti Antonio Brogi 60 Il Milione: A Journey in the Computational Logic in Italy SOMMARIO/ABSTRACT should be representable in the KR framework, and the mechanism specifying when an action must be performed In questo articolo descriviamo brevemente l’attivitá di must be defined. Moreover, usually interactive applica- ricerca che abbiamo portato avanti negli ultimi anni sui tion continually receive external inputs in the form of mes- programmi logici dinamici. Dopo aver rivisto i nostri sages, perceptions, commands and so on. Such inputs can contributi al consolidamento dei fondamenti semantici dei be considered as events to which the AI application is sup- programmi logici dinamici, descriviamo un semplice for- posed to react in an intelligent way. Reactivity is a key fea- malismo —basato su programmi logici dinamici— per ra- ture in dynamic domains, where changes frequently occur. gionare su azioni ed una sua recente estensione che per- Among the existing proposals for programming reactive mette di specificare ed eseguire programmi reattivi del tipo behaviour, Event-Condition-Action (ECA) languages dis- evento-condizione-azione. tinguish themselves for their flexibility and intuitive syntax In this paper we briefly describe the research activity that and semantics. we have been carrying over during the last years on dy- Dynamic domains also demand AI applications for tak- namic logic programs. After reviewing our contributions ing into account frequent changes and consequently up- to strengthening the semantics foundations of dynamic dating their KBs. The required updates surely involve the logic programs, we describe a simple formalism to rea- extensional part of the knowledge base (facts), but occa- son about actions —based on dynamic logic programs— sionally it may be necessary to update also the intentional and its recent event-condition-action extension that sup- part (logic formulas) to represent the fact that the very rules ports the specification and the execution of reactive pro- of the domain changed. Moreover, for adapting to the new grams. situation, besides knowledge updates, it might be neces- sary to update the beaviour of the AI applications, i.e. the Keywords: Logic programs, dynamic knowledge, action reactive mechanisms themselves. These updates may be description languages, event-condition-action languages. the result of external inputs, but it might be necessary for the application to perform actions leading to self-updates. Moreover, besides what could be called basic actions like, 1 Introduction for instance, insertion and deletion of facts and formulas, Research in Artificial Intelligence (AI) is concerned with developera may want to specify more sophisticated actions producing machines to automate tasks requiring intelligent obtained by combining the basic ones. beaviour. An important problem to face when implement- Among the existing formalisms for KR, Logic Program- ing AI applications is how to represent knowledge, and ming (LP) has a simple logic-based syntax, formal declar- how to extract information from such knowledge. This ative semantics and implemented inference systems. In the area of research is known as knowledge representation past years, part of the research on LP focused on represent- (KR) and reasoning. The dominant approach in KR is to ing dynamic knowledge, i.e. knowledge that is constantly define symbolic paradigms based on some form of logic, self-updated, leading to the dynamic logic programming usually consisting of crude facts and more sophisticated (DyLP) framework [5, 9, 10, 12, 13]. Taking advantage logic formulas. Together, facts and formulas form the of the established results in the field, we developed a (dy- knowledge base (KB) of the AI application. Many tasks namic) LP framework for programming AI applications for AI applications also demand to perform some kind of satisfying the above listed features. actions. Hence actions, and possibly the effects of actions, In this paper, we first review (Section 2) our contribu- 61 Il Milione: A Journey in the Computational Logic in Italy tions to strengthening the semantics foundations of dy- to change the semantics of a DyLP, while immunity to tau- namic logic programs that yielded a refined stable-model tologies is a property generally required to a semantics. based semantics and a well-founded semantics for this For instance, the single program DyLP class of logic programs. We then describe (Section 3) P1 : not rain. rain ← cloudy. a simple formalism (EAPs) to reason about the effects cloudy ← not sun. sun ← not cloudy. of actions —based on dynamic logic programs and on the LP update language Evolp [4]— and its recent event- has one model {not rain, sun}. If we update P 1 with condition-action extension ERA that supports the speci- P2 : rain ← rain. fication and the execution of reactive programs. As we will see, ERA supports the specification and the execution another model {rain, not sun} is allowed. Somehow, the of reactive programs, by detecting (simple and complex) tautology has generated another model by rejecting the rule events, by performing (simple and complex) actions and by not rain. In general, all the known counterintuitive beav- allowing self-updates. Since ERA can also encode EAPs, iour occur in DyLPs with cyclic dependencies among liter- it hence satisfies the features listed earlier in this Introduc- als, somehow leading to the addition of undesired models. tion. Finally some conclusions and directions for future although a formal definition of counterintuitive beaviour work are discussed (Section 4). and undesired model was missing. Our contribution was: We assume the reader is familiar with logic program- • to formalise the concept underlying such counterintu- ming and the stable models and well-founded semantics itive beaviour and to clarify which should be the right and refer to [6] for details on syntax and semantics of LPs. semantics for DyLPs by establishing which properties should be satisfied by such semantics, and 2 Dynamic Logic Programs • to define a semantics satisfying these properties, thus avoiding the known counterintuitive beaviour. Dynamic Logic Programs represent evolving knowledge. To achieve these results we defined the refined extension Syntactically, a DyLP P is a sequence P 1 , . . . , Pn (rather principle [1]. The refined extension principle is a criterium than a single program) of generalized logic programs stating when the addition of rules to a program should not (GLPs), viz., programs where rule heads may be nega- add more models to its semantics and it enables to formal- tive literals. P1 represents the initial knowledge and the ize the undesired addition of models. Then, we defined the other Pi s are supervenient updates representing the evolu- refined stable model semantics (or simply refined seman- tion of the described situation. Given two updates P i , Pj , tics) for DyLPs that refines the other stable-like semantics of a DyLP P, Pj is said to be more recent than P i if Pj for DyLPs. Formally this was achieved by associating to follows Pi in the sequence P. In the past years, several each DyLP P = P1 , . . . , Pn , an operator over sets of lit- semantics have been defined for providing a meaning to erals ΓR P and defining the refined models of P as the fix- DyLPs [5, 9, 10, 12, 13]. These semantics are extensions points of ΓR R P . The ΓP operator is formally defined as fol- of the stable model semantics of normal logic programs, in lows: the sense that, whenever the considered DyLP is a single normal program P , the models of P in the considered se-   ΓR R P (M ) = least ρ(P) \ Rej (P, M ) ∪ Def (P, M ) mantics for DyLPs coincide with the stable models of P . Another common denominator of these semantics, is the where ρ(P) is the multiset of all the rules appearing in causal rejection principle [10, 12]. This principle states any program of the sequence P and Rej R (P, M ) is the that a model M of a DyLP P must fulfill a rule τ in an multiset of all the rules τ in some update P i of P for which update of P, unless there exists a rule in a more recent up- there exist a rule η in some update P j with i ≤ j such that τ date that is in conflict with τ and whose body is true in and η are in conflict and the body of η is true in M . Finally M . Two rule τ and η are said to be in conflict if they have Def (P, M ) is the set of default assumptions, i.e. the set complementary heads, viz., the head of τ is a literal A and of all the negative literals not A such that there exists no the head of η is not A or viceversa. The principle allows rule in P whose head is A and whose body is true in M . a more recent rule to specify an exception to an older one, The refined semantics was proved to satisfy the refined thus allowing to update previous beliefs. extension principle and the causal rejection one. Moreover, The semantics for DyLPs based on the causal rejection we extended the concept of well supported models [6] to principle coincide on large classes of programs but dis- DyLPs and proved that the refine models of a DyLP are agree on some examples and, at the time we started our exactly its well supported models. investigation, there was no general agreement on which A further result was the definition of a well founded se- should be the stable model-like semantics for DyLPs based mantics for DyLPs [8]. The well founded semantics is a on the causal rejection principle. Moreover, all the seman- skeptical approximation of the stable model one. From a tics defined before we started our investigation show coun- practical point of view, the well founded semantics has less terintuitive beaviour in some well known example. The expressivity (for instance it does not allow to express logic simpler examples involve tautological updates that happen constraints) and less inference power (it allows to derive 62 Il Milione: A Journey in the Computational Logic in Italy less conclusions). On the other hand, the well founded se- of our own, christened Evolving Action Programs (EAPs) mantics is computationally less expensive than the stable [2]. EAPs are defined as a macro language on top of Evolp model semantics. Indeed, determining a (refined) stable in the sense that every statement in EAPs is syntactic nota- model of a (dynamic or generalized) logic program is a tion for a set of Evolp statements and the semantics of an NP-complete problem, while the computation of the well EAP is given by the semantics of the corresponding Evolp founded model of a normal logic program has polynomial program. complexity. Syntactically, an EAP statement can be: Moreover, unlike the stable model one, the well founded • an inertial declaration inertial(f ), semantics is always defined and, according to it, a program • a static, logic programming-like rule L ← L 1 , . . . Ln , can be queried about specific information without the need to compute its whole semantics. Due to these features, the • a dynamic rule effect(H ← B) ← Cond. well founded semantics is a better candidate than the sta- The meaning of an inertial declaration inertial(f ), where ble model one for applications that are time-committed and f is an atom (usually called a fluent in the context of ac- require to process huge amount of data, like most of real tion description languages) is that the truth value of f is world database related applications. preserved in time unless it changes as an effect of the exe- We defined a well founded semantics for DyLPs that ex- cution of an action. A static rule describes the (static) rules tends the well founded semantics for normal LPs and ap- of the environment by expressing correlations among flu- proximates the refined one, in the sense that (as for normal ents. A dynamic rule expresses the effect of the execution LPs) the well founded model of a DyLP is a subset of any of actions. Syntactically, the effect H ← B is a static rule, of its refined models. Moreover, the well founded seman- while Cond is a conjunction of action literals representing tics for DyLPs preserves the good features shown for the actions being or not executed and fluent literals represent- class of normal and generalized LPs, i.e. the well founded ing preconditions for the considered effects to take place. model always exists, its computation is polynomial, and a The expressivity of EAPs was compared with that of the DyLP can be queried about specific information without action languages A, B, C (see [11] for a detailed descrip- the need to compute its whole semantics. tion of these languages) and for each of these languages, The well founded model was defined as the least fix- a modular embedding of their action programs into EAPs point of an operator ΓΓ R , combining the Γ R operator used was defined. Moreover, being based on DyLPs, EAPs are for defining the refined model semantics with another op- shown to be particularly suitable for encoding successive erator Γ used for defining another semantics for DyLPs i.e. elaborations or updates of an action description problem. the dynamic stable model semantics [12]. Besides reasoning about the effects of actions, we also needed a formalism for executing them. This was achieved by defining an ECA formalism called ERA (after Evolving 3 Reasoning about and executing actions Reactive Algebraic programs) [3]. Along with inference logic programming rules, ERA presents two new forms of After strngthening the formal foundation of dynamic logic rules for specifying the execution of actions, i.e. active and programs, we turned our attention to the the problem of inhibition rules of the form, respectively: programming self-updatable AI applications capable of reasoning about and executing actions. A bridge between On Event If Condition Do Action. (1) dynamic KR via DyLPs and this kind of applications was When B Do not Action. (2) already established by the family of LP updates languages [4, 10, 12]. These languages are built on the top of a where Event is an event literal encoding the occurrence DyLP semantics and, besides representing dynamic and of an event and Condition is a conjunction of literals ex- constantly updated knowledge, they allow one to specify pressing the condition under which an Action (syntacti- how a KB should be updated. Among these formalism the cally an atom) is executed. Finally, B is a conjunction of Evolp language [4] has a particularly simple, but highly ex- literals expressing conditions under which Action should pressive syntax and semantics, and hence it was chosen as not be executed. Both events and actions can be basic or the starting point of our investigation. Evolp is a language complex ones. Complex events and actions are obtained by for building sequences of DyLPs starting from an original combining simple ones via an event and an action algebra. program. Syntactically, Evolp extends the language of LP Events occur at a given instant and are volatile informa- with new atoms assert(r) where r is a rule. An Evolp tion. Basic events may be external, representing incoming programs evolves passing from the current state to the suc- inputs and commands or internal, raised by the system it- cessive one, by updating the program with all the rules r self. The event algebra allows to combine events occurring such that the atom assert(r) is true in the current state. simultaneously or at different time points. For instance, the A widely used way to describe and reason about the complex event A(e 1 , e2 , e3 ), where A/3 is a ternary oper- effects of actions are action description programs writ- ator and the e i s are events, occurs at instant i iff e 3 occurs ten in specific formalisms called action description lan- at instant i, e1 occurred at some previous instant and e 2 did guages [11]. We defined an action description language not occurr in between. 63 Il Milione: A Journey in the Computational Logic in Italy Actions represent operations to be executed. Basic ac- address planning issues, e.g., how to determine, given a tion can be external, representing some external operation current state and a goal, a sequence of actions leading to a to be executed, or internal. As for events, basic actions can state satisfying that goal. Another direction for future work be combined by an algebra of operators for specifying flow are transactions. Although the action algebra of ERA al- of operations. For instance, given two action a 1 and a2 , ac- lows one to program complex actions, it is still less than tion a1  a2 specifies that action a2 must be executed after adequate for defining transactions. In order to define and a1 , while action (a1 , a2 ) specifies that a1 and a2 can be execute transactions, the action algebra of ERA should be concurrently executed. extended for coping with the execution of ACID transac- Among internal actions, particularly important ones are tions as well as of compensation activities. the assertion and the deletion of facts and rules. While deletion removes facts and rules from the KB, the asser- REFERENCES tion of rules causes the application to update itself by a new fact, an inference, an active or an inhibition rule. New [1] J. J. Alferes, F. Banti, A. Brogi, and J. A. Leite. The facts and inference rules are incorporated by the underly- refined extension principle for semantics of dynamic ing DyLP semantics (that can be the refined as well as the logic programming. Studia Logica, 79(1), 2005. well founded one). Also new active and inhibition rules are incorporated by the underlying DyLP semantics. As- [2] J.J. Alferes, F. Banti, A. Brogi. From logic programs sertions of rules of the forms (1) and (2) are translated, updates to action description updates. In J. Leite, P. respectively, into the LP updates Torroni (eds.), CLIMA V, LNAI, pages 52–77, 2005. Action ← Condition, Event. [3] J.J. Alferes, F. Banti, A. Brogi. An event-condition- not Action ← B. action logic programming language. JELIA 2006, LNAI, pages 29-42, 2006. The underlying DyLP framework allows to establish whether the atom Action is derived or not and, in the for- [4] J. J. Alferes, A. Brogi, J. A. Leite, L. M. Pereira. mer case, the corresponding action is executed. In this Evolving logic programs. JELIA’02, LNAI, 2002. way the application can update not only its KB but also [5] J. J. Alferes, J. A. Leite, L. M. Pereira, H. Przy- its beaviour by asserting new active rules and specifying musinska, and T. C. Przymusinski. Dynamic updates exceptions to existing active rules by asserting inhibition of non-monotonic knowledge bases. The Journal of ones. Moreover, it was proved that every Evolp program, Logic Programming, 45(1–3):43–70, 2000. and hence every EAP, can be directly encoded into ERA. Thus ERA is a paradigm capable of both executing and [6] K. R. Apt and R. N. Bol. Logic programming and reasoning about actions. In [7] ERA is discussed in detail negation: A survey. The Journal of Logic Program- and compared to existing formalisms for programming re- ming, 19 & 20:9–72, May 1994. active behaviour. We simply point out here the two main novelties of ERA, i.e. its self evolution capabilities and [7] F. Banti. Evolving Reactive Logic Programs. PhD the- featured possibility of both programming the execution of sis, Universitade Nova de Lisboa, 2008. actions and reasoning about their effects. [8] F. Banti, J.J. Alferes, A. Brogi. Well founded seman- tics for logic program updates. IBERAMIA’04, LNCS 4 Conclusions and future work 3314, pages 397–407, 2004. In this paper we have tried to briefly describe the research [9] F. Buccafurri, W. Faber, and N. Leone. Disjunctive activity that we have been carrying over during the last logic programs with inheritance. ICLP’99, 1999. years on dynamic logic programs. After reviewing our contributions to strengthening the semantics foundations [10] T. Eiter et al.. A framework for declarative update of dynamic logic programs, we have presented the EAPs specifications in logic programs. In IJCAI, 2001. formalism to reason about actions, and its recent event- [11] M. Gelfond and V. Lifschitz. Action languages. Elec- condition-action extension ERA that supports the specifi- tronic Transactions on AI, 16, 1998. cation and the execution of reactive programs. While space limitations only allowed us to provide an extended abstract [12] J. A. Leite. Evolving Knowledge Bases. Frontiers in of this research activity, more details can be found in the Artificial Intelligence and Applications, vol. 81, 2003. papers [1, 2, 3, 8] and a complete presentation of all the results is reported in [7]. [13] J. A. Leite and L. M. Pereira. Generalizing updates: There are several open windows for future work. One from models to programs. LPKR’97, 1997. of them is the definition of action query languages [11], that is, languages for extracting information about the pos- sible evolution of the situations described by EAPs and to 64