A Framework for Control in Production Systems

1. INTRODUCTION

Over the years a range of different mechanisms have been proposed for representing and using knowledge about general and possibly ill-defined problem domains. Of these, production systems [12] have been among the most promising, and have been applied to a diverse collection of pro­ blems, including mass spectroscopy [4],medical diagnosis [15], electronic circuit design [10] and automated theory formation in mathematics [8]. Most theorem provers can also be viewed as production systems (e.g. PROLOG [16]).

Informally, a production system consists of a set of modules or procedures called productions and a data base on which these productions operate. Now one of the most fundamental and significant characteristics of production sys­ tems is the lack of explicit control information ---that is, production invocation can only be achieved indirectly through the data base. The primary effect of this indirect means of produc­ tion invocation is to produce a system which is strongly modular, flexible and adaptive, and thus well-suited as a knowledge based system. However, it is also perhaps the most significant factor in complicating the programming of pro­ duction systems, in making the behaviour flow more difficult to analyse, and in increasing the difficulty of an adequate formalization [1].

Now there are two reasons why we would like to have control. The first, and to which we alluded above, is that the solutions to many problems are most naturally represented by sequences of actions rather than by sets of actions in which the order of application is unimportant. We tend to use plans or strategies, even whenwe are manipulating declarative knowledge or facts about the world (e.g. consider the wide use made of procedural attachment in most knowledge based systems). Secondly, any large production system tha.t does not somehow constrain the number of productions that are active at any one time be­ comes so inefficient as to be unworkable. ·The problem is: how do we achi~ve such control with out sacrificing the raison d 'etre of production systems.

!fany production systems use some form of control information. Usually, this remains hidden in the productions or in the data base in the form of special flags and other hand-crafted markers [11]. Other systems use more explicit means of control (e.g. NASL [10], annotated systems [6]), but the control structures are limited and are often difficult to access or modify. But most importantly, no system provides a uniform frame­ work in which control issues can be addressed, nor a direct means of implementing control con­ straits---in every case the control schemes are essentially ad hoc.

In this paper we approach the problem from the other direction. That is, we formally charac­ terize the notion of control a~plied to produc­ tion systems, and then consider how best to implement such a s cheme. The scheme we propose, which we will call a cont:r>oZZed p:r>oduction system , simply consists of a production system together with a control device called a control language. This provides us with a uniform framework for representing control in production systems, and allows us to examine in a very general way how the various approaches to realizing (imp­ lementing) control affect the properties and behaviour of the system as a whole.

In fact, it first appears that the notion of con­ trol in production systems is quite obvious, and hardly needs formalizing. However, if we examine the control schemes of current production sys­ t ems---apart from their ad hoc nature---we see control being used in quite different ways. For example, in most schemes (e.g. PROLOG) control is interded to simply enhance the efficiency of the system---given enough time, the systemwith­ ou t the control component would find the same solutions as the system with control. In other schemes (e.g. (13]), and in fact in most of the aforementioned schemes (e.g. PROLOG), control can be used in the same manner as in procedural languages---that is, the solutions obtained depend critically on the order in which the pro­ due tions are invoked. Such confusion leads to ad hoc systems the behaviour of which it is very difficult to predict and the solutions to which it is very difficult to validate. That is, it leads to a programming methodology quite the opposite of that favoured for procedural langu­ ages . Further, domain specific control knowledge is difficult to realize as it becomes confused with efficiency issues (3]. Formalizing the no­ tion of control avoids these difficulties, and allows system efficiency to be treated as a separate issue.

2. CONTROLLED PRODUCTION SYSTEMS

Informally, a production system (PS) consists of a set of modules or procedures called pPo­ duction Pu les and a data base or woPking memoPy to which these rules are applied. Each produc­ tion rule is an expression or string of symbols which consists of two parts called the lefthand­ side (LHS), or antecedent, and the Pighthandside (RHS), or conaequent . These respectively denote a cund·/t·ion which is to be satisfied before the production can be applied or invoked, and an action whi ch specifies the result of application of the production to the data base.

