Parallel-Serial Production Systems with Many Working Memories

1. 2 Tradit i onal Production Systems

A Pr oduction System (PS) (Newell and McDermott, 1975; Rychener, 1976; Waterman, 1975) consist s of an ordered set of Productions (P),Pl, ... PM, each with a set of Conditions (C) and a set of consequent Acts (A), plus one Working Memory (WM). E.g.:

Pl : RED BLUE~ GREEN DELETE (RED) DELETE (BLUE)

P2 : BRmlN YELLOW ~ DIRT

P3: GREEN-DIRT = POOR- GRASS (STOP)

WM: RED BLUE YELLOW BROWN

Each Condition specifies a set of elements. An el ement specifies a s tring (or list s tructure) of sub-elements to be matched with strings found in WM. The mat ch usually demands that the f"i r~;t sub-elemenk> match, and that each ~;ub~;cquent :;ub-element in ci match a :mb~>equent (but not necessarily the next) sub-element in WM. Variablc:o are us ually bound by whatever they find in the first match where they occur (rather than have the system try all possibil­ ities). Acts specify insertions or deletions in Workinp, Memory, the generation of new Pro­ ductions, or any of several primitive Acts, like OU'rPUT, or STOP . A Product ion 11 fires 11 its Acts if all its Conditions are satisfied. Usually the ::ystem moves from the top Produc­ tion down, until one Production fires , when it jump:o back to the top, t o repeat the process . Some sy:otems use different flows , e.g. contin­ uing on to the next production whether the prior one Ered or not (note t hat thi s does not mean that Productions are applied in parallel , for each fired Product ion immediately effects its Act:o , and therefore modifies WM). Some systems find ull Productions that ~meceed, and then use one of' a variety of crite r ia for choos ing and !'iring one Production, c . ,~ . the one that matches Lhe mn:: l n~eenLly added element in WM (Newell aud Ml:!Jcrmutt, 1975) .

l. 3 Parallel-~> erial Multi-Memory Production Systems

Livin~ cognitive systems effect sets of parallel transt'ormationn, and use a number of temporary buffer Worki n1; Memories . Such parallel-serial multi-layered architectures ~;ecm nimilarly de­ s irable f or computer-proc;rammed systems s ince (once they run on the parallel-serial computers, see e . g. Duff, 1976, Lipovski , 1977, that cur­ rent technology is on the ve r ge of making fea­ s ible) they offer great economy and power.

(PS) 2 Mn extends traditional Production Sy:;tems so that they can conveniently handle parallel processes applied to more than one Memory. The key extensions include the following.

1. Any numbe r of Memories can be npec ified and used, with net s of Productions looking at and firing into each.
2. Each Production can look at severalMemorie~ and fire into several Memori es , if desi red.
3. Sets of Productions can be applied in either a Parallel or a Serial mode, as specified , and the mode can be changed during a r un.
4. A Production can fire one or more Pr oduc­ tions t o be applied, as specified .
5. After a Production s ucceeds in firing, the system can either attempt t o fire the next Pro­ ducti on, or go back to attempt to fi r e the first Production , as specified.

These cxten:>ionn allow for relatively conve­ nient codin1; of a variP.ty of' perceptwLl and cognitive syntems , some cxurnples of which are described below.

1.4 Some of the Uses of Multiple Memories , and of Parallel and pynamically Implied Productions

A single Memory can always be set up to do any­ thing that multiple memori es can do (since s tandard Pr oduction Systems arc based on Post Productions they are uni vernal computers , and anythinr; can be programmed in them) -but arten at a heavy price . Essentially, the sy~>tem can no longer use the Memories' nHmcs and attendant pointers to directly access s ub-sets of infor­ mation in the relevant Memories . Rather, element s in the s ingle Memory mu:; t be given appropriate name-like tags , and the syst em must use the r elatively slow Production- matching routines to :;ear ch for the appropriately tail/7,ed element s . All the element s in a particular Memory could be r;rouped to1~· :t. h e r, ~;o thut only one tat~ wcw needed. But that mean~; the :;y~;tem mus t work with und try to mat ch a lan~e and cumbersome list of list s - and that can be a s low and costly process. Alternately, each element can be separate, but each with the same Memory tag . But that means the search for the appropriate taG mus t be turned i nt o a l oop , iterating through the entire Memory .

'rhe oriF>innl dev·,lopment of Pr·odw:tion System:; wus directed toward work wi Lh a very :;mull

