In questo articolo descriviamo brevemente l’attivita´ di ricerca che abbiamo portato avanti negli ultimi anni sui programmi logici dinamici. Dopo aver rivisto i nostri contributi al consolidamento dei fondamenti semantici dei programmi logici dinamici, descriviamo un semplice formalismo —basato su programmi logici dinamici— per ragionare su azioni ed una sua recente estensione che permette di specificare ed eseguire programmi reattivi del tipo evento-condizione-azione.
In this paper we briefly describe the research activity that we have been carrying over during the last years on dynamic logic programs. After reviewing our contributions to strengthening the semantics foundations of dynamic logic programs, we describe a simple formalism to reason about actions —based on dynamic logic programs— and its recent event-condition-action extension that supports the specification and the execution of reactive programs. 1
Research in Artificial Intelligence (AI) is concerned with producing machines to automate tasks requiring intelligent beaviour. An important problem to face when implementing AI applications is how to represent knowledge, and how to extract information from such knowledge. This area of research is known as knowledge representation (KR) and reasoning. The dominant approach in KR is to define symbolic paradigms based on some form of logic, usually consisting of crude facts and more sophisticated logic formulas. Together, facts and formulas form the knowledge base (KB) of the AI application. Many tasks for AI applications also demand to perform some kind of actions. Hence actions, and possibly the effects of actions, should be representable in the KR framework, and the mechanism specifying when an action must be performed must be defined. Moreover, usually interactive application continually receive external inputs in the form of messages, perceptions, commands and so on. Such inputs can be considered as events to which the AI application is supposed to react in an intelligent way. Reactivity is a key feature in dynamic domains, where changes frequently occur. Among the existing proposals for programming reactive behaviour, Event-Condition-Action (ECA) languages distinguish themselves for their flexibility and intuitive syntax and semantics.
Dynamic domains also demand AI applications for taking into account frequent changes and consequently updating their KBs. The required updates surely involve the extensional part of the knowledge base (facts), but occasionally it may be necessary to update also the intentional part (logic formulas) to represent the fact that the very rules of the domain changed. Moreover, for adapting to the new situation, besides knowledge updates, it might be necessary to update the beaviour of the AI applications, i.e. the reactive mechanisms themselves. These updates may be 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, for instance, insertion and deletion of facts and formulas, developera may want to specify more sophisticated actions obtained by combining the basic ones.
Among the existing formalisms for KR, Logic
Programming (LP) has a simple logic-based syntax, formal
declarative semantics and implemented inference systems. In the
past years, part of the research on LP focused on
representing dynamic knowledge, i.e. knowledge that is constantly
self-updated, leading to the dynamic logic programming
(DyLP) framework [
In this paper, we first review (Section 2) our
contributions to strengthening the semantics foundations of
dynamic logic programs that yielded a refined stable-model
based semantics and a well-founded semantics for this
class of logic programs. We then describe (Section 3)
a simple formalism (EAPs) to reason about the effects
of actions —based on dynamic logic programs and on
the LP update language Evolp [
We assume the reader is familiar with logic
programming and the stable models and well-founded semantics
and refer to [
Dynamic Logic Programs represent evolving knowledge.
Syntactically, a DyLP P is a sequence P1, . . . , Pn (rather
than a single program) of generalized logic programs
(GLPs), viz., programs where rule heads may be
negative literals. P1 represents the initial knowledge and the
other Pis are supervenient updates representing the
evolution of the described situation. Given two updates P i, Pj ,
of a DyLP P , Pj is said to be more recent than Pi if Pj
follows Pi in the sequence P . In the past years, several
semantics have been defined for providing a meaning to
DyLPs [
The semantics for DyLPs based on the causal rejection principle coincide on large classes of programs but disagree on some examples and, at the time we started our investigation, there was no general agreement on which should be the stable model-like semantics for DyLPs based on the causal rejection principle. Moreover, all the semantics defined before we started our investigation show counterintuitive beaviour in some well known example. The simpler examples involve tautological updates that happen to change the semantics of a DyLP, while immunity to tautologies is a property generally required to a semantics.
For instance, the single program DyLP
P1 : not rain. cloudy ← not sun.
rain ← sun ← cloudy. not cloudy. has one model {not rain, sun}. If we update P1 with P2 : rain ← rain. another model {rain, not sun} is allowed. Somehow, the tautology has generated another model by rejecting the rule not rain. In general, all the known counterintuitive beaviour occur in DyLPs with cyclic dependencies among literals, somehow leading to the addition of undesired models. although a formal definition of counterintuitive beaviour and undesired model was missing. Our contribution was: • to formalise the concept underlying such counterintuitive beaviour and to clarify which should be the right semantics for DyLPs by establishing which properties should be satisfied by such semantics, and • to define a semantics satisfying these properties, thus avoiding the known counterintuitive beaviour.
To achieve these results we defined the refined extension
principle [
P points of ΓR. The ΓR operator is formally defined as fol
P P lows: ΓR(M ) = least ρ (P ) \ RejR(P , M) ∪ Def (P , M)
P where ρ (P ) is the multiset of all the rules appearing in any program of the sequence P and Rej R(P , M) is the multiset of all the rules τ in some update Pi of P for which there exist a rule η in some update Pj with i ≤ j such that τ and η are in conflict and the body of η is true in M . Finally Def (P , M) is the set of default assumptions, i.e. the set of all the negative literals not A such that there exists no rule in P whose head is A and whose body is true in M .
The refined semantics was proved to satisfy the refined
extension principle and the causal rejection one. Moreover,
we extended the concept of well supported models [
A further result was the definition of a well founded
semantics for DyLPs [
Moreover, unlike the stable model one, the well founded semantics is always defined and, according to it, a program can be queried about specific information without the need to compute its whole semantics. Due to these features, the well founded semantics is a better candidate than the stable model one for applications that are time-committed and require to process huge amount of data, like most of real world database related applications.
We defined a well founded semantics for DyLPs that extends the well founded semantics for normal LPs and approximates the refined one, in the sense that (as for normal LPs) the well founded model of a DyLP is a subset of any of its refined models. Moreover, the well founded semantics for DyLPs preserves the good features shown for the class of normal and generalized LPs, i.e. the well founded model always exists, its computation is polynomial, and a DyLP can be queried about specific information without the need to compute its whole semantics.
The well founded model was defined as the least
fixpoint of an operator ΓΓR, combining the ΓR operator used
for defining the refined model semantics with another
operator Γ used for defining another semantics for DyLPs i.e.
the dynamic stable model semantics [
After strngthening the formal foundation of dynamic logic
programs, we turned our attention to the the problem of
programming self-updatable AI applications capable of
reasoning about and executing actions. A bridge between
dynamic KR via DyLPs and this kind of applications was
already established by the family of LP updates languages
[
A widely used way to describe and reason about the
effects of actions are action description programs
written in specific formalisms called action description
languages [
Syntactically, an EAP statement can be: • an inertial declaration inertial(f ), • a static, logic programming-like rule L ← L 1, . . . Ln, • a dynamic rule effect(H ← B) ← Cond.
The meaning of an inertial declaration inertial(f ), where f is an atom (usually called a fluent in the context of action description languages) is that the truth value of f is preserved in time unless it changes as an effect of the execution of an action. A static rule describes the (static) rules of the environment by expressing correlations among fluents. A dynamic rule expresses the effect of the execution of actions. Syntactically, the effect H ← B is a static rule, while Cond is a conjunction of action literals representing actions being or not executed and fluent literals representing preconditions for the considered effects to take place.
The expressivity of EAPs was compared with that of the
action languages A, B, C (see [
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
Reactive Algebraic programs) [
On Event If Condition Do Action.
When B Do not Action. (1) (2) where Event is an event literal encoding the occurrence of an event and Condition is a conjunction of literals expressing the condition under which an Action (syntactically an atom) is executed. Finally, B is a conjunction of literals expressing conditions under which Action should not be executed. Both events and actions can be basic or complex ones. Complex events and actions are obtained by combining simple ones via an event and an action algebra.
Events occur at a given instant and are volatile information. Basic events may be external, representing incoming inputs and commands or internal, raised by the system itself. The event algebra allows to combine events occurring simultaneously or at different time points. For instance, the complex event A(e1, e2, e3), where A/ 3 is a ternary operator and the eis are events, occurs at instant i iff e3 occurs at instant i, e1 occurred at some previous instant and e 2 did not occurr in between. Actions represent operations to be executed. Basic action can be external, representing some external operation to be executed, or internal. As for events, basic actions can be combined by an algebra of operators for specifying flow of operations. For instance, given two action a 1 and a2, action a1 a2 specifies that action a2 must be executed after a1, while action (a1, a2) specifies that a1 and a2 can be concurrently executed.
Among internal actions, particularly important ones are the assertion and the deletion of facts and rules. While deletion removes facts and rules from the KB, the assertion of rules causes the application to update itself by a new fact, an inference, an active or an inhibition rule. New facts and inference rules are incorporated by the underlying DyLP semantics (that can be the refined as well as the well founded one). Also new active and inhibition rules are incorporated by the underlying DyLP semantics. Assertions of rules of the forms (1) and (2) are translated, respectively, into the LP updates
Action ← Condition, Event.
not Action ← B.
The underlying DyLP framework allows to establish
whether the atom Action is derived or not and, in the
former case, the corresponding action is executed. In this
way the application can update not only its KB but also
its beaviour by asserting new active rules and specifying
exceptions to existing active rules by asserting inhibition
ones. Moreover, it was proved that every Evolp program,
and hence every EAP, can be directly encoded into ERA.
Thus ERA is a paradigm capable of both executing and
reasoning about actions. In [
In this paper we have tried to briefly describe the research
activity that we have been carrying over during the last
years on dynamic logic programs. After reviewing our
contributions to strengthening the semantics foundations
of dynamic logic programs, we have presented the EAPs
formalism to reason about actions, and its recent
eventcondition-action extension ERA that supports the
specification and the execution of reactive programs. While space
limitations only allowed us to provide an extended abstract
of this research activity, more details can be found in the
papers [
There are several open windows for future work. One
of them is the definition of action query languages [