8/14/2019 p86-Zeng.pdfkkm e) Khamis

1/5

An Expert System Model forManufacturing PlanningLaiguang ZengSchool of Computer Science

Rochester Institute of TechnologyHsu-Pin (Ben) WangDepartment of Industrial EngineeringState University of New York at Buffalo

AbstractIn this paper, a patchboard expert systemmodel is presented. It is an effort to deal with someproblem s regard ing the dynamics existing in certain

manufacturing areas. The difference between the patch-board model and the blackboard model is discussed andthe theoretical foundation of the patchboard model isdetailed.Introduction

Engineers are beginning to take interest in ex-pert systems as a means of solving problems in theirdomain. Several prototype systems have been built inthe areas of structural design [l], seismic hazard assess-ment [2], offshore structural analysis [3], mechanical de-sign [4], engineering parts selection [5], operations re-search [6], telephone cable repair [7], just to name afew. In many manufacturing engineering problems, thesolutions are not deterministic and provide many alter-native courses of action. The solution adopted usuallydepends on the expertise of the engineer. Hence manyproblems in the manufacturing engineering domain areamenable to solution via intelligent expert systems.

Stefik et al. [8] classify the different types ofexpert systems into the following groups: (1) interpre-tation, (2) prediction, (3) diagnosis, (4) debugging, (5)design, (6) planning, (7) monitoring, (8) repair, (9) in-struction, (10) control. Among these application areas,we are particularly interested in manufacturing plan-ning. Manufacturing planning involves managerial de-cision making in three main levels of activities:

Permission to copy without fee all or part of this matertial is grantedprovided that the copies are not made or distributed for directcommercial advantage, the ACM copyright notice and the title of thepublication and its date appear, and notice is given that the copying is bypermission of the Association for Computing Machinery. To copy other-wise, or to republish, requires a fee and/or specific permission.0 1990 ACM 089791-372-8/90/0007/0086 $1.50

(1) the strategic level of production and inventory plan-ning and control. Decisions at this level are really cru-cial and should be taken with utmost care. (2) thetactical level of manufacturing operations planning andcontrol. At the tactical level, the batching and loadingproblems are the central focus. (3) the operational levelof process and material flow planning and control. Theoperational level is concerned with the detailed decisionmaking required for real time operation of an automatedmanufacturing facility. The dynamic nature of the man-ufacturing environment stems from the highly variablenature of factors such as customer orders influencing thestrategic level; material and capacity constraints in thetactical level; and machine or workstation availabilityin the operational level. In order to aid manufacturingmanagers in achieving productivity goals, various con-cepts of information systems and computer control havebeen developed.The blackboard model

Three major research issues of expert system-based paradigm are grouped as (1) knowledge repre-sentation, (2) knowledge utilization, and (3) knowledgeacquisition [9]. In order to achieve these goals, thearchitecture of expert systems is extremely importan t.The blackboard is the one which has been extensivelyadopted. A blackboard records intermediate hypothe-ses and decisions that the expert system manipulates.There are three types of decisions recorded on the black-board: (1) plan, (2) agenda, and (3) solution elements.The plan element describes the overall or general strat-egy the system will pursue against the current prob-lem, including current plans, goals, problem states andcontexts. The agenda element records the potential ac-tions awaiting execution, which generally correspond toknowledge base rules that seem relevant to some deci-sion placed on the blackboard previously. The solutionelement represents the candidate hypotheses and deci-

86

8/14/2019 p86-Zeng.pdfkkm e) Khamis

2/5

sions that the system has generated thus far, along withthe dependencies which relate decisions to one another.Historically, the blackboard model arose fromabstracting features of the HEARSAY-II speech-understanding system developed between 1971 and1976. The blackboard model is a problemsolving model,which is a scheme for organizing reasoning steps and do-main knowledge to construct a solution to a problem.In a blackboard system, the problem solving data arekept in a global data base - the blackboard. Knowledgesources produce changes to the blackboard that leadincrementally to a solution to the problem. Commu-nication and interaction among the knowledge sourcestake place solely through the blackboard.The blackboard model is perhaps the mostwidely used paradigm for building expert systems.Many expert systems dealing with manufacturing plan-ning and control problems stemmed from this model.There are some other applications, however, that theblackboard model is not able to handle.

In a blackboard system, premises a re addedinto the state space (blackboard). Depending on thepremises presented in the space, certain rules are fired.As a result of rule firing, some more premises are addedinto the space, which results in more rule firing. Thiscontinues until the goal state is reached. A typical ruleis shown below.T,: if [(PI) and (~2) and ..- and (Pj)]then [((cl) and (cz) and . and (ck))and

(add&,,) and add(p,,) and .WPa, )>Iwhere

