Interactive Graph Production System

1. INTRODUCTION

Eversince production systems (PS) were first proposed by Post [7] as a general computational mechanism, the methodology has heen a great deal of development and has been applied to a diverse collection of problems. A production system may be viewed as consisting three compo­ nents: a set of rules, a data base, and an in­ terpreter for the rules. In the simplest de­ sign, a rule is an ordered pair of symbol strings with a left and right hand sides, the set of rules has a predetermind total ordering and the data base is simply a collection of symbols.

Throughout much of the work reported, there ap­ pear to be two major views of PSs, as charac­ terized on one hand by the psychological model­ ling efforts (PSG, PAS n, VIS, etc.) [S, 6] and on the other by the performance-oriented, knowledge-based expert systems (e.g. MYCIN, DENDRAL) [ 2, 3]. For the psychological model­ lers, production rules offer a clear, formal, and powerful way of expressing basic symbol processing acts, which form the primitives of information processing psychology. For the designer of knowledge-based system, production rules offer a representation of knowledge that is relatively easily accessed and modified, making it quite useful for systems designed for incremental apploaches to competence.

Now we have trend to apply PSs to more and more complex prob~~ms. Those problems need more complex knowledge-bases. For instance, the DENDRAL system uses a literal pattern match, but its patterns are graphs representing chemi­ cal classes. For expressing complex situa~ tions graphs are better than collections of literals for human understandability. In many cases graphs are used for describing situations, and we see many usage of graphs for explana­ tions while collections of assertions are used for an internal representation of a system. So we want to construct a PS which treats not symbol strings or collections of assertions, but graphs.

In complex problems we find two situations in­ teracting each other. For instance, in a problem solving for controlling a robot we find a robot and its environment interacting each other. We think that it is better than a de­ scription by a single situation which repre· sents the robot and its environments, to de­ scribe the world by the set of two sub-situa­ tions: one represents the robot and the other does its environment; and changing of the world by interactive changing of two sub-situations. So we want to construct a PS which can express systems that interact each other also.

In this paper we will propose a new graph pro­ duction system that has interactions called an Interactive Graph Production System (IGPS). An IGPS represents a situation by a set of two labelled directed graphs and changing of situa­ tions by rewriting rules of graphs. So we will construct an IGPS based on the graph grammar system which is discussed in [1]. In this pa­ per we will first describe definitions of an IGPS, next show some examples of IGPSs for mak­ ing clear the method of descriptions and moves, and then discuss execution of an IGPS.

2. INTERACTIVE GRAPH PRODUCTION SYSTEM

In this section we will describe definitions of an IGPS. An IGPS is constructed by two la­ belled directed graphs and two sets of produc­ tion rules which control interactions and chang­ ing of situations.

2.1 Situations of an IGPS

A situation of an IGPS is represented by a tuple,

where o 0 and o 1 are sub-situations described by labelled directed graphs. More formally, a sub-situation Oi is represented by a 3-tuple,

where Ni is a set of nodes, L. 1- is a function: N. -+-a set of labels, and E. is a set of edges 11and is included into N. X N. 11-

[Example 1] situation. Here we show an example of a sub-

Then the sub-situation (N., L., E.) is the 111-

graph:

2.2 Structure of IGPS

An IGPS is a 7-tuple:

where C is a set of labels of sub-situations, V is a set of variables whose ranges are subsets of C, R is a function: V-+- 2C which defines the ranges of variables, i 0 and i 1 are two finite initial sub-situations whose sets of labels are C, and P 0 and P 1 are sets of productions which are applied to two sub-situations : o 0 and o 1 , respectively.

In this paper we will describe elements of C by strings of lower case letters and elements of V by strings of upper case letters.

2.3 Variables

An element of V is vi whose range is R(vi) E C. A variable v . can have a va lue of an element 0f R(v .) . t 1-

[Example 2] iable. Here we show an example of a var-

Then the value of 'PLACE' can be 'station' or 'school', but it can not be 'boy' nor 'girl'.

2.4 Productions

We describe a production of P 0 or P 1 by the form:

where G 1 is a labelled directed graph whose IN 1 1 is a non-negative integer and the set of labels is CUV, G 2 is a labelled directed graph whose IN 2 1 is a natural number and the set of label s is CUV, and G 3 is a labelled directed graph

whose set of labels is CUVU{null} and satisfies the conditions listed below.

At an application of a production each variable has one value. When two labelled directed graphs are compared, a variable V and a con­ stant c are compatible if the value of v is c.

[Example 3] We show an example of a produc­ tion in Fig. 1. In this example C, V and R of the IGPS are same as those in Example 2.

2.5 Effect of Application of Production