"Workint~ Memory" for scratch-pad-like inter­ mediate results, one that models the hwnan "short-term memory" that il> capable of handling some small nwnber like '7 i terns. For such uses there is no need to add more Memories or other st ructures. But for a general-purpose program­ ming language multiple Memories serve a nUI:lber of purposes.

Without a parallel capability of the sort pro­ vided in ( P[J) 2Mn, a pror;ram must make l>everal extra passe~; through a set of trans forms to s imulate parallel processes . The first pass would not actually change the Memory; rather, it would out put it::; r>et of acts each specially tagged as a temporary output . Then the program would have to keep applyinr; a set of Produc­ tions that looked for all these tags , use the output information from the tagged elements to modify Memory, and eral;e all these tae;ged tem­ porary element :; .

The dynamic implication of tram;:f'orms gives the programmer powerful control capabilities for st ructuring the flow of processes . Without this feature a pr·ogram mus t use a production that adds an element to Memory that only one other Production - the one to be fired next -will s ucceed in matching. This means the system mur; t.. make an extra cycle through it:; produc­ t..ionr> to find that.. next.. production , in addition to adding and deletin1~ the identifyint~ element . Dynamic Productions make this process direct and simple,

The present sy::;tem cm1 use dynamically implied productions , but it eannot generate them. For it can insert newly generated productions only i nto its main liL;t of Productions (a:; is done by Btanda.rd Production Systems). Hut.. it also needs the ability to in:;ert a Production 's name into the lh;t or Consequences of another Produc­ tion, and to choose that Production correctly. This needs a capability of modifying a Produc­ tion, and not simply creating one, and of accessing and conveniently storing histories of the names of Productions fired. Such an exten­ s ion is discussed below, as part of a more gen­ eral ability to create, modify, and erase both Productions and Mem01·it!:> - that i:;, to treat product ions and memori ell in exactly the same WfiY.

2 . EXAMPLES OF SYS'rEMS THAT COULD FHUITFULLY USE (Ps)2Mn

2 ,1 Parallel Sets of "Knowledge Sources" a::; Parallel Communi eating Production Systems

An attractive structure for cognitive and pr'r­ ceptual systems is one that uses a set of inde­ pendent "Knowledge Sources" (e.g. Reddy, 19'7~, Lowerre, 19'76), or "demons" (e.g. Lenat, 197'7). Each works at the same time, independently of the others, and therefore could be executed in parallel by one processor in a suitable network of minicomputers, or parallel processors . All communicate with one another by passing infor­ mation into and out of a common "blackboard" memory. Such systems cannot be conveniently coded in a standard Production System languar,e like PSG or PAS-2, because the knowledge sources act in parallel, and often contain parallel processes.

Such a system can quite straightforwardly be handled by (Ps)2Mn, as follows: Each knowledge Source is executed in turn, since each works with its own local memory. Then, after all have completed their processes, a set of paral­ lel production transfers thei r (present, inter­ mediate) results to the common Blackboard Memory. Then a second set of parallel produc­ tions transfers selected information from the common Memory to the individual Knowledge Sources ' memories.

The parallel capabilitie~; of (pr;)2Mn make the tram;fer of information into 11nd out of the common Memory very convenient, since there ir; now no danger of unwanted interactions between Knowledge Sources, And now each Knowledge Source can itself contain a mixture of parallel and serial flows of ~roductions. And each can contain one (or more) separate memories , where­ as in a standard PS each sub:>et of memoriec> would have to be protected (in a very cwnber­ some way) from all Knowledge Sources that did not have access to it.

Most large Production-oriented programs of this sort appear to be Production Systems in spirit, but without being coded in an actual Production System language. The ext em; ions handled by (PS)2Mn would appear to move in the direction of a language that might be :;ui table for c~on­ venient codinp; and running o r such lurp;e pro­ duction Production Systeml>.

2.2 Compatibility Pairs

A production for relaxation us ing pairs of com­ patibility labels (e.g. Zucker, 19TI; Davis and Rosenfeld, 1978; Tennenbaum and Barrow, 1976)

need only bc a 2-tuple, designating the label Lo bc looked at and the context label. When both are found the label is fired into an out­ pt<L Memory . But each label must be searched for in l t,; Lie:;iomted memory, and many such produc­ L ion:; mu~;t be applieLi in parallel . And to i Lc nd,<~ to more di:;tant contexts each must im­ ply tile next production to apply . The present :;y:; tern will handle determinh;tic constraints , i 1' l L rai:;es a flue with each success, tests and lowers the flag after each iteration , and then :; top:; iterating after one pass without ral:;ing the flae (meaning that nothing new has been a<.:complished) . Extensions to be discussed below will handle probabilistic constraints and dynamic :;toppine; rule:;, and also situations thaL rrd x compatibility pairs with other types of tr:m:;form:; .