pi = a valid premise. i E {1,2, . . j};ci = a valid conclusion if r, is fired. i E { 1,2, . . . k};add(p,,) = a function which adds a premise pai to thepatchboard if r,, is fired. In such a case, pai is an addi-tion premise; i E {1,2, . . . I}

For some manufacturing planning problems,premises can be added into or removed from the statespace as a result of rule firing. Because of the fact thatsome premises may be removed from the space, certainrules which are fireable may not be fireable at a laterstage. As such, these problem domains are more dy-namic and thus require a different expert systems model,which is able to capture the dynamics of such problems.A typical rule in such application domains is given asfollows:

r*: if [(PI) ad (~2) ad . . and (P~Jthen 22) and (cz) and . . and (ck))(add(p,,) and add(%,) and .=%Pa, )Iand(sub(p,,) and sub(p,,) and . .sub(pGJ)l

wheresub(p,i) = a function which subtracts a premise psi fromthe patchboard if r,, is fired. In such a case, psi is anegation premise; i E { 1,2, . . m}.

In order to further elaborate the inability of theblackboard model in some manufacturing applications,we use process planning as an example.

Process planning is defined as the functionwhich converts design specifications into manufactur-ing instructions [lo]. Computer-Aided Process Plan-ning (CAPP) has been recognized as the bridge betweenCAD and CAM, and has drawn substantial research in-terests since the mid-sixties.

In PCB assembly, there are blocks of assemblyprocesses relatively independent of each other and theseblocks represent the flow of the board through the as-sembly process. Depending on the buyers requirementand specification, certain blocks may not be necessaryat all. Also the way these blocks are implemented andthe components utilized within are dependent on theboard requirement and the buyers specification.Typically the process planning task is carriedout by several resident expert planners, each havinghis/her own expertise and own ways of planning pro-cesses. As a result of the uncoordinated operation,many companies are desperate for having a unifiedframework in which process planning expertise is col-lected and utilized in an ordered manner. Expert sys-tems seem to be a reasonable solution.

PCB process planning is unique in that theblackboard model is not applicable. We are giving anexample to elaborate:

Suppose a t some point of planning, there areseveral premises in the state space: wave-solder, man-ualsolder, mass-lead-tinning, heatsensitive-DIP, resis-tor, capacitor, and edge-type-terminator. Note thatthe first three a re process premises; others are compo-nent premises. All three processes are legitimate can-didates for selection during the entire course of thisplanning session. However, because of the presence ofheat-sensitive-DIP, mass-lead-tinning becomes not ap-propriate, meaning mass-lead-tinning has to be removedfrom the state space. This scenario is illustrated usingthe following rules:

r,: if [(PIS) and . . . and (pgz)]then (add(heataensitive,DIP))

87

8/14/2019 p86-Zeng.pdfkkm e) Khamis

3/5