Let a situation of an IGPS be (a 0 , a 1 ), and let a production pij: (G 1 ) c 2 => c 3 ; be included in P. (i=O, 1). Then the production p .. may be ~ ~J applied, if Condition 1 and 2 are satisfied.

[Condition 1) Let a be al-i' and let G be G 1 , then Condition 1' is satisfied. If G is an empty graph, then this condition is satisfied.

[Condition 1')

then there exists N'cN: (N', L, EnN'xN') and G are compatible.

When Condition 1 is satisfied, the production p ·. can be applied if Condition 2 is satisfied. ~J

[Condition 2) Let c 2 ' be a graph which is made by rewriting labels of c 2 which are elements of V and used in c 1 as the value of the variable. Let a be ai and G be c 2 ·, then Condition 1' is satisfied.

If a production satisfying Condition 1 and 2 is applied, then a sub-graph of ai matching c 2 is rewritten as c 3 ·. Here c 3 · is a graph made by rewriting labels which are elements of V as the value of the label.

In an IGPS, production has a structuredescribed in 2.4, therefore deletion of nodes or edges is not avairable. But in an IGPS the special la­ bel 'null' expresses that the node will be not rewritten nor referred. Hence an IGPS inter­ preter can delete a node whose label is 'null' and edges which connect those nodes, there are no defferences in moves of the IGPS.

[Example 4] We show an example of aproduction and its application in Fig. 2 In this example,

and R(PLACEX) = R(PLACEY) = { placel, place2 }. When a situation of the IGPS is (ag, a~) of

Fig. 1 An example of a production of IGPS.

Fig. 2, if production-! of Fig. 2 is an element of P 0 of the IGPS, then in production-! thevalue of PLACEX is palce2 and the value of PLACEY is placel, and the production can be applied to

0 a 0 . If the production is applied to a situation of the IGPS becomes to be of Fig . 2.

Fig. 2 Example of a production and its appli­ cation.

2.6 Moves of an IGPS -------

One move of an IGPS is constructed by two sub0 0 moves. When a situation of an IGPS is (a 0 , a 1 ), one sub-move is an application of an element of 0 0 P 0 to a 0 , or preservation of a 0 when no element 0 of P 0 can not be applied to a 0 · Let the result Next one sub-move is an applies0 tion of an element of P 1 to a 1 , or preservation 0 of a 1 when no elements of P 1 can not be applied 0 1 1 to a 1 · Let the result be (a 0 , a 1 ).

3. SOME EXAMPLES OF IGPS ---

In this section we show some examples of IGPS for making clear the structure of an IGPS and the moves of an IGPS.

3.1 Three Coin Problem

Here we show the three coin problem of Jackson [4).

Problem: Given three coins initially HHT (i. e., head, head, tail), in exactly three moves make all coins show the same face. A move con­ sists of flipping a coin over.

We show below elements of an IGPS which de­ scribes the three coin problem and chunks of knowledge for solving the problem.

• C = { start, cont, flip, end, coinl, coin2, coin3, inc, countO, countl, count2, count3, head, tail, op, counter } ,
• V COINX, COINY, COINZ, CONT, COUNT, COUNTALL, COUNTNEXT, STATE, STATEX, STATEY } ,

R(COINX) = R(COINY) = R(COINZ) = { coinl, coin2, coin) } , R(CONT) · { cont, end }, R(STATE) = R(STATEX) = R(STATEY) = { head, tail } , R(COUNTALL) "' { countO, countl, count2, count3 } , R(COUNTNEXT) = { countl, count2, count) } , R(COUNT) · { countO, countl } , io start .... cont il inc .... countO .... count! coin! .... head inc .... countl .... count2 coin2 .... head inc .... count2 .... count) coin) .... tail head + op -+- tail counter -+- countO

P 0 and P 1 are shown in Fig. 3 and Fig. 4, re­ spectively.

(COINX-+- STATE COINY-+- STATE) cont :::> flip-+- cont

counter-+- COUNT

-t

COINX (I)

(COINX-+- STATE COINY-+- STATE) cont :::> flip-+- end

COINZ counter-+- count2

-t

COINZ (ll)

Fig. 3 P 0 of the IGPS which represents the three coin problem.

flip -+- COINX COINX-+- STATEX STATEX + op-+- STATEY

( -t

) counter-+- COUNTALL

CONT

inc -+- COUNT ALL -+- COUNTNEXT

• :::> COINX-+- STATF.Y STATEX + op -+- STATEY counter-+- COUNTNEXT inc -+-COUNT ALL-+- COUNTNEXT

Fig. 4 P 1 of the IGPS which represents the three coin problem.

