“Monitoring of a Multi-stage Manufacturing Process”
using Dynamic Bayesian Networks
Kietikul Jearanaitanakij (Lee)
August 12, 1999
Report completed in partial fulfillment of the requirements for the
Master of Science at Oregon State University
TABLE OF CONTENTS
1. INTRODUCTION.....................................................................................................................12. THE CAP ALIGNMENT PROCESS......................................................................................32.1 BASIC LAYOUT.......................................................................................................................32.2 INSPECTION DATA..................................................................................................................32.3 PRODUCTION RATE AND PART FLOW......................................................................................52.4 COMPONENT FAILURE TYPES..................................................................................................53. BAYESIAN NETWORKS........................................................................................................63.1 BAYES’ RULE........................................................................................................................64. STATIC AND DYNAMIC MODEL DESIGNS.....................................................................84.1 STATIC MODEL.......................................................................................................................84.2 DYNAMIC MODEL...................................................................................................................95. ANALYSIS OF THREE ALGORITHMS............................................................................125.1 A TRADITIONAL POSTERIOR COMPUTATION.........................................................................125.2 DIVIDE AND CONQUER ALGORITHM (OR SPACE-EFFICIENT ALGORITHM)..............................135.3 TREE-BASED ALGORITHM....................................................................................................146. IMPLEMENTATION.............................................................................................................176.1 CLASS DEFINITIONS.............................................................................................................176.2 CLASS INTERACTIONS..........................................................................................................207. EXPERIMENTAL RESULTS...............................................................................................228. CONCLUSIONS.....................................................................................................................24REFERENCES............................................................................................................................25
i
1. INTRODUCTION
Hewlett-Packard (HP) is one of the world's largest computer companies and the foremostproducer of test and measurement instruments. In Corvallis, Oregon, HP manufactures severalprecision products on high speed, automated assembly lines. The alignment process of a cap to abase part is one of the essential processes in its manufacturing process. This process has severalstages with a large number of parts flowing through between stages. Each stage composes of anoperation device and a visual sensor device. When a part flows pass the operation device, thevisual sensor device then makes an observation on that part. The monitoring of this process hasto be efficient because of two important factors. First, the accuracy of the alignment processaffects the quality of the product. Second, the more accuracy the process is, the lowermanufacturing cost the product has.
Dynamic Bayesian networks are used to design the monitoring and diagnosis of thealignment process. Unlike the traditional Bayesian networks that statically show the
relationships of the state variables at a particular time, the relationships between state variablesin dynamic Bayesian networks are monitored across the time steps. Bayesian networks haveseveral advantages over other diagnostic methods for the following reasons. First, Bayesiannetworks can lead to rational decisions by using conditional probabilities although there is notenough information. Second, Bayesian networks provide a better way to represent the problemusing directed graph. Finally, Bayesian networks use prior knowledge of the causal relationshipsbetween variables in the domain, leading to a more accurate initial result.
The purpose of this project is to monitor and expeditiously identify a component failure.The component is either an operation device or a visual sensor device. The paper will thendescribe the application of dynamic Bayesian networks in developing a system for monitoring
1
and diagnosis of the cap alignment process. In addition, the project is a continuation of theformer work by Eric Wolbrecht. In his work, a prototype of a real time monitoring and diagnosissystem was developed in order to compute the posterior probability of the state variable at anytime step. The posterior probability of the state variable tells how well the component isworking at that time. However, the existing posterior updating algorithm performsmultiplication of the joint probabilities of every part in the system, resulting in a significantspeed problem for a large number of parts. This is because the computation is linear in thenumber of stages. Nevertheless, the speed problem can be avoided by a more efficient algorithmillustrated in this paper. In addition, there is a proposed algorithm by Binder, Murphy, andRussell that solves similar problem with a different idea from the algorithm used in this paper.The time complexity in their divide and conquer algorithm is O(SNlogN), where S is the statespace size for each time step and N is the total length of the observation sequence. This paperpresents an O(SlogN) time tree-based algorithm. The analysis of these three algorithms will alsobe discussed in the paper.
The paper will start with a general description of the alignment process, a briefintroduction to Bayesian networks, and static and dynamic models of the cap alignment process.Next, the analysis of three algorithms is presented. This is followed by an outline of systemimplementation and experimental results. Finally, conclusions and recommendations for futurework are discussed.
2
2. THE CAP ALIGNMENT PROCESS
2.1 BASIC LAYOUT
In order to make the cap alignment model easy to understand and simple to implement,the cap alignment model in this paper has been slightly modified from the original model in EricWolbrecht’s thesis. The cap alignment process consists of three main stages: 1) aligner, 2) pre-join operation, and 3) join operation. An upstream process feeds base parts and cap material intothe cap alignment stage automatically. After this stage, the aligned cap and base parts flow outinto an alignment inspection sensor. The alignment inspection sensor makes an observation andreports the data. Then the aligned parts are fed into the pre-join operation, where anotherinspection takes place. Next, the join operation receives the parts and joins them. At this stage,the last set of data from the join operation is observed by the post-join inspection sensor. Asimplified diagram of this process is shown in Figure 1.
2.2 INSPECTION DATA
The simplified diagram in Figure 1 used for controlling the cap alignment automatedassembly line provides data from three inspection points throughout the process: after alignment,pre-join, and join operations. Each of these inspection points is capable of rejecting parts exceptfor pre-join inspection, which performs only position measurements.
3
MaterialAlignerStage1Aligner InspectionObservation1Approx.80 partsPreJoin OperationStage2PreJoin InspectionObservation2Approx.360partsJoiningStage3PostJoin InspectionObservation3Figure 1: Diagram of the cap alignment process showing the process layout and inspection points
4
2.3 PRODUCTION RATE AND PART FLOW
The cap alignment is a high speed and automated process. The speed of each processrequires a large number of parts to be queued between stages. There are about 80 parts betweenaligner and pre-join and 360 parts between pre-join and post-join inspections. The number ofparts on the assembly line is also shown in Figure 1.
2.4 COMPONENT FAILURE TYPES
The alignment process consists of three component types: sensor, operation, and material.Each of them is capable of failing. A failure, however, does not indicate that parts beingoperated are out of specifications; they rather imply an improper operation or material. Theobjective of this project is to identify these failures as early as possible.
Material failure occurs only when cap materials have incorrect dimensions or features.This type of failures will affect all the data received down along the stream.
Operation failure can possibly occur at three points: alignment operation, pre-joinoperation, and joining operation. Similar to the material failure, the data received from eachfuture operation is distorted.
Sensor failure could occur at the inspection points. Sensor malfunctions cause local dataerrors but do not affect data received from the downstream operations and do not necessarilyindicate the faulty of any parts.
5
3. BAYESIAN NETWORKS
A Bayesian network is a graphical model that encodes probabilistic relationships amongvariables of interest. When used in conjunction with statistical techniques, the graphical modelhas several advantages in data analysis. First, because the model encodes dependencies amongall variables, it readily handles situation where some data entries are missing. Second, aBayesian network can be used to learn causal relationships, and thus can be used to gainunderstanding about a problem domain and to predict the consequences of intervention. Third,because the model has both a causal and probabilistic semantics, it is an ideal representation forcombining prior knowledge (which often comes in causal form) and data. Last, Bayesianstatistical methods in conjunction with Bayesian networks offer an efficient and principledapproach for avoiding the over-fitting of data.
A Bayesian network is a directed acyclic graph (DAG). The nodes in the graph representvariables within the domain of interest. The directed links between nodes represent the causalrelationships between the variables. The degree of influence that a parent node has on a childnode is represented by the conditional probabilities associated with the child node.
3.1 BAYES’ RULE
The basic expressions in the Bayesian formalism are statements about conditionalprobabilities –e.g., P(A|B) –which specify the belief in A under the assumption that B is knownwith absolute certainty. If P(A|B) = P(A), we say that A and B are independent.
Contrary to the traditional practice of defining conditional probabilities in terms of jointevents,
P(A|B) =
P(A,B) . P(B)6
This conditional relationship in a Bayesian network is seen as a more basic idea than that of jointevents, i.e., more compatible with the organization of human knowledge. In this view, B servesas a pointer to a context or frame of knowledge, and A|B stands for an event A in the contextspecified by B.
The heart of Bayesian network lies in the inversion formula (Bayes’ rule),
P(A|B)=P(B|A) . P(A)
P(B),
which states that the belief we accord a hypothesis A upon obtaining evidence B can becomputed by multiplying our previous belief P(A) by the likelihood P(B|A) that B willmaterialize if A is true. P(A|B) is sometimes called the posterior probability (or simplyposterior), and P(A) is called the prior probability (or prior).
The importance of Bayes’s rule is that it expresses a quantity P(A|B) –which people oftenfind hard to assess –in terms of quantities that often can be drawn directly from our experientialknowledge. For example, if a person at the next gambling table declares the outcome “Twelve,”and we wish to know whether he was rolling a pair of dice or spinning a roulette wheel, ourmodels of the gambling device readily yield the quantities P(Twelve | Dice) and P(Twelve |Roulette) –1/36 for the former and 1/38 for the latter. Similarly, we can judge the prior
probabilities P(Dice) and P(Roulette) by estimating the number of roulette wheels and dice tablesat the casino. Issuing a direct judgment of P(Dice | Twelve) would have been much moredifficult; only a specialist in such judgments, trained at the very same casino, could do it reliably.
7
4. STATIC AND DYNAMIC MODEL DESIGNS
The monitoring of the cap alignment process is based on Bayesian network models. Twoparts that need to be designed are static model and dynamic model. The static model representsthe nodes and the probabilistic relationships between nodes at a particular time slice. The staticmodels of all time slices are combined to form the dynamic model.
4.1 STATIC MODEL
Refer to Figure 1, there are seven basic nodes in the static model: Material node (M),
Stage1 node (ST1), Observation1 node (O1), Stage2 node (ST2), Observation2 node (O2),Stage3 node (ST3), Observation3 node (O3).
4.1.1 Material node (M)
Material node represents the status of the cap material used in the alignmentprocess. There are two states for the material node; i.e. OK and Fault.4.1.2 Stage1 (ST1), Stage2 (ST2), and Stage3 (ST3) nodes
All the above three nodes have the same states; i.e. OK and Fault. Thedifferences are that they locate at different locations in the production line and performdifferent functionality. ST1, ST2, and ST3 nodes represent the alignment operation, pre-join operation, and joining operation, respectively.
4.1.3 Observation1 (O1), Observation2 (O2), and Observation3 (O3) nodes
Similar to nodes in 4.1.2, all the observable nodes have two stages; i.e. OK andFault. Observable nodes represent the status of the visual sensors at different locations.O1, O2, and O3 nodes represent the alignment inspection, pre-join inspection, and post-join inspection, respectively.
8
In the cap alignment process, each operation is dependent upon the accuracy of theprevious operation. For example, if the position of the cap is faulty after the alignmentoperation, then the position of the cap is expected to be faulty at pre-join and post-joininspections.
Note that there is a possibility that two successive operations are faulty but the datareceived from inspection after both operations is good. This would occur only if the faults werecounter-acting. The probability is extremely low, and therefore it will not be considered in thestatic model as a possibility.
The static model of the cap alignment process at a particular time is shown in Figure 2.
ST1Sen1ST2Sen2ST3Sen3MO1O2O3Figure 2: Diagram for the static model of the cap alignment process
4.2 DYNAMIC MODEL
The dynamic model, as shown in Figure 3, is constructed by connecting multiple staticmodels. This dynamic model is known as a dynamic Bayesian network. It consists of infinitelyrepeated slices; the variables in the t’th slice represent the state of the process at time t.
9
ST1Sen1ST2Sen2ST3Sen3Time 1
MO1O2O3ST1'Sen1'ST2'Sen2'ST3'Sen3'Time 2
MO1'O2'O3'ST1''Sen1\"ST2\"Sen2\"ST3\"Sen3\"Time N
MO1\"O2\"O3\"Figure 3: Diagram for the dynamic model of the cap alignment process
From Figure 3, notice that the node ST1 is not the same as ST1’. The reason is the stateof the node ST1 at any time slice may change at the next time slice. For example, the alignermight be OK at the beginning of the process, but might be faulty in the future. Similarly, theinspection node O1 is not the same as O1’.
For the simplicity of the analysis and implementation, the following assumptions areintroduced:
10
• For each time slice, we treat all the state variables (ST1, ST2, and ST3) as a single-state variable (S). This means we can make a query only for one state variable (S) ofeach time slice.
• For each time slice, we treat all the observable variables (O1, O2, and O3) as a singleobservable variable (O).
The final dynamic model is shown in Figure 4.
Time1
S.1Time2
S.2Time3
S.3Time4
S.4Time n-1
S.n-1Time n
S.nO.1O.2O.3O.4O.n-1O.nFigure 4: Diagram for the simplified dynamic model of the cap alignment process
11
5. ANALYSIS OF THREE ALGORITHMS
5.1 A TRADITIONAL POSTERIOR COMPUTATION
The traditional algorithm to compute the posterior probability uses O(SN) time and
space, where N is the total length of the observation sequence and S is the state space size foreach time step. For example, the posterior probability of S.i ; P(S.i), given an observation at O.ican be computed by the following formulas.
P(S.i) = Σ( P(S.i | S.i-1) * P(O.i = o.i | S.i) * PPL(S.i-1) ) * PPR(S.i+1)
S.i-1PPL(S.i) = Σ( P(S.i | S.i-1) * P(O.i = o.i | S.i) * PPL(S.i-1) )
S.i-1
Boundary condition: PPL(S.0) = 1;
PPR(S.i) = Σ( P(S.i | S.i-1) * P(O.i = o.i | S.i) )* PPR(S.i+1)
S.i
Boundary condition: PPR(S.n+1) = 1;
Note that PPL and PPR are the likelihood on the left and on the right of S.i, respectively.
In order to show how to compute the posterior probability by using the traditionalalgorithm, a sample model in Figure 5 is introduced.
S.1S.2S.3S.4S.5S.6S.8(1)
(2)
(3)
S.7S.9S.10S.11S.12S.13S.14S.15O.1O.2O.3O.4O.5O.6O.7O.8O.9O.10O.11O.12O.13O.14O.15Figure 5: The diagram shows a sample model for posterior probability computation.
12
Suppose that we have an observation of a part at time slice 2 and we want to query theposterior probability of a part at time slice 12. First, the algorithm uses the equation (1) for S.12and then calls the PPL of S.11 and the PPR of S.13. Then, the algorithm recursively calls thePPL’s and PPR’s until both ends have reached. Next, the results from both two sides arereturned and combined together at S.12.
It is obvious that the traditional algorithm must do the computation on every time slice inorder to get the posterior result. This presents a significant speed problem for a large number oftime slices since computation is linear in the number of N.
5.2 DIVIDE AND CONQUER ALGORITHM (OR SPACE-EFFICIENT ALGORITHM)
Alternatively, there is an existing algorithm for similar problem by [1] Binder, John, andKevin Murphy, and Stuart Russell. The essential idea of this algorithm is to store the PPL’s andPPR’s at k-1 intermediate “checkpoints” or “islands”, thereby dividing the original sequence intok segments. Next, we recursively apply the posterior algorithm to each smaller segment, makinguse of the boundary conditions stored at each checkpoint. For example, if N = 24 and k=2, wecompute PPL1, PPL2, …, PPL24 and PPR23, PPR22, …, PPR0 by recursively applying the PPLand PPR operators to the boundary conditions PPL0 and PPR24 respectively, but we only storePPLt and PPRt for t=12. We compute P(S.12) by combining PPL12 and PPR12, pass it to thenext recursion, and then do the same thing with the sub-sequences for t=1…11, using PPL0 andPPR12 as a boundary conditions, and for t = 13…23, using PPL12 and PPR24 as boundaryconditions. This algorithm solves the problem that needs to query the state variable at every timeslice.
13
The time required by this approach, T(N), is the time taken to propagate the messagesacross k segments of length roughly N/k each, plus the time to solve the k sub-problems: T(N) =k(N/k) + kT(N/k), so T(N) = NlogkN.
5.3 TREE-BASED ALGORITHM
The speed problem in the traditional algorithm can be avoided with more efficientalgorithm; tree-based algorithm. The posterior probabilities are important only at eachinspection point, and therefore need not be computed at every time slice. The total of themultiplications between time slices can be saved and then updated when a new data is received.This requires only a set of multiplications between time slices rather than a set of multiplicationsfor every part between time slices. The implementation of this algorithm is shown in Figure 6.
15|17|111|515|93|15|37|59|711|913|1115|13S.1S.2S.3S.4S.5S.6S.7S.8S.9S.10S.11S.12S.13S.14S.15O.1O.2O.3O.4O.5O.6O.7O.8O.9O.10O.11O.12O.13O.14O.15Figure 6: Diagram shows the implementation of tree-based algorithm, for k=2.
14
The diagram in Figure 6 shows the tree-based algorithm by using two as a value of k.
For parts of every k time slices, there is a node at the lowest level of the tree that covers them.For example, the node 3|1 covers the time slices from 1 to 3, the node 5|3 covers the time slicesfrom 3 to 5, and so on. All the nodes of the upper levels of the tree will cover the time slicesmore than the leaf nodes do. For example, the node 7|1 covers the time slices from 1 to 7, thenode 11|5 covers the time slices from 5 to 11, and so on. The upper level of the node, the moretime distance it can cover.
The next step is to keep the information into every node in the tree. We keep both leftand right multiplications (PPL, PPR) between two time slices into the node that covers thisduration. For example, both multiplications of both PPL and PPR between time slice 1 and timeslice 3 are kept in the node 3|1.
With the same query as the traditional algorithm, the tree-based algorithm first uses theequation (1) for S.12 and then calls the PPL and PPR of S.11 and S.13, respectively. Since wehave the node 11|5 that covers the time slices from 5 to 11 and the new observation does notoccur inside that range, the algorithm can use the multiplication of PPL of this node. Next, thealgorithm jumps directly to the part at time slice 5 and uses the multiplication of PPL of the node5|3. This will save the steps of computations because it does not have to do the computational oneach part from time slices 11 to 5. However, at the part of time slice 3, it can not continue tojump to the part at time slice 1 because the new observation is inbound between time slice 1 andtime slice 3. Therefore, the traditional algorithm must be used from time slice 3 to time slice 1while a new PPL multiplication of the node 3|1 is updated. The computation of the PPR can bedone in similar way.
15
The algorithm in 5.2 queries the posterior probability of the state variable at every timeslice, while the algorithm in 5.3 queries the posterior probability of the state variable at aparticular time slice. The number of steps in computation of the tree-based algorithm depends onthe height of the tree, i.e. the higher the tree, the more likely faster the computation. The reasonfor this claim is the node at the higher level covers more time slices than the node at the lowerlevel does. Since both k and the number of time slices (N) have influence on the height of thetree, the computation of this algorithm is O(Slogk N)
5.3.1 A Simulation when a new part is inserted into the system
The alignment system must have an ability to handle a large number of parts that aresequentially inserted into the system. A tree is shifted to the right at every time slice. Somelinks in the tree are broken when the right child leaves the system. However, new links will becreated on another side. The diagram in figure 7 shows the simulation of this process.
Figure 7: A diagram shows the simulation when a new part is inserted into the system
16
6. IMPLEMENTATION
The implementation of the tree-based algorithm is designed in an object-orientedprogramming style. The stream of the time slices is represented by an array of objects in theclass Net, while the tree is represented by a two-dimension array of objects in the class Tree.
In addition to these two main classes, the class DBN and the class Utils are needed in theimplementation. The class DBN have a responsibility of performing the management tasks, forexample, brings the parameters from the input text fields and then passes them to appropriatemethods of the objects in other classes. The class Utils performs the basic operations andmiscellaneous tasks, for example, it can find the multiplication of two one-dimension arrays andreturn the result or it can print an array to the display. The full details of the four classes can bedescribed as the following.
6.1 CLASS DEFINITIONS
6.1.1Class Net
The data values that are kept in the class Net are:• Psi: Prior probability of S.i
• P(Si+1|Si): The probability of S.i+1 given S.i• P(Oi|Si): The probability of O.i given S.iThe main methods in this class are:
• Posterior: An object in the class DBN calls this method in order to computethe posterior probability at location S.i.
• PPL and PPR: These two methods are called within the method Posterior inorder to compute the likelihood on the left and right.
17
6.1.2 Class Tree
The data values kept in the class Tree are:
• LAvailable: Status shows whether the saved value of PPL is available.• RAvailable: Status shows whether the saved value of PPR is available.• Left: Point to the left child.• Right: Point to the right child.• SavePL: The saved value of PPL.• SavedPR: The saved value of PPR.
Most of the methods in the class tree are the methods that handle the interfaces onthe data values, except the method ShiftTree that shifts the tree to the right when the newpart was inserted.6.1.3 Class DBN
The data values kept in the class DBN are mostly the text fields that get the inputfrom the user entries.
The methods in the class DBN are:
• Init: This method initializes all the labels and text fields of the applet.• DoComputation: This is the main function of the program.
• HandleEvent: This method handles the mouse-click event that occurs in theapplet.
6.1.4 Class Utils
The data values kept in the class Utils are:• NTSlices: The number of time slices (N).
• SiLoc: The location of S.i that needs to do the query.
18
• OiLoc: The location of the new observation.• K: the constant k in the algorithm.The methods in the class Utils are:
• Projection: Perform the projection of a two-dimension array.
• SumOverRow: Perform the summation on the two-dimension array by roworientation.
• SumOverCol: Perform the summation on the two-dimension array by columnorientation.
• SumOverM: Perform the summation on the middle dimension of the three-dimension array.
• MulOneOne: The multiplication of two one-dimension arrays.• MulTwoOneRow: The multiplication of two-dimension array and one-dimension array by row orientation.
• MulTwoOneCol: The multiplication of two-dimension array and one-dimension array by column orientation.
• MulTwoTwo: The multiplication of two two-dimension array.
• PrintArray: Print any kind of arrays to the display. Note that the PrintArray isthe polymorphism function.
• FindCheckPoints: Assign the check points to the time slices. The checkpointof the time slice shows that there is a node in the tree that point to it.• BuildTree: Build the tree structure based on the given time slices (N) andconstant k.
• IncrementLeft: Increment the left data values of the nodes in the tree.
19
• IncrementRight: Increment the right data values of the nodes in the tree.
6.2 CLASS INTERACTIONS
The interactions of the classes can be described in two diagrams; i.e. the staticrelationship diagram, and the dynamic relationship diagram.
DBNTreeNetUtilsFigure 8: Diagram shows the static relationship diagram.
The static relationship diagram shows the communication between the four componentsof the system. The DBN is the manager who needs to contacts the Net by calling the posteriorcomputation method. It also needs to call the methods ShiftTree and PrintArray of the Tree andthe Utils, respectively. In addition to communicate with the DBN, the Tree also needs tocommunicate with the Net in order to provide the saved result of multiplication, and with theUtils in order to call the utility functions. The diagram in Figure 8 shows their dynamicinteractions during the execution of a scenario.
20
DBNStart withrandomly pickSiLoc andOiLocNetUtilsTreeCall PosteriorCall utilitymethodsTree lookup & UpdateShift & Insert anew partShift the tree to the rightFigure 9: Diagram shows the dynamic relationship diagram.
21
7. EXPERIMENTAL RESULTS
The experiment of the tree-based algorithm is designed to run with the different values of
N and k. The query time is measured in the milliseconds. The values of N are 5, 10, 25, 50, 100,200, 400, 800, 1000 and the values of k are 2, 4, and 8. In addition, the results from thetraditional algorithm are compared with the results from the tree-based algorithm. Due to themissing of the time measurement in another approach, comparison is not applicable.
Figure 10: The graph shows the experimental results
The graph of a traditional algorithm is linear in the number of time slices; O(SN). On theother hand, all of the graphs; with different values of k, of the tree-based algorithm grow slowlybelow the linear line. The trend of the tree-based graph is congruent to the argument set forth in
22
the introduction; i.e. the query-time complexity of this algorithm is O(SlogN). However, thetime spent on the tree shifting of the tree-based algorithm does not in the form of logarithm.This affects the total run time of the system because every node in the tree needs to be shift to theright. The suggested solution of the future work is to use the different kind of data structure torepresented every part in each time slice, for example, one object in the circular queue representone part. The current pointer is needed to specify the current location of the newest part. Byusing this approach, we do not have to do the shifting operation.
23
8. CONCLUSIONS
Bayesian networks applied in the manner presented in this report can provide a goodmodel of the probabilistic relationships between multiple parts in a multi-stage manufacturingprocess. The results from this project indicate that system developed in this manner has thecapability to represent a complicated process by modeling each part separately and thenconnecting the multiple static models to form one process model. This assumes the followingthree things. First, if a good part is produced, there is high probability that the next partproduced will be good, and vice versa. Second, data from part inspections is correlated to boththe state of the part and the state of operations used to produce the part. Finally, theconfiguration parameters of the inspection data are well known.
For the number of time slices (N) that less than 1,000, the appropriate value of k that canimprove the query time are 4 or 8, depending upon the limitation of space. That is the greatervalue of k consumes space for keeping the nodes in the tree less than the smaller value of k does.
In a real application of this system, a failed component can be shut down when a failureis detected. When more evidence is received from the bad parts already in process, the systemcan provide probabilistic diagnosis.
In general, this system may be applied to similar manufacturing processes, where partsare produced in sequential manner, and inspection is performed at several points throughout theprocess. However, the shifting part of the algorithm still needs to be improved in order to limitthe total time complexity of the system to the proportion of logN.
24
REFERENCES
1. Binder, John, and Kevin Murphy, and Stuart Russell. Space-efficient inference in dynamic
probabilistic networks. In Proc. Fifteenth International Joint Conference on ArtificialIntelligence, Nagoya, Japan, 1997.
2. Breese, John S., and David Heckerman. Decision-Theoretic Troubleshooting: A Frameworkfor Repair and Experiment. Technical Report, MSR-TR-96-06, Revised May 1996,Microsoft Research, Advanced Technology Division, Microsoft Corporation, One MicrosoftWay, Redmond, WA 98052. Also appears in the Proceedings of the Twelfth Conference onUncertainty in Artificial Intelligence, August 1996.
3. Budd, Timothy. An Introduction to Object-Oriented Programming, Second edition. Animprint of Addison Wesley Longman, Inc.
4. D’Ambrosio, Bruce, and Scott Burgess. Some Experiments with Real-time DecisionAlgorithms. Technical Report, CS department., Oregon State University, 1996.5. Heckerman, David, John S. Breese, and Koos Rommelse. Troubleshooting underUncertainty. Technical Report, MSR-TR-94-07, Revised September 1994, MicrosoftResearch, Advanced Technology Division, Microsoft Corporation. Portions appear in theProceedings of the Fifth International Workshop on Principles of Diagnosis, New Paltz, NY.6. Pearl, Judea. Probabilistic Reasoning in Intelligent Systems: Networks of PlausibleInference. Morgan Kaufmann Publishers, Inc.
7. Russell, Stuart, and Peter Norvig. 1995. Artificial Intelligence. Englewood Cliffs, N.J.:Prentice Hall
8. Wolbrecht, Eric. Monitoring and Diagnosis of a Multi-stage Manufacturing Process using
Bayesian Networks. A thesis submitted to Oregon State University.
25
因篇幅问题不能全部显示，请点此查看更多更全内容