Hierarchical Production System

1. INTRODUCTION

In the field of AI, production systems(PS) have been used for representing domain-specific knowledge in a number of successful projects such as DENDRAL[5] and MYCIN[l6]. A PS[l][2] [6][10][11][14][15][19][20] cons1sts of three components, data base(working memory or short term memory), a set of condition-action rules, and interpreter. In the simplest case the inter­ preter operates by scanning the left hand side of each rule until one is found which is suc­ cessfully matched against the data base. Then, the corresponding right hand side(action) is invoked and the data base is usually changed. In a pure PS all interaction between rules is forced through a very narrow channel, i.e., the data base . Such restriction on interaction gives PS's "modularity", which is one of the most remarkable advantages of PS's. Thanks to the modularity PS's are superior to procedural approaches in flexibility and adaptability.

One draw back of PS's is lack of programm­ ability. Therefore, several PS's rather than pure ones adopt tags, markers, or conflict resolution methods to control the sequence of rule invocation. Consequently, however, they

make it hard to understand what is intended.

In this short paper, we present a general concept of hierarchical production system(HPS). The HPS is an extended version of the current PS. It consists of several PS's arranged in a two-directional hierarchy to augment the ability of the system while retaining its modularity and flexibility.

2. HIERARCHICAL PRODUCTION SYSTEM

As pointed out by Davis[!], PS's have appropriate domains in which they show good performance. By using PS's for knowledge representation in designing problem solving systems, one must decompose the problem domain into almost independent states and embed the domain-specific knowledge into a system regard­ less of the manner in which it is to be used . So, the competence of the system depends largely on the results of the decompos ition.

It is well known that PS's provide a useful framework for embedding domain-speci f i c knowledge into a system with high intelligence. However, a pure PS is probably inefficient because of its excessive modularity . There­ fore, certain modifications are made in sever al dimensions[1][3][7][11][15] in order to augment the competence of the system. In this short paper, we present an additional dimension in which PS's are to be augmented, that is, we propose a hierarchical production system consisting of the current PS's arranged hier­ archically.

Decomposition of the problem domains is an important task in building an effic ient problem solving system. In speech understanding syst em, e.g., Hearsay-!! [4][8][12], the problem domain

is divided into 6 levels such as phrase, wordsequence, word, syllable, segment, and parameter levels. Kanade[9] has also introduced a multi­ level representation of image understanding domain(object, subimage, region, patch, and pixel levels). Nine-level of pattern descrip­ tion is introduced into learning system by Soloway and Riseman[l8]. In their systems learning is considered as knowledge-directed interpretation in order to deal with real world domain where a significant amount of knowledge is required. These multi-level representations of the problem domains are natural to the human intuition, and they help the system designer to consider the problem topdown.

In the GPS paradigm, abstraction spaces are employed by Sacerdoti[l7]. In his ABSTRIPS sys tem plan making is done as follows: Suppose that the system wants to solve a certain problem. It usually has a collection of actions whose preconditions and effects are completely known. Initially, it makes a rough plan ignoring detailed situations. In this case, the first plan is a sequence of the actions in the highest space. Although it may be inappli­ cable to the problem domain directly, the plan does not miss the major causal chain. For example , it may contain the action "GO TO A FROM B" regardless of the transportation media or of their subactions required to be performed beforehand. Then, it can refine the plan using the actions on the next lower level. This process is continued until a realizable sequence of actions are obtained. This "Step-wise refinement" of a plan is useful especially when making a large scale plan.

The above observation- shows that the hierarchical(multi-level) .representation of problem domain and knowledge* plays a crucial role i n dealing with complex problems.

Among the issues of PS design, conflict resolution is a major one. Davis[2][3] has discussed the conflict resolution problem by introducing meta-rules. Meta-rules are heuristic ones for guiding the selection of the next rule to be invoked from the conflict set and can be com; ldered as knowledge concerning how t o use the lower level knowledge. Further­ mon·, we can have me ta-me ta-rules . This hier­ archy of rules t'nahles us to embed the strate­ gies into the sys t em while retaining the uni­ formity of representation. Goldstein and Grimson [7) and Hayes-Roth and Lesser[8) have also considered a similar problem. Although their representa tions are different, the under­ lying ideas a r e same, that is, they want to make their systems efficient by firing appro­ priate rules ~n every recognition-act cycle based on attached heuristic knowledge.

Taking the above two kinds of hierarchical knowledge structures into account, we obtain a general concept of hierarchical production system having the block diagram in Fig. 1.

- heuristic level -

Fig. 1 m Hierfrchical production system, HPSn. (HPS 1 corresponds to the current PS)

The HPS has the following characteristics:

1. The vertical dimension corresponds to the hierarchy of the domain-specific knowledge for step-wise construction of plans or something like that.
2. The horizontal dimension corresponds to the hierarchy of the meta-rules as strategies for conflict resolution.
3. Every component has a usual PS architec­ ture.
4. Interaction between components is restricted to between neighboring ones.
5. Type of the interaction is only the access to the data base.

The HPS is designed to extend the current PS in a natural direction by introducing the hier­ archical organization of rules, in which no ad-hoc techniques for conflict resolution are employed. In our system user-defined heuris­ tics can be embedded in the form of rules as well as other knowledge. Furthermore, the hier­ archy of the domain-specific knowledge helps the system to invoke appropriate rules, since a PS on a certain level can refer to the plan generated by the PS on the next higher level when determining which rule to fire. Thus, invocation of rules on every level is guided by its next higher level plans.

* The need of hierarchical representation of knowledge is recognized in knowledge represen­ tation paradigm[l3].

3. CONCLUSIONS

A hierarchical production system has been proposed and its outline has also been described. The HPS enables us to represent the hierarchical domain-specific knowledge and several levels of heuristics.

The HPS has highly parallel computational structure in principle. In the ideal case where decomposition of domain-specific knowledge into a number of independent knowledge is made suc­ cessfully, every rule and hence every component of the HPS can be activated in parallel. In practice, however, this is not the case. There­ fore, we need a monitor or supervisor which arranges the flow of control to work the HPS.