In the simplest execution scheme, the conditions in each production ar2 evaulated for the current s tate of the data base, one of the satisfied produc t ions is selected, and the action specified by that production then execut ed. The procedure is then repeated for this new stat e of the data base. Execu tion terminates either when there are no satisfied productions or when SDme desired state of the data base is achieved. Ingeneral execution is nondeterministic, as at any stage during execution more than one production may be applicable. The set of productions applicableat each stage of execution is known as the conflict set, and the selection procedure is usually called conflict Pesolution.

For example, consider the following production system where states of the data base are words over the alphabet {S,A,B,C,a,b,c}andwhere the productions (which are to be interpreted in the normal rewriting sense) include

p 1 : S -+ ABC

p s: A -+ a

P4:A-+aA

P6:B-+b

p3: B -+ bB

P7 : C -+ c

p .. : C-+ cC

For an initial state S of the data base, the set of possible final states is the set of strings {a-1\mcn: t~l,m~l, and n~ l}. Depending on how the sys tern is implemented, it can be used either as a generator of these strings or as a recognizer for these strings.

Suppose that we now wish to introduce explicit control constraints into such a system. One way to achieve this is to allow productions to throw special symbols into the data base to constrain invocation of other productions (e.g. [11]). However, this scheme has numerous drawbacks. Firstly, in order that the desired constraint is effected, it is necessary to invest the produc­ tions that respond to these special symbols with a higher priority of invocation than all other productions that might also be satisfied by the current state of the data base. We thus end up with two classes of symbols in the data base, or equivalently, two c lasses of productions. Nothing is wrong with this, of course, except that we have changed the nature of the produc­ tion sys tern. Secondly, it is clear that the above scheme will not work unless the special symbols are known to be unique to the invoking and the invoked productions, and such uniqueness can only be established by reference to the condi­ tion part of all other produc tions. Other pro­ blems are also present in the above scheme. The system loses its potential extensibility as these special symbols essentially invoke pro­ ductions by name rather than by content. Further, augmentation and modification of control infor­ mation is extremely difficult.

Other contol schemes have been proposed which avoid some of these problems (e.g. (13]), but control is still achieved indirectly through the conflict resolution scheme. One consequence of this indirection is that code is also indi­ rect and cumbersome, as, for example, that needed for keeping loop productions dominant during iteration [13]. What is worse, control information can only be expressed having a full knowledge of the conflict resolution scheme, and this is not always possible nor desirable- con­ sider, for example, systems that involve a dyna­ mic conflict resolution scheme e.g. TEIRESIAS [2). Furthermore, in order that control cons­ traints are not eventually overridden, production sequencing determined duringconflictresolution must be irrevocable, at least for control ele­ ments, and this brings into question the function of the conflict resolution scheme as a means of handling nun-determinism.

We thuB adopt an alternative approach whereby we specify control information explicitly and inde­ pendently of the conflict resolution scheme. To do this we will simply require that any cons­ traints on production invocation be specified by means of a language over the production set. We will call such a language a control language. A production sequence and the relation it defines on the data base is then only allowed if this production sequence is included in the control language. Thus at each stage of execution, the control language restricts the set of produc­ tions that may be considered for invocation and only a subset of the total production set is active. The only productions that can enter the conflict set are those that both have their con­ dition satisfied by the current state of the data base and are contained in the active produc­ tion set. We will call a production system to­ gether with a control language a controolled proo­ duction system (CPS).

For example, consider the above production sys­ tem together with a control language defined by the regular expression

P!(PLP3P4)*P5P6P7

Then the set of final states of the data base given the initial stateS is the set of strings {anbncn: n<:l}. Note that this controlled produc­ tion system is nondeterministic and that after executing production P4 the conflict set will contain two productions (namely, PL and ps).

Thus it is seen that a controlled production system differs from the more usual production systems only in that it has an explicit and inde­ pendently specified control structure. This con­ trol structure acts as a constraint on production invocation---it effectively reduces the possible interactions between productions. In one sense, the control structure provides private channels of communication between productions. This allows the power of a production system to be increa!;ed without increasing the complexity of the produc­ tions. For example, if we allow productions that check for a symbol not being in the current state of the data base, then it can be shown that con­ text-free rewriting systems with regular control languages generate all the recursively enumer­ able languages [14].

