C H A P T E R  5
Dynamic Logic Programs

5.1 Introduction

In our discussion thus far, we have been talking about the use of datasets and logic programs and deductive databases to describe individual states of the world. In many application areas, it is necessary to describe not just individual states but also transitions between states. Dynamic logic programs provide a means for us to describe such changes.

In what follows, we first introduce the notion of a transition rule. We then show how transition rules can be used to describe the dynamics of closed systems (where the system changes state on its own); and then we describe how transition rules can be used in describing the dynamics of open systems (where the system's behavior changes in response to external stimuli). We then discuss the trade-offs between differential update and whole-state update. And we conclude by comparing transition rules to situation calculus, a popular alternative to formalizing the behavior of dynamic systems.

5.2 Transition Rules

The language of dynamic logic programming is a superset of the language of ordinary logic programing. Every ordinary logic program is also a dynamic logic program. As in ordinary logic programming, we can write ground atoms and view definitions. However, in dynamic logic programming, we can also write "transition rules", which encode information about how the state of the world changes (over time or in response to external stimuli).

A transition rule is an expression of the form shown below. Each rule consists of (1) a literal (an atom or a negation of an atom) or a conjunction of literals, (2) a double shafted forward arrow, and (3) a literal or a conjunction of literals. The literals on the left are called conditions, and the literals on the right are called effects.

[~]φ1 & ... & [~]φm ==> [~]ψ1 & ... & [~]ψn

Intuitively, the meaning of a transition rule is simple. If the conditions of a rule are true in any state, then the effects must be true in the next state. (Remember that, for a literal to be true, the atom inside the negation must be false.)

For example, the following rule expresses the fact that, when p(a) is true and q(a) is false, then p(a) becomes false and q(a) becomes true in the next state.

p(a) & ~q(a) ==> ~p(a) & q(a)

As with view definitions, the conditions and effects of rules may contain variables to express dynamic information in a compact form. For example, we can write the following rule to express the fact that the preceding transition rule holds for all objects.

p(X) & ~q(X) ==> ~p(X) & q(X)

As with view definitions, transition rules are required to be safe. In this case, this means that every variable among the effects of a rule or in negative conditions must appear in the positive conditions of that rule.

The transition rule rules shown above are all safe. However, the rules shown below are not. The effect of the first rule contains a variable that does not appear in any condition. In the second rule, there is a variable that appears in a negative condition that does not appear in any positive condition.

p(X) & ~q(X) ==> ~p(X) & q(Y)
p(X) & ~q(Y) ==> ~p(X) & q(X)

If we were to allow the first of these rules, the resulting dataset might contain infinitely many effects (all the instances of the rule's effect). If we were to allow the second rule, we might have to check infinitely many conditions (all of the instances of the negated condition).

A dynamic logic program (DLP) is simply a collection of view definitions and transition rules. As with ordinary logic programs, we are interested primarily in dynamic logic programs that are finite. However, in analyzing dynamic logic programs, we occasionally talk about infinite DLPs, e.g. the set of all ground instances of the rules.

5.3 Closed Systems

A deterministic closed dynamic system is one that operates without external input, changing from one state to the next in a deterministic fashion. These are sometimes called closed systems or Markov systems.

Note that, in addition to deterministic closed dynamic systems, there are also non-deterministic closed dynamic systems (systems in which there are multiple successor states for each state); and there are probabilistic closed dynamic systems (systems in which the transitions between states have different probabilities of occurring). However, in this book, we concentrate exclusively on deterministic closed dynamic systems.

Transition rules are an effective way of describing the behavior of closed systems. As an example, consider a simple dynamic system like the one shown below There are three conditions that can hold in a state - p, q, and r - meaning that the system has a total of eight possible states.

The state transition diagram (or state graph) shown here illustrates the behavior of the system. Note that each state has a unique successor state. Note that, once the system enters some states, it never returns to those states. At the same time, the system loops among some states over and over again.

The following transition rules express the behavior of this system. Given any state in which p is true, p becomes false in the next state; and vice versa. If p is true in a state, then q becomes true in the next state. If p and q are true in a state, then r becomes true in the next state; otherwise it becomes false.

p ==> ~p
~p ==> p
p ==> q
p & q ==> r
~p ==> ~r
~q ==> ~r

This, of course, is a very simple closed system. There are many examples of closed systems in the real world. In fact, the universe as a whole can be viewed as a closed system (though there are some who would argue that it is really a non-deterministic closed system). The following section describes an class of more complex closed systems that exhibit interesting behavior.

5.4 Example - The Game of Life

The Game of Life is a cellular automaton devised by the British mathematician John Conway in 1970. The universe of the game is a two-dimensional orthogonal grid of square cells, each of which is in one of two possible states - alive (shown in black) or dead (shown in white). Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent. On each step, the next state is determined by applying the following rules.

  • Any live cell with fewer than two live neighbors dies, as if caused by underpopulation.
  • Any live cell with two or three live neighbors lives on to the next generation.
  • Any live cell with more than three live neighbors dies, as if by overpopulation.
  • Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Press Play to allow the system to operate on its own. Press Pause to pause operation. Press Step to advance one step.


                 
                 
                 
                 
                 
                 
                 
                 
                 

Changing the initial state of the system can change the way the system evolves. In some cases, the system reaches quiescence, i.e. nothing changes from step to step. In some cases, the system oscillates. With an infinite universe, it is possible for a system to run forever without repeating any state.

With the game paused, create a new state by clicking cells to toggle their statuses between live and dead. Once you are done, click Play to see what happens with your new state. Reload the page to return to the initial state.

Now, let's see how we can describe this system using transition rules.

index(M) & index(N) & ~value(cell(M,N),on) & countofall(Y,support(cell(M,N),Y),3) ==> value(cell(M,N),on) value(X,on) & countofall(Y,support(X,Y),N) & bad(N) ==> ~value(X,on)

Of course, we must also define the concepts used in these transition rules.

support(X,cell(M,N)) :- kingmove(X,cell(M,N)) & value(cell(M,N),on) bad(N) :- max(N,1,1) bad(N) :- min(N,4,4) kingmove(cell(X1,Y),cell(X2,Y)) :- succ(X1,X2) & index(Y) kingmove(cell(X1,Y),cell(X2,Y)) :- succ(X2,X1) & index(Y) kingmove(cell(X,Y1),cell(X,Y2)) :- succ(Y1,Y2) & index(X) kingmove(cell(X,Y1),cell(X,Y2)) :- succ(Y2,Y1) & index(X) kingmove(cell(X1,Y1),cell(X2,Y2)) :- succ(X1,X2) & succ(Y1,Y2) kingmove(cell(X1,Y1),cell(X2,Y2)) :- succ(X2,X1) & succ(Y1,Y2) kingmove(cell(X1,Y1),cell(X2,Y2)) :- succ(X1,X2) & succ(Y2,Y1) kingmove(cell(X1,Y1),cell(X2,Y2)) :- succ(X2,X1) & succ(Y2,Y1)

Finally, we need some base data.

index(1) index(2) index(3) index(4) index(5) index(6) index(7) index(8) index(9)   succ(1,2) succ(2,3) succ(3,4) succ(4,5) succ(5,6) succ(6,7) succ(7,8) succ(8,9)

5.5 Open Systems

An open dynamic system is one in which state changes depend not only on the current state of the system but also on inputs from the system's external environment.

The most common example of such inputs are actions performed by one or more agents operating on the system. As an example, consider a variation on the closed system describe in Section 2. Again, the state of the system is based on three conditions p, q, and r. However, in this variation, the behavior of the system is determined not just by the current state but also by the actions on an external agent. In the version shown here, the agent has three possible actions - a, b, and c. Doing action a toggles p; doing action b interchanges p and q; and doing action r interchanges q and r.

We can described the behavior of this simple system with the transition rules shown below.

a & p ==> ~p
a & ~p ==> p
b & p ==> q
b & ~p ==> ~q
c & q ==> r
c & ~q ==> ~r

Note that, if the system started in a state in which all three conditions were false, it could achieve a state in which they are true by executing the action sequence a, b, c, a, b, a. Can you think of a different sequence of actions that would do the trick? How many sequences are there that produce the desired state?

5.6 Example - Blocks World

As a more complex example of an open system, once again consider the Blocks World introduced in Chapter 3. One state of the Blocks World is shown below. Here block C is on block A, block A is on block B, and block D is on block E.

A
B
D
C
E
 
Figure 1 - One state of Blocks World.

Now, let's consider a dynamic variation of this world, one in which there is a robot that can modify the state of the world.

u(X,Y) & clear(X) & on(X,Y) ==> ~on(X,Y) & table(X) & clear(Y)
s(X,Y) & table(X) & clear(X) & clear(Y) ==> ~table(X) & ~clear(Y) & on(X,Y)

5.7 Example - Databases

In updating a database, a user specifies a sentence to add to a database or a sentences to delete. In some cases, the user can group several changes of this sort in a single, so-called, atomic transaction. If the result of executing the transaction satisfies the constraints, the update is performed; otherwise it is rejected.

Unfortunately, if a user forgets to include an addition or deletion required by the constraints, this can lead to errors. In order to simplify the update process for the user, some database systems provide the administrator the ability to write update rules, i.e. rules that are executed by the system to augment a specified transaction with the additions and deletions necessary to avoid errors. In what follows, we show one way that this can be done with transition rules.

Our update language includes two new operators - pluss and minus. pluss takes an atom as argument and is true in a state if and only if the user specifies that atom as an addition in that state. minus takes an atom as argument and is true if and only if the user specifies that atom as a deletion in that state. Using this new vocabulary, administrators can write transition rules to specify how the database should change in response to user requests.

As an example of this mechanism in action, consider the rules shown below. The first directs the system to remove a sentence of the form male(X) whenever the user adds a sentence of the form female(X). The second rule is analogous to the first with male and female reversed. Together, these two rules enforce the mutual exclusion on male and female.

pluss(female(X)) ==> ~male(X)
pluss(male(X)) ==> ~female(X)

Similarly, we can enforce the inclusion dependency on parent and adult by writing the following rule. If the user adds a sentence of the form parent(X,Y), then the system also adds a sentence of the form adult(X).

pluss(parent(X,Y)) ==> adult(X)

Another use of this update mechanism is to maintain materialized views. (A materialized view is a defined relation that is stored explicitly in the database, usually to save recomputation.)

Suppose, for example, we were to materialize the father relation defined earlier. Then we could write the update rules to maintain this materialized view. According to the first rule, the system should add a sentence of the form father(X,Y) whenever the user adds parent(X,Y) and male(X) is known to be true and the user does not delete that fact. The other rules cover the other cases.

pluss(parent(X,Y)) & male(X) & ~minus(male(X)) ==> father(X,Y)
parent(X,Y) & pluss(male(X)) & ~minus(parent(X,Y)) ==> father(X,Y)
pluss(parent(X,Y)) & pluss(male(X)) ==> father(X,Y)
minus(parent(X,Y)) ==> ~father(X,Y)
minus(male(X)) ==> ~father(X,Y)

Note that not all constraints can be enforced using update rules. For example, if a user suggests adding the sentence parent(art,art) to the database in our interpersonal relations example, there is nothing the system can do to repair this error except to reject the transaction. In some cases, there is no way to make a repair unambiguously; more information is needed from the user. For example, we might have a constraint that every person is in either the male or the female relation. If the user specifies a parent fact involving a new person but does not specify the gender of that person, there is no way for the system to decide that gender for itself.

Exercises

Exercise 5.1: The transition rules for the Buttons and Lights World in Section 5.3 assume that just one action is performed at a time. Find a situation in which the rules will give an incorrect update if multiple actions are performed at the same time. Write transition rules that correctly update the database for any combination of actions.

Exercise 5.2: Consider the game of life presented in Section 5.4. The state in which all cells are dead is stable in that it does not change from one step to the next. Find another state in which the world is stable.

Exercise 5.3: Consider the game of life presented in Section 5.4. The initial state shown in that section eventually reaches a point at which the world oscillates between two different states. Find a different state in which the world oscillates between two different states.

Exercise 5.4: Consider the Blocks World described in Section 5.6, and imagine an action m(x,y,z) that moves block x from block y to block z provided that block x is clear, block x is on block y, and block z is clear. Write a transition rule that describes the effects of this action.