In this IGPS the sub-situation o 1 which is ini­ tially i 1 expresses a situation of coins, and the sub-situation o 0 which is initially i 0 ex­ presses a situation of a process of solving. Productions of P 0 generate moves which fit in the situation with referring a sub-situation o 1 by getting knowledges of coins' situation and how many times the move is with c 1 . A production of P 1 expresses the move which is gener­ ated by P 0 · In o 1 "inc-+- countO-+-countl" ex­ presses the move of a counter. And "head +op-+- tail" expresses that 'head' and 'tail' are opposite faces of each other.

In Table 1, we show changes of a sub-situation o 0 of the IGPS. And in Table 2, changes of a sub-situation o 1 of the IGPS are shown. In Table 2 we omit part of sub-situation o 1 which do not change for making short.

3.2 Monkey/banana Problem

The familiar monkey and banana problem is for­ mulated as an IGPS. In three coin problem, IGPS always generates correc t answers, but in the present case IGPS expresses a process of monkey's trial and error process. Here, monkey does not want to do a move which can not be car­ ried out. And if monkey can take banana, hP must take it. We show elements of the IGPS below.

P 0 and P 1 of the IGPS are shown in Fig. 5 and Fig. 6, respectively. The initial sub-situation

Fig. 5 P 0 of the IGPS which represents the monkey and banana problem.

Fig. 6 P 1 6f the IGPS which represents the monkey and banana problem.

i 0 is shown in Table 3, and i 1 is shown in Fig. 7. A process of monkey's trial and error are shown in Table 3.

Table 3 Process of changing of o 0 ·

mky ~at~ placel box-+ at~ place2 ban~ver~ place3 Fig. 7 The i 1 of the monkey and banana problem.

4 . .:::;E:.:.XE:::.;C::..:U:..:Tc.::I.=.ON:..:. OF _IG_P_S

In this section we discuss execution of IGPS. The core of execution of IGPS is an IGPS inter­ preter, which receives an IGPS and execute the IGPS. And we need a production editting sys­ tem for easy description of productions. The production editting system enables us to edit productions on a graphic display unit and gen­ erate sets of productions.

4.1 IGPS Interpreter

We implement an IGPS interpreter which executes an IGPS originally in accordance with the def­ initions of IGPS. But the IGPS interpreter has some functions for making processing fast and description of productions easy.

The IGPS interpreter has two modes except a basic mode. In the basic mode the IGPS inter­ preter applies one production at one time ac­ cording to the definition of the IGPS. In ex­ panded mode 1, the IGPS interpreter tries to apply productions which are permitted to apply at one time. And in expanded mode 2, the IGPS interpreter tries to apply all productions to all sub-graphs at one time while productions can be applied. In those expanded modes, the number of decisions on whether a production may be applied or not decreases, so processing time at one application of a production decreases.

In the definition of IGPS we did not define how to se lec t a production, so we must now decide how to select a production. In most of pro­ duction systems, for instance RPS [8], produc­ tions are ordered and the first production which matches the data-base is applied. But if we use rule-ordering for selection of a pro­ duction, we can not describe the monkey and ba­ nana problem as in 3.2. Therefore the IGPS interpreter enables us to decide a selection method of a production among three methods. The first method is the conventional rule-or­ dering. The second one enables us to specify a priority of productions at each move. And the last one enables us to specify an algorithm which decides a priority of productions at each move.

4.2 Production Editting System

A production of IGPS is constructed by three tuple of labelled directed graphs. For ed­ itting productions e"fficiently, we need some functions, which enables us to define a set of constant C, a set of variables V and a range function R, and to input labelled directed graphs, and to check inputted productions. Input of labelled directed graphs can be done by inputting a label of each node and a tuple of a head and a tail of each ed~e using punched cards, but we can not inspect graphs efficient­ ly using a list of a label of each node and a list of a tuple of a head and a tail of each edge. So the production editting system must enable us to edit productions: three tuple of labelled directed graphs, using graphical de­ scriprion. Therefore the production editting system uses a graphic display unit for display of productions. And the production editting system enables us to edit productions interac­ tively.

5. CONCLUSION

In this paper, we have proposed a new produc­ tion system: IGPS. IGPS is a formal system which expresses a structure and moves of a system which has interaction. And we have shown examples of an IGPS for making clear de­ scriptive power and moves of IGPS.

In the field of artificial intell i gence, we treat a diverse collection of problems. Some of them have interaction in their s ituations . For express ing these probl ems we need a produc­ tion system which can express interac tion. Of course conventional produc t ion sys tems· can ex­ press a system which has interaction . But simplicity, modularity and other favourable PS's features are lost. IGPS can express a system which has interact ion while increasing favourable PS's features. And further us ing labelled directed graphs, IGPS can expres s very complex situa tions.

ACKNOWLEDGEMENTS

The authors appreciate ·many helpful conversa­ tio with several graduate s tudent s and mem­ bers of Prof. Tanaka's Lab. of Osaka Universi­ ty.