2.2 Formal Definitions

A production system (PS) is a triple P = o:,n,h>

(2 . 1)

where l: is an alphabet called the set of prooduc­ tion names, D is a set called the data base and h, called the interproetation of l:, assigns to each element of Eapair (q,r), where q is a total predicate on D and r is a relation on ll. For any production name p, we will say that the first co-ordinate of h(p) is the condition denoted by p and that the second co-ordinate of h(p) is the action denoted by p. Elements of D will usually be ref erred to as states of the data base. For each production o, we will also require that all states of the data base which satisfy the condi­ tion of p be in the domain of the action of o.

We now introduce the notion of a controlled pro­ duction system. We take as our control device a language over E. Formally a control language over l: is any subset of l:*, where !.* is the free monoid over l: with idenlity A.

We define a controolled production system (CPS) to be a quadruple

where C is a control languag,~ over I. and ( l: ,D,h) is a production system. A CPS (E,D,h,c> with C = l: * is equivalent to the PS(E,D,hl. We can therefore consider a PS to be a special case of a CPS.

We are now in a position to define the execution of a CPS. Let Cbea CPSasdefined in (2.2). We first define a state of execution (or simply state) of C to be a pair s = <u,x) where u is a prefix of some word in C and x is an element of D. Now let u and up be orefixes for some word in C, where u E E~ p E E and h(p) = (q,r>. Then we say a state <up,xz) is diroectly computed from a state (u,xl >, denoted <u,xl) ~ c (up,XL >, if and only if we have q (xt) = true and <x1, X:t) E r. If the above holds, we will also say that the state (up,xl) results from execution of produc­ tion p in state <u,xl >.

Let~ c* denote the reflexive transitive closure of the relation ~ c. Then the relation computed by C is defined to be the set R(C) = {<x,y>: <A,x>~c*<w,y) for some win C}

Informally, a CPS Cmay be (nondeterministically)

executed for some initial state x of the data baseD in the following manner. At each morr.ent of time, execution is at some state. Initially this sta te is CA,x). Suppose that execution has arrived at some state Cu,y). Now a production p can be considered for evaluation if up is apre­ fi x of some word in C. Let us call the set of a ll such productions the active production set. Suppose this set is empty. Then execution ter­ minates successfully if u is an element of C and terminates unsuccessfully if u is not in C. Otherwise, execution may either terminate suc­ cessfully (if u is in C) or continue by evalu­ a ting the condition of each active production wi th r espect to the current state of the data base. All of those productions which are satis­ f i ed form what is known as the conflict set. If the confli c t set is empty, tt.en execution termi­ na t es unsuccessfully. Otherwise, a production p i s (nondeterministically) selected from this set, and execution continued from a (not neces­ sarily unique) state Cup, z ), where Cy, z) is an e lement of the ac tion denoted by p. The final s tate of the data base is obtained on success­ ful t ermination of execution.

The most obvious wa y to implement such a scheme i s simply to augment the recognize-act cycle of c l assica l produc tion systems with a stage that de termines, on the basis of the control langu­ age, the set of active productions (or equiva­ l ently masks off the non-active productions). However , it is not clear how the control langu­ age should be spec ified.

3 . SYSTEM BEHAVIOUR

i t is first necessary to consider how the con­ trol l a nguage and its means of specification wi ll a ffect the behaviour of the system as a whole. In part i cular, we need to consider how the imposition of a control language will affect the additivity and adaptive behaviour of the system.

3. 1 Additivity a nd Adaptive Behaviour

Extensibility and the capacity for self modifi­ ca t i on are important charac teristics of intelli­ gent sys t err.s, and any control scheme should a llow of . such behaviour. Consider for example the problem of learning to add two positive i nt eger s gi ven only the successor function. We wi ll need the following two actions: DEP (d ) which places d in the data base and PUT(p,q,r ,c ) whi ch (i) adds the production with name p, LHS q and RHS r to the production set and ( ii ) adds the symbol string c to the control l anguage . GENSYM is a parameterless procedure whi ch generates a new symbol (production name), and s i s the successor function.