2 . 3 1\ l'roduction System that Uses Compatability I 'air:.; t o Choose Among Productions

Zu<.:ker, l9Tf , has su1~1~e:;ted that compatibility pait· relaxation techniques might fruitfully be u:;eLi to choo:.;e the sin1~le judged-best Produc­ tion Lo fire next , when a serial Production Syc;tem finds that more than one Production might J'ire. (This is Lhe case in those stan­ dard 1-'roduction Systems that , instead of firing the l'ir:>t Product ion that succeeds , get all ProducLions that succeed , and then use some criterion to choose amone; them.)

( P~;) ;'M 11 allow:; such a r.ystem to be coded entirely as a parallel-:;erial Production System, a:; follows :

Li:.;L all the Production:; to be chosen among as a parallel set on the MASTER lis t (the main lilit of productions - see Uhr, 1978). Each Produ<.:tion implies all of its compatibility label :.; as dynamically implied Productions on its :;e t of ACTS . Thus all Product ions that :;ucceed fire their compatibility labels onto the :;et of (parallel) productions that will fire next, after this parallel set has been completed . Then this parallel set of compati­ bility label :.; will be applied . This procedure continues, as in the proceeding section, until either a sinele production remains or no more relaxation can be done . Thus the separate relaxation phase is absorbed into and handled by the (PG)2Mn Production System.

2 .11 DL;crirnination Nets , Concept Formation, 111'1\M

The progrum uses making one test . a tree of Product ions , each The Master list starts with a Production that tests for the first node of the discrimination net (really a t r ee) , followed by all Productions on its negative path. If it succeeds it implies the Production on its positive path to be immediately executed in the serial mode followed by all Productions on that node's negative path . Thus the fra1~ent of a discrimination tree shown in l"ip;ure 1 need:; the Production:; r.hown in Table l (a number refers to the test for that node):

Figure 1

.·rable 1

Note that the only Productions on the MASTER list are the first and the successive 1 - 1 (failure) branches from it. All other Produc­ t i ons are implied by Productions that fire .

This program uses a true discrimination tree, where each Production t ests only the single next node. This is in sharp contrast to the EPAM program (Waterman , 1975) coded in PAS- 2 (which uses a separate template for each entire path in the tree, and has no ability to dynamically imply transforms).

2 . 5 Layered Perceptual Systems (e.g. Cones, Fyramids, Hierarchical Relaxation)

The use of a sequence of several memories be­ tween pairs of which are sandwiched sets of parall el productions can be quite straightfor­ wardly coded as a parallel-serial production system. Productions need only be stored as parallel sets , their INput MEMory and OUTput MEMory specified for each such set , with the OUTput MEMory for one set the INput MEMory for the corresponding s ubsequent set .

Dynamically implied transforms can be handled as productions that are implied as consequent acts of successful productions . Iterations through relaxation can be handled by using the same INput MEMory and OUTput MEMory for several cycles . These would be especially attractive for parallel- serial layered perceptual systems such as the cones and pyramids bein" developed by Hanson and Riseman, 1974; Tanimoto , 1976 ;

Uhr, 19'r2, 197l1b, and others.

Such systems would benefit greatly from several extensions (that are projected for future pro­ ductions :systems). These include a) weights, thresholds, and probabilistic productions, b) a convenient way to iterate through a whole array of memory locations (as in the 2-dimensional retinal mosaic), applying the same set of paral­ lel productions in parallel to each cell in the array, and c) techniques for choosing among alternative implications (as in naming and describing), and for deciding when to choose (as in deciding when to stop relaxine).

2.6 Heuristic Problem-Solving

A heuristic problem-solver could take advan­ tages of several levels of parallel processes, given a suitable language, Typically, a whole set of heuristic evaluation functions is to be applied in parallel to a node that might be a candidate for further search. And a whole set of such candidate nodes might conveniently be evaluated in this way, in parallel.

A (Ps)2Mn program with the following structure can handle such a system:

The set of heuristics is coded as a parallel set of Productions.