r,: if bl) and (Pdlthen (print avoid mass-lead-tinn ing)and(sub(mass-lead-tinning))

The Patchboard ModelThe patchboard based expert system is an in-tegrated assembly of several modules.

dynamic rule base - a collection of rules spawnedout of a need for updating the rule base. A dynamicrule can be in the form of a quasi-metarule or anordinary rule. A quasi-metarule, unlike a typicalmetarule, manipulates ordinary inference rules byturning them ON or OFF. A quasi-metarule is notcapable of creating new rules.rule base - a preliminary collection of hard-definedrules input as the collective knowledge of humanexperts in different departments. When a rule isupdated, it goes to the dynamic rule base.data base - various input files associated with thedecision making such as the data base of processes,components, statement of work, and PCB CAD in-puts.patchboard - the patchboard will be explained indetail later, but it can actually be understood as acollection of premises at a certain given moment inthe decision making process.inference engine - a procedure determining rule fir-ing sequence, fetching rules from both rule bases,updating the patchboard and creating the conclu-sion file (for example, a process plan in the exampleof PCB assembly planning).user interface - the front end of the expert systemwhich is a dialogue manager between the user andthe expert system.conclusion file - this is the main output of the ex-pert system and it gives a detailed sequence of as-sembly processes and the elements thereof.

Theoretical foundationThese are several features that make this modelunique. These include the use of the patchboard con-cept, focus control blocks (FCBs), and the concept of

system states during reasoning. The details of theseconcepts are explained below.FCBsAs the authors discussed earlier, the entire ss-

sembly process is built out of blocks which are relatively

independent in function and content. This idea is ex-tended to the inclusion of the concept of Focus Con-trol Blocks (FCBS). FCBs are the nodes at which anexpert (human or machine) pays attention in the con-tinuous process of reasoning. An FCB would basicallyconsist o f rules associated with a sub-problem.For example, the population of a PCB can betreated as a FCB. For instance, the processes priorto and after PCB population have hardly any bearingon the various details of how to populate the board.Any rules associated with the above sub-process can begrouped together, segregated from the other rules connected with PCB assembly.

A typical FCB has input from various databases, and communicates two ways with the dynamicrule base and the patchboard. The rules associated withthe FCB are run under the sole control of the genericinference engine. Every FCB on execution adds variousconclusions to the conclusion file.PatchboardThe patchboard is a collection of premiseswhich a t certain point in the decision making processrepresent the valid basis for reasoning. A premise canbe understood as a token (fact) representing an aspect of the problem domain. In PCB assembly processplanning, for instance, common premises are component premises (connectors, resistors, through-type connectors, etc.) and process premises (board population,degrease, testing, etc.).

The patchboard is dynamic in that premises canbe added to or removed from it. The continuing statesof the patchboard show the flow of the decision makingprocess. The presence or absence of a premise shows thetruth or falsity, respectively, of a decision m aking basisRulesA rule is a set of criteria based upon whichan expert makes judgment of the state of the system.Therefore, rules not only give rise to conclusions, butalso effect the further decision making of the expert system (by changing the state of the patchboard).A typical rule was given earlier in the Intro-duction section. In addition to ordinary inference rules,there are quasi-metarules. A quasi-metarule manipu-lates inference rules and takes the following form:Mn: if [(PI) and (~2) ad .

and (Pi)1then [((cl) and (~2) and .and (~1)and

where(swt(rl, IQ) and swt(rs, IQ)and . . and swt(rm, k,)]

swt(rj, kj) is a function which switches rule rj on (kj =1) or off (kj = 0), j E (1,2, . . . m}.

88

8/14/2019 p86-Zeng.pdfkkm e) Khamis

4/5

System StatesThe pa tchboard and set of rules fired to reachthe state comprise the system state at any stage in theexecution of the expert system. The system state isupdated after every rule application (rule firing).Inference MechanismTo develop a procedure for inference, it wouldbe appropriate to lay the foundation first. The followingdefinitions are the basis of inference.Leading premises: those premises, which if held true,would result in the firing of the rule. In the abovegiven generic rule structure, pr, pz, . . are the leadingpremises.Fireable rules: the set of rules which can be fired at anygiven s tate of the system, i.e., the set of rules whoseleading premises a re all true (present in the patch-board). A rule is fireable if and only if all its leadingpremises are presented in the patchboard at the time ofrule examination. A fireable rule is denoted as rf, andthe collection of all fireable rules at any given inferencestate is denoted as RI.Independent rules: the set of fireable rules, none ofwhose leading premises are presented as the negationof premises of any other fireable rules. A fireable rule isindependent if and only if

where,L, = a set of leading premises of r;M, = a set of premises which will be removed from thepatchboard as the result o f the firing of rule r.Let ri denote an independent rule and Ri denote thecollection of all independent rules at the time of ruleexamination.For example, a system state, Ss, contains in itspatchboard the premises ~1, pz, p3 and ~4. Given thefollowing rules:

no: if KPd and (Pz)lthen [((cl) and (4)andgyP3))(sub(P4Nl

r29: if cw and (P4)lthen [((a) and (4)andW(P5Nl

f-37: if KP2) and (P3)lthen [((a) and (CS))]Since leading premises are satisfied, r-1, r2, andrs are all fireable rules. However, r2 is not an inde-pendent rule because one of its leading premises, ~4, is

present as a negation premise in ~1. Therefore, the inde-pendent rule set contains rl and t-3, i.e., & = (q, rg}.Independent states: a system state in which there is atleast one independent rule. Therefore, the above stateSs is an independent state. Ri and Rr denote the fire-able rule set and the independent rule set at the n*state of inference, respectively.

The semantics of rule firing is summarized be-low:Pj : if Vp E L, (p is true)then output (conclusion)andP := P u {P I P E A,} - {P I P E Mrwhere, P = a set of all premises in the patchboard.

Also,

Vr E R;+ Vr f RF (p E L, -+ p 6 M,I).Before leading up to the inference mechanism,

it would be necessary to make a few assumptions.Assumption 0: It is possible to codify all the knowledgeof a human expert in the form of if . . then . . rules.Assumption 1: For a given assembly process planningproblem, there exists, in the mind of the expert, at leastone solution which the expert deem s to be the correctsolution.Assumption 2: In the expert system, there is a finiterule path from the initial state to the final correctstate.Assumption 3: Intuitively, it would appear that the hu-man expert would operate with independent rules andhence, the rule path which the expert system takes fromthe initial to the final states would consist of indepen-dent rules.

Given the above assumptions, the problem re-duces to a procedure for determining a correct inde-pendent rule to fire at any given state.The procedure for rule firing is described below:1. Obtain the fireable rule set, F. If llFl[ = 0, then

stop. Else, to to Step 2.2. Obtain the independent rule set, I. If llIll = 0,then stop. Else, go to Step 3.3. Fire an independent rule. Go to Step 1.

However, there can be situations where thereare multiple independent rules which commonly knownas rule conflict. The choice of which independent ruleto fire (conflict resolution) is not clear. Therefore, aproposition is stated as follows:

89

8/14/2019 p86-Zeng.pdfkkm e) Khamis

5/5

Proposition 1: The firing of an independent rule willnot change subsequent system states in such a way asto make a current independent rule non-independent.That is to say that once a rule becomes independent,this rule will be independent at all states thereafter.In other words, the following relation holds. For j Ei&L 2, . .I. Ry c q+j.Since this proposition is critically important to thesoundness of this expert system approach, a proof ap-pears to be necessary.ProoF-Induction on j:Basis: j = 0, Ry 5 RrInduction: Let us assume Rr C Ry+j is ture.For any r E Ry, according to the assumption, r E Rrj.Also, Vr E R;+j+ Vr E Rj (p E L, + p $ n/r,)).Since R?+j+l c Rn+j+lVr' E Rk+j+ T+ : Rv+jTherefoie r E R?+j+

(p E L, + p 4 M,.,).and Ry 5 Rl+j+l, leading to

for all j i 0, Ry c Rr+j.Concluding Remarks

The theoretical foundation of a patchboard-based expert system m odel is discussed in this paper. Itis developed for those problems that blackboard-basedexpert systems are not applicable.As can be seen from the discussion, these twomode ls are quite different in that:

In a blackboard system, rules can only have addi-tion premises. But in a blackboard system, rulescan have both addition and negation premises.As a result, in a blackboard system, p remises canonly be added into the memory space; while in apatchboard system, premises can be added to andremoved from the memory space. The subtractionof premises from the patchboard can sometimesmake a fireable rule not fireable.

This patchboard approach has some potential appli-cations in manufacturing such as process planning,scheduling, and product design.

References[l] Fenves, S.J. et al., Knowledge-Based Expert Sys-tems in Civil Engineering, Expert Systems in CivilEngineering, ASCE, 1986.[23 Ishizuka, M. et al., Rule-Based Damage Assess-

ment System for Existing Structures, NSF ReportNo. CESTR-82-14, 1982.

PIPI

[51

PI

PIPIPI

PO1Pll

Jain, A.K. et al., WAVE: An Expert OffshorStructural Analysis System, Expert Systems Civil Engineering, ASCE, 1986.Bose, G., and Krishnamoorthy, C.S., GEAREX A Unix Based Gearbox Selection Expert System,KBES for Engineering: Classification, Educationand Control, D. Sriram and R.A. Adey, (eds.Computational Mechanics Publications, 1987.H&e, G. Stokke, G. and Kloster M., BETSY An Expert System for the Selection of Bearings,KBES for Engineering: Classification, Educationand Control, D. Sriram and R.A. Adey, (eds.Computational Mechanics Publications, 1987.OKeefe, R.M., Belton V. and Ball T., Experi-ences with Using Expert Systems in O.R., Journal of Operational Research Society, Vo1.37, No.1986.Kastner, J.K. and Hong, S.J., A Review of Epert Systems, European Journal of OperationalResearch, Vo1.18, 1984.Stefik, M. et al., The Organization of Expert Sytems: A Tutorial, Artificial Intelligence, Vo1.11982.Buchanan, B.G. and Feigenbaum, E.A., Foreworin Knowledge Based Systems in Artificial Intelli-gence, R. Davis and D.B. Lenat (eds.), McGraw-Hill, New York, 1982.Chang, T.C. and R.A. Wysk, An Introduction Automated Process Planning Systems, PrenticeHall, 1985.Shrobe, H.E., Exploring Artificial Intelligence,Morgan Kaufmann Publisher, Inc., California,1988.

90