The initial production set for solving this pro­ blem is as follows p1: (ready) ~READ; DEP( count 0) pz: (count ?x1)(m "?x1)(n ?xz) -·DEP(count (s ?xJ)); DEP(n(s?x2)) P3: (count ?x1 Xm ?x1 ){n ?x;l) ~WRITE(?x:L) P'+: (n ?x1) ~nEP(no ?x1) ps : (count ?x1 )(n ?xz)(no ?x3)~?x~t+�ENSYM; PUT(?x .. ,((m?xl)(no ?x3)),(WRITE ?xz),PIP'+?x4) (The notation obeys typical AI language conven­ tions i.e. variables prefixed by ? have values bound to them and when bound must match that value, and variables prefixed by I? are taken to match anything other than the value bound). Hi th the control language PI P:L*P3 the sys tern per­ forms addition without learning anything, with the control language PI p4 p2 *PJ p5 we have essentially the example in [ 17], and with the control language PIP'+(PLP~)*P3 the system learns intermediate results as well.

The important point to note is that adaptive behaviour and additivity- in the sense of being able to modify the production set- is not pre­ cluded by the introduction of a control compo­ nent. Further, a control language need not, and rarely will, specify all and only those produc­ tion sequences that represent solution paths, but will simply place (greater or lesser) con­ straints on production invocation. Thus the synergic properties of the system will also be retained.

3.2 Semantic Specifications

In the above example we achieved additivity at the expense of havi11g to explicitly augment the control language. Now in many applications such explicit modification of the control language will be difficult.

For example, consider the problem of cascading two amplifiers [10). We could represent this problem using productions of the form to: (make cascade-amp)-+(make collectorXmake emitter )(make couple)

t1: (make collector) -+ . · .

t:L: (make emitter) -+ . · .

t3: (make couple) -+ .·.

together with the control constraint given by the regular expression (t1t:L+t2t1)t3. In English, this simply says that to cascade two amplifiers we first construct a common collector and a com­ mon emitter (in any order) and then couple them. Now if we add to the production set a new method t '+ for making collectors this new method will never be considered unless we explicitlysubsti­ tute (tl + t4) for each occurence of t1 in the above control sequences. Furthermore, we should do the same thing for every control sequence in which t 1 appears, not just those appearing above.

The problem clearly lies in the means used for specifying the control language. Let us briefly consider what's going on. Most languages are specified syntactically because of a desire to describe the language solely in terms of its alphabet without regard to any semantic inter­ pretation of the language. But in the present case there is no need to be so restrictive. As the interpretation is a component of the formal model (see eqn 2.2), it can also be used in specifying the control language, that is, the control language can be specified by its seman­ tic content rather than its syntactic form.Thus in the above example, we could have specified the control constraint semantically: if Pl is a production that makes a collector (or whose LHS mentions 'collector') and pi. is a production that makes an emitter and P3 is a production that couples them, then P1Pi.P3 and P2PlP3 are in the control language.

Pl, pi., and P3 are variables ranging over the set of productions, and the specification says, in effect, that a production that makes a common collector and a production that makes a common emitter should be invoked before a production that couples the two components.

Semantic specification thus avoids the problem of explicit modification of the control language, and additivity is better realized. Most other properties desired of knowledge based systems are also retained- the system remains highly modular and flexible, and retains its explana­ atory capacity. Of course, the dependence of these properties on the means of production ref­ erence is well known [ 2] - the only difference is that here we are using semantic reference to effect control constraints rather than to improve system performance.

Semantic control information is also the type of information most likely to be possessed by an expert interacting with such a knowledge based system. For example, consider a world consisting of some blocks and a (large) table. Now we know that in an optimum solution we will never put one block on top of another block that has to be subsequently cleared, which we may express as follows:

if the action part of a production puts a block x on a block y then it cannot be followed (no matter how much later) by a production whose condition part requires y to be clear. We can then interpret this directly as a seman­ tic specification of the control language. (Interestingly, such a simple control constraint considerably reduces the search space as, for example, production sequences of the form ... (PUTON x y) ... (PUTON y z) ...

are excluded from consideration.)

One problem with implementing such a scheme is that in the general case it is very difficult to extract the required semantic information from a body of code. The problem is not so severe in (controlled) production systems because the code usually consists of a number of relatively small , independent chunks of knowledge, and these often represent computationally primitive opera tions. More important, however, is that in a CPS the control information is specified in such a way that semantic criteria can be used as a means of invocation---how the semantic information is obtained can be treated as a separate issue [3].

The other problem is one of system eff iciency. Even in cases where the object level system i s made more efficient, the time spent in evalu­ ating semantic criteria can easily offse t thes e gains. However, if the product i on s et is fixed then it is not necessary that the semanti c cr i ­ teria be evaluated at execution time---in many cases it will be more efficient to transform the semantic specification into a syntac ti c ~peci­ fication at compile time. In these cas es, seman­ tically based invocation can be expected to pro­ vide both a powerful and relatively efficient means of control.

4. CONTROL LANGUAGE DEVICES

Any desired control constraint can be specif ied by a control l anguage. In turn, however, we require some device for specifying control lang­ uages. Now \ve are in a better pos i ti .:>n to con­ struct such a device if we know wha t c l ass of languages the device is required t o generat e. Thus in this section we examine some t ypica l AI control constructs and see how they are placed within the standard hierarchy of languages [ 14] .

4.1 Control Language Types

One of the simplest c lasses of l anguages is t he type 3 or regular languages. As control languages they are surprisingly powerful---thus, as men­ tioned in Section 2.1, they can inc r ease the power of context-free rewriting systems to that of a Turing machine. As the solutions to many problems are often conceptualized as a sequence of actions, regular control languages a lso i m­ prove constructibility.

Both direct sequencing and iterat i ve control can be specified by means of regular control langu­ ages (e.g . see the example of Section 3.1) . This class of languages is also powerful enough t o realize partitioned production systems (pro­ cedures [11], packets or multiple produc tion memories [9]). If we consider the control lang­ uage to be generated by a transition network, then each state in that network defines a set of active productions, these being the produc-­ tions that label the outgoing arcs. Each tran­ sition either loops and thus leaves control in the same state (i.e. with the same set of active productions) or transfers control to another state (i.e . to another set of active productions). Thus as long as we continue to loop on a given state we effectively operate on a subset of the entire production memory.

Context-free control languages can be used to specify recursive procedures or goal-subgoal control cons true ts where the subgoals are to be achieved in a specified order. This is readily seen as follows. Let the control language be generated by a context-free grammar. We can interpret each non-terminal symbol appearing in the grammar as the name of a procedure in the CPS, and each terminal symbol simply as the name of a production in the CPS. Now (top-down) left-right generation of control language sen­ tences produces possible execution sequences of the CPS, where each expansion of a non-terminal symbol is interpreted as a call to the procedure having that name. In AI terms, each expansion of a non-terminal is equivalent to the reduc­ tion of a goal to a sequence of subgoals. Such control constraints correspond to the SUCCESSOR and SUBTASK relations in NASL (10] and to the fall-back and held-result-useage control constructs described in (13].

Let us consider again the problem of construc­ ting a cascade of amplifiers. The solution pro­ posed in Section 3.2 was not really sufficient, as firstly it did not restrict the scope of the control constraint to the case of cascading amplifiers, and secondly because it required the subtasks (i.e. the making of the common collector, etc.) to be primitive. However, we can overcome both these difficulties by letting the production names stand as non-terminals in

a con text-free grammar which contains the rules

to -+ t 1 tzt 3 to -+ t 2t1 t 3 The result is that in trying to achieve to, we have to achieve t1 and t2 before t3, where this time tt, t2 and t 3 may themselves be expanded into further (sequences of) subtasks. (In fact, we have really changed the entire nature of the object level production system, as it now need contain only primitive productions (i.e. pro­ ductions with no subtasks). For our purposes this is not important, but it does indicate that much domain specific knowledge, in our terms at least, occurs at the control level).

One particularly interesting aspect of con text­ free CPSs is that they encompass augmented transition networks (ATNs) [18]. An ATN is simply a controlled production systel!l where the context­ free control language is specified not by a phrase structure grammar but by a recursive transition net. The conditions and actions on each arcof the transition net are simply the conditions and actions denoted by the LHS and RHS of the pro­ duction corresponding to that arc. Thus aninput word to an ATN simply acts as a control word (stric­ tly a homomorphism of a control word) over the productions attached to each arc of the network.

There are also a number of control constructs which cannot be specified by context-free control languages. For example, the control language of the blocks world examole (Section 3.2) is not a context-free language. Similarly, direct-result­ usage control constructs [13] need language generators of the form merge (tj,t 2), where t1 and t2 act as non-terminals in a phrase struc­ ture grammar and merge (tJ,t2) is to be inter­ preted as providing all merges of the words gen­ erated by t1 with those generated by t~. Again, such languages are not context-free.

Of course, we are not suggesting that we should use phrase structure grammars for specifying control languages- what we are saying is that we need to make sure our control device, what­ ever it is, has the power to describe the types of control that we need. For examole, if we are to allow context-free control langua~es- and the above considerations suggest that we should­ then the type of productions used in TEIRESIAS [2] for specifying production orderings at the meta-level are not going to be powerful enough at the control level as they can only describe regular languages.

4.2 Control Device Structure

We have so far said nothing about the structure of the device to be used in specifying the con­ trol language. If the specification is to be syn­ tactic, then ~ny of the standard methods---ex­ plicit enumeration, property specification, finite state automata, phrase structure gramma~ augmented transition networks, etc.---could be used. These devices could also be used where the control language is to be specified semanticall~ but would need to be augmented with some infer­ ence device. Alternatively, the system could be provided with a number of control primitives, such as those used in NASL [10] or described in [13]. Of course, for a CPS these primitives would be implemented through a separate control device, rather than indirectly through the con­

flict resolution scheme.

However, all the above approaches limit, to a greater or lesser degree, the additivity and flexibility of the system to the object level. A potentially more powerful approach is thus to specify the control language using a second level or controZ ZeveZ CPS. This reflects very closely what 11cDermott had in mind when designing NASL­ that the order of steps within and between sub­ plans be itself rule governed. One advantage of this approach is that the programmer has avail­ able a language and framework in which he can easily define his own invocation criteria. Fur­ thermore, the rapresen tat ion of knowledge at both the object level and control level is uniform, and additivity and flexibility is preserved at both levels.

The control language of the control level CPS would need to be specified, and one could envisage a hierarchy of CPSR, each determining the control language of the one below it. There is probably not much advantage in such a wealth of control language CPSs. Of course, this is not to suggest that there should be no further levels of know­ ledge- for example, it might be desirable to handle non-determinism using a meta-level CPS [1,3,5].

5. CONCLUSIONS

The imiJ<>rtance of control information should not be underemphasized. In placing constraints on production invocation, control reduces the in­ teraction between knowledge units. The more con­ trol constraints we impose, the fewerpatterns of interaction have to be explored, and the smaller and less complex the search space.Toparaphrase Hayes [7] it is precisely the resulting restri­ ctions on interactions that makes control so useful.

In this paper we have presented a uniform frame­ work in which control issues can be addressed, and which provides a basis for implementing such control. We have attempted to show that the in­ troduction of a explicit control device need not result in the loss of any of the properties desired of a knowledge based system, and in par­ ticular that additivity and adaptive behaviour can be retained. Given that the power of pro­ duction systems is equal tu that of controlled production systems, the question remains as to whether it is advantageous to introduce control at all. At an intuitive level it would appear that the answer is yes- it is not difficult to find problem areas where expert knowledge is expressed in terms of sequences of actions. Further, if we look at the formal language domain, regulated (controlled) rewriting sy~tems are usually simpler to construct than equivalent (uncontrolled) rewriting systems. Of course, until a system is actually implemented and applied to typical AI problems, the question must still remain open.