For a he uris tic ally r;uided search for a path f r om a set of Givens to a Goal (or from Goal to Givens), the Givens (or the Goal) are input as elements in the first WM. The Rules of Infer­ ence (sometimes called legal moves, transforma­ tions, etc.) are coded as a parallel set of productions and put on the MASTER list, They are applied, giving the buds (which are put into a second WM) from the presently achieved expressions, deletin1~ elements in the first WM, and firing set of heuristics (coded as a second parallel set of productions). The heuristics now look at these budded expressions, and accumulate the evaluation of each. They are followed by a serial set of productions that chooses and puts into the first WM the most highly valued expression(s), and deletes all expressions in the second WM. The Rules of Inference are again applied, and this process continues.

I have ignored a number of important details, but almost certainly several more Working Memories will be preferable - e,g, to store the pointers back from buds to their fathers for later use in getting the solution-path, and to get that path.

3. SOME ADDITIONAL EXTENSIONS 'rHAT WOULD SEEM TO BE USEFUL

There are several further extensions that would appear to make for substantial further improve­ ments in the ease of coding of cognitive and perceptual systems, and the resulting transpar­ ency and clarity of structure of the resulting systems, These include the following:

1. Probabilistic transforms would allow for the emerging of multiple implications, from percep­ tual characterizers or problem-solving heuris­ tics. This entails rather simple extension;, : l) Associated with each element of a condition will be a number (that can be interpreted as nwei1~ht, probability, fuzzy value, or whatever the pro­ grammer desires), associated with each produc­ tion will be a treshold, and associated with each implied act will be a weight. When the combined weights of success ful conditions ex­ ceeds the Production's threshhold, the Produc­ tion will be considered to succeed, and fire its implications with their asr.igned weights, 2) Several implications of the same thing will have their weights merged. 3) When this is specified in the program, then the system will choose among alternative implications from among some mutually exclusive set that the programmer has specified.
2. ll) A set of Production:: ::ltould be abl<! to iter·­ ate conveniently through an array or rn<'rno r··i '':: . This would allow for very convenient nn<l straightforward coding of perception r:y::term:, e,g, pyramids and cones, and relaxation label­ ling, where sets of transforms (coded as Pro­ ductions) could be applied to the different cells, or regions, of the retinal image, or· internal abstracted images.
3. A system should have a more general set of capabilities for creating and erasing lis t s (whether Productions or Memories), and adding and deleting information to and from these lists, This would allow for the convenient building, and modifying, or complex list struc­ tures and graphs of information, If done with as much generality as possible, it should also make Productions and Memories, and their manipulations, quite similar.

4, DISCUSSION

Today's production systems have a herit age much older than Post's productions, and much broader than problem-selving. For Post productions are probably the single Turing machine-equivalent formulation that mos t directly embodies that elusive (and poss ibly imaginary) entity,

"intuitive thinking." The rules of inference of Euclid's geometry, and of Aristotle's syllogism, are very similar to productions. Consider the linguist's rewrite rules and transformations, the physicist's Feynam diagrams, the psycholo­ gist's S-R mappings, the "if a,b,c, then d,e,f" lines of re~soning of detective, diagnostician or trouble-shooter.

So an embodiment of thinking in terms of produc­ tions would seem especially desirable. We could use it conveniently; we could understand it; and it might well be appropriate, and powerful. But the particular production system chosen should be sufficiently flexible and powerful for convenient programming.

The three major extensions to Production Systems incorporated into (PS)2Mn - 1) the ability to apply productions in parallel, when desired, 2) the partitionine of information into several working memories, and 3) the firing of produc­ tions to be applied next by productions that are fired - often appear to go together, and to complement and enhance one another. But one might prefer to use only one, or two, of these extensions , for the following reasons:

1. If it is known that all programmers who will use the production system language will code all their programs using only serial productions, then the parallel capability is not needed. But many cognitive processes, especially in percep­ tion and associative memory search but also in heuristic deductive problem-solving, appear to have important parallel components. And al­ though yesterday's computers are serial, today's are beginning to be parallel, and tomorrow's will become increasingly parallel.
2. From a certain esthetic perspective as to the meaning of "simplicity" the single Working Mem­ ory seems simpler than several Working Memories. But if a program uses several memory stores it seems less s imple to throw them all together into one, and then do a lot of otherwise un­ necessary searching and matching to find the one that is needed.
3. Productions that fire productions to be applied may well violate the simple modular structure of standard production languages, with their top-down flow through the stack of producLion!;. But they may more closely reflect the actual operuti ve structure and flow of the prop:rum, ln the sense of the productions that flCt unlly will fire. Without thin capability a pro~;r-nm beeomc!; cluttered up with cumbersome and time-consuming devices that make use of the addition and deletion of special data symbols to direct the program's flow.