Home

Computer-Assisted Troubleshooting for Efficient Off-board

1. Algorithm Problem Expan Backups Comp No of class sions time s problems wIBLAO Trivial 17 8 217 3 0 02 12 12 Easy 166 4 3191 9 0 26 12 12 Intermed 1291 4 44235 4 5 08 9 11 Hard 3241 7 123996 3 16 06 3 10 FRTDP Trivial 30 9 168 3 0 02 12 12 Easy 646 7 3089 8 0 53 12 12 Intermed 30989 9 103930 9 41 63 9 11 Hard 83576 7 244798 0 125 60 3 10 BRTDP Trivial 421 6 2903 2 0 19 12 12 Easy 7398 0 43186 8 4 18 12 12 Intermed 58501 7 221979 1 65 99 9 11 Hard 131694 3 478653 3 161 61 3 10 VPI RIDP Trivial 608 2 6303 2 0 21 12 12 Easy 9528 3 55563 5 4 08 12 12 Intermed 56332 6 2135787 64 50 9 11 Hard 145276 3 582009 3 165 08 3 10 ILAO Trivial 71 6 808 3 0 06 12 12 Easy 4114 2 57218 3 4 44 12 12 Intermed 724963 1573655 1 93 95 9 11 Hard 131622 7 2938452 0 167 4 3 10 5 4 Evaluation 125 Table 5 7 Average results for troubleshooting using wIBLAO when composite actions are used and when they are not Comp Problem Error Expan Backups Comp Solv actions class bound sions time s ed Yes Trivial 0 0003 18 0 215 2 0 01 100 0 Easy 0 0009 166 6 2955 5 0 20 100 0 Intermed 0 0009 1371 5 45414 5 4 04 100 0 Hard 0 0009 8211 1 343506 1 33 08 100 0 Very hard 0 0116 47849 9 3037271 9 337 42 81 8 No Trivial 0 0004 323 2 14677 9 0 38 100 0 Easy 0 0009 2909 8 203435 7 5 14 100 0 Intermed 0 0010 3
2. 3 3 1 Troubleshooting Plans A solution to the troubleshooting problem is a conditional plan of actions that can be followed to successfully repair any faulty component The troubleshoot ing plan is a function that tells what action to do next given the sequence of events that has occurred Definition 3 3 Troubleshooting Plan Let I M elc 0 Fa Cg be a trou bleshooting problem where te is the current time and let be a set of se quences of events specific to a troubleshooting plan 7 that is a a function 7 Ex A where all of the following holds 1 elt ie the plan has an action for the sequence of events that has occurred up to the current time 2 for all elf and all e mel e pirl n elt y t 1 t n des a elite aeth is also in Ez i e for all sequences of events el al t 1 t n the sequence 52 Chapter 3 Troubleshooting Framework ready in 5 the plan has an action for every outcome of the action z e i3 3 forallel Ez it is the case that el A F 0 F f for id f Ferry Le if the plan has an action for a sequence of events el then the preconditions of that action F ey are satisfied given the status of the feature variables at time t A troubleshooting plan 7r is said to be a solution to the troubleshooting problem I M elte f0 F Cg if for every elt E where z el ag it holds that P C Cel M 1 and el A F f
3. This is a stronger result than in the way that e may be an arbitrary sequence of events and that B also is stationary but is weaker in that we also have to condition on the persistent variables at time tw However if we keep track only of the probability distribution over the persistent variables at time tw and the repair events r that has occurred between time tw and time t we can find rules to compute and 3 10 64 Chapter 3 Troubleshooting Framework 3 5 5 Computing the Probabilities using the Static Represen tation Definition 3 6 Belief state after the last operation event The belief state after the last operation event is a function by Oc gt 0 1 b c P C cle Bus where tw is the time of the most recent operation event in elt This represents our belief of the state that the components had at the time of the last operation event given what we know at time t Because of Assumption B the values of the components statuses at time t can be determined by knowing r and the component statuses at time tw Let y r c Og x Oc gt Qc be a function that returns a vector that has the same values as c for all components except those repaired in r which have the value NF then 1 ify cte P c r Bus Ple cto e1 Bas 3 22 0 otherwise Given the belief state at last operation event bt and the recent repair events r the belief state b can be obtained using 3 22
4. llle 28 232 Partial Observability 30 2 9 8 Stochastic Shortest Path Problems 32 2 3 4 Finding the Optimal Policy for an MDP 33 2 3 5 Finding the Optimal Policy fora POMDP 40 II Decision Theoretic Troubleshooting of Heavy Vehicles 43 3 Troubleshooting Framework 45 PEPTIDE 45 32 The Troubleshooting Model rese rr es 46 SAL AGHORS amp an ed ee T dde PCS o E opes ig 48 3 22 Probabilistic Dependency Model 50 SPUR Red dies a Meee 51 3 3 1 Troubleshooting Plans soo res se ss llle 51 3 3 2 Troubleshooting Cost o o o ooo 54 a dio df a BT 56 3 4 1 Assumptions for the Problem 56 3 42 Assumptions for the Action Model 56 3 4 3 Assumptions of the Probabilistic Modell 57 Lio Re E Sou We Ee bee Ea ee ee ee ue s 58 3 5 1 Computing the Probabilities 59 3 5 2 Static Representation of the nsDBN for Troubleshooting 60 3 5 3 Computing the Probabilities using the Static Representa EI A CUPDERCNDU PR 64 Dio Planner neos xo Res Sue ae Pade ewe EX EO e RR 69 EA A 70 3 62 Solving the SSPP so ooo ee sees sr sr ooo 72 3 6 3 Search Heuristics for the SSPP for Troubleshooting 73 3 6 4 Assembly Modell 0 0 2000 81 igh te E he eee ee es A 85 3 71 A Different Repair Goal 85 a ee A ee ek 87 3 7 3 General Feature Variables
5. ln 91 3 74 Different Probabilistic Models 92 vii 93 41 Iterative Bounding LAO rr ooo ooo 94 411 Evaluation functions oss ss ss so ss so 0004 95 412 Error Bound sse ede 4 6 as Rn 9n 97 30 ie eu eS a e PAR RUN 98 Bs Hats chs IN at atta te eae 1 99 POSEE 101 421 Racetrack 101 E E bbe da ia ES 104 109 5 1 Introduction a 109 52 TheRetarder css close oda ge abe et 109 b3 The M dell 2 06 cae a e e er den OH dne Ex BN 111 sty bye aot A os a Gee Sree A anak an 115 541 TheProblemSet l llle 115 LU 117 ua ELT 120 CHRIS 120 RLW PP 122 Ans doeet REM eus e RE ES 122 127 131 133 143 147 C The Retarder Model File 149 viii Part I Introduction 1 Background Troubleshooting is the process of locating the cause of a problem in a system and resolving it This can be particularly difficult in automotive systems such as cars buses and trucks Modern vehicles are complex products consisting of many components that interact in intricate ways When a fault occurs in such a system it may manifest itself in many different ways and a skilled mechanic is required to find it A modern mechanic must therefore have an understanding of the mechanical and thermodynamic processes in for example the engine and exhaust system as well as the electrical and logical processes in the control units Every year the next gene
6. Ft f for same f F This means that the stop action will only be executed when the troubleshooting goals are achieved A troubleshooting plan can be seen as a tree where the nodes are actions and edges are events The leaves of this tree are stop actions because the stop action is the only action that has no effects and therefore generates no events Example 3 4 Let Mex be the sample system modeled in Section D 2 Consider an instance of the troubleshooting problem I where the low oil pressure alarm has been triggered and it has been observed that the oil level is normal lex Mex ol ind Ct NF fit fit fit fit NF NF NF NF Figure 3 3 shows a graphical representation of a troubleshooting plan Tex that is a solution to the problem Iex Written out Tex is the following Action Sequence of events ag 05 ind C NF as O5 ind C2 NE F rem a3 Ol ind CI NF F rem C4 NF av Ol ind C4 NE F3 rem C NF C NF ap Ol ind C2 2 NF F rem C NF C3 NF F fit ay Ol ind CI NF FS rem CT fail az Ol ind C2 NF F3 rem C4 fail C NF ag Ol ind Ci NE F3 rem C4 fail C NF F fit ap Ol ind C2 NF F rem C fail C NF F fit O cn az Ol ind C2 NE Fj rem C1 fail C NF Fe fit 03 ind ao l ind C NF F
7. stop do 6 if O G A 0 then 7 Sexpand Subset of G 8 for each s Sexpand do EXPAND s 9 Sbackup ancestors Sexpand 10 else 11 Spackup NI 12 end if 13 for each s Shackup do DOBACKUP s 14 end while 15 end while 16 return 7r 17 end procedure 18 procedure EXPAND s 19 for each a A do 20 for each s succ a s s N do 21 fi s lt hy s 22 Fals huls 23 end for 24 N N U succ a s 25 E U s succ a s 26 end for 27 end procedure 28 procedure DOBACKUP s 22 fils minge 4 T fi s 30 m s arg min ea Tafi s 31 fuls minaca T fu s 32 my s arg min 4 T fu s 33 end procedure 4 1 Iterative Bounding LAO 97 Then after applying on a state s fi s T y fu s gt ming T f s and for all other states s f s gt ming Tyfu s gt ming T f s Since fu is initialized with h the condition implies that holds Let fo fi be functions such that fis Va s ifi 0 or s is a goal state s Tr 5 f 1 8 otherwise This corresponds to the value function of a policy where actions are chosen according to 7 until i steps into the future when actions are chosen according to 7 Asi oo fi s gt Va s If i gt O and fi_1 s fu s then using fils Tz Gyfu s fuls Because fo s Vz s lt fu s it follows that fils fu s for all i Theorem H 1 guar
8. 108 Chapter 4 Planning Algorithm Table 4 5 Comparison of algorithms on the problem rover6 from the rovers domain rover Va expansions backups time wIBLAO 01 704 2 11532 313933 7 11 0 01 686 7 33027 1672932 217 0 001 686 7 38112 2225727 26 1 IBLAO 0 1 735 0 33089 455971 173 0 01 686 7 39773 567859 20 6 0 001 686 7 47724 700254 247 ILAO 0 1 6933 23117 331570 112 0 001 686 7 80666 1990941 37 0 0 001 686 7 94863 2566326 44 4 BRTDP 0 1 6933 43140 168840 16 9 0 01 686 7 156051 769806 62 1 0 001 686 7 177238 900978 71 3 FRTDP 01 7033 54505 232704 21 5 0 01 686 7 160857 842038 654 0 001 686 7 180946 974982 74 7 VPI RTDP 01 7017 45111 182136 17 5 0 01 686 7 148060 739986 59 0 0 001 686 7 168699 868600 677 5 Case Study Hydraulic Braking System 5 1 Introduction This chapter presents a case study of the troubleshooting framework for a hy draulic braking system of a truck This system is called a retarder and we will describe the system and how it can be modeled in the framework The perfor mance of the planning algorithm IBLAO and the new heuristics is evaluated through empirical tests on the model 5 2 The Retarder The retarder is an auxiliary hydraulic braking system that allows braking of the truck without applying the conventional brakes It consists of a mechanical system and a hydraulic system and is controlled by an electronic control unit ECU The retarder generates bra
9. The current values of these bounds are denoted by f s and f s respectively The lower and upper bound policies 71 and 7r corresponding to these evaluation functions are defined as follows nj s arg min T f s n s arg min T f s acA acA Every time a new unvisited state is added to G its bounds are initialized using two heuristic functions f s h s and f s h s These heuristics are assumed given as part of the problem and must satisfy h s lt V s and hy s gt V s for all states s When a state is backed up new bounds f s and f s are calculated from the previous f values as follows fi s max fi s Tm s fils 4 1 fi s min fuls Ts 5 Lu s 4 2 The bounds guarantee that there exists a policy 7 such that f s lt Va s lt fu s However they do not tell us how such a policy can be found Theorem 4 1 If the upper bound heuristic h is uniformly improvable i e for all states s hy s gt min T h s 4 3 acA then the value function of the upper bound policy V is bounded by f and fu so that for all states s f s Vr s lt fuls Proof Since fj s Vr s we also have that f s Vr s Assume that fu s 2 min T f s 4 4 96 Chapter 4 Planning Algorithm Algorithm 5 Iterative Bounding LAO 1 procedure IBLAO SSPP S A p C S0 Sg hu hue 2G NE 650 0 3 while stop do 4 EA so 5 while so gt
10. e ra s s oe fi s Ty s fils When 0 G 0 the estimated error in all leaves of G is less than or equal to In this case if the error bound has not converged so that so lt e repeated backups of all the states in G7 will either cause D G7 4 I or by Theorem 4 2 cause so lt When so lt the inner loop is exited and the error threshold e is reduced by a factor where 0 1 Then the algorithm restarts on line 5 and expands states previously considered solved on the fringe of G s lt 4 13 Expanding the Fringe Since Iterative Bounding LAO does not use depth first trials like many RTDP based algorithms the fringe may become very large In each iteration of the inner loop the algorithm therefore only selects a subset Sexpand of the states in G7 for expansion Ideally the algorithm should select those states whose expansions would have the largest impact on the estimated error of the initial state Omitting such states may lead to unnecessarily many backups while including other states leads to unnecessary work during expansion A possible measure of this impact is the product of the estimated error in a state and the likelihood that the state will be reached from so in the solution graph G7 Since calculating exact state likelihoods is computationally expensive we use an approximation f s The calculation of this approximation is interleaved wi
11. Luis Alejandro Cortes A Petri Net Based Modeling and Verification Technique for Real Time Embedded Systems 2001 Niklas Sandell Redovisning i skuggan av en bankkris V rdering av fastigheter 2001 Fredrik Elg Ett dynamiskt perspektiv p individuella skillnader av heuristisk kompetens intelligens mentala modeller m l och konfidens i kontroll av mikrov rlden Moro 2002 Peter Aronsson Automatic Parallelization of Simulation Code from Equation Based Simulation Languages 2002 Bourhane Kadmiry Fuzzy Control of Unmanned Helicopter 2002 Patrik Haslum Prediction as a Knowledge Representation Problem A Case Study in Model Design 2002 Robert Sevenius On the instruments of governance A law amp economics study of capital instruments in limited liability companies 2002 Johan Petersson Lokala elektroniska marknadsplatser informationssystem f r platsbundna aff rer 2002 Peter Bunus Debugging and Structural Analysis of Declarative Equation Based Languages 2002 Gert Jervan High Level Test Generation and Built In Self Test Techniques for Digital Systems 2002 Fredrika Berglund Management Control and Strategy a Case Study of Pharmaceutical Drug Development 2002 Fredrik Karlsson Meta Method for Method Configuration A Rational Unified Process Case 2002 Sorin Manolache Schedulability Analysis of Real Time Systems with Stochastic Task Execution Times 2002 Diana Szentiv nyi Performance and Availability Trade offs
12. P X1 X 5 X Bas e 3 17 62 Chapter 3 Troubleshooting Framework time slice 0 time slice 1 time slice 2 xi X5 X2 x2 Figure 3 4 The first three time slices of the nsDBN in ExampleD 5 left and its static representation right Note that P X X DX can be computed using for example the Variable Elimination algorithm described in Section 2 2 4 Also note that a BN de fined according to DefinitionB 5 will bea two layer BN Figure B 4 shows the first three time slices of the nsDBN in Example and its corresponding static representation In this example the parents of the variable X are non persistent Therefore we will replace the paths OQ X9 X9 XO X9 XI X9 X2 and X2 X9 X9 X2 with the edges Xi Xs X2 X6 and Xo X6 The conditional probabilities for this variable are obtained by marginalizing away X3 and X4 P Xg xe X2 X2 X4 X1 X2 Xp P X xe X4 x2 X gi xl X2 Y XP0G xe X xs X4 X4 P X3 x3 X7 X1 X3 x2 P XG x4 X3 22 x3 0 xaxa Ox When using DefinitionB 5 as a definition for the static representation of the nsDBN we can state a theorem similar to 3 16 Theorem 3 1 Let D be the static representation of an nsDBN Bs defined ac cording to Definition 3 5 let e1 1 be an arbitrary sequence of events and let e be the event X x Then the two networks and Bus el are equivalent 3 5 Diag
13. When the weight is high poli cies with many fringe states close to the goal where the heuristic estimates of the expected cost to go are smaller will be chosen before less explored policies This reduces the size of the search space but may cause optimal solutions to be missed As with LAO in the worst case the algorithm may converge towards a solution that is suboptimal by a factor w and for all states s fowls WV s 4 7 100 Chapter 4 Planning Algorithm The error bounds in states are estimated with the weighted estimated error fu s fols w Where 0 fs Theorem 4 3 If a4 amp w s lt p n 1 4 8 holds then the relative error e s lt Proof Using Theorem 4 Tland 4 7 _ fuls fo s gt Vm fw s WV amp w s Then using and 4 5 lt 1 e s 1 1 w w 1 Theorem 4 3 makes it possible to choose a weight w lt 1 such that when a solution is found in Gr the relative error is still less than or equal to There is some freedom in how the weight w may be assigned If w 1 all excess error is used for the weight function and a state s will not be considered solved until s 0 forcing the algorithm to expand every state in Gr We use w VE 1 which ensures that search branches can be pruned when w s VE 1 This choice distributes the amount of acceptable error given by evenly between w and j s When the
14. tial plan repairing all faulty components with optimal cost The probability of each outcome of this observing action is the probability of each diagnosis Let s bw r f and let b be the belief state computed from by using 3 23 Further let c c f be the minimal cost of repairing the faulty components in c and setting the feature values to some f Fg given the values of the feature variables f Then the full observability heuristic hp is defined as hg s Y b c c c f 3 40 ccOc Another way to create a search heuristic is to measure the level of uncer tainty in the state In all goal states we have full certainty since a goal state is a system state where the probability that all components are non faulty is 1 The uncertainty can be measured using the entropy H s 2 Y b c log b c 3 41 ccOc where H s 0 means that we have full certainty of the current diagnosis in s An observing event with n possible outcomes can at most reduce the en tropy by log n and a repair event of a component with n fault modes may at most reduce the entropy by log n 1 An action that may generate multi ple events can reduce the entropy by at most an amount corresponding to the sum of the entropy each individual event may reduce Let cy a be the min imum cost of reducing the entropy by one through the action a A heuristic based on entropy Ment can be formed as following hent s H s mincg a 3 42 acA The full
15. type discrete 2 Not faulty Faulty node C15 name 0il category persistent type discrete 2 Not faulty Poor quality node C16 name Radial gasket retarder category persistent type discrete 2 Not faulty Leakage node C17 name Gasket retarder side category persistent type discrete 2 Not faulty Leakage node C18 name Radial gasket gearbox category persistent type discrete 2 Not faulty Leakage Y node C19 name Cables ECU category persistent type discrete 3 Not faulty Break ret side Break ECU side Y node C20 name ECU category persistent type discrete 2 Not faulty Faulty Y Observations node 001 4 name Oil temp category nonpersistent type discrete 2 Normal Y node 002 name Retarder disengagement category nonpersistent type discrete 2 Normal Y node 003 name Engine warning lamp category nonpersistent type discrete 2 Not lit node 004 name Cooler category nonpersistent type discrete 2 Normal node 005 name Torque category nonpersistent type discrete 2 Normal node 006 name Torque driver category nonpersistent type discrete 2 Normal node 007 name Torque mech category nonpersistent type discrete 2 Normal
16. 0 1 0 0 0 0 1 0 probability 018 C15 0 1 0 1 0 1 probability 019 C04 C06 C16 C17 4 type NI NI NI NI function nor 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 2 0 0 0 1 0 9 0 0 1 00 0 1 0 9 0 0 0 1 0 2 0 8 probability 020 C14 C17 C18 4 type NI NI NI function nor 0 0 0 1 0 1 0 0 0 1 Appendix C The Retarder Model File 158 0 2 0 8 0 1 0 13 0 0 0 1 probability 022 C14 C16 NI NI gt function nor type 1 0 0 0 o a o ao o oo AA ou no oe probability 023 C19 4 gt 0 5 13 1 0 0 1 gt 0 1 2 Y probability 024 C19 probability 025 C19 C20 function nor oad uoo AAA ooo Oun v 0 1 0 9 0 1 probability 026 C20 4 1 0 0 0 1 0 9 1 probability FC C01 C02 C03 C04 C05 C06 C07 C08 CO9 C10 C11 C12 C13 C14 C15 C16 C17 C18 C19 C20 4 function nor 0 1 1 1 1 T i 1 1 1 T 1 1 i i 1 1 1 1 1 1 i 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 O 0 0 0 0 O 0 O O 0 O O O 0 O 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 O 1 0 0 0 O O O O 0 O O 0 O O O O O 0 0 0 O 1 0 0 0 0
17. Improving the conver gence of real time dynamic programming In Proceedings of the 13th Inter national Conference on Automated Planning ICAPS 03 2003 10 Blai Bonet and Hector Geffner Solving POMDPs RTDP Bel vs Point based Algorithms In Proceedings of the 21st International Joint Conference on Artificial Intelligence IJCAI 09 2009 11 Daniel Bryce and Subbarao Kambhampati Sequential Monte Carlo in probabilistic planning reachability heuristics In Proceedings of the 16th International Conference on Automated Planning ICAPS 06 2006 12 A R Cassandra L P Kaelbling and M L Littman Planning and Acting in Partially Observable Stochastic Domains Artificial Intelligence 101 1 2 99 134 1998 13 Marie Odile Cordier Philippe Dague Frangois L vy Jacky Montmain Marcel Staroswiecki and Louise Trav Massuy s Conflicts versus ana lytical redundancy relations a comparative analysis of the model based diagnosis approach from the artificial intelligence and automatic control perspectives IEEE Transactions on Systems Man and Cybernetics Part B 34 5 2163 2177 2004 14 Daimler AG From hard haul to high tech 50 years of truck development for the sake of the environment safety comfort and economy Press release http www media daimler com 2010 15 R Davis and W Hamscher Model based reasoning troubleshooting In Exploring Artificial Intelligence pages 297 346 Sa
18. Intermed 0 0009 1312 3 1320 2 6 76 Hard 0 0010 7429 3 15423 101 58 Very hard 0 0147 36314 9 1826 96 767 34 Yes No Trivial 0 0003 23 1 1071 6 0 05 Easy 0 0008 169 1 1110 0 0 65 Intermed 0 0009 1544 7 1331 3 12 06 Hard 0 0010 8707 7 1548 6 158 23 Very hard 0 0165 38886 5 1833 9 832 97 5 4 Evaluation 127 expected cost of repair becomes higher The problem becomes only slightly more difficult to solve when there is no possibility of making a function control but when repairs may fail the problem becomes much more difficult to solve This is because every repair action introduces may introduce new faults that have to be treated and the search space becomes larger For the same model the performance of the planner is slightly reduced when the heuristic fixed is used instead of Ij 5 4 7 Troubleshooting Performance with Limited Decision Time In this section we will compare troubleshooting using IBLAO when the time allowed to make decisions is limited with the greedy look ahead approaches used in Sun and Weld and Langseth and Jensen 42 and with the other planning algorithms Comparison with Look Ahead Search In Sun and Weld 79 the estimated remaining ECR in a state s ECRsun s is the sum of the cost of repairing all components if the true diagnosis is known plus the entropy weighted with the average observe action cost i e ECRsun 8 hg s hent 5 where for the computation of hent s the average cost of th
19. J node 008 High Early Lit Oil stained Uncontrollable Uncontrollable Uncontrollable name DTC unplausible coolant temp category nonpersistent type discrete 2 Not indicating Indicating node 009 name DTC unplausible oil temp 151 152 category nonpersistent type discrete 2 Not indicating Y node 010 name Vis leakage magnet valves category nonpersistent type discrete 2 Not indicating Y node 011 4 name Vis leakage prop valve category nonpersistent type discrete 2 Not indicating Y node 012 name DTC unplausible oil pres category nonpersistent type discrete 2 Not indicating Y node 013 name Vis leakage control valve category nonpersistent type discrete 2 Not indicating Y node 014 name Leakage air tube category nonpersistent type discrete 2 Not indicating Y node 015 name Leakage air valves category nonpersistent type discrete 2 Not indicating Y node 016 name Retarder engagement category nonpersistent type discrete 2 Normal Late node 017 name Braking force category nonpersistent type discrete 2 Normal Bad node 018 name Oil quality category nonpersistent type discrete 2 Normal Bad node 019 name Dil lev
20. No 498 No 503 FHS 8 95 FHS 9 95 No 513 No 517 No 518 No 522 No 538 No 545 No 546 FiF a 1 96 No 549 No 550 No 557 No 558 No 561 No 563 Johan Ringstr m Compiler Generation for Parallel Languages from Denotational Specifications 1993 Michael Jansson Propagation of Change in an Intelligent Information System 1993 Jonni Harrius An Architecture and a Knowledge Representation Model for Expert Critiquing Systems 1993 Per sterling Symbolic Modelling of the Dynamic Environments of Autonomous Agents 1993 Johan Boye Dependency based Groudness Analysis of Functional Logic Programs 1993 Lars Degerstedt Tabulated Resolution for Well Founded Semantics 1993 Anna Moberg Satellitkontor en studie av kommunikationsm nster vid arbete p distans 1993 Peter Carlsson Separation av f retagsledning och finansiering fallstudier av f retagsledarutk p ur ett agent teoretiskt perspektiv 1994 Camilla Sj str m Revision och lagreglering ett historiskt perspektiv 1994 Cecilia Sj berg Voices in Design Argumentation in Participatory Development 1994 Lars Viklund Contributions to a High level Programming Environment for a Scientific Computing 1994 Peter Loborg Error Recovery Support in Manufacturing Control Systems 1994 Owen Eriksson Informationssystem med verksamhetskvalitet utv rdering baserat p ett verksamhetsinriktat och samskapande perspektiv 1994 Karin Pettersson Informationssystemstru
21. The actions are found in the reverse order in which they should be executed Therefore new effects are added to the beginning of a The cost c a c a is the smallest possible cost of all action sequences that take us from the system state s to a state where the precondition of a is satisfied 3 6 Planner 83 Algorithm 4 Create Composite Action 1 procedure CREATECOMPOSITEACTION M a f 2 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 c a c a E a E a F queue for each F f P a do if F f f then ENQUEUE F f Fqueue end for while Fyjueue 7 do F f DEQUEUE queue if f D then a lt disassemble F for each F pa F do if F D A F D Fquue F D a then ENQUEUE F D Fqueue end if end for else a lt assemble F for each F ch F do if F A A F A E Fqueue F A Ela then ENQUEUE F A Faueue end if end for end if c a c a c a a E a a end while 28 end procedure 84 Chapter 3 Troubleshooting Framework Applicable Actions When we use composite actions the set of possible actions will instead of A be A which is a function of the state For any state s A s will contain the composite action for all actions in A that have at least one effect that is either a repair observation or operation of the system An action t
22. The work described in this thesis contributes to solving the troubleshooting problem in such a way that a good trade off between computation time and solution quality can be made Emphasis is placed on solving the decision problem better than existing methods A framework for troubleshooting is de veloped where the diagnosis problem is solved using non stationary dynamic Bayesian networks nsDBN and the decision problem is solved using a new algorithm called Iterative Bounding LAO IBLAO The main contributions are the new algorithm and new and improved heuristics for solving the decision problem by searching The algorithm is ap plicable for probabilistic contingent planning in general and in this thesis it is applied to troubleshooting of subsystems of a modern truck Pernestal has developed a framework for nsDBN s applied to troubleshooting In this work we show how those nsDBN s can be converted to stationary Bayesian networks and used together with IBLAO for troubleshooting in our application IBLAO is a new efficient anytime search algorithm for creating e optimal 1 5 Contributions 15 solutions to problems formulated as Stochastic Shortest Path Problems a sub group of MDPs In this thesis we show how the troubleshooting problem can formulated as a Stochastic Shortest Path Problem When using IBLAO for solving the decision problem the user has access to and may monitor an upper bound of the ECR for the current plan as well as a l
23. When Af s s is suboptimal at least one feature variable F is set from a mode f to a mode f that is not necessary to satisfy the precondition of 7r s Let a be the last action in Af s s that affects a feature variable F that is not necessary to satisfy the precondition of 7 s If a disassembles F then it can safely be postponed to after 7r s without preventing any other action in Af s s from being performed and it will still be applicable because any action that assembles a variable in pa F requires F to be assembled which would mean that Af s s contains actions that both assemble and disassemble F This is not possible because then either a is necessary to satisfy the precondi tion of zr s or ais not the last in Af s s that affects a feature variable F that is not necessary to satisfy the precondition of 7r s The same reasoning applies if a is an action that assembles F This means that we can postpone any action that is not necessary to satisfy the precondition of z s in any state s S until they are needed and thereby we create a policy where all sequences of actions affecting only feature variables have minimal cost Therefore the as sumption V lt V cannot be true 3 7 Relaxing the Assumptions In this section we will see how some of the assumptions made in Section B 4 can be relaxed and how this can be treated in the troubleshooting framework 3 71 A Different Repair Goal
24. bl c x P O ind Cy c1 Ca C3 C4 c4 B b c b c x P C4 NF C4 c4 B b c b2 c e P C4 fail C1 c1 B b2 c The probability of the event outcome P C3 fail e is obtained during normalization i e P Ci fail e Y P Ci fail C1 c1 B b2 c 0 2002 cc Oc The fourth event is a repair event so the rule is used to update bw i e no change is made and C1 NF is added to the list of repairs The fifth event is an operation event and now the effect of C1 NF will be accounted for when by is updated using the rule 3 38 bo c Y te v r4 e tEOc bi c b4 c1 c2 c3 10w if e c1 c2 c3 NF 0 if c c1 C2 C3 low After the last event troubleshooting stops because the system is believed to be repaired i e using 3 23 b6 NF NF NE NF Y I nenenenr Y G5 2 b c 1 tEOc 3 6 Planner The second component of the troubleshooting framework is the Planner Its purpose is to recommend actions to the user so that the expected cost of repair becomes minimal This may be done by finding an optimal troubleshoot ing plan as given by 3 8 However it is not necessary to explicitly know the entire plan It is sufficient to know that the next action is part of an optimal plan The Planner explores a portion of the space of all possible plans that is large enough to give an estimate of the optimal expected cost of repair The first action in this plan is the deci
25. i e a new time slice is gener ated whenever a new event has occurred This differs from other DBN s where the amount of time that elapses between each time slice is static An event can either be an observation a repair or an operation of the system If the system is a vehicle the operation of the system is to start the engine and drive for a certain duration of time After each event a transition occurs and a new time slice is generated We use the notation X x to describe the event that the variable X is observed to have the value x at time t 1 and X x to describe a repair event that causes X to have the value x at time t 1 For the event that the system is operated for a duration of T time units between the time slices t and t 1 we use the notation w 7 Note that the duration Tis a different time measure than the one used for the time slices which is an index Persistent and Non Persistent Variables The variables in the nsDBN for troubleshooting are separated into two classes persistent and non persistent The value of a persistent variable in one time slice is dependent on its value in the previous time slice and may only change value due to an intervention such as a repair or the operation of the system A com ponent s state is typically modeled as a persistent variable e g if it is broken at one time point it will remain so at the next unless it is repaired A non persistent variable is not directly dependent o
26. probability C14 0 999 0 001 Y probability C15 0 9995 0 0005 Y probability C16 C15 0 0 999 0 001 1 0 2 0 8 Y probability C17 0 999 0 001 Y probability C18 0 997 0 003 Y probability C19 0 9955 0 003 0 0015 Y probability C20 0 999 0 001 Y probability 001 C01 C02 CO3 C10 function nor 0 0 0 0 1 0 AO 0 5 0 235705 hs 0 1 0 0 0 1 0 9 0 0 1 00 0 1 0 0 0 1 0 1 y probability 002 C04 4 0 1 0 1 0 01 0 99 probability 003 019 020 4 function nor 0 0 1 0 1 0 0 1 0 1 0 1 probability 004 C04 4 type NI 0 1 0 1 0 01 0 99 probability 005 C05 C06 C10 4 function nor 0 0 0 1 0 1 0 0 0 001 0 999 2 0 00 0 2 0 8 156 0 1 0 0 001 0 999 0 2 0 0 2 0 8 0 0 1 0 001 0 999 probability 006 0 0 99 0 01 1 0 01 0 99 probability 007 0 1 0 1 0 1 probability 008 type I NI function nor 0 0 O 1 0 0 0 0 0 0 0 0 OOooot tn OoOonNroo o oo vo OorOoooooo o m LY probability 009 type NI I function nor 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 O probability 010 type NI NI function nor 0
27. the improvement is consistent For all problems in the problem sets the selection of actions using planning yielded an ECR equal to or less than for the greedy selection strategies Also a reduction of the ECR saves money and reducing the ECR with only a few percent can lead to a great increase in marginal profit for both the workshop and the vehicle owner Comparison with Other Planning Algorithms In Section 5 4 4 we saw that wIBLAO produced troubleshooting plans with better quality than when the other state of the art algorithms were used It could be the case that some of these algorithms make better decisions than wIBLAO even though the error bound of the plan is worse In this section we will evaluate this by comparing all algorithms when 1 and 10 seconds of planning time is allowed The results are shown in Table 5 11 and weighted Iterative Bounding LAO 130 Chapter 5 Case Study Hydraulic Braking System still has the best average performance for all problem sets Different Upper Bound Heuristic Function When a constant upper bound heuristic Mconst s 10000 for all non goal states s is used instead of the hfyeg heuristic the performance degrades for the intermediate hard and very hard problems 1346 9 1565 6 and 1932 7 for heonst versus 1342 7 1561 3 and 1854 1 for Nfixed after 1 second of planning time This upper bound grossly overestimates the optimal expected cost and therefore the algorithm needs to explore every
28. 2 6 AND OR graphs for the SSPP 1so 53 41 42 p c S0 83 joined with a small arc A solution graph for a search graph G is a subgraph Gr Nz En where Na CN and Ex CE satisfying the following constraint First the initial state sy is part of Gz Second only states that are leaves in G can be leaves in Gz Third for any non leaf s in Gz there is exactly one outgoing hyperedge cor responding to a chosen action a to be performed in that state and all possible successor states succ a s of that action belong to Gz Figure shows an example of a solution graph for the search graph shown in Figure Given a solution graph Gr we can directly generate a policy 72 where for all non goal states s Gz V Sg the chosen action 7r s is defined by the single outgoing hyperedge from s Such a policy is complete in the sense that 38 Chapter 2 Preliminaries it specifies an action for every non goal state that is reachable by following the policy within G Now we will show how we incrementally can build a solution graph by gradually expanding a subgraph G of G From this solution graph we can ex tract a complete policy without necessarily explore all of G Let G N be an arbitrary subgraph of G containing the initial state s Further let Gh 4 N4 be a solution graph for G where each non leaf s G has an outgoing edge labeled with an action n s arg ud Taf s 2 8 ae If all leaves in G are goa
29. 2000 Benneth Christiansson Att komponentbasera informationssystem Vad s ger teori och praktik 2000 Ola Pettersson Deliberation in a Mobile Robot 2000 Dan Lawesson Towards Behavioral Model Fault Isolation for Object Oriented Control Systems 2000 Johan Moe Execution Tracing of Large Distributed Systems 2001 Yuxiao Zhao XML based Frameworks for Internet Commerce and an Implementation of B2B e procurement 2001 Annika Flycht Eriksson Domain Knowledge Management in Information providing Dialogue systems 2001 Per Arne Segerkvist Webbaserade imagin ra organisationers samverkansformer Informationssystemarkitektur och akt rssamverkan som f ruts ttningar f r aff rsprocesser 2001 Stefan Svar n Styrning av investeringar i divisionaliserade f retag Ett koncernperspektiv 2001 Lin Han Secure and Scalable E Service Software Delivery 2001 Emma Hansson Optionsprogram f r anst llda en studie av svenska b rsf retag 2001 Susanne Odar IT som st d f r strategiska beslut en studie av datorimplementerade modeller av verksamhet som st d f r beslut om anskaffning av JAS 1982 2002 Stefan Holgersson IT system och filtrering av verksamhetskunskap kvalitetsproblem vid analyser och be slutsfattande som bygger p uppgifter h mtade fr n polisens IT system 2001 Per Oscarsson Informationss kerhet i verksamheter begrepp och modeller som st d f r f rst else av infor mationss kerhet och dess hantering 2001
30. 3 43 we can compute the value for the fixed strategy heuristic to be 199 7 3 6 Planner 81 3 6 4 Assembly Model There are many reasons why we may choose to perform a specific action It can be to repair a component that is suspected to be faulty or to make an observation to learn more of which components may be faulty but it can also be to affect the feature variables such that the goal state is reached or to satisfy the preconditions of another action that we want to perform If we only needed to consider which repair or observation we wish to make solving the planning problem can become easier When Assumptions 4 6 hold this is exactly what we can do Assumptions are plausible for a system where the feature variables correspond to parts of the system that may be obstructing each other such that they must be removed ina specific order Figure 3 7 a illustrates this with a set of building blocks standing on top of each other Formally these assumptions can be described like following Each feature variable F F has the value space A D i e they can either be assembled A or disassembled D When a certain feature is assembled cer tain other features must also directly or indirectly be assembled Likewise when a certain feature is disassembled certain other features must also di rectly or indirectly be disassembled Nothing else is relevant to whether a feature can be assembled or disassembled This is equivalent to order
31. 44 Data Driven Methods In data driven methods the model is learned from training data instead of deriving it from explicit knowledge of the system s behavior When large amounts of previously classified fault cases in similar systems are available the data driven methods can learn a function that maps observations to diagnoses Such methods include Support Vector Machines Neural Networks and Case Based Reasoning see e g 69 43 91 and respectively Discrete Event Systems For Discrete Event Systems DES the system to be diagnosed is modeled as a set of states that the system can be in together with the possible transitions the system can make between states Some transitions may occur due to faults 1 3 Solution Methods 9 An observation on a DES gives the information that a certain transition has oc curred However not all transitions give rise to an observation The diagnosis task is to estimate which states the system has been in by monitoring the se quence of observations and to determine if any transitions have occurred that are due to faults Approaches used for DES include Petri Nets and state automata 55 92 Probabilistic Approaches Probabilistic methods for diagnosis estimate the probability of a certain di agnosis being true The model can be a pure probabilistic model such as a Bayesian Network BN that describes probabilistic dependencies between components and observations that can be made 39 Thi
32. ARC16 name Replace radial gasket retarder preconditions F13 1 effects do C16 0 cost 260 action ARC17 name Replace gasket retarder side preconditions F11 1 effects do C17 0 cost 120 Y action ARC18 name Replace radial gasket gearbox preconditions F13 1 effects do C18 0 cost 265 Y action ARC19 name Replace cables ECU preconditions Fil 1 effects do C19 0 cost 200 Y action ARC20 name Replace ECU preconditions F02 1 effects do C20 0 cost 2200 Appendix C The Retarder Model File action A0CO2 name Inspect temp sensor coolant preconditions F06 1 effects observe C02 cost 40 action A0C03 name Inspect temp sensor oil preconditions F06 1 effects observe C03 cost 25 Y action A0C04 4 name Inspect gasket gearbox side preconditions F11 1 effects observe C04 cost 45 Y action A0CO7 name Inspect pres sensor oil preconditions F06 1 effects observe C07 cost 22 Y action A0C12 name Inspect bearing preconditions F12 1 effects observe C12 cost 34 Y action A0C13 name Inspect pump preconditions F12 1 effects observe C13 cost 25 Y action A0C14 name Inspect iron goods preconditions F12 1 effects observe C14 cost 75 Y action A0C16 name Inspect radial gasket retarder preconditions F13 1 effects observe C16 cost 16 Y
33. Anna Pernest l Mattias Nyberg and H kan Warnquist Modeling and inference for troubleshooting with interventions applied to a heavy truck auxiliary brake Submitted to Engineering Applications of Artificial Intelli gence 2010 59 Joelle Pineau Geoffrey Gordon and Sebastian Thrun Point based value iteration An anytime algorithm for POMDPs In Proceedings of the 16th International Joint Conference on Artificial Intelligence IJCAI 03 2003 60 Martin L Puterman Markov Decision Processes Discrete Stochastic Dy namic Programming John Wiley amp Sons Inc 2005 61 Raymond Reiter A Theory of Diagnosis from First Principles Artificial Intelligence 32 1 57 95 1987 62 Jussi Rintanen Complexity of planning with partial observability In Proceedings of the 14th International Conference on Automated Planning QCAPS 04 2004 63 Giorgio Rizzoni Simona Onori and Matteo Rubagotti Diagnosis and Prognosis of Automotive Systems Motivations History and Some Re sults In Proceedings of the 7th IFAC Symposium on Fault Detection Supervi sion and Safety of Technical Processes SAFEPROCESS 09 2009 64 Joshua W Robinson and Alexander J Hartemink Non stationary dy namic Bayesian networks In Proceedings of the 22nd Annual Conference on Neural Information Processing Systems NIPS 08 pages 1369 1376 2008 65 Indranil Roychoudhury Gautam Biswas and Xenofon Koutsoukos A Bayesian approach to efficient diag
34. Artificial Intelligence AAAT 90 1990 74 Tomi Silander and Petri Myllym ki A Simple Approach for Finding the Globally Optimal Bayesian Network Structure In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence UAT 96 2006 d al Trey Smith and Reid G Simmons Heuristic Search Value Iteration for POMDPs In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence UAT 04 2004 76 Trey Smith and Reid G Simmons Focused Real Time Dynamic Program ming for MDPs Squeezing More Out of a Heuristic In Proceedings of the 21st National Conference on Artificial Intelligence AAAI 06 2006 7 Marcel Staroswiecki and G Comtet Varga Analytical redundancy rela tions for fault detection and isolation in algebraic dynamic systems Au tomatica 37 5 687 699 2001 140 Bibliography 78 K J str m Optimal control of markov processes with incomplete state information Journal of Mathematical Analysis and Applications 10 1 174 205 1965 79 Ying Sun and Daniel S Weld A framework for model based repair In Proceedings of 11th National Conference on Artificial Intelligence AAAI 93 1993 80 Sebastian Thrun Wolfram Burgard and Dieter Fox Probabilistic Robotics MIT Press 2001 81 Vandi Verma Geoff Gordon Reid Simmons and Sebastian Thrun Parti cle Filters for Rover Fault Diagnosis IEEE Robotics amp Automation Maga
35. Assumption I states that all faulty components must be repaired in order to successfully solve the troubleshooting problem However in some situations it can be preferred to accept a certain risk of some component still being faulty over doing many more actions to make sure that the system really is fault free This can be modeled by extending the troubleshooting model with a set of loss functions lj Qc R where l c is the penalty on the cost of repair that is added if it is discovered that the component C is in mode c after the troubleshooting session is ended A special stop action with the precondition that the feature variables should be in the mode f takes us directly to an 86 Chapter 3 Troubleshooting Framework abstract goal state The cost of this action Cstoy will depend on the belief state of the system state s in which ppp is Cstop S ey b c 3 46 cc Oc where l c J V l t LUu ci 1 Cn and n C The loss function can be modeled to reflect things such as bad will perfor mance loss or the risk of damaging the system further For example the loss function may be high for a fault such as low engine oil since this may cause the engine to seize up but for a fault such as broken position light with less severe consequences the loss function may be lower Typically c is much larger than the cost of repairing C Relaxing this assumption does not prevent us from solving the trou bleshooting p
36. Designers 2004 Ioan Chisalita Safety Oriented Communication in Mobile Networks for Vehicles 2004 Thomas Gustafsson Maintaining Data Consistency in Embedded Databases for Vehicular Systems 2004 Vaida Jakonien A Study in Integrating Multiple Biological Data Sources 2005 Abdil Rashid Mohamed High Level Techniques for Built In Self Test Resources Optimization 2005 Adrian Pop Contributions to Meta Modeling Tools and Methods 2005 Fidel Vasc s Palacios On the information exchange between physicians and social insurance officers in the sick leave process an Activity Theoretical perspective 2005 Jenny Lagsten Verksamhetsutvecklande utv rdering i informationssystemprojekt 2005 Emma Larsdotter Nilsson Modeling Simulation and Visualization of Metabolic Pathways Using Modelica 2005 Christina Keller Virtual Learning Environments in higher education A study of students acceptance of edu cational technology 2005 C cile berg Integration of organizational workflows and the Semantic Web 2005 Anders Forsman Standardisering som grund f r informationssamverkan och IT tj nster En fallstudie baserad p trafikinformationstj nsten RDS TMC 2005 Yu Hsing Huang A systemic traffic accident model 2005 Jan Olausson Att modellera uppdrag grunder f r f rst else av processinriktade informationssystem i transaktionsintensiva verksamheter 2005 Petter Ahlstr m Affarsstrategier f r seniorbostadsmarknaden 2005
37. Diagnostic Engine and are assigned probabilities from a prior probability distribution as previ ously described in Section 1 3 1 The utility function is defined by the entropy of the probability distribution over the possible diagnoses In information sci ence the entropy of a random variable is a measure of its uncertainty 30 Here it is used to describe the remaining uncertainty regarding which is the true diagnosis among the set of possible diagnoses Using only a fast one step lookahead search this method is remarkably efficient in finding action sequences that find the true diagnosis at a low expected cost Sun and Weld 79 extend this method to also consider the cost of repairing the remaining possible faults in addition to the entropy In Heckerman et al and Langseth and Jensen 42 troubleshooting of printer systems is considered A BN is used to model the system the output from the diagnosis is a probability distribution over possible diagnoses and the goal is to repair the system By reducing the set of available actions and making some rather restricting assumptions regarding the system s behavior the optimal expected cost of repair can efficiently be computed analytically Even though these assumptions are not realistic for the printer system that they troubleshoot the value for the optimal ECR when the assumptions hold is used as a utility function for a look ahead search using the unreduced set of actions Planning Based
38. ECE p elit y P e elt T Mp Cale CR 7 e t na e ECE et Cafe P e etat Mp P ele e a Mp CR 7 amp t qui e EE elt ecE Cq eli P e e 7r el Mp ECR rr e e 3 6 e CE lt zt elt el Example By using repeatedly and inserting the values for the action costs from Example 3 2 the expected cost of repair for the troubleshooting plan 7tex in FigureB 3 can be computed to be approximately 178 1 ECR 7tex Od ind C NF Cay ECR 7tex Ol ind C NF Fj rem Cay ca Y Pel O3 ind C3 NF F rem Mp 4 FLEECE ECR tex Ol ind C NE F rem e 178 1 Optimal Troubleshooting Plans The optimal expected cost of repair ECR for a troubleshooting problem I M ee is ECR el min ECR z e m eTl 1 min Cas eit ED P le v e Mp ECR 7 e e m ETN I ECE 1 1 min Cap Pele 2 e Mp ECR e 8 37 a en I eE E et where TT 1 is the set of all troubleshooting plans that are solutions to I An optimal troubleshooting plan 7r is a solution to I and ECR z e ECR el The actions of 71 are 7 e argminc e11 P ele a Mp ECR e e 3 8 ac A t ECE elt 56 Chapter 3 Troubleshooting Framework where the set n C A consists of all actions that have their preconditions satisfied given elt 3 4 Assumptions This section contains a list of assumptions that can be made
39. ECU a29 Inspect temp sensor coolant 471 Inspect temp sensor oil az Inspect gasket gearbox side 423 Inspect pressure sensor oil 424 Inspect bearing 425 Inspect pump a26 Inspect iron goods 457 Inspect radial gasket retarder azg Inspect gasket retarder side 429 Inspect radial gasket gearbox 439 Check for oil on cooler az Check for leakage magn valves 437 Check for leakage prop valve 433 Check for leakage control valve 435 Check oil quality 436 Check oil level retarder 437 Check oil level gearbox a3g Check ECU cables retarder side 439 Check ECU cables ECU side 449 Check retarder performance a4 Drive in vehicle 842 Drive out vehicle 443 Tilt cab 444 Close cab 445 Fit frame support 446 Remove frame support 447 Remove noise shield 248 Fit noise shield 449 Drain retarder oil aso Fill retarder oil as Drain coolant as2 Fill coolant 453 Drain gearbox oil 454 Fill gearbox oil 455 Remove proportional valve 456 Fit proportional valve 457 Remove propeller shaft asg Fit propeller shaft 459 Remove oil cooler agg Fit propeller shaft fg Remove retarder a62 Fit retarder 163 Disassemble retarder housing ag4 Assemble retarder housing 465 Remove retarder axle a66 Fit retarder axle 4g7 Test drive 5 4 Evaluation 115 Retarder unit Retarder housing a Retarder axle Figure 5 4 The assembly graph for the retarder All details and parameters for the retarder model can
40. Mathias C ster Beyond IT and Productivity How Digitization Transformed the Graphic Industry 2005 sa Horzella Beyond IT and Productivity Effects of Digitized Information Flows in Grocery Distribution 2005 Maria Kollberg Beyond IT and Productivity Effects of Digitized Information Flows in the Logging Industry 2005 David Dinka Role and Identity Experience of technology in professional settings 2005 No 1191 No 1192 No 1194 No 1204 No 1206 No 1207 No 1209 No 1225 No 1228 No 1229 No 1231 No 1233 No 1244 No 1248 No 1263 FiF a 90 No 1272 No 1277 No 1283 FiF a 91 No 1286 No 1293 No 1302 No 1303 No 1305 No 1306 No 1307 No 1309 No 1312 No 1313 No 1317 No 1320 No 1323 No 1329 No 1331 No 1332 No 1333 No 1337 No 1339 No 1351 No 1353 No 1356 No 1359 No 1361 No 1363 No 1371 No 1373 No 1381 No 1386 No 1387 No 1392 No 1393 No 1401 No 1410 No 1421 No 1427 No 1450 No 1459 No 1466 Andreas Hansson Increasing the Storage Capacity of Recursive Auto associative Memory by Segmenting Data 2005 Nicklas Bergfeldt Towards Detached Communication for Robot Cooperation 2005 Dennis Maciuszek Towards Dependable Virtual Companions for Later Life 2005 Beatrice Alenljung Decision making in the Requirements Engineering Process A Human centered Approach 2005 Anders Larsson System on Chip Test Scheduling and Test Infrastructure Design 2005 John Wilander Policy and Implementat
41. NE leakage NF failure leakage NF NF NF failure NF failure NF failure NF 5 0 1074 1331 NF leakage failure NF 0 181 4 b c Cfixed failure leakage failure NF 0 2431 0 181 0 124 231 0 181 0 181 0 500 181 NE NF NF NF INF NF NF low 0 249 30 2 failure NF NF low 2 5 10 11302 NE leakage NF low 1 2 10 4 11302 failure leakage NF low 8 0 1077 2230 2 INF NE failure low 0 0010 1130 2 ailure NF failure low 1 0 1075 2230 2 NF leakage failure low 5 0 1074 2230 2 failure leakage failure low 5 0 1077 3330 2 3 7 3 General Feature Variables By relaxing Assumptions 446 one could consider features that impose more general preconditions Then the composite actions can no longer be used lt is possible however to create composite actions by solving the preconditions using an efficient algorithm for classical planning This is for example done in 79 In this case however we cannot guarantee optimality as with Theo rem 92 Chapter 3 Troubleshooting Framework 3 7 4 Different Probabilistic Models It is also possible to consider other types of probabilistic models for the Diag noser As long as it is possible to have some efficient state representation and compute the same planner can be used in the troubleshooting frame work If also the probabilit
42. Proceedings of the 20th International Workshop on Principles of Diagnosis DX 09 2009 42 Helge Langseth and Finn V Jensen Decision theoretic troubleshooting of coherent systems Reliability Engineering amp System Safety 80 1 49 62 2002 Bibliography 137 43 Mario Lenz Eric Auriol and Michel Manago Diagnosis and decision support In Case Based Reasoning Technology From Foundations to Applica tions pages 51 90 London UK 1998 Springer Verlag 44 J Armengol Llobet A Bregon T Escobet E R Gelso M Krysander M Nyberg X Olive B Pulido and L Trave Massuyes Minimal Struc turally Overdetermined Sets for Residual Generation A Comparison of Alternative Approaches In Proceedings of IFAC Safeprocess 09 Barcelona Spain 2009 45 MAN Group Service contracts Retrieved from http www man mn com en Services MAN Service MAN Service jsp August 2010 46 H Brendan Mcmahan Maxim Likhachev and Geoffrey J Gordon Bounded real time dynamic programming RTDP with monotone upper bounds and performance guarantees In Proceedings of the 22nd Interna tional Conference on Machine Learning ICML 05 2005 47 Swee M Mok Kenlip Ong and Chi haur Wu Automatic generation of assembly instructions using step In Proceedings of the IEEE International Conference on Robotics and Automation 2001 48 Kevin Murphy Dynamic Bayesian Networks Representation Inference and Learning PhD thesis UC Berkeley
43. Such actions are said to be not applicable in those states Definition 3 8 Applicable Actions An action a is said to be applicable in state s if there exist a state s S such that s 7 s and p s s a gt 0 For any state s the set of applicable actions A C A consist of all actions that are applicable in S In every state s only the actions in A need to be considered DefinitionB 8 also excludes actions that are inappropriate because they will lead to the same system state even though they are physically executable e g repairing a com ponent that is already repaired or making an observation where it is already known what the outcome will be The action costs in the cost function c are taken directly from the trou bleshooting model and are independent of the state 72 Chapter 3 Troubleshooting Framework Goal States The set of absorbing goal states of the SSPP is S lbu 1 f Fy Y ble 1 c C where b is computed from bw and r using 3 23 and Fy C Op and C Oc specify the permitted combinations of modes for feature and component vari ables when troubleshooting is complete We will assume that F is a singleton f where f is such that all feature variables are in the mode assembled and following Assumption 1 C cg where c is such that all component vari ables are in a non faulty mode 3 6 2 Solving the SSPP From the Planner s point of view allit has to do is to
44. Visualization of Dynamic Multibody Simulation With Special Reference to Contacts 2003 Jens Gustavsson Towards Unanticipated Runtime Software Evolution 2003 Calin Curescu Adaptive QoS aware Resource Allocation for Wireless Networks 2003 Anna Andersson Management Information Systems in Process oriented Healthcare Organisations 2003 Bj rn Johansson Feedforward Control in Dynamic Situations 2003 Traian Pop Scheduling and Optimisation of Heterogeneous Time Event Triggered Distributed Embedded Systems 2003 Britt Marie Johansson Kundkommunikation p distans en studie om kommunikationsmediets betydelse i affarstransaktioner 2003 Aleksandra Tesanovic Towards Aspectual Component Based Real Time System Development 2003 Arja Vainio Larsson Designing for Use in a Future Context Five Case Studies in Retrospect 2003 Peter Nilsson Svenska bankers redovisningsval vid reservering f r befarade kreditf rluster En studie vid inf randet av nya redovisningsregler 2003 Fredrik Ericsson Information Technology for Learning and Acquiring of Work Knowledge 2003 Marcus Comstedt Towards Fine Grained Binary Composition through Link Time Weaving 2003 sa Hedenskog Increasing the Automation of Radio Network Control 2003 Claudiu Duma Security and Efficiency Tradeoffs in Multicast Group Key Management 2003 Emma Eliason Effektanalys av IT systems handlingsutrymme 2003 Carl Cederberg Experiments in Indirect Fault Injection
45. as b c P c e Bus ERE P c c o ett Bus P e e Bus tEOc Pl iue 3 23 ccOc Corollary 3 1 Probability of an event Let e be an event that is generated by the effect el Given that b and r 7 are known then if e is an observation event X 2x Pele e Bus y s Prey ee 3 24 cEOc otherwise Melee Bus 1 3 25 Proof First we will consider the case where e is an observation event X x Identify that P ef e t1 e Bus P X euet Bns e y P C w c elt71 B e P X x C c e171 B el4 cc Oc 3 26 3 5 Diagnoser 65 where as before Bj e is the BN obtained by applying the events e on the nsDBN Byns Note that since e is not an operation event the time tw refers to the same time as t 1 By applying Definition 3 6 on the result of 3 26 we get Pele Bus y BP xo ee Bus e 3 27 ccOc Identify that P X 2x Cf c ee B us e 4 2 PIC e C c etl p ste y ecOc P X x c e Cie c elt 1 By e 3 28 Since e is not a repair event then r r and 3 22 can be applied such that P C C c e B s e is P C 1 e C e c elt 1 Bn s e y z if y t c 3 29 0 otherwise By using 3 29 on 3 28 we get that P X x C o c et Bj eF P XF x Cf y r c CI c et Bas elt 3 30 By applying Theorem 3 1 on the result of and inserting this into 3 27 we get the final resu
46. do F12 1 cost 160 action AAF12 name Assemble ret housing preconditions F12 1 F13 0 effects do F12 0 cost 332 action ADF13 name Remove retarder axle preconditions F13 0 F12 1 effects do F13 1 cost 55 action AAF13 name Fit retarder axle preconditions F13 1 effects do F13 0 cost 23 F10 1 165 166 Notes Notes 167 168 Notes Notes 169 GS Uny S ET Avdelning institution m 5 U Division department 3 A E Institutionen f r datavetenskap f 5 nos us Department of Computer 2011 06 09 LINK PINGS UNIVERSITET and Information Science Spr k Rapporttyp ISBN Language Report category 978 91 7393 151 9 Svenska Swedish X Licentiatavhandling A x ISRN LiU Tek Lic 2011 29 X Engelska English Examensarbete C uppsats Lj FRESAS Serietitel och serienummer ISSN L D uppsats Title of series numbering 0280 7971 vrig rapport Link ping Studies in Science and Technology URL f r elektronisk version Thesis No 1490 http urn kb se resolve urn urn nbn se liu d iva 67522 Titel Title Computer Assisted Troubleshooti
47. error threshold is decreased after the inner loop of Iterative Bounding LAO has completed the value of the weight is updated as w VE 1 In the next iteration the explicit search graph G N cannot be reused directly because only holds for the previous value of w In each state s we store the value w s which is the value of w used by the algorithm the previous time s was visited Let SY s A w s w where w is the current weight Any state s S will be considered unexpanded However the information in G is kept Therefore if a state s O G that is to be expanded has already been expanded before the old values of f s and f s are reused and the new value of the weighted evaluation function f s is computed as follows fols max gt fu fi 8 w 4 2 Evaluation of Iterative Bounding LAO 101 4 2 Evaluation of Iterative Bounding LAO The new algorithm is evaluated against three other state of the art algorithms for SSPP s that also use two sided bounds FRTDP BRTDP and VPI RTDP It is also compared with ILAO 31 which is a more efficient version of LAO that only performs the Value Iteration step when a complete solution is found Also in this evaluation ILAO is altered so that it just as the other algorithms maintains an upper bound function that can be used to extract a policy anytime if needed All algorithms have been carefully implemented in Java according to the autho
48. fault free This is the termination condition When the termination condition holds the troubleshooting session is ended The troubleshooter must generate a se quence of recommendations that eventually results in a situation where the termination condition holds If the troubleshooter is correct when the termina tion condition holds i e the system really is fault free the troubleshooter will be successful in solving the troubleshooting task When the system to troubleshoot is a truck the user would be a mechanic 6 Chapter 1 Background The observations can consist of information regarding the type of the truck op erational statistics such as mileage a problem description from the customer or feedback from the mechanic regarding what actions have been performed and what has been seen The output from the troubleshooter could consist of requests for additional information or recommendations to perform certain workshop tests or to replace a certain component 1 2 1 Performance Measures Any sequence of actions that solves the troubleshooting task does not neces sarily have sufficient quality to be considered good troubleshooting Therefore we will need some performance measures for troubleshooting For example one could make sure that the system is fault free by replacing every single component While this would certainly solve the problem doing so would be very time consuming and expensive One interesting performance measure is t
49. find a partial policy 7 for an SSPP and be able to return the first action of that policy 77 so anytime The initial state s is given and the functions p succ and testing for membership in Sy are implemented by the Diagnoser Therefore the Planner can be imple mented by any algorithm for solving SSPP s that can return an approximate solution anytime A policy zt for the SSPP for a troubleshooting problem I M e f 7 C that has finite cost corresponds to a troubleshooting plan 7 that is a solution to I For every sequence of events e leading from the initial state to a system state s 7t el e zr s Theorem 3 2 Let I M elt 0 Fs Cg be a troubleshooting problem where Assumptions 7H9 hold and let S A p c So Sg be an SSPP corresponding to the troubleshooting problem I Further let 71 be an optimal policy for the SSPP and let 7 be the corresponding troubleshooting plan Then 71 is an optimal troubleshooting plan i e Vr sp ECR 7m et ECR el Proof For every sequence of events e leading from the initial state to a system state s 7t s is the same action as zr el e Therefore c 7 s s in 2 7 corresponds to C e1 t e in 3 7 For every sequence of events e E nj ei t e that can be generated by the action 71 el e we can generate another system state s using the rules in Corollary 3 2 9 37 and 3 38 Using Corollary 3 1 and we know that p s s zt s in corresponds
50. for the trou bleshooting problem The assumptions can be exploited for a faster and more efficient solution For many of these assumptions we will also show how the troubleshooting problem can be solved when the assumptions do not apply in Section 3 4 1 Assumptions for the Problem Assumption 1 Repair Goal All faulty components must be repaired Assumption Iis reasonable because it states that the troubleshooting task is the same as stated in the problem formulation in Section 1 2 3 4 2 Assumptions for the Action Model Assumption 2 Repairable Components For each component C C there exists at least one action that generates the event C NF If Assumption l is made but not Assumption 2 then the repair goal may not be achievable because some components cannot be repaired Assumption 3 Perfect repair An action that attempts to repair a component will succeed in doing so with probability 1 Assumption 3 is valid for systems where the typical repair action is to replace a faulty component with a brand new one This assumption is not applicable for systems where the components are sensitive and there is a risk that they are damaged upon replacement or where repairs are difficult and attempted repairs may fail Assumption 4 Satisfiable preconditions All actions have preconditions that are such that for every possible mode the feature variables can be in there exist some sequence of actions that satisfies those precon
51. heuristics that give both an optimistic and a pessimistic estimate of the expected cost The new heuristics Mcomp and Axe are such heuristics for the troubleshooting problem By grouping actions together into composite actions as described in Section B 6 4 the set of possible actions can be reduced The orem B 5 shows that any optimal solution found using composite actions will have the same expected cost as the optimal solutions for the general problem without composite actions 4 Planning Algorithm In Section 3 6 1 we showed that the troubleshooting problem can be formulated as an SSPP where successor states and transition functions are computed by the Diagnoser This means that the troubleshooting problem can be solved by general algorithms for SSPP s Many efficient algorithms for solving SSPP s use search heuristics that give both pessimistic and optimistic estimates for of the optimal expected solu tion cost and as described in Section 3 6 3 we can formulate such heuristics for the troubleshooting problem In the literature there exist three such al gorithms that are all extensions of the Real Time Dynamic Programming algo rithm RTDP 2 described in Section 2 3 4 These are Bounded RTDP BRTDP 46 Focussed RTDP FRTDP 76 and Value of Perfect Information RTDP VPI RTDP 67 A lower bound of the optimal value function is used to define the policy in each state and an upper bound of the optimal value function is used to hel
52. in the conditional probability tables 66 In this section we will describe the most basic methods for making inference in BN s Variable Elimination Algorithm Variable Elimination is an algorithm for exact inference in BN s Other algorithms in the same family include Bucket Elimination and Symbolic Probabilistic Inference 73 Let X E O be a BN where the variables X Xo Xn are ordered so that X pa X if j lt i and let Y C X be the set of variables we want to obtain n a joint probability distribution over Further let YT Yn U X be the set of k i i 1 variables in Y that have the position i or greater in X and let X U Xx be k 0 the set of variables in X that have the position i 1 or less in X Then the joint 28 Chapter 2 Preliminaries probability distribution over Y P y P yg x where P yilx nand EY 1 ifi nand X Y P y lx B P yilx PY alx U xj ifi lt n and X Y 2 1 E Pei Pae Uy ifi nand X E Y The Variable Elimination algorithm solves using dynamic programming so that the results of repeated calculations are saved for later use Message Passing If the BN is a tree it is possible to do inference in time linear in the size of the network by using the method of message passing 51 The size of the network again refers to the number of entries in the conditional probability tables A general BN can be converted into a tree but in the worst case this operati
53. is explored one step for all actions except a where it is ex plored two steps To evaluate these look ahead methods against the planning based method presented in this thesis we will study the expected cost of repair for each method i and each problem in the problem set where the expected cost of repair is computed as ECR s c a s s y p s s a ECR s s esucc a s where the decision a7 s is computed for all reachable states s using the method i The value ECR so is the actual expected cost of repair when the decisions are made using method i By varying the time the planner can use to make a decision we can evaluate the advantage of planning The expected cost of repair is computed when weighted IBLAO aborts planning after a fixed time The expected cost ECR is for 1 second of planning time and ECR10 is for 10 seconds of planning time The results are shown in Table 5 10 The greedy selection strategy used in Sun and Weld performs the worst This is because their cost function often underestimates the minimal ECR Underestimating the minimal ECR when actions are selected greedily can cause the selected action to be an action with low cost and little effect on the state and thereby move expensive but inevitable actions beyond the plan ning horizon On the other hand the selection strategy used in Langseth and Jensen performs remarkably well together with the 1 heuristic This is because the value 15 i
54. lost This is modeled as P O low C NF C4 NF 0 and P O low C4 4 NF V C4 NF 1 Assuming that a pump breakdown or a loss of oil immediately causes the pressure to drop these dependencies are modeled as instant The low oil pressure alarm will trigger if either the oil pressure is low or the pressure sensor fails i e P O3 indicating C3 failure V O2 low 1 and P O3 indicating Ca NF O normal 0 These dependencies are also instant Visible leakage is modeled as a non instant dependency where P O yes Co leaking 0 9 and P O4 yes Co NF 0 This means that the leakage is not always visible from the outside and it is required that the vehicle is operated for the leakage to appear 3 3 The Troubleshooting Problem 5 e Pump a e Pressure Sensor ES boi Level N y oy sible Leakage 02 Low Oil ME uos Oil Pressure Alarm Figure 3 2 Initial non stationary Dynamic Bayesian Network of the sample system Persistent variables are shaded and non instant edges are dashed 3 3 The Troubleshooting Problem Definition 3 2 Troubleshooting problem A troubleshooting problem is repre sented by the tuple M el igs 3 2 where M is the troubleshooting model e are all events that have happened up to the current time t f are the feature modes the system initially is in and Fo C Op and Cg C Oc are the modes all feature and component variables should be in when troubleshooting is complete
55. minimizing the expected cost of repair is not considered and as with other data driven methods these methods require large amounts of training data 14 Troubleshooting Framework For the troubleshooting task we want to minimize the expected cost of repair This requires that we can determine the probabilities of action outcomes and the probability distribution over possible diagnoses This information can only be provided by the probabilistic methods for diagnoses We will use a 1 4 Troubleshooting Framework 13 method for probability based diagnosis using non stationary Dynamic Bayesian Networks 56 This method is well suited for troubleshooting since it allows us to keep track of the probability distribution over possible diagnoses when both observations and repairs can occur In Section 1 32 we mentioned that when we know the probability distri bution over possible diagnoses we can solve the decision problem using look ahead search or planning based methods The main advantage of the methods that use look ahead search is that they are computationally efficient However when troubleshooting systems such as trucks actions can take a long time for the user to execute With planning based methods this time can be used more effectively for deliberation so that a better decision can be made We will use a planning algorithm for MDP s to solve the decision problem This is because we emphasize minimizing the expected cost of repair and that
56. of the explicit search graph G A7 7 consists only of the leaf state sy The set D G consists of all non goal leaves in the current solution graph of G that are reachable from sp Initially D G7 so unless the initial state happens to be a goal state The loop in lines 141411 will ensure that eventually in G the set D G7 0 i e that there is eventually an action to perform for every non goal state Until this is the case one or more states s in D G are expanded 2 3 Markov Decision Processes 39 lines Bl Then for all actions a A the successor states succ s a and the corresponding hyperedges s succ a s are added to C Algorithm 3 LAO 1 procedure LAO SSPP S A p c So Sg h 2 G N E so 0 f s0 h so while G 0 do Sexpand 0 for some s D G do Sexpand Sexpand U s EXPAND s end for 10 VALUEITERATION Sexpand U ancestors Sexpand A p 1 0 f 11 end while 12 VALUEITERATION s s Gi A p 1 0 e f 13 if O GL Z then goto linef 14 return 7 15 end procedure 16 procedure EXPAND s 17 for each a Ado 18 for each s succ a s V do 19 f s h s 20 end for 21 N N Usucc a s 22 E E U s succ a s 23 end for 24 end procedure After the expansions is evaluated for all the newly expanded states in Sexpand and their ancestors Sexpand using the Value Iteration algorit
57. policy deeper to make a bet ter decision than when the heuristic Ago is used With only one second of planning there is not enough time for this on the more difficult problems 6 Conclusion This thesis presents a framework for computer assisted troubleshooting that can for example be used to help a mechanic find and repair faults on a dam aged truck The framework consists of two major components The first com ponent is the Planner that tries to find a plan of actions that repairs all faults on the system The Planner uses the second component the Diagnoser which given the knowledge of previously made observations and performed actions can compute a probability distribution over possible diagnoses and the prob ability that the next action will have a certain outcome The decision that is recommended to the user of the computer assisted troubleshooting system is the first action of the plan created by the Planner Emphasis is placed on solv ing the decision problem better than can be done with existing methods so that a good trade off between computation time and solution quality can be made We have shown how a Diagnoser can be made that uses non stationary dynamic Bayesian networks nsDBN s to model the system The framework of nsDBN s for troubleshooting supports many events that are relevant for troubleshooting heavy vehicles observations repairs and the operation of the system In this thesis we show how we can convert the nsDBN
58. problems the upper bound quickly converges to a value within a few percent of optimal while the lower bound converges much slower This means that a high quality decision can be made long before it can be proven to have that quality since Iterative Bounding LAO uses the upper bound to create the policy that is returned while the lower bound is used only to prove how close to optimal that policy is 118 Chapter 5 Case Study Hydraulic Braking System Trivial 0 95 H go dp ooo doo E p 5 10 15 20 25 30 35 40 45 50 Time ms Easy 0 50 100 150 200 250 300 350 400 Time ms Intermediate 1 2 3 4 5 6 7 8 Time s Figure 5 6 Convergence of the average upper and lower bounds using wIBLAO solid line and IBLAO dashed line 5 4 Evaluation 119 Hard 0 9 1 1 1 1 1 L I 1 0 10 20 30 40 50 60 70 80 90 Time s Very hard 1 1 T T T T T T T T T 0 100 200 300 400 500 600 700 800 900 1000 Time s Figure 5 7 Convergence of the average upper and lower bounds using wIBLAO solid line and IBLAO dashed line 120 Chapter 5 Case Study Hydraulic Braking System 5 4 3 Lower Bound Heuristics The lower bound heuristic affects how many states must be expanded to prove that a troubleshooting plan has a certain quality We have compared weighted Iterative Bounding LAO using three different lower bound heuristic func tions Acomb Afo and hent Table 5 3 shows for each
59. resultatavr kning av p g ende arbeten Fallstudier i tre byggf retag 1995 Peter Jonsson Complexity of State Variable Planning under Structural Restrictions 1995 Anders Avdic Arbetsintegrerad systemutveckling med kalkylprogram 1995 Eva L Ragnemalm Towards Student Modelling through Collaborative Dialogue with a Learning Companion 1995 Eva Toller Contributions to Parallel Multiparadigm Languages Combining Object Oriented and Rule Based Programming 1995 Erik Stoy A Petri Net Based Unified Representation for Hardware Software Co Design 1995 Johan Herber Environment Support for Building Structured Mathematical Models 1995 Stefan Svenberg Structure Driven Derivation of Inter Lingual Functor Argument Trees for Multi Lingual Generation 1995 Hee Cheol Kim Prediction and Postdiction under Uncertainty 1995 Dan Fristedt Metoder i anv ndning mot f rb ttring av systemutveckling genom situationell metodkunskap och metodanalys 1995 Malin Bergvall Systemf rvaltning i praktiken en kvalitativ studie avseende centrala begrepp aktiviteter och ansvarsroller 1995 Joachim Karlsson Towards a Strategy for Software Requirements Selection 1995 Jakob Axelsson Schedulability Driven Partitioning of Heterogeneous Real Time Systems 1995 G ran Forslund Toward Cooperative Advice Giving Systems The Expert Systems Experience 1995 J rgen Andersson Bilder av sm f retagares ekonomistyrning 1995 Staffan Flodin Effici
60. s 2 08 All repair 76 Chapter 3 Troubleshooting Framework actions and observing actions may reduce the entropy by at most one and the cheapest action cost is 10 and thereby hen s 17 4 The full observability heuristic gives a higher value h s 100 9 After the repairs the expected remaining entropy is approximately 0 65 and thereby 1 s 107 3 Upper Bound Heuristics Heckerman et al describes a heuristic for troubleshooting using look ahead search We will use this heuristic as a starting point for creating a search heuristic that is an admissible upper bound for the troubleshooting problem Heckerman et al made the following assumptions actions have no precondi tions at most one component can be faulty and on the onset of troubleshooting the probability that some component is faulty is 1 The set of possible actions is restricted to be actions that replace a component actions that observe the value of a component variable and a function control action as specified by Assump tion 11 An upper bound heuristic is created by transforming the problem into a more difficult problem that is easier to solve Therefore it is required that the function control action is performed after each repair action because then it is possible to compute the optimal expected cost of repair analytically A trou bleshooting plan 711 where each component in turn is first observed and then if necessary is replaced is guaranteed to reach
61. the optimal expected reward it is sufficient that the proba bility that each state will be backed up infinitely often is 1 0 during an infinite sequence of backups This means that all states must have a non zero proba bility of being backed up 34 Chapter 2 Preliminaries Algorithm 1 Value Iteration 1 procedure VALUEITERATION MDP y e h 2 foreachs S do f s h s 3 A oo 4 while A gt e 1 y 2y do 5 A 0 6 for each s do 7 8 9 p MaxacA r a s Ys esucc a s p s a s f s A max A f s pl Fs p 10 end for 11 end while 12 foreachs S do 7 s arg max y r a s Ys Esucc a s p s a s f s 13 return 7r 14 end procedure Real Time Dynamic Programming Real Time Dynamic Programming RTDP is an algorithm for finding near optimal policies for SSPP s 2 For SSPP s convergence can be achieved without backing up all states The value function will converge toward the optimal expected cost for all states reachable from the initial state under the optimal policy if the following condi tions holds 2 e the value function is initialized to some value strictly lower than the optimal expected cost and e any state that is reachable from the initial state using the policy that is greedy on the current value function is backed up with a non zero probability Consider an SSPP S A p c 50 4 For any action a A let T be an operator on functions f S R such t
62. the partial plans of the 15 heuristic become less efficient since any repair or operation of the system may insert new faults Therefore we propose another upper bound heuristic based on a fixed troubleshooting strategy that does not rely on function controls Let f be the values that the feature variables should be in when each partial plan begins and ends let p be the probability that the repair of component C fails and let p be the probability that C is faulty i e pi Y bo Ci c Oc Ci 4 NF cec Further let gue be the cost of the composite action that observes C given the previous state let pe be the cost of the composite action that repairs C given the previous state and let c be the cost of a composite action that sets the feature variables to the values fg The last composite action is created from a dummy action that has the precondition that F fo but it has no cost and no effects Without loss of generality assume that each component may either be in the mode non faulty NF or faulty F An observable component C can be repaired using any of the five following partial plans P1 P5 P1 Observe the component and if the component is faulty repair it Repeat this until the component is observed to be non faulty If C is the first component observed then the expected cost of the partial plan P1 is e d pie ANA df P2 Observe the component and if the component is faulty repair it and then ac
63. to P e el z ef Mp in and we can identify that and are the same for all sequences of events el e and their corresponding system states 3 6 Planner 73 3 6 3 Search Heuristics for the SSPP for Troubleshooting Many algorithms for solving SSPP s gain from using search heuristics A heuristic is a function h S R that estimates the expected cost of reaching a goal state from any given state in the state space Algorithms such as LAO and RTDP require that the heuristic is an admissible lower bound in order to guaran tee convergence toward an optimal policy i e they require h s lt Vz s for alls S An admissible lower bound can be used by the algorithms to prove that certain parts of the search space cannot be part of an optimal policy and can thereby safely be ignored Algorithms such as FRTDP 76 BRTDP 46 and VPI RTDP are helped by also having a heuristic that can give an upper bound of the optimal expected cost Le h s gt Vz s for alls S Such a heuristic said to be an admissible upper bound Apart from that the heuristics are admissible it is also important that they can be efficiently computed Typically we want the heuristic to be computable in polynomial time In this section will present some polynomial time search heuristics that are useful for solving the troubleshooting problem when it is formulated as an SSPP Lower Bound Heuristics A common way to create lower bound heuristics is t
64. to an Auxiliary Truck Brak ing System In Proceedings of the 7th IEAC Symposium on Fault Detection Supervision and Safety of Technical Processes SAFEPROCESS 09 2009 Bibliography 141 90 Jason D Williams Applying POMDPs to dialog systems in the trou bleshooting domain In Proceedings of the Workshop on Bridging the Gap NAACL HLT 07 2007 91 Bo Suk Yang Tian Han and Yong Su Kim Integration of ARI Kohonen neural network and case based reasoning for intelligent fault diagnosis Expert Systems with Applications 26 3 387 395 2004 92 Wonham W M Zad S H Kwong R H Fault Diagnosis in Discrete Event Systems Framework and model reduction IEEE Transactions On Automatic Control 48 7 1199 1212 2003 142 Bibliography Q om m m u M mM 203 A Notation An indicator function The decrease factor in Iterative Bounding LAO The discount factor for an MDP policy or a function for determining the statuses of the component variables after a set of repair events The relative error or An effect that occurred at time f Upper bound of the relative error The current error threshold in Iterative Bounding LAO A sequence of effects that occurred between time 1 and t A normalizing function for probability distributions A parameter of a Bayesian network A set parameters of a Bayesian network A troubleshooting plan or an MDP policy A lower bound policy A upper bound policy An optima
65. transitions that may occur nominal transition transition after operation and transition after repair When an observation event has oc curred the nsDBN makes a nominal transition Then all variables X X from time slice t are copied into a new time slice t 1 and relabeled X For each instant edge X Xj where Xt is non persistent an instant edge X xi is added Let tw be the time of the most recent operation event or 0 if no such event has occurred For each non instant edge X Xj where x is non persistent an edge X Xi l is added For each persistent variable X an edge Xt X is added In Pernest l the nominal transition is referred to as the transition after an empty event Transitions After Operation When the system is operated between times t and t 1 a transition after operation occurs During such a transition persistent variables may change values All variables X and edges X X from time slice 0 are copied into the new time slice t 1 and labeled X and X 1 xit respectively Also for each persistent variable X an edge Xt X is added The conditional probability distributions of the persistent variables are updated to model the effect of operating the system Such a distribution can for example model the probability that a component breaks down during operation Then this distribution will be dependent on the components state before the operation event occurs The distri
66. w m 1 With the new repair goal Assumption 11 function control can also be relaxed If we tolerate a certain risks of components being faulty when the troubleshooting ends it becomes less important to have a test that can verify that the system is guaranteed to be free of faults 3 7 2 Adapting the Heuristics After relaxing these assumptions we can still find an optimal troubleshooting plan using the troubleshooting framework Some of the search heuristics de scribed in Section are however no longer valid in their current form 88 Chapter 3 Troubleshooting Framework Lower Bound Heuristics The 1 heuristic is still an admissible lower bound and does not need to be adapted because it is a general heuristic that can be used for any SSPP The heuristic hent however is no longer admissible Taking the penalty b c l c instead of finding the faults in c and repairing them is equivalent with setting b c 0 Therefore the entropy will be reduced by b c log b c The cost of reducing the entropy by one in this way is c 1log b c which is a value that can be arbitrarily smaller than min c 4 cH a which makes the heuristic non admissible The following new admissible entropy based heuristic fent is proposed to be used instead of hent hent s He log c min 5 minen a 3 51 The imperfect repairs interfere with the hfo heuristic If we assume full observability we can repeat a repair action until th
67. we instead remove any blockage in the fuel pump at time 1 we have the knowledge that the pump is OK but the probability that the battery is dead at time 2 is now 0 633 not 1 0 because the pump could still have been blocked at Hus 0 The action of removing the blockage is an intervention on the variable X us that removes the dependency between Xj pump and Xl ump By allowing these P types of interventions B 2 becomes an nsDBN For Example a DBN is not really needed since the variables cannot change values over time unless we allow interventions or we want to model that components may break down between time slices 2 2 3 Non Stationary Dynamic Bayesian Networks for Troubleshooting In Pernestal a framework for representing non stationary dynamic Bayesian networks in the context of troubleshooting is developed In this framework interventions relevant for troubleshooting are treated The nsDBN for troubleshooting is causal and describes the probabilistic dependencies be tween components and observations in a physical system The same compact representation of the structure with an initial BN and a transition BN that 24 Chapter 2 Preliminaries is applicable for stationary DBN s is not possible for general non stationary DBN s However the nsDBN for troubleshooting can be represented by an initial BN B and a set of rules describing how to generate the consecutive time slices Events The nsDBN for troubleshooting is event driven
68. 0 1 0 1 0 1 03 2 0 0 1 0 1 1 0 0 2 0 9 0 1 005 005 C02 CO5 C06 C08 C09 4 NI m Oooooooon o a C01 C03 C05 CO6 COB NI NI NI NI NI 0 1 0 0 0 01 0 99 0 0 1 0 0 05 0 95 0 0 95 0 05 0 0 05 0 95 0 0 95 0 05 0 0 2 0 8 1 0 2 0 8 C05 C06 probability 011 C05 C06 4 type NI NI function nor 0 0 1 0 1 0 1 01 2 0 0 9 0 1 0 1 1 0 0 2 0 1 Y probability 012 C05 C06 COT C08 CO9 type NI NI function nor 0 0 0 0 0 UI 1 0 NI 1 0 0 0 0 0 05 0 95 NI Appendix C The Retarder Model File C09 4 157 2 0 0 0 0 0 95 0 05 0 1 0 0 0 0 05 0 95 0 2 0 0 0 0 95 0 05 0 0 1 0 00 0 1 0 0 0 1 0 0 2 0 8 0 0 0 0 1 0 2 0 8 probability 013 C06 C10 4 type NI NI function nor 0 0 1 0 1 0 1 0 2 0 0 9 0 1 0 1 0 1 probability 014 CO8 CO9 4 function nor 0 0 1 0 1 20 04 1 0 1 0 9 0 1 probability 015 C08 CO9 4 function nor 0 0 1 0 1 0 0 9 0 1 0 1 0 1 probability 016 C11 C13 C20 4 function nor 0 0 0 0 99 0 01 1 0 0 0 01 0 99 0 1 0 0 01 0 99 0 0 10 0 1 0 9 probability 017 C10 C11 C13 function nor 0 0 0 1 1 0 0 0
69. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 O 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 O 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 O 0 0 0 0 0 O O 0 O O 1 0 O O 0 O 0 O 0 O 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 O O 0 O O O O 1 O 0 O O O 0 O 0 0 0 0 0 0 0 0 0 0 0 0 O 1 0 O 0 0 0 O 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 O 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 O O 0 O 0 O 0 O O 0 O O 1 0 O 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 O O 0 O O O 0 O O 0 O O O O 1 0 0 0 0 0 O O 0 O O O 0 O O O O O O 0 2 0 0 0 0 0 0 0 0 O 0 0 0 0 O 0 0 0 O 0 O 1 Actions 159 action AFC name Test drive preconditions F01 0 effects operate 900 observe FC cost 125 action ARCO1 name Replace oil filter preconditions F05 1
70. 009 Tommy Ellqvist Supporting Scientific Collaboration through Workflows and Provenance 2009 Fabian Segelstr m Visualisations in Service Design 2010 Min Bao System Level Techniques for Temperature Aware Energy Optimization 2010 Mohammad Saifullah Exploring Biologically Inspired Interactive Networks for Object Recognition 2011 No 1468 Qiang Liu Dealing with Missing Mappings and Structure in a Network of Ontologies 2011 No 1469 Ruxandra Pop Mapping Concurrent Applications to Multiprocessor Systems with Multithreaded Processors and Network on Chip Based Interconnections 2011 No 1476 Per Magnus Olsson Positioning Algorithms for Surveillance Using Unmanned Aerial Vehicles 2011 No 1481 Anna Vapen Contributions to Web Authentication for Untrusted Computers 2011 No 1485 Loove Broms Sustainable Interactions Studies in the Design of Energy Awareness Artefacts 2011 FiF a 101 Johan Blomkvist Conceptualising Prototypes in Service Design 2011 No 1490 H kan Warnquist Computer Assisted Troubleshooting for Efficient Off board Diagnosis 2011
71. 0913 5 3908583 4 120 30 100 0 Hard 0 0010 109820 2 13864854 9 541 70 100 0 Very hard 0 0286 226209 9 223418243 1620 42 9 1 Table 5 8 Average results for troubleshooting when a loss function is used and when they are not Loss Problem class Error Expan Upper Comp functions bound sions bound time s No Trivial 0 0003 18 0 1098 2 0 01 Easy 0 0009 166 6 1147 2 0 20 Intermed 0 0009 1371 5 1342 9 4 04 Hard 0 0009 8211 1 1559 3 33 08 Very hard 0 0116 47849 9 1848 3 337 42 Yes Trivial 0 0002 9 8 1058 6 0 01 Easy 0 0008 96 9 1094 3 0 13 Intermediate 0 0009 755 8 1302 5 2 17 Hard 0 0009 3667 0 1522 7 15 62 Very hard 0 0108 19156 3 1806 1 161 10 126 Chapter 5 Case Study Hydraulic Braking System Table 5 9 Average results for troubleshooting when repair actions may fail and function control is not available Failing Function Problem Error Expan Upper Comp repairs control class bound sions bound time s No Yes Trivial 0 0002 8 7 1058 6 0 01 Easy 0 0008 99 2 1094 2 0 17 Intermed 0 0009 771 4 1302 5 2 73 Hard 0 0010 3396 2 1522 7 19 18 Very hard 0 0128 22854 1 1810 5 279 73 No No Trivial 0 0002 8 8 1058 6 0 01 Easy 0 0007 104 3 1097 5 0 16 Intermed 0 0009 942 1 1311 2 3 17 Hard 0 0010 4367 0 1527 8 22 58 Very hard 0 0127 24477 1 1813 2 286 16 Yes Yes Trivial 0 0003 21 8 1071 6 0 03 Easy 0 0009 164 8 1105 6 0 44
72. 211 1 343506 1 33 08 Very hard 0 0116 47849 9 3037271 9 337 42 The comparison in Section is done on a 2 67 GHz Intel Core2 Quad Q6600 CPU where the Java Virtual machine was allowed a maximum heap size of 5 GB 5 4 2 Weighted IBLAO vs IBLAO In this section we study how IBLAO behaves when a weight function is used compared to when it is not The upper and lower bounds are recorded over time for Iterative Bounding LAO using the weight function w 1 wIBLAO and Iterative Bounding LAO using no weights w 0 IBLAO The algorithms are halted when either the relative error bound becomes smaller than 0 001 or they run out of memory Figures shows five plots of how the average upper and lower bounds converge over time for each problem class On the value axis the bounds at each time point are normalized with the converged value of the upper bound This value is our best estimate of the optimal ECR so the value axis shows the bounds relative difference from the optimal ECR The bounds for wIBLAO are shown with solid lines and for IBLAO they are shown with dashed lines The upper bound value for wIBLAO converges significantly faster while for IBLAO the convergence of the lower bound is slightly faster Compared to IBLAO when the weight is high wIBLAO commits more to suboptimal solutions and will explore these further before the weight is reduced and other potentially optimal solutions are explored Note that for the harder
73. 32553 192490 4 77 0 001 9 59 41058 272936 6 36 4 2 2 Rovers Domain In the Rovers domain the surface of the planet Mars is explored with a small planetary rover an autonomous ground vehicle The rover can move around between different locations on the planet and collect soil and rock samples to be analyzed It can also take photos of an objective if that objective is visible from the rover s location If a base station is visible from the rover s location it can communicate the results of the rock and soil analysis as well as any images it has taken back to earth However the rover does not always know which locations are visible from each other and where interesting rock and soil samples may be Therefore the rover may need to perform sensory actions to detect this In Bryce and Kambhampati 11 six different problems from this domain are specified with increasing difficulty In all problems except rover1 the rover does initially not know the exact locations of interesting samples and which locations are visible from each other In the problems the goals are one or more of the following have communicated data of a soil sample have communi cated data of a rock sample or have communicated data of an image taken of objective o using camera mode m Compared to the racetrack domain the number of possible actions to per form is much greater in the rovers domain The number of fluents actions 4 2 Evaluatio
74. 416 0 016 IBLAO 0 001 230 0 30 156 0 016 ILAO 0 001 230 0 59 497 0 016 BRTDP 0 000 230 0 64 168 0 016 FRTDP 0 000 230 0 57 208 0 016 VPI RTDP 0 000 230 0 64 168 0 016 rover3 Va expansions backups time wIBLAO 0 000 2117 68 959 0 016 IBLAO 0 001 211 7 59 341 0 016 ILAO 0 000 211 7 146 1572 0 031 BRTDP 0 0010 211 7 183 500 0 031 FRTDP 0 001 211 7 173 608 0 031 VPI RTDP 0 001 2117 190 522 0 031 rover4 Va expansions backups time wIBLAO 0 001 2613 277 5380 0 078 IBLAO 0 000 261 3 273 2055 0 047 ILAO 0 000 261 3 697 10360 0 13 BRTDP 0 000 261 3 1199 3752 0 19 FRTDP 0 000 261 3 1105 3836 0 19 VPI RTDP 0 000 2613 1156 3638 0 19 4 2 Evaluation of Iterative Bounding LAO 107 Table 4 4 Comparison of algorithms on the problem rover5 from the rovers domain rover5 Va expansions backups time wIBLAO 0 1 609 4 13785 358106 7 0 0 0 597 5 48744 2514690 29 6 0 001 597 5 57387 3271515 364 IBLAO 01 6213 37362 549328 18 0 0 01 599 4 61086 976507 29 9 0 001 597 5 66628 1079763 32 8 ILAO 0 1 6094 40175 502817 172 0 01 597 5 166227 3142255 71 2 0 001 5975 195892 4489816 83 1 BRIDP 0 1 6138 92274 295412 353 0 01 597 5 288137 1070994 109 0 0 001 597 5 344766 1324538 121 3 FRTDP 0 1 615 9 90410 317096 363 0 01 597 55 286655 1158646 1211 0 001 5975 338432 1411122 135 4 VPI RTDP 01 617 5 96444 317162 38 5 0 01 597 5 286928 1080442 119 4 0 001 597 5 340103 1322150 135 2
75. 7 4 0 we select a subset Sexpanq of G7 that is expanded as described in Section 4 1 3 When a state is expanded all successors to that state are inserted in G and the lower and upper bounds for the successor states are calculated After the expansions on line 6 all ancestors of the newly expanded states ancestors Sexpana are backed up line 13 During backups the bounds f and fy and the lower and upper bound policies 7 and 7 are updated In stead of performing value iteration until convergence as in LAO only a single 4 1 Iterative Bounding LAO 95 backup is performed over the set of all ancestors of the newly expanded states ancestors Sexpand Since we already have bounds on the optimal expected cost the convergence is not necessary to have a provable bound Much of the total convergence can be obtained with only one backup per state if states far from the initial state are backed up first If G7 is empty at EIS the states in G7 are backed up until either the estimated error of the initial state so lt or Gr changes so that unsolved nodes appear among the leaves States are never backed up twice in the same iteration and again states far from the ini tial state are backed up first The policy that is returned is the upper bound policy 7t where Vr so 1 so Vz 4 1 1 Evaluation functions IBLAO maintains lower and upper bounds of the optimal expected cost for each state s in the explicit graph G
76. 98 Marie Therese Christiansson Inter organisatorisk verksamhetsutveckling metoder som st d vid utveckling av partnerskap och informationssystem 1998 Christina Wennestam Information om immateriella resurser Investeringar i forskning och utveckling samt i personal inom skogsindustrin 1998 Joakim Gustafsson Extending Temporal Action Logic for Ramification and Concurrency 1998 Henrik Andr J nsson Indexing time series data using text indexing methods 1999 Erik Larsson High Level Testability Analysis and Enhancement Techniques 1998 Carl Johan Westin Informationsf rs rjning en fr ga om ansvar aktiviteter och uppdrag i fem stora svenska organisationers operativa informationsf rs rjning 1998 se Jansson Milj h nsyn en del i f retags styrning 1998 Thomas Padron McCarthy Performance Polymorphic Declarative Queries 1998 Anders B ckstr m Vardeskapande kreditgivning Kreditriskhantering ur ett agentteoretiskt perspektiv 1998 Ulf Seigerroth Integration av f r ndringsmetoder en modell f r v lgrundad metodintegration 1999 Fredrik berg Object Oriented Frameworks A New Strategy for Case Tool Development 1998 Jonas Mellin Predictable Event Monitoring 1998 Joakim Eriksson Specifying and Managing Rules in an Active Real Time Database System 1998 Bengt E W Andersson Samverkande informationssystem mellan akt rer i offentliga taganden En teori om akt rsarenor i samverkan om utbyte av infor
77. B are Uxtex X U pa X for some arbitrary t gt 0 and the edges are all edges between variables in X and all edges from variables in pa X to X X Often in the literature DBN s are assumed to be first order stationary DBN s see e g 481 66 A DBN where the probabilistic dependencies change between time slices is said to be non stationary 64 Non stationary dynamic Bayesian networks nsDBN s are more general than stationary DBN s and can handle changes to the network that arise with interventions such as repair actions in trou bleshooting lOften such as in the work by Pearl the notation Do X 1 x is used to describe inter vention events but it is the author s opinion that X x is more compact and appropriate since the concept of intervention on a variable is similar to the assignment of a variable in programming 2 2 Bayesian Networks 23 0 Figure 2 3 The first three time slices of Bezgin Example 2 4 Example 2 4 Dynamic Bayesian Network The BN B jz1jcan be made into a DBN B jgz1 where the states of the battery and the pump do i change over time by letting the variables X and Xt mp depend on XI and X battery pump bariery pump that P xf 4 T P xt Xpump lung 1 The first three time slices of an are shown in Figure 2 3 If the engine is observed to not start at time 0 and we then observe that the pump is OK at time 1 we can infer that the battery must be dead at time 2 If
78. Based Object Oriented Languages and Environments 2007 Mikhail Chalabine Invasive Interactive Parallelization 2007 Susanna Nilsson A Holistic Approach to Usability Evaluations of Mixed Reality Systems 2008 Shanai Ardi A Model and Implementation of a Security Plug in for the Software Life Cycle 2008 Erik Kuiper Mobility and Routing in a Delay tolerant Network of Unmanned Aerial Vehicles 2008 Jana Rambusch Situated Play 2008 Martin Karresand Completing the Picture Fragments and Back Again 2008 Per Nyblom Dynamic Abstraction for Interleaved Task Planning and Execution 2008 Fredrik Lantz Terrain Object Recognition and Context Fusion for Decision Support 2008 Martin stlund Assistance Plus 3D mediated Advice giving on Pharmaceutical Products 2008 H kan Lundvall Automatic Parallelization using Pipelining for Equation Based Simulation Languages 2008 Mirko Thorstensson Using Observers for Model Based Data Collection in Distributed Tactical Operations 2008 Bahlol Rahimi Implementation of Health Information Systems 2008 Maria Holmqvist Word Alignment by Re using Parallel Phrases 2008 Mattias Eriksson Integrated Software Pipelining 2009 Annika hgren Towards an Ontology Development Methodology for Small and Medium sized Enterprises 2009 Rickard Holsmark Deadlock Free Routing in Mesh Networks on Chip with Regions 2009 Sara Stymne Compound Processing for Phrase Based Statistical Machine Translation 2
79. Decision Theoretic Troubleshooting Communications of the ACM 38 3 49 57 1995 34 Max Henrion Some Practical Issues in Constructing Belief Networks In Proceedings of the 3rd Conference on Uncertainty in Artificial Intelligence UAI 87 1987 35 Inseok Hwang Sungwan Kim Youdan Kim and C E Seah A Survey of Fault Detection Isolation and Reconfiguration Methods Control Systems Technology IEEE Transactions on 18 3 636 653 2010 Q O a Rolf Isermann Model based fault detection and diagnosis status and ap plications In Proceedings of the 16th IFAC Symposium on Automatic Control in Aerospace ACA 04 2004 37 ISO 10303 1 1994 Industrial automation systems and integration Product data representation and exchange Part 1 Overview and fundamental princi ples ISO Geneva Switzerland 1994 38 L B Jack and A K Nandi Fault detection using support vector machines and artificial neural networks augmented by genetic algorithms Mechan ical Systems and Signal Processing 16 2 3 373 390 2002 39 Finn V Jensen Bayesian Networks Springer Verlag New York 2001 40 Finn V Jensen and Thomas D Nielsen Bayesian Networks and Decision Graphs Springer Verlag New York 2007 41 Tolga Kurtoglu Sriram Narasimhan Scott Poll David Garcia Lukas Kuhn Johan de Kleer Arjan van Gemund and Alexander Feldman First International Diagnosis Competition DXC 09 In
80. Link ping Studies in Science and Technology Thesis No 1490 Computer Assisted Troubleshooting for Efficient Off board Diagnosis H kan Warnquist GS UN E T KA IN Xn Nes gii 0 Liy o lt T o 18 gt d 29 S Org O Link pings universitet INSTITUTE OF TECHNOLOGY Department of Computer and Information Science Link pings universitet SE 581 83 Link ping Sweden Link ping 2011 Copyright H kan Warnquist 2011 ISBN 978 91 7393 151 9 ISSN 0280 7971 Printed by LiU Tryck 2011 URL http urn kb se resolve urn urn nbn se liu diva 67522 Computer Assisted Troubleshooting for Efficient Off board Diagnosis by H kan Warnquist June 2011 ISBN 978 91 7393 151 9 Link ping Studies in Science and Technology Thesis No 1490 ISSN 0280 7971 LiU Tek Lic 2011 29 ABSTRACT This licentiate thesis considers computer assisted troubleshooting of complex products such as heavy trucks The troubleshooting task is to find and repair all faulty components in a malfunc tioning system This is done by performing actions to gather more information regarding which faults there can be or to repair components that are suspected to be faulty The expected cost of the performed actions should be as low as possible The work described in this thesis contributes to solving the troubleshooting task in such a way that a good trade off between computation time and solution quality can be made A framework for troubles
81. Methods The troubleshooting problem can be formulated as a Markov Decision Process MDP or a Partially Observable MDP POMDP 4 An MDP describes how stochastic transitions between states occur under the influence of actions A natural way of modeling our problem is using states consisting of the diagnosis and the observations made so far Since we know the observations made but do not know the diagnosis such states are only partially observable and can be handled using a POMDP We can also use states consisting of a probability distribution over possible diagnoses together with the observations made so far Such states are more complex but are fully observable and allow the troubleshooting problem to be modeled as an MDP A solution to an MDP or a POMDP is a function that maps states to actions called a policy A policy describes a plan of actions that maximizes the ex pected reward or minimizes the expected cost This is a well studied area and 12 Chapter 1 Background there are many algorithms for solving PO MDP s optimally However in the general case solving PO MDP s optimally is intractable for most non trivial problems Anytime algorithms such as Learning Depth First Search or Real Time Dynamic Programming for MDPs and for POMDPs Point Based Value It eration or Heuristic Search Value Iteration 75 provide a trade off between computational efficiency and solution quality These algorithms only explore parts of the state space
82. T all non instant edges are restored i e B B After an observation event no change is made to the BN In it is proven that holds if the structure of Bys belongs to a certain family of structures F and the events in e are such that there is at least one operation event between two repair events However the second condition is too prohibitive for the purposes of this thesis since we may want to repair multiple components if we are uncertain of which component is faulty Therefore a different static representation of the nsDBNs for troubleshooting is proposed in this thesis A More Efficient Representation Let tw denote the time for the last operation event A query in an nsDBN that is conditioned on all persistent variables in the current time slice t and those in time slice tw d separate all variables in time slices t and tw from the variables in all other time slices t where t lt t and Z ty If a copy of the persistent variables in time slice tw are kept in every time slice of the nsDBN the nsDBN will only be dependent on the current time slice This is used to define the static representation of an nsDBN 3 5 Diagnoser 61 Definition 3 5 Static Representation of an nsDBN Let Bus Xp Xnp E Eni e es be an nsDBN where X Xp Xp and Xnp Xp Xnpm The static representation of B is a BN B X E O where e the variables X X U Xp U Xy where Xp X51 Xpn represents the varia
83. The SMMART Project In Proceedings of the 9th European conference on Advances in Case Based Reasoning ECCBR 08 2008 2 Andrew G Barto Steven J Bradtke and Satinder P Singh Learning to act using real time dynamic programming Artificial Intelligence 72 1 2 81 138 1995 3 R Bellman A Markovian Decision Process Journal of Mathematics and Mechanics 6 5 679 684 1957 4 E Benazera and E Chanthery The Challenge of Solving POMDPs for Control Monitoring and Repair of Complex Systems In Proceedings of the 19th International Workshop on Principles of Diagnosis DX 08 2008 5 Emmanuel Benazera and Sriram Narasimhan An Extension to the Kalman filter for an Improved Detection of Unknown Behavior In Pro ceedings of the American Control Conference ACC 05 2005 6 Dimitri P Bertsekas and John N Tsitsiklis An analysis of stochastic short est path problems Mathematics in Operation Research 16 580 595 1991 7 Mogens Blanke Michel Kinnaert Jan Lunze Marcel Staroswiecki and 133 134 Bibliography J Schr der Diagnosis and Fault Tolerant Control Springer Verlag New York 2006 00 Blai Bonet Learning Depth First Search A Unified Approach to Heuristic Search in Deterministic and Non Deterministic Settings and its applica tion to MDPs In Proceedings of the 16th International Conference on Auto mated Planning ICAPS 06 2006 O Blai Bonet and Hector Geffner Labeled RTDP
84. USA July 2002 49 N Navet Y Song F Simonot Lion and C Wilwert Trends in automotive communication systems Proceedings of the IEEE 93 6 1204 1223 2005 50 Nils J Nilsson Principles of Artificial Intelligence Morgan Kaufmann San Francisco 1980 51 Judea Pearl Reverend Bayes on Inference Engines A Distributed Hierar chical Approach In Proceedings of The 2nd National Conference on Artificial Intelligence AAAI 82 1982 52 Judea Pearl Fusion Propagation and Structuring in Belief Networks Artificial Intelligence 29 3 241 288 1986 53 Judea Pearl Probabilistic Reasoning in Intelligent Systems Networks of Plau sible Inference Morgan Kaufmann San Francisco 1988 54 Judea Pearl Causality Cambridge University Press 2000 55 Yannick Pencol and Marie Odile Cordier A formal framework for the decentralised diagnosis of large scale discrete event systems and its ap plication to telecommunication networks Artificial Intelligence 164 1 2 121 170 2005 138 Bibliography 56 Anna Pernest l Probabilistic Fault Diagnosis with Automotive Applications PhD thesis Link ping University Vehicular Systems The Institute of Technology 2009 57 Anna Pernest l H kan Warnquist and Mattias Nyberg Modeling and Troubleshooting with Interventions Applied to an Auxiliary Truck Brak ing System In Proceedings of 2nd IEAC workshop on Dependable Control of Discrete Systems DCDS 09 2009 58
85. Unless stated otherwise time is assumed discrete and increases by 1 for each discrete event that occurs When an action a A that has n effects is performed at time t an event sequence El efu is generated For a repair effect repair C the generated event is Cf NF which means that the variable C is forced into the mode NF at time t independently of the 3 2 The Troubleshooting Model 49 mode of C at time t 1 An effect that changes the mode of a feature variable F f is treated similarly and the event F f is generated An operation effect operate T generates an operation event w T For an observe effect obs O one of Oo different events is generated depending on the response from the system The event O o means that the variable O is observed to be in the mode o at time f e g at time t the effect obs O2 generates one of the events O normal and O low The value of the feature variables will not be affected by any other event than those of the type F f After the occurrence of such an event at time t we can trivially infer the values of the feature variables at time t given their value at time t 1 We indicate this by writing e A F F where e F f is the event that results from assigning the value f to the feature F at time f F f fa is a sequence specifying all feature values at the preceding time step t 1 and Ff fir r fia ft fit1 fn is the same sequence wi
86. a goal state It is proven that if the components are observed in descending order by the ratio between their probability of being faulty and the cost of observing them this troubleshooting plan will be optimal for this simplified and restricted case Let pj be the probability that component C is faulty in the system state s let c7 be the cost of replacing C let c be the cost of observing the mode of Cj and let cf be the cost of performing the function control The expected cost of 7r is Va s y y pi gp pile d 3 44 i 1 1 i 1 The inner sum 1 Y pj is the probability that no earlier component Cj j lt i j 1 is faulty Thisis ie probability that C is observed because it is assumed that no more than one component can be faulty at the same time When a component is found to be faulty that component is replaced and troubleshooting is complete If C cannot be observed by any action it is instead repaired immediately and a function control is used to verify whether C was before the repair or not Therefore if C cannot be observed by any action we set c and cf to zero and substitute c with the cost of repairing it plus doing the function control A heuristic h V is an admissible upper bound for the troubleshooting 3 6 Planner 77 Figure 3 5 A troubleshooting plan for repairing an observable component C problem specified in Heckerman et al 33 because a policy with equal or smal
87. action A0007 name Check retarder performance preconditions F01 1 effects observe 007 observe 016 observe 017 operate 90 cost 100 action ADFO1 4 name Drive in vehicle preconditions F01 0 effects do F01 1 operate 30 cost 15 action AAFO1 4 name Drive out vehicle preconditions F01 1 F02 0 FO3 0 FO4 O FO5 0 effects do F01 0 operate 30 cost 15 action ADFO2 name Tilt cab preconditions F02 0 F01 1 effects do F02 1 cost 28 action AAFO2 name Close cab preconditions F02 1 effects do F02 0 cost 30 action ADFO3 4 name Fit frame support preconditions F03 0 FO1 1 effects do F03 1 cost 24 action AAFO3 4 name Remove frame support preconditions F03 1 F06 0 FO7 0 FO8 0 effects do F03 0 cost 3 action ADFO4 name Remove noise shield preconditions F04 0 F01 1 effects do F04 1 observe 022 cost 10 action AAFO4 name Fit noise shield preconditions F04 1 FO7 0 effects do F04 0 cost 5 action ADFO5 4 name Drain retarder oil preconditions F05 0 FO1 1 effects do F05 1 cost 5 163 164 Appendix C The Retarder Model File action AAFO5 4 name Fill retarder oil preconditions FO5 1 F08 0 FO9 0 F10 0 effects do FO5 0 do C15 0 pfail C15 1 0 cost 64 action ADFO6 4 name Drain coolant pre
88. action A0Ci7 name Inspect gasket retarder side preconditions Fil 1 effects observe C17 cost 25 Y action A0C18 name Inspect radial gasket gearbox preconditions F13 1 effects observe C18 cost 75 161 162 action A0004 name Check for oil on cooler preconditions F03 1 F04 1 effects observe 004 cost 16 action A0010 name Check for leakage magn valves preconditions F08 1 effects observe 010 cost 50 action A0011 name Check for leakage prop valve preconditions F03 1 F04 1 effects observe 011 cost 70 action A0013 name Check for leakage control valve preconditions F03 1 F04 1 effects observe 013 cost 80 action A0014 name Check for air leakage preconditions F03 1 F04 1 effects observe 014 observe 015 cost 50 action A0018 name Check oil quality preconditions F05 1 effects observe 018 cost 20 action A0019 name Check oil level retarder preconditions F02 1 effects observe 019 cost 10 action A0020 name Check oil level gearbox preconditions F02 1 effects observe 020 cost 10 action A0023 name Check ECU cables ret side preconditions F03 1 F04 1 effects observe 023 cost 34 action A0024 name Check ECU cables ECU side preconditions F02 1 effects observe 024 cost 34 Appendix C The Retarder Model File
89. al system with a causal BN than with a BN that does not follow the causal relationships The BN in Example 2 1 is causal since having a dead battery and a blocked pump causes the engine not to start However the same joint probability distribution P Xengines Xbattery Xpump can be modeled with other BN s that do not follow the causal relationships Example 2 2 Non causal Equivialent Consider a BN B y73 with same set of stochastic variables as Bj from the previous example but with the edges Xenginer Xpump Xbatterys Xpump and Xenginer Xbatteryl The graph and CPT s for B z1 are shown in Figure 2 2 2 2 Bayesian Networks 21 p ngine 0 316 Xen gine Xpattery OXpump starting OK 0 starting dead 0 5 not starting OK 0 690 not starting dead 0 1 Xeng ine OX pattery starting 0 not starting 0 633 Figure 2 2 The Bayesian network in Example The parameters OXpattery Ox ANd Ox sm describe the conditional probabilities of having Xpattery dead Xpump blocked and Xengine not starting respectively The joint probability distribution represented by B y27 is exactly the same as the one represented by B y21 However the CPT s of B y27 are less intuitive For example the original model specified separate probabilities of the engine failing to start depending on whether the battery was dead and or the pump was blocked In this model these probabilities are baked into a
90. algorithm Iterative Bounding LAO creates troubleshooting plans with a lower expected cost faster than existing state of the art algorithms in the literature The case study shows that the troubleshooting framework can be applied to systems from the heavy vehicles domain Nyckelord Keywords Automated planning diagnosis automotive industry troubleshooting Bayesian networks No 17 No 28 No 29 No 48 No 52 No 60 No 71 No 72 No 73 No 74 No 104 No 108 No 111 No 113 No 118 No 126 No 127 No 139 No 140 No 146 No 150 No 165 No 166 No 174 No 177 No 181 No 184 No 187 No 189 No 196 No 197 No 203 No 212 No 230 No 237 No 250 No 253 No 260 No 283 No 298 No 318 No 319 No 326 No 328 No 333 No 335 No 348 No 352 No 371 No 378 Department of Computer and Information Science Link pings universitet Licentiate Theses Link pings Studies in Science and Technology Faculty of Arts and Sciences Vojin Plavsic Interleaved Processing of Non Numerical Data Stored on a Cyclic Memory Available at FOA Box 1165 S 581 11 Link ping Sweden FOA Report B30062E Arne J nsson Mikael Patel An Interactive Flowcharting Technique for Communicating and Realizing Al gorithms 1984 Johnny Eckerland Retargeting of an Incremental Code Generator 1984 Henrik Nordin On the Use of Typical Cases for Knowledge Based Consultation and Teaching 1985 Zebo Peng Steps Towards the Formalization of Desi
91. ame way as for the comparisons in Section 4 2 As before the algorithms are halted when the algorithm runs out of memory or when a problem is solved i e a solution that is proven to have an error bound lower than 0 001 is found To obtain a higher success rate the algorithms are allowed 5 GB of memory instead of 1600 MB Table D 5 shows for each algorithm and for each problem class how many percent of the problems that were solved and the average of the error bounds when the algorithms were halted Table 5 6 shows for each algorithm and for each problem class the aver age number of expansions the average number of backups and the average computation time in seconds The averages in Table 5 6 are taken only over 5 4 Evaluation 121 Table 5 3 Percentage of the problems that were solved and the average of the error bounds when the algorithm was halted for weighted Iterative Bounding LAO using different lower bound heuristics Heuristic Problem class Solved Error bound lcomb Trivial 100 0 0 0003 Easy 100 0 0 0009 Intermediate 100 0 0 0009 Hard 100 0 0 0009 Very hard 81 8 0 0116 hj Trivial 100 0 0 0003 Easy 100 0 0 0009 Intermediate 100 0 0 0009 Hard 100 0 0 0010 Very hard 81 8 0 0128 hent Trivial 100 0 0 0007 Easy 100 0 0 0010 Intermediate 9 1 0 7431 Hard 0 0 4 5195 Very hard 0 0 9 8214 Table 5 4 The average number of expansions the average number of backups and the average computa
92. and converge towards optimality as more computation time is available If a problem that can be modeled as a POMDP is a shortest path POMDP then it can be more efficiently solved using methods for ordinary MDP s such as RTDP rather than using methods developed for POMDP s TO In a shortest path POMDP we want to find a policy that takes us from an initial state to a goal Case Based Reasoning In Case Based Reasoning CBR decisions are taken based on the observations that have been made and decisions that have been taken previously 43 After successfully troubleshooting the system information regarding the observa tions that were made and the repair action that resolved the problem is stored in a case library The next time we troubleshoot a system the current observa tions are matched with similar cases in the case library 24 If the same repair action resolved the problem for all these cases then this action will be taken Information retrieving actions can be taken to generate additional observation so that we can discriminate between cases for which different repairs solved the problem The case library can for example initially be filled with cases from manual troubleshooting and as more cases are successfully solved the li brary is extended and the performance of the reasoning system improves 21 CBR has been used successfully in several applications for troubleshooting see e g 1121 29 In these applications the problem of
93. antees that the cost of the upper bound policy is always less than or equal to f s for all s No such guarantee exists for the lower bound policy Also since we have bounds on Vx the final value iteration step of LAO is not needed 4 1 2 Error Bound The relative error in a state s is the relative difference between the expected costs of the upper bound policy and the optimal policy in that state _ Vm s V s eim Vals 4 5 A state s is considered solved if e s is smaller than the current error threshold The true relative error is not known since we do not know the exact values for Va s and V s The value of V4 s is bounded by f s and f s and using Theorem 4 1 we know that f s gt Vm s for all states s Therefore we can bound the relative error with an estimate n O Vel ot 7 0 i When all successor states of a state s are considered solved s will also be considered solved after being backed up Theorem 4 2 Let s be a state and let s lt for all s succ s 7 s Then backing up s will ensure that s lt Proof By and 42 we have that fi s 2 Tra s fils 98 Chapter 4 Planning Algorithm and fals lt T4 5 fu s ss Tra s fu s for all states s Since s lt for all s succ s zi s fals 1 e i s and thereby uls lt 1 T4 f s c m s 5 Finally fuis Fi gt T fils
94. any action on the pump or gasket Also to replace the gasket the smaller pipe must be removed To test the system and see if a low pressure alarm is triggered the entire system must be assembled 3 2 The Troubleshooting Model Parts of the system that may fail i e components such as sensors actuators wiring and pipes are modeled with variables called component variables Parts of the system that may affect when an action can be performed such as the protective casings around components that must be removed before certain actions can be performed are modeled with variables called feature variables 3 2 The Troubleshooting Model 47 The same component can be modeled with both a component variable and a feature variable since they model different aspects of the component A com ponent variable models a component s health e g whether the component is faulty or not while a feature variable models a component s position e g whether the component is in place or removed Variables called observation variables are used to model observable quantities such as the readings from sensors and alarms from the ECU s The troubleshooting model for any given system consists of these variables and also the model contains information regarding how the values of the vari ables depend on each other and which actions that can be performed on the system Definition 3 1 Troubleshooting model The troubleshooting model is a tuple M C O F A M
95. ary 5 4 5 Composite Actions In this section we will study how much more difficult the planning problem would be if we did not consider composite actions When composite actions are not used the total search space becomes much larger and we can expect the planner to have difficulties with the harder problems This is confirmed by the result shown in Table 5 7 5 4 6 Relaxing the Assumptions In Section 3 7 it is discussed how some of the assumptions made in Section 4 can be relaxed When Assumption Tis relaxed we can use loss functions but then we must use different lower bound heuristics However the troubleshoot ing problem becomes easier to solve since components that are suspected to be faulty with only a very small probability can safely be disregarded The loss function that we will use assigns a penalty of 10000 for each faulty component that is not repaired Table 5 8 shows the results for the problems when loss functions are used and when they are not where the upper bound of the ex pected cost of repair is also recorded We can see that the problems are solved faster when loss functions are used and that the expected cost of repair is lower When repairs may fail and it is not possible to verify the function of the system the problem becomes more difficult However using the heuristics ha and ifixed described in Section 3 7 many problems can be solved in reasonable time Table 5 9 shows the results for the following cases r
96. assembly graph that describes the other like building blocks dependencies between the feature vari ables to the left Figure 3 7 The dependencies between feature variables can combine a with such a sequence of actions forming a macro action called the composite action of a This composite action will then be applicable in s Assume that the precondition of an action a can be described by conjunc tion of expressions F f Let P a be a set consisting of all these expressions that describe the precondition of a Let the sequence a consist of the effects of the action a Let assemble F be the cheapest action that assembles the feature F and let disassemble F be the cheapest action that disassembles the feature F We are interested in the cheapest actions because from Assumption 6 it fol lows that no action may have effects that change the values of multiple feature variables Given the state of the feature variables f a composite action a of a can be created using Algorithm 4 For every precondition in P a of the type F D and for every ancestor of F that is not disassembled in f a disassembling action must be performed Likewise for every precondition in P a of the type F A and for every suc cessor to F that is not assembled in f an assembling action must be performed Algorithm 4 creates anew composite action a with a cost c a that is the com bined cost of these actions
97. backtracks and backs up all the encountered states again in reverse order The algorithm stops when the time limit Tstop is reached RTDP is guar anteed to converge toward an optimal policy as Tstop oo However when the algorithm stops we cannot tell how close the expected cost of the obtained policy will be to the optimal expected cost RTDP does not need to explore every state in the state space and will there fore work even if the state space is infinite It is sufficient that the number of actions and action outcomes in each state are finite which is the case in a belief MDP Since the trials originate from the initial state so the quality of the policy will tend to improve faster there Therefore RTDP can be used as an anytime algorithm when computation time is limited 2 LAO LAO 31 is an algorithm for finding solutions in cyclic AND OR graphs and it can also be used to find near optimal policies for SSPP s LAO is an extension of AO 50 a search algorithm for acyclic AND OR graphs This algorithm will be the basis for the new algorithm Iterative Bounding LAO that is one of the contributions of this thesis Chapter 4 We will therefore go through this algorithm in detail The search graph for LAO is an AND OR graph which can be repre sented as a directed hypergraph where the nodes are states and the edges correspond to actions We can create such a graph G A for an SSPP S A p c o S4 as follows Let s
98. be seen in the retarder model file shown in Appendix C 5 4 Evaluation 5 4 1 The Problem Set There are 10 initial observations that can be made All of these observations are binary which means that a troubleshooting session may start in one of 1024 initial states However many of these are either highly improbable or impos sible Given that some component is faulty the 56 most likely combinations of initial observations represent 99 of the probability mass These 56 initial 116 Chapter 5 Case Study Hydraulic Braking System Very hard Logd H fada 0 01 0 1 1 10 100 1000 Computation Time s Figure 5 5 The partition of the problems into classes trivial easy intermediate hard and very hard states will be our problem set Plans for each of the 56 problems are found using Iterative Bounding LAO with the following settings the lower bound heuristic hop the upper bound heuristic 15 4 the parameter a 0 9 and the weight function w VA 4 amp Planning is halted when a troubleshooting plan is found that can be proved to have a relative error bound smaller than 0 001 or when it runs out of memory If the error bound is smaller than 0 001 when the algorithm is halted the problem is considered to be solved The relative error bound upper bound number of state expansions number of state backups and total computation time is recorded for each problem The problems were sorted by the time it took to find a
99. bility of reaching b from b n o b a y w o s a Y p sis a b s ses s Esucc a s This function normalizes b ensuring that Y b s 1 Let t Ox B x A B bea function that computes the next belief state using 2 4 Then the total expected discounted reward of a POMDP policy 7 is a function VA B R where y 0 1 is a discount factor and V b Y b s r n b s y Y n o b a Vz v o b a 2 5 ses ocO An optimal POMDP policy 7 has the maximal expected discounted reward VY in every belief state b a b arg max Y b s r n b s y Y n o b a VZ x o b a 2 6 acA ses ocO Belief MDP s It is possible to convert any POMDP into an ordinary MDP 12 This allows us to find policies for the POMDP using algorithms designed for MDP s which is something we will do in this thesis If the current belief state is known and an action is performed the resulting belief state leads to a unique next belief state In other words a belief state can be seen as a fully observable state in an MDP This is called a belief MDP Definition 2 9 Belief MDP Let S A O r p w be a POMDP and B be the belief state space over S The corresponding belief MDP is an MDP 32 Chapter 2 Preliminaries S A r p where the state space S B is the belief state space of the POMDP the set of possible actions A A remains the same r a b Ysesb s r a s is the expected reward of performing a in b and p b b a n
100. bles X at the time of the last operation event e for every ee oe Xpir Xnp j Ej there is a corresponding edge in Xp i Xnp j je e for every non instant v Xpir Xnp j Eni there is a corresponding edge in X Xnp j for every directed path in Bj from a persistent variable Xy to a non persistent variable X passing through at least one other non persistent variable such that the outgoing edge from X is non instant there is an edge Xp Xnp j E for every directed path in Bj from a persistent variable Xy to a non persistent variable X passing through at least one other non persistent variable such that the outgoing edge from X is instant there is an edge Xpi Xnp j E and e the parameters O specify the conditional probabilities P Xnp Xp Xp for each non persistent variable X Xnp of given its parents in X and Xp The parameters do not specify any conditional probabilities for the persistent variable because these will never be used The parameters in O are created as follows Let e be a dummy observation event at time 1 such that Bj e has made a single nominal transition Let Xnp Xnp be a non persistent variable in B and let X C X and X C Xy be its parents in Further let X p and X be the corresponding variables to Xnp and X in time slice 1 of Bns e A and ia x be the corresponding variables to X in time slice 0 of Bns e Then P Xs X Xp B
101. butes to the total cost of repair However if the user is not ready to execute the recommended action because the user is busy executing a previously recommended action or doing something else there is no loss in using this time for additional computations We do not know precisely how long this time can be so therefore it is desirable that the Planner is an anytime planner i e itis able to deliver a decision quickly if needed but if it is given more time it can plan further and make a better 14 Chapter 1 Background i Sysieri User System Troubleshooter information information i I 2 1 System to E ibl di EN ossible diagnoses troubleshoot DIEA ae outcorhe likelihoods 1 I Performed Recommended actions actions Figure 1 2 The troubleshooting framework decision Since the decision may improve over time the best thing to do is not nec essarily to abort the planning as soon as the user begins idling The algorithm that is used for the Planner in this thesis can provide the user with an upper bound on the difference between the ECR using the current plan and the opti mal ECR The larger this bound is the greater the potential is to make a better decision If the user sees that the bound is steadily improving the user may then decide to wait in hope of receiving an improved recommendation that leads to a lower ECR despite the additional computation time 1 5 Contributions
102. bution can also be dependent on the duration of the operation event Transition After Repair When a component variable X is repaired a transition after repair occurs This transition differs from the nominal transition in that the repair is an interven tion on the variable X and therefore X will have all its incoming edges re 26 Chapter 2 Preliminaries time slice 0 time slice 1 time slice 2 time slice 3 gt lt Dn Il 2 an gt lt NN N 8 Q2 ro a Nee Figure 2 4 Transitions in an nsDBN moved The new conditional probability distribution of X will depend on the specific repair event For example it will depend on the success rate of the repair Example 2 5 Figure shows an example of an nsDBN from time slice 0 to 3 Persistent variables are shown as shaded circles non persistent variables are shown as unfilled circles instant edges are shown as filled arrows and non instant edges as dashed arrows The first transition after the observation xl xg is nominal The second transition is after the intervention xj X2 and the third is after operation After the operation the time slice looks the same as in the first time slice If instead of w 1 we would have observed the variable X again this variable would have a value that is dependent on A before the intervention Parameters The parameters required for the nsDBN for troubleshooting describe the de pe
103. cept the risk that the component still may be faulty If C is the first component observed then the expected cost of P2 is cP dh pie pfl cf 90 Chapter 3 Troubleshooting Framework P3 Repair the component and then observe it If the component is still faulty then repeat until the component is observed to be non faulty The expected cost of P3 is P3 e 08 1 pl e cf P4 Repair the component and then accept the risk that the component still may be faulty The expected cost of P4 is d Sd efi c P5 Do nothing and accept the risk that the component is faulty The expected cost of P5 is cP pili F cl For unobservable components only the last two partial plans P4 and P5 are applicable The fixed troubleshooting strategy Agxeg is to first observe observable com ponents one by one using either the partial plan P1 or P2 If an observable com ponent is shown to be faulty we will finish the partial plan for that component and then stop and take the penalty for any remaining faulty components If none of the observable components are faulty the strategy is to go through the remaining components using the partial p P3 P5 The partial plan that is used for each EQ i is arg minjc s 6 c for observable components and arg min cu s I for unobservable components An observable component for which it is pest to use one of the partial plan P3 P5 will be delayed until after all partial plans P1 and P2 have been p
104. computed as state backup and therefore we expect the RTDP based algorithms to be faster in this domain We have used two racetrack maps large b and block80 that have been pub lished in Barto et al 2 and Sanner et al 67 respectively The action dynamics are specified as in Smith and Simmons where in large b actions may fail causing the vehicle to skid and have zero acceleration and in block80 a per turbing gust of wind may accelerate the vehicle in a random direction The probability with which an action fails is 0 1 The lower bound heuristic used is the Amin heuristic where for non goal states s his Imin 5 min cs min Imin 5 and for goal states s h s 0 This is the optimal cost if action outcomes could be chosen freely This heuristic has previously been used for problems from the racetrack domain 9 76 The upper bound heuristic is a constant 1000 for all non goal states This is a gross overestimate of the optimal expected cost This heuristic is in general not uniformly improvable However by introducing a special plan more action with a cost of 1000 that takes the vehicle directly to the goal Theorem 4 1 will be applicable For each algorithm in the experiment values of the upper and lower bounds in the initial state are available at any time When these values have converged so that their relative difference is less than a threshold e the algo rithm is halted and the time in seconds and the total numb
105. conditions F06 0 F03 1 effects do F06 1 cost 5 action AAFOG 4 name Fill coolant preconditions F06 1 FO9 0 effects do F06 0 cost 66 action ADFO7 4 name Drain gearbox oil preconditions F07 0 FO3 1 F04 1 effects do FO7 1 cost 18 action AAFO7 name Fill gearbox oil preconditions FO7 1 F09 0 F10 0 effects do FO7 0 cost 68 action ADFO8 4 name Remove proportional valve preconditions F08 0 F03 1 FO5 effects do F08 1 cost 47 action AAFO8 4 name Fit proportional valve preconditions F08 1 Fil effects do F08 0 cost 45 action ADFO9 name Remove propeller shaft preconditions F09 0 FO5 effects do FO9 1 cost 20 action AAFO9 4 name Fit propeller shaft preconditions F09 1 Fil effects do F09 0 cost 33 action ADF10 name Remove oil cooler preconditions F10 0 FO5 effects do F10 1 cost 94 M m M o M m F06 1 FO7 1 M o 1 F07 1 Y action AAF10 4 name Fit propeller shaft preconditions F10 1 Fil 0 effects do F10 0 cost 86 action ADF11 4 name Remove retarder preconditions F11 0 FO9 1 effects do F11 1 cost 76 action AAF11 name Fit retarder preconditions Fil 1 F12 0 effects do F11 0 cost 54 action ADF12 4 name Disassemble ret housing preconditions F12 0 Fil 1 effects
106. d let 71 be an optimal solution to the SSPP for troubleshooting SSPP S A p c s9 Sg where composite actions are used instead Then Vz s V s Proof In any state s each applicable composite action corresponds to a se quence of applicable ordinary actions Therefore a version of 7 where every composite action is replaced by its constituting actions is a valid solution to SSPP and Vw s gt Vals Let S C S be all states s S that are either in S or such that 7r s is an action that either makes an observation repairs a component or operates the system In any state s S using 7 must lead to a sequence of actions Af s s that only affects feature variables that reaches a state s in S Assume that Af s s always has minimal cost Then 4 s will contain a composite action a that also reaches s A policy z where z s aj for all s S will be 3 7 Relaxing the Assumptions 85 a solution to SSPP such that Vz V The policy 7 is optimal therefore V V and Vy Vz if Al s has minimal cost for all s s S Now assume that V lt V Then it must be so that for some state s s S using 7 leads to a sequence of actions Af s s that does not have minimal cost We shall prove that for each such case we can create an equivalent policy with the same expected cost where all such sequences are optimal and thereby prove that the assumption V lt V never can be true
107. deterministic planning Characteristic for problems from this domain is that their solutions contain few cycles the actions have heterogeneous costs and the branching factor is high 4 2 1 Racetrack The racetrack domain was first presented in Barto et al 2 The task is to drive a vehicle from a starting position to a goal position The states are integer vectors s x y X y describing the vehicle s position and velocity in two di mensions Actions are integer accelerations a X ij where x y 1 0 1 The states are fully observable and uncertainty is introduced when actions are 102 Chapter 4 Planning Algorithm performed If a wall is hit the vehicle is instantly moved back to the starting position and its velocity is set to zero A goal state is reached if the vehicle crosses a goal position The state resulting from performing an action is easily computed by adding the velocity to the position the acceleration to the veloc ity and by making simple check whether a straight line between the current position and the next position is blocked by a wall or a goal position The racetrack domain is a domain where the RTDP based algorithms have been shown to be especially successful The deep RTDP trials in combination with low branching factor allows them to converge toward an optimal solutions with few backups We expect IBLAO to do fewer expansions but more back ups In the racetrack domain state expansions are as easily
108. ditions Also every such sequence is such that no non faulty component is caused to become faulty with certainty If Assumption 4 is not made there could be actions that never could be performed and components that cannot be repaired 3 4 Assumptions 57 Assumption 5 Assembly modes Each feature variable has only two feature modes assembled mode A or disassembled mode D Assumption 5 is applicable for systems where the feature variables rep resent parts of the system that may be physically obstructing other parts of the system so that an action cannot be performed e g a cover or a part that needs to be disassembled to expose the components of which the part is com posed Note that the modes of a feature variable may have different names e g the feature variable Outer Casing in the example has the assembled mode is called fitted and the disassembled mode is called removed Assumption 6 Dependencies between feature variables An action causing F D only has preconditions requiring other features to be disassembled and F to be assembled An action causing F A only has preconditions requir ing other features to be assembled and F to be disassembled Furthermore the dependencies between features are acyclic in the sense that disassembling one feature cannot directly or recursively require the feature to already be disassembled and similarly for assembling a feature Assumption 6 can be made for systems where the feature
109. e C02 name Temp sensor coolant category persistent type discrete 2 Not faulty Faulty Y node C03 name Temp sensor oil category persistent type discrete 2 Not faulty Faulty Y node C04 name Gasket gearbox side category persistent type discrete 2 Not faulty Leaking Y node C05 name Magnet valves category persistent 149 150 Appendix C The Retarder Model File type discrete 3 Not faulty Stuck Leakage node C06 name Proportional valve category persistent type discrete 3 Not faulty Stuck Leakage node C07 name Pres sensor oil category persistent type discrete 2 Not faulty Faulty node C08 name Air tube category persistent type discrete 2 Not faulty Leakage node C09 name Air valves category persistent type discrete 2 Not faulty Leakage node C10 name Control valve category persistent type discrete 2 Not faulty Faulty node C11 name Accumulator category persistent type discrete 2 Not faulty Faulty node C12 name Bearing category persistent type discrete 2 Not faulty Faulty node C13 name Pump category persistent type discrete 2 Not faulty Faulty node C14 name Iron goods category persistent
110. e Sensor Component NF failure C4 Oil Level Component NF low Ol Visible Leakage Observation no yes O2 Low Oil Pressure Observation normal low O3 Low Oil Pressure Alarm Observation not indicating indicating F Outer Casing Feature fitted removed Fy Small Pipe Feature fitted removed 3 2 1 Actions We define actions similarly to ground planning operators with precondition effects and cost For an action a A the precondition Fa C Or defines a set of possible assignments of the feature variables such that if F f and f Fa we are allowed to perform a An action may have zero or more effects that are ordered in a sequence The effects can be e to repair a component repair C e to change the mode of a feature F f e to observe the mode of an observation obs O or a component obs C or e to operate system for a duration of T time units operate T The cost of an action a is real valued constant c4 The action ap is a special stop action that has no effects and zero cost It is used to indicate that the troubleshooting is complete and no more actions should be performed All other actions must have at least one effect Events When an action is performed on the system in the real world an event is gener ated for each effect A sequence of events represents an outcome of the action and it is dependent on how the system responds so we cannot always know in advance which the event will be
111. e component we want to repair is repaired This means that the expected cost of repairing a component is increased by at least a factor 1 p where pf is the probability that the repair fails Therefore during the computations of c c f we will increase the costs of all repair actions by the associated factor It may also be the case that it is better to not repair a component and instead take the penalty for leaving it unrepaired This can be considered in the following way As before let c c f be the minimal cost of repairing the faulty components in c and setting the feature values to some f Fg given the values of the feature variables f The computation of c c f is as following Let c c1 c and let c be the same as c except that C is in the mode NF If c c f c f gt l c itis better to not repair C Let e OTe Pier ife scien ie min li ci f c c ifi C Then the optimal cost of either repairing or taking the penalty for the compo nents in c is amp 1 c f and the new full observability heuristic is hp s Y b c c f 3 52 ccOc A new combined heuristic f1 can be formulated using fient and ha instead 3 7 Relaxing the Assumptions 89 of hent and hg Hcomb s hg s E A l c max 0 uo log b c H c min SS ble min cula 3 53 Upper Bound Heuristics When all these assumptions are relaxed even if a function control action is available
112. e composite actions with observe effects is used instead of the minimum action cost The selected action a3 is then DE acu S arg min T ECRs s ac A s where A s is the set of possible composite actions applicable in s In Langseth and Jensen the ECR is estimated using the heuristic given by from Heckerman et al 33 This heuristic does not apply when actions have preconditions and multiple components can be faulty at the same time Therefore we will use the heuristic 15 instead Let a be the first action in the fixed strategy used to derive Mgyog If c a s Y p s s a min Tahfixea s arg min T h xea s s succ a s ae A s ac A s the selected action a g is a otherwise Aang arg min Tahfixea s i acA s 128 Chapter 5 Case Study Hydraulic Braking System Table 5 10 Average expected cost of repairs for troubleshooting when deci sion time is limited ECR and ECR shows the best known lower and upper bounds of the optimal expected cost of repair Trivial Easy Inter Hard Very mediate hard ECR 1098 0 1146 8 1342 5 1559 0 1846 1 ECR 1097 9 1146 5 1341 7 1557 8 1822 4 ECRsun 1189 4 1296 2 1734 2 2176 2 2949 8 ECRrang 11252 1178 6 1381 9 1626 4 1908 0 ECR 1098 0 1146 8 1342 7 1561 3 1854 1 ECRi0 1098 0 1146 8 1342 5 1559 0 1846 6 where A s is the set of possible composite actions applicable in s This means that search space
113. e ordered in descending order by p c5 the fixed trou bleshooting strategy heuristic will reduce to the heuristic in Heckerman et al for the case when actions have no preconditions and at most one compo nent can be faulty The choice of f may affect the value of the heuristic and it is a good idea to choose some value that fulfills many of the preconditions of the actions that observes an observable component or repairs an unobservable one Since a function control is not needed when the last component has been repaired the cost can further be reduced by setting c to zero for the last component with non zero probability of being faulty which yields a tighter upper bound Example 3 7 Consider the same initial state as in Example 3 6 If we let f fit fit then c s ch s 0 The components C and C4 are observable and the values for p p C d e c p and p p for all components are the following iae Ta He 4 e 1135 25 150 65 0 0 0 125 0 0036 2 185 10 0 0 0 0 0 125 6 7 1074 3 140 0 0 0 0 O 0 501 0 0036 4 110 O 20 140 0 0 0 376 0 038 When the components are ordered descending by the ratios p ae we get T 3 4 2 1 The probabilities ps p p and p are i p J d A 0 251 0 125 0 125 1 3 104 0 125 0 0 0 125 0 0 0 751 0 250 0 500 0 0010 1 0 0 624 0 249 0 127 BON aja Using
114. e x independently of the other parent variables when Y has the value yj where m gt 0 When each parent variable Y has the value y 0 99 is the probability that X x due to some unknown cause other than Y For the modeling of the retarder first all the components that are known to fail were identified and then for each such component domain experts listed all observations that may occur because that component fails Since leaky noisy or distributions are used for the CPT s only one parameter needed to be set for each dependency and each fault mode of the components There are 68 actions available for the retarder and they are listed in Ta blepb 1 The effects and preconditions of all actions are obtained from the work shop manual 71 The cost of each action is set to the sum of the costs of the resources consumed when the action is performed and the standard mechanic wage times the standard time for that action i e the amount of time it takes to perform the action in normal work pace Of these 68 actions 20 have a repair effect 23 have observe effects and 26 have effects that assemble or disassemble parts of the vehicle that are modeled with feature variables The features that were necessary to model were obtained from the work shop manual and the assembly graph for the retarder shown in Figure shows how the 13 features depend on each other The feature variables F4 F Fi3 represent parts of the retarder that can be disassemb
115. effects do C01 0 cost 45 Y action ARCO2 name Replace temp sensor coolant preconditions F06 1 effects do C02 0 cost 145 Y action ARCO3 name Replace temp sensor oil preconditions F06 1 effects do C03 0 cost 150 Y action ARCO4 name Replace gasket gearbox side preconditions Fil 1 effects do C04 0 cost 90 Y action ARCO5 name Replace magnet valves preconditions F12 1 effects do C05 0 cost 310 Y action ARCO6 name Replace proportional valve preconditions F12 1 effects do C06 0 cost 240 Y action ARCO7 name Replace pres sensor oil preconditions F06 1 effects do C07 0 cost 190 Y action ARCO8 name Replace air tube preconditions F03 1 F04 1 effects do C08 0 cost 150 action ARCO9 name Replace air valves preconditions F03 1 F04 1 effects do C09 0 cost 150 160 action ARC10 name Replace control valve preconditions F12 1 effects do C10 0 cost 390 Y action ARC11 4 name Replace accumulator preconditions F12 1 effects do C11 0 cost 790 Y action ARC12 name Replace bearing preconditions F10 1 effects do C12 0 cost 130 Y action ARC13 name Replace pump preconditions F12 1 effects do C13 0 cost 120 Y action ARC14 name Replace iron goods preconditions F12 1 effects do C14 0 cost 2000 Y action
116. el gearbox category nonpersistent type discrete 2 Normal Low node 020 name Qil level retarder category nonpersistent type discrete 2 Normal Low node 022 name Noise shield Appendix C The Retarder Model File Indicating Indicating Indicating Indicating Indicating Indicating Indicating category nonpersistent type discrete 2 Normal 0il stained node 023 name ECU cables ret side category nonpersistent type discrete 2 Normal Visible damage node 024 name ECU cables ECU side category nonpersistent type discrete 2 Normal Visible damage node 025 name DTC ECU connectors category nonpersistent type discrete 2 Not indicating Indicating node 026 name DTC ECU internal category nonpersistent type discrete 2 Not indicating Indicating Feature variables node F01 4 name Vehicle category feature type discrete 2 In workshop Outside workshop node F02 name Cab category feature type discrete 2 Closed Tilted node F03 name Frame support category feature type discrete 2 Removed Fit node F04 name Noise shield category feature type discrete 2 Fit Removed node FO5 4 name Retarder oil category feature type discrete 2 F
117. ember 2010 26 Alexander Feldman Gregory M Provan and Arjan J C van Gemund Approximate Model Based Diagnosis Using Greedy Stochastic Search In Proceedings of the 7th Symposium on Abstraction Reformulation and Approx imation SARA 07 2007 27 Gerhard Friedrich and Wolfgang Nejdl Choosing Observations and Ac tions in Model Based Diagnosis Repair Systems In Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning KR 92 1992 28 Sahika Genc and St phane Lafortune Distributed diagnosis of discrete event systems using Petri nets In Proceedings of the 24th international conference on Applications and theory of Petri nets ICATPN 03 2003 29 Eric Georgin Frederic Bordin S Loesel and Jim R McDonald CBR Applied to Fault Diagnosis on Steam Turbines In Proceedings of the 1st United Kingdom Workshop on Progress in Case Based Reasoning 1995 30 R M Gray Entropy and Information Theory Springer Verlag New York 1990 136 Bibliography 31 Eric A Hansen and Shlomo Zilberstein LAO A heuristic search algo rithm that finds solutions with loops Artificial Intelligence 129 1 2 35 62 2001 32 Peter Hart Nils Nilsson and Bertram Raphael A Formal Basis for the Heuristic Determination of Minimum Cost Paths IEEE Transactions on Systems Science and Cybernetics 4 2 100 107 1968 33 David Heckerman John S Breese and Koos Rommelse
118. ent Management of Object Oriented Queries with Late Binding 1996 Vadim Engelson An Approach to Automatic Construction of Graphical User Interfaces for Applications in Scientific Computing 1996 Magnus Werner Multidatabase Integration using Polymorphic Queries and Views 1996 Mikael Lind Affarsprocessinriktad f r ndringsanalys utveckling och till mpning av syns tt och metod 1996 Jonas Hallberg High Level Synthesis under Local Timing Constraints 1996 Kristina Larsen F ruts ttningar och begr nsningar f r arbete p distans erfarenheter fr n fyra svenska f retag 1996 Mikael Johansson Quality Functions for Requirements Engineering Methods 1996 Patrik Nordling The Simulation of Rolling Bearing Dynamics on Parallel Computers 1996 Anders Ekman Exploration of Polygonal Environments 1996 Niclas Andersson Compilation of Mathematical Models to Parallel Code 1996 No 567 No 575 No 576 No 587 No 589 No 591 No 595 No 597 No 598 No 599 No 607 No 609 FiF a4 FiF a 6 No 615 No 623 No 626 No 627 No 629 No 631 No 639 No 640 No 643 No 653 FiF a 13 No 674 No 676 No 668 No 675 FiF a 14 No 695 No 700 FiF a 16 No 712 No 719 No 723 No 725 No 730 No 731 No 733 No 734 FiF a 21 FiF a 22 No 737 No 738 FiF a 25 No 742 No 748 No 751 No 752 No 753 Johan Jenvald Simulation and Data Collection in Battle Training 1996 Niclas Ohlsson Software Quality Engineering by Earl
119. epairs never fail and function control is possible repairs never fail and function control is not possible repairs fail with probability 0 001 and function control is possible and repairs fail with probability 0 001 and function control is not possible Adding the possibility of failed repairs and removing the possibility of a function control makes the troubleshooting problem more difficult and the 5 4 Evaluation 123 Table 5 5 Percentage of the problems that were solved and the average of the error bounds when the algorithms were halted for the different planning algorithms Algorithm Problem class Solved Error bound wIBLAO Trivial 100 0 0 0004 Easy 100 0 0 0009 Intermediate 100 0 0 0009 Hard 100 0 0 0010 Very hard 81 8 0 0124 FRTDP Trivial 100 0 0 0003 Easy 100 0 0 0008 Intermediate 100 0 0 0009 Hard 50 0 0 0091 Very hard 0 0 0 0680 BRTDP Trivial 100 0 0 0004 Easy 100 0 0 0008 Intermediate 100 0 0 0010 Hard 40 0 0 0170 Very hard 0 0 0 0782 VPI RTDP Trivial 100 0 0 0003 Easy 100 0 0 0008 Intermediate 100 0 0 0010 Hard 40 0 0 0178 Very hard 0 0 0 0681 ILAO Trivial 100 0 0 0001 Easy 100 0 0 0006 Intermediate 81 8 0 0025 Hard 0 0 0 0538 Very hard 0 0 0 2566 124 Chapter 5 Case Study Hydraulic Braking System Table 5 6 The average number of expansions the average number of back ups and the average computation time in seconds for the different planning algorithms
120. er of expansions and back ups are registered Also the expected cost of the current upper bound policy Vz is evaluated since this represents the actual quality of the policy that is returned from the algorithm Two versions of Iterative Bounding LAO are tested a weighted version wIBLAO and an unweighted version IBLAO Both uses a 0 5 and wIBLAO uses w amp v1 BRTDP uses t 50 FRTDP uses e 0 001 Do 10 and kp 1 1 and VPI RTDP uses a 0 001 and f 0 95 These 4 2 Evaluation of Iterative Bounding LAO 103 Table 4 1 Comparison of algorithms on racetrack large b large b Va expansions backups time wIBLAO 0 1 23 95 2606 108064 0 53 0 01 2331 3743 203323 1 00 0 000 23 26 4353 286681 1 39 IBLAO 0 1 24 86 3381 56766 0 45 0 01 23 45 3995 86356 0 53 0 001 2327 4706 120142 0 78 ILAO 0 1 2328 9133 342745 0 74 0 00 2325 9884 811285 1 49 0 001 23 25 9909 902720 1 64 BRIDP 0 1 2348 5527 33800 0 23 0 01 2327 6416 48270 0 28 0 001 23 25 6800 58586 0 33 FRTDP 0 1 23 61 5354 53242 0 30 0 01 2327 6565 76546 0 38 0 001 23 25 7246 96844 0 47 VPI RTDP 0 1 23 63 5357 57528 0 31 0 01 23 29 6053 98088 0 44 0 001 23 25 6768 160680 0 66 are the same values used in the empirical evaluations in 46 l671 76 The results are shown in Tables 4 1 and 4 2 The best results in each cate gory are in bold The best performance is obtained with BRTDP and Iterative Bounding LAO requires m
121. erformed Let the ordered set 7 be some permutation of 1 C such that the ith partial plan that is executed is the one for component Cz Let n be the number of undelayed observable components that shall be processed with the partial plans P1 or P2 The undelayed observable components are just as before ordered in descending order of p c 5 The remaining components are placed last in the order arbitrarily since if none of the first components are faulty all the remaining C n partial plans will be executed regardless of any further observations Let Z c be the first i Z such that C F in c and let c c be the expected cost of performing the partial plan for the component C when the true diagnosis is c If the true diagnosis is c the expected cost of repair using 3 7 Relaxing the Assumptions 91 the fixed strategy Pts vod will be T c 1 Y docs c E Ca c ifZ c lt n Cfixed EE 3 54 E yr d b P ci c otherwise The new fixed strategy heuristic fixed is the MS value of 3 54 hifixea S E b c C C fixed 3 55 Example 3 8 Consider the system state in Example 3 6 and a loss function where C 4 NF 1100 for i 1 2 3 4 The partial plans for each compo nent will be P1 P5 P4 P2 respectively and they will be executed in the order T 4 1 3 2 Then the value of heed in this state is 271 06 where the values Of Cfixea for all c are 1 c C3 NF NE NF failure NF NF
122. es C A feature variable or the fault mode faulty A set of feature variables A set of assignments of feature variables Family of structures A graph Gr h gt SU Sa z Uo wey CQ 99 Xx m Uh Se BE Qo m x x ess o 145 A solution graph A heuristic function A lower bound heuristic function An upper bound heuristic function A troubleshooting problem Ordering of components when computing the heuristic 15 4 A loss function A troubleshooting model A probabilistic model The set of nodes of a graph The fault mode not faulty of a component variable An observation mode of the observation variable C An assignment of the observation modes of the observation variables C An observation variable A set of observation variables A set of POMDP observations The state transition probability function for MDP s The preconditions of an action A repair event or the reward function of an MDP A set of repair events A state A set of states Time The current time The time of the last operation event The Bellman update operator The value function of an MDP policy A weight function A value of the stochastic variable X Values of the stochastic variables X A stochastic variable A set of stochastic variables 146 Appendix A Notation ACC BN BRTDP CBR CR CPD CPT DAE DAG DBN DES DTC ECR ECU FRTDP GDE HSVI IBLAO ILAO LAO MDP nsDBN B Acronyms A
123. es between the stochastic variables s t X E is a directed acyclic graph The set O contains parameters that define the conditional probabilities P X pa X where pa X are the parents of X in the graph The joint probability distribution of all the stochastic variables X in the Bayesian network is the product of each stochastic variable X X conditioned on its parents P X T P Xlpa X Xex Let Ox C O be the parameters that define all the conditional probabilities P X pa X of a specific variable X This set Ox is called the conditional proba bility distribution CPD of X When the variables are discrete the CPD is called the conditional probability table CPT Bayesian networks can be used to answer queries about the probability distribution of a variable given the value of others 2 2 Bayesian Networks 19 OXpuny 0 1 Xbattery 0 2 Xbattery Xpump Xbattery Xpump uM OK OK 0 05 OK blocked 1 dead OK 1 dead blocked 1 Figure 2 1 The Bayesian network in Example i The parameters ey cea Ox and Ox describe the conditional probabilities of having Xpattery dead Xpump blocked and Xengine notstarting respectively ngine Example 2 1 Simple Car Model Consider a car where the engine will not start if the battery is dead or the fuel pump is blocked When nothing else is known the probability of a dead battery is 0 2 and the probability of a b
124. gning VLSI Systems 1985 Johan Fagerstr m Simulation and Evaluation of Architecture based on Asynchronous Processes 1985 Jalal Maleki ICONStraint A Dependency Directed Constraint Maintenance System 1987 Tony Larsson On the Specification and Verification of VLSI Systems 1986 Ola Str mfors A Structure Editor for Documents and Programs 1986 Christos Levcopoulos New Results about the Approximation Behavior of the Greedy Triangulation 1986 Shamsul I Chowdhury Statistical Expert Systems a Special Application Area for Knowledge Based Computer Methodology 1987 Rober Bilos Incremental Scanning and Token Based Editing 1987 Hans Block SPORT SORT Sorting Algorithms and Sport Tournaments 1987 Ralph R nnquist Network and Lattice Based Approaches to the Representation of Knowledge 1987 Mariam Kamkar Nahid Shahmehri Affect Chaining in Program Flow Analysis Applied to Queries of Pro grams 1987 Dan Str mberg Transfer and Distribution of Application Programs 1987 Kristian Sandahl Case Studies in Knowledge Acquisition Migration and User Acceptance of Expert Systems 1987 Christer B ckstr m Reasoning about Interdependent Actions 1988 Mats Wir n On Control Strategies and Incrementality in Unification Based Chart Parsing 1988 Johan Hultman A Software System for Defining and Controlling Actions in a Mechanical System 1988 Tim Hansen Diagnosing Faults using Knowledge about Malfunctioning Behavior 1988 Jo
125. goal state fy Otherwise a sequence of actions Aj is performed to take the system to a system state where F f 1 Note that this system state is not necessarily the same as the one reached when C NF However they have in common that the probability that C is faulty is zero and that F f 1 Figure B 6 depicts a similar plan for repairing a component where there is no action that observes it In any system state s we can start with a sequence of actions Aj s that 78 Chapter 3 Troubleshooting Framework AT AF O C NF Figure 3 6 A troubleshooting plan for repairing an unobservable component Ch takes us from s to a system state where F f and then execute these partial plans in order until all faults are repaired We call this type of troubleshooting plan for a fixed troubleshooting strategy Mixed If s is such that no components can be faulty we start instead with a sequence of actions A s that takes us to the nearest goal state If f f for all i j these partial plans can be executed in any order We will now define two functions S RF and six real valued constants that gives the cost of executing parts of the partial plans in a system state s that we will use to create the new heuristic cols Pacare 0 c s nc AR s c a ET Y ac aes cla if C is observable c i repre AS c a otherwise ci Luck c a EP c Laca c a if C is observable 0 otherwise Je As A c a if C i
126. has rained with probability 1 0 However if take a hose and wet the grass we perform an intervention on the grass Then if we observe that the grass is wet the probability that it has rained is still 0 1 P X 44 has rained Xorass Wet Xerass wet where Xgrass wet means that the variable Xgrass is forced to take on the value wet by an external interventioq 22 2 Dynamic Bayesian Networks Because we perform actions on the system troubleshooting is a stochastic process that changes over time Such processes can be modeled as dynamic Bayesian networks 19 Definition 2 3 Dynamic Bayesian Network A dynamic Bayesian network DBN is a Bayesian network where the set of stochastic variables can be par titioned into sets X X where X describes the modeled process at the dis crete time point f If for each variable X X it is the case that pa X C Uj_ X the DEN is said to be an n th order DBN In other words all the variables in Xt are only dependent of the values of the variables up to n time steps earlier The stochastic variables X and the edges between them form a Bayesian network Bf called the time slice t The network B is a subgraph of the DBN If all time slices t gt 0 are identical the DBN is said to be stationary A sta tionary first order DBN B can be fully represented by an initial BN B and a transition BN B representing all other BN s B B2 in the DBN The vari ables in
127. hat for any state s T f s c a s Y p s s a f s s succ a s The RTDP algorithm explores the state space randomly through a series of trials depth first random walks starting from the initial state The RTDP algorithm is shown below as Algorithm As input it is given an SSPP a heuristic function h S Rt that gives an estimate of the optimal expected cost for every state s S such that h s X V s a time limit Tstop that 2 3 Markov Decision Processes 35 specifies when the algorithm should halt and a time limit T j that specifies the maximum duration of each trial The current policy 7 is undefined for states that have not been backed up The trials lines are run repeatedly until the algorithm times out when CPU time ty gt Tstop starting from the initial state s If a state s is encountered and s has not been expanded before then s is expanded at line 11 That is all successor states s are generated for all actions and s is inserted into the set G and the value function is set according to the heuristic f s h s Every encountered state s is first backed up i e the current policy for that state 7t s is selected and value function f s is updated Then a successor state s succ 7t s s is drawn randomly from the distribution p s 7r s ME and the trial continues from s through a recursive call to RUNTRIAL line 14 If a goal state is reached or the time limit T is reached RTDP
128. hat has preconditions that cannot be represented as a conjunction is replaced by one action for every disjunction that is needed For example an action with the precondition Fi D V F Dj will be replaced by the actions a and az where P a1 F1 D and P a2 F D respectively If in a state s the probability that no component is faulty is one A s will also contain a composite action corresponding to the stop action ay that sets the feature variables to fy Fg Definition B 8 defines an action to be applicable in a state s if that action has a non zero probability of reaching any other state s S s from s All actions in A s have their preconditions satisfied in s and cannot be deemed inapplicable for that reason However we can rule out further actions that will not be applicable in s These are actions whose repair effects if any repair components with zero probability of being faulty whose observation effects if any observe variables that have a known value or have parents in the BN that all have known values and whose operation effects if any operate the system when no repair events have occurred since the last operation event Any optimal solution that is found using only applicable composite actions will be equivalent to any optimal solution that can be found when only ordi nary actions are used Theorem 3 5 Let 7 be an optimal solution to the SSPP for troubleshooting SSPP S A p c 89 Sz an
129. hat has three effects is invoked at time t 10 the next action after a is invoked at time t 13 Then the plan will not be defined for the sequences of events elll ore 2 We cannot compute the cost of repair in advance but we still want to be able to prioritize between different plans Therefore we are interested in the expected cost of repair Let Es 11 be stochastic variables where the outcome space Og set of 4 such that for each e Og it exist such that e is strict prefix of e I e the outcome space of E ev consists of the sequences of events generated from every possible longest path in 7 be ginning with e1 The probability distribution of E melt given the sequence of events generated so far el and the probabilistic dependency model Mp is S a sub m et e is a prefix of e and no e Ex melt P E ev elo elt T Mp P e e T Mp 3 4 ll The expected cost of repair ECR of a troubleshooting plan 7 after the events el have occurred is the expected value of CR z E elt t ECR m e E CR 7 Ez as t e Mp Y P je 2 Mp CR 7 e t 3 5 e E elit Let E be the set of events that may be generated when the action a is performed and let 1 be the number ud events generated by a Using 3 3 and 3 4 the expected cost of repair 3 5 can be reformulated into recursive 3 8 The Troubleshooting Problem 55 form as ECR z el Y P je x Mp CR r e t
130. he cost of solving the trou bleshooting task This is the cost of repair and we will define it as the sum of the costs of all actions performed until the termination condition holds However depending on the outcome of information gathering actions we may want to perform different actions The outcomes of these information gathering actions are not known in advance Therefore the expectation of the cost of re pair given the currently available information is a more suitable performance measure This is the expected cost of repair ECR If the ECR is minimal then the average cost of using the troubleshooter is as low as possible in the long run Then troubleshooting is said to be optimal For large systems the problem of determining what actions to perform for optimal troubleshooting is computationally intractable 62 Then another in teresting performance measure is the time required to compute the next action to be performed If the next action to perform is computed while the user is waiting the computation time will contribute to the cost of repair The compu tation time has to be traded off with the ECR because investing more time in the computations generally leads to a reduced ECR Being able to estimate the quality of the current decision and give a bound on its relative cost difference to the optimal ECR can be vital in doing this trade off 1 3 Solution Methods A common approach when solving the troubleshooting task has been to div
131. he event at time t 1 is a repair event the belief state after the last op eration event does not change because it does not give us any new knowledge of which components were faulty at time tw i e t 1 _ pt by bw rtl coat ett 3 37 If the event at time t 1 is an operation event the next belief state after operation becomes equal to the belief state b and the set of recent events 3 5 Diagnoser 67 is cleared r Let P c c c T be the probability that the component statuses are c after an operation event of duration Tt given that they were c before Then using 3 23 bit c LP Bns ER el rl Ba b 3 38 Because of Assumption BJand Assumption 10 repairs are perfect and com ponents do not break down during operation Let 1 y be an indicator func tion such that if x y then 1 y 1 and otherwise 1 y 0 Then can be significantly simplified into bit e Y 1ey 1 7 b e 3 39 c With the update rules 3 32 3 37 3 38 the belief state after pier can be tracked for all events A i may occur Then using 3 23 3 23 and 3 24 we can fulfill the task of the Diagnoser Example 3 5 Tracking the Belief State for the Sample System Consider the sequence of events in the left most path in Figure The events regarding feature variables are ignored and an operation event is also generated for the Test System action The sequence of events is Ol ind C2 2 NF C fa
132. he retarder is engaged oil is taken from the oil sump and inserted into the system through the accumulator valve 12 Smaller adjustments of the amount of oil in the system are made using the control valve 6 When the retarder is disengaged the safety valve 10 is opened The valves are controlled by the ECU through a set of magnetic air valves 7 and a proportional valve 7 To control the system the ECU uses input from sensors that measure the coolant temperature 13 the oil temperature 14 and the oil pressure 15 The retarder is representative for heavy vehicles because it consists of a combination of mechanical hydraulic and electronic components 5 3 The Model We can create a diagnostic model for the retarder system that is an nsDBN as described in Section The first time slice of the network is shown in Figure 5 3 The model has 20 persistent variables representing the components and it has 25 non persistent variables representing the observations that can be made The component variables are shown as filled circles and the observation variables are shown as white circles Instant edges are shown as filled lines while non instant edges are shown as dashed lines Component variables that have no parents may fail independently of each other The CPT for such a component variable models the failure rate of that component The CPT s for the remaining variables are modeled with leaky noisy or probability distributions 34 Leaky n
133. he set of ab sorbing goal states All states s 5 are such that for all actions a A p s s a 1 and c a s 0 All other states s Sy are such that for all actions a A c a s gt 0 A policy for an SSPP is a policy for the corresponding MDP Therefore and because the cost function is the negative reward function of the corresponding MDP the expected cost of a policy 7 of an SSPP is a function defined as Vz Vi where y 1 An optimal policy 7r has minimal expected cost in all states i V s min r a s Y p s s a Vz s 2 7 ae s Esucc a s 2 3 Markov Decision Processes 33 Since the SSPP has absorbing goal states it may be possible to find a pol icy that can reach a goal state from the initial state with a finite expected cost since in the absorbing states all infinite sequences of actions will have an ex pected cost that is zero Such a policy exists if all action costs are finite and if by following the policy from the initial state a goal state will eventually be reached 2 3 4 Finding the Optimal Policy for an MDP In this section we will go through some methods for finding optimal or subop timal policies for the different types of MDP s described in Sections 2 3 11 2 3 3 Value Iteration Value Iteration 3 is a standard method for finding near optimal policies for ordinary MDP s with discrete state spaces When the discount factor y 1 Value Iteration can find a policy 71
134. he value x at time t and X x means that for each variable X X x xj The letter t is used for discrete 17 18 Chapter 2 Preliminaries event time that increases by 1 for each discrete event that occurs and T is used for real time e The outcome space of a stochastic variable X is denoted Ox i e the set of all possible values the X can have The set of all possible outcomes of multiple variables Xy Xy is denoted O X4 Xn e The concatenation of sequences and vectors is indicated with a semi colon e g a b c c d e a b c c d e A list of all the notation and variable names used can be found in Appendix A and a list of acronyms is found in Appendix B 22 Bayesian Networks This section will give a brief overview of Bayesian networks particularly in the context of troubleshooting For more comprehensive work on Bayesian networks see e g Jensen 39 We will begin by describing the basic Bayesian network before we describe the concepts of causality and dynamic Bayesian networks that are needed to model the troubleshooting process A Bayesian network BN is a graphical model that represents the joint probability distribution of a set of stochastic variables X The definition of Bayesian networks used in this thesis follows the definition given in 40 Definition 2 1 Bayesian Network A Bayesian network is a triple B X E O where X is a set of stochastic variables and E is a set of directed edg
135. here 7r s specifies which action that should be performed in state s This means that the policy indirectly specifies action plans that are dependent on actual action outcomes and can result in an infinite number of actions being performed The quality of such a policy can be measured using the total ex pected discounted reward criterion The total expected discounted reward of a policy zr is given by a function V S R where y 0 1 is a discount factor and Vis r n s s 7 Y pss n s Vz s 22 s esucc nt s s 30 Chapter 2 Preliminaries p s2 92 01 1 1 81 01 0 5 p s1 51 41 TET r a1 s2 1 51 82 42 0 5 LIB a p s2 82 4 0 5 2 191 Figure 2 5 An example of a small discrete MDP s1 52 41 42 p r The discount factor y enables us to value future rewards less than immediate rewards When the discount factor is 1 0 then is the expectation of the total accumulated reward gained from using the decision rule over an infinitely long period of time This would mean that the reward can be infinite but if y 1 and all rewards are finite then VI s lt oo for all policies 7 and all states s An optimal policy z has the maximal expected discounted reward V7 in all states s 7t s arg max r a s y Y p s s a V s 2 3 acA s Esucc a s 2 3 2 Partial Observability In troubleshooting the state of the system can for example be its true diagnosis i e the status of all c
136. heuristic function and for each problem class how many percent of the problems that were solved and the average of the error bounds when the algorithm was halted Table shows for each heuristic function and for each problem class the average number of expansions the average number of backups and the average computation time in seconds The averages in Table are taken only over the problems that were solved using both hop and hg No values are shown for hen for the problem classes intermediate hard and very hard because not all problems that were solved using Meo and hp were solved using hent The results shows that the 1 heuristic is a tremendous improvement over the heuristic hey and that it is only slightly but consistently better than hg This is because many information gaining actions in the retarder model have much smaller cost than most repair actions This causes the contribution from the entropy in eomp to become low This is also the reason why the hent heuristic becomes so relatively ineffective 5 4 4 Comparison with Other Algorithms In this section IBLAO is compared to the other algorithms for solving SSPP s used in the comparisons in Section 4 2 FRTDP BRTDP VPI RTDP and ILAO We will expect all of these algorithms to perform worse than Iterative Bound ing LAO because for the troubleshooting problem state expansions are ex pensive and not very cyclic The algorithms are implemented and parameterized in the s
137. hm in line Value Iteration updates both the value function f and the current policy 7t for these states When 0 G 0 then in line I2 LAO performs value iteration again this time over all states in M until either the f values converge or some non goal state appears among the leaf states of G7 in which case LAO goes back to line 4 When all leaves in G are goal states and the f values have properly converged by Value Iteration G I and Vy Vr lt ein line 14 40 Chapter 2 Preliminaries 2 3 5 Finding the Optimal Policy for a POMDP Finding an optimal policy for a POMDP is much more difficult than for an MDP with a finite state space of equal size However in certain situations a POMDP may be solved more efficiently than the corresponding belief MDP which has a much larger state space If we are interested in finding plans with a fixed depth T the value function of an optimal policy can be represented by a piecewise linear function This is used by several POMDP algorithms Instead of representing the opti mal value function as a vector over states the optimal T step policy is repre sented with a set of linear constraints Yr on the belief space B Each constraint is a pair a Vr where a is the first action of some T step policy and Vr isa vector specifying the expected reward of that policy for each state s S The optimal T step policy is extracted from Yr as Tp b arg max Y b s Vr s a Vr eYr ses Ini
138. hoose an action to perform and we will follow the branch corresponding to the chosen action If the action can have one of multiple outcomes we reach a chance node Depending on the outcome we will follow a branch corresponding to that outcome from the chance node to another decision node or an end node In the end nodes the final result is noted e g all suspected faults repaired at a cost of 130 A decision can be made by choosing the action that leads to the most favorable results In the example in Figure 1 1 the most favorable decision would be to repair component A and then proceed by testing the system This yields a 75 chance of a cost of 100 and a 25 chance of a cost of 140 This approach has been used for many types of decision problems in the area of economics and game theory 66 For complex decision problems though the decision tree can become im mensely large One way to make the decision problem tractable is to prune the tree at a certain depth k and assign each pruned branch a value from a heuristic utility function The decision is then the action that either minimizes or maxi 1 3 Solution Methods 11 mizes the expected utility in k steps This is sometimes referred to as k depth look ahead search 68 In de Kleer and Williams the task is to find the fault in the system by sequentially performing observing actions Here the possible diagnoses are in ferred from the available observations using their General
139. hooting is developed where the system is diagnosed using non stationary dynamic Bayesian networks and the decisions of which actions to perform are made using a new planning algorithm for Stochastic Shortest Path Problems called Iterative Bounding LAO It is shown how the troubleshooting problem can be converted into a Stochastic Shortest Path problem so that it can be efficiently solved using general algorithms such as Iterative Bounding LAO New and improved search heuristics for solving the troubleshooting problem by searching are also presented in this thesis The methods presented in this thesis are evaluated in a case study of an auxiliary hydraulic braking system of a modern truck The evaluation shows that the new algorithm Iterative Bounding LAO creates troubleshooting plans with a lower expected cost faster than existing state of the art algorithms in the literature The case study shows that the troubleshooting framework can be applied to systems from the heavy vehicles domain This work is supported in part by Scania CV AB the Vinnova program Vehicle Information and Communi cation Technology VICT the Center for Industrial Information Technology CENIIT the Swedish Research Council Linnaeus Center CADICS and the Swedish Foundation for Strategic Research SSF Strategic Research Center MOVIII Department of Computer and Information Science Link ping universitet SE 581 83 Link ping Sweden i Acknowledgments First I would
140. ide the problem into two parts the diagnosis problem and the decision problem 271 33 42 79 90 First the troubleshooter finds what could possibly be wrong 1 3 Solution Methods 7 given all information currently available and then it decides which action should be performed next In Section 1 3 1 we will first present some common variants of the diagno sis problem that exist in the literature These problems have been studied ex tensively in the literature and we will describe some of the more approaches The approaches vary in how the system is modeled and what the purpose of the diagnosis is In Section 1 32 we will present previous work on how the decision problem can be solved 13 1 The Diagnosis Problem A diagnosis is a specification of which components are faulty and non faulty The diagnosis problem is the problem of finding which is the diagnosis or which are the possible diagnoses for the system being diagnosed given the currently available information Diagnosis is generally based on a model that describes the behavior of a system where the system is seen as a set of com ponents 77 This can be a model of the physical aspects of the system where each component s behavior is modeled explicitly using for example universal laws of physics and wiring diagrams 7177 It can also be a black box model which is learned from training data 69 97 Then no explicit representation of how the system works is required The p
141. ies P c e Mp can be computed efficiently many of the search heuristics can be used as they are However extending the frame work to be able to use other probabilistic models than the nsDBN s for trou bleshooting is not explored further in this thesis 3 8 Summary This chapter presented how the troubleshooting problem is modeled in the troubleshooting framework The troubleshooting model specifies which com ponents the system is composed of and in which ways they can be faulty which observations that can be made what actions that can be performed and which probabilistic model is used The probabilistic model describes how compo nents observations and events depend on each other We have showed how an nsDBN for troubleshooting can be used as a probabilistic model for a system where the assumptions presented in Section 3 4 3 are applicable By us ing the method presented in Section 3 5 2 the nsDBN for troubleshooting can be represented with a two layer static Bayesian network Theorem B 1 shows that this network can be used instead of the explicit nsDBN to answer queries of the type that are needed by the Diagnoser in the framework In Section B 6 1 we showed that the troubleshooting problem can be trans formed into an SSPP Once we have formulated the troubleshooting problem as an SSPP any general algorithm for solving SSPP s can be used Many state of the art SSPP algorithms such as BRTDP 46 FRTDP 76 and VPI RTDP use search
142. ify the values of all feature variables A state that contains information of the belief state after the last operation event the repair events that have occurred since the last operation event and the current status of the feature variables is called a system state Definition 3 7 System state Let I M elt 0 Fe C4 bea troubleshooting problem where Assumptions 79 hold Then a system state corresponding to the troubleshooting problem I is a tuple s b r f where by is a belief state after the last operation event before the time t as defined in Definition 3 6 r is an unordered set of all repair events that have occurred since this operation event and f specifies the values of all feature variables given the events that have occurred up to time f If no operation event has occurred by b and r consists of all repair events that have occurred up to time f State Transitions Let I M el f C and b M el ef C be two trou bleshooting problems where Assumptions 7H9 hold and let s1 bw1 r1 f1 and sz bw2 T2 f2 be their corresponding system states If the event e is a feature event F f s2 can be computed from s by first letting fp f and then setting the element in f corresponding to F to f A feature event will have no effect on the belief state therefore by bw1 and rp r4 In the case of any other type of event bq and rz can be computed from bw and r in the Diagnoser
143. il Ct NF a 7 O6 ind C4 NF 3 4 1 3 3 The initial distribution b is computed using the initial time slice of the nsDBN b c P c B 0 P ci Bus 0 P c2 Bns 0 P ca Bus 0 P ca co Bus 0 Att 0 tw t so therefore p b The static representation B will be flattened out to a two layer BN Therefore the CPT for Os will be the following Cy C3 C4 P O ind C4 C5 C4 NF NF NF 0 NF NF low 1 NF fail NF 1 NF fail low 1 fail NF NF 1 fail NF low 1 fail fail NF 1 fail fail low 1 68 Chapter 3 Troubleshooting Framework Table 3 1 Belief states at time of operation in Example 5 Entries in the table where b c 0 are blank rf 0 e c1 c2 c3 C4 PO c 0 0 0 C NF C 2NF bi c balc bole bale bale dele NE NE NE NF 0 994 F NE NE NF 0 001 NE F NE NF F F NE NF NENE E NF 0 004 0 996 0 166 0 199 0 996 0 996 0 666 0 800 0 004 1 c E NP 4 107 E NF NE E E ENE T NE NE F NE NE NE ENE F ENE NE NE F NE N 0 001 1 1076 tri trj rj nj jn Mor n 4 1078 4 107 iE Man mn m ME 7 1074 8 1074 0 004 0 004 3 6 Planner 69 The values of bt c for all c cy c2 c3 c4 Oc t 0 7 are shown in Table 3 1 The first three events are observation events so the rule is used to update b
144. illed Drained node F06 name Gearbox oil category feature type discrete 2 Filled Drained node FO7 name Coolant category feature type discrete 2 Filled Drained node F08 153 154 Appendix C The Retarder Model File name Proportional valve category feature type discrete 2 Fit Removed node FO9 name Propeller shaft category feature type discrete 2 Fit Removed node F10 name Oil cooler category feature type discrete 2 Fit Removed node Fii name Retarder unit category feature type discrete 2 Fit Removed node Fi2 name Retarder housing category feature type discrete 2 Assembled Disassembled node F13 name Retarder axle category feature type discrete 2 Fit Removed Conditional probabilities probability C01 4 0 9965 0 0035 probability C02 4 0 9925 0 0075 probability C03 4 0 998 0 002 probability C04 4 0 997 0 003 probability C05 4 0 997 0 002 0 001 probability C06 4 0 994 0 005 0 001 probability C07 4 0 9965 0 0035 probability Cos 4 0 9965 0 0035 probability Cog 4 0 998 0 002 probability C10 0 9945 0 0055 155 probability C11 0 9945 0 0055 Y probability C12 0 998 0 002 Y probability C13 C12 0 0 999 0 001 1 0 1 Y
145. in Fault Tolerant Middleware 2002 Iakov Nakhimovski Modeling and Simulation of Contacting Flexible Bodies in Multibody Systems 2002 Levon Saldamli PDEModelica Towards a High Level Language for Modeling with Partial Differential Equations 2002 Almut Herzog Secure Execution Environment for Java Electronic Services 2002 No 999 No 1000 No 1001 No 988 FiF a 62 No 1003 No 1005 No 1008 No 1010 No 1015 No 1018 No 1022 FiF a 65 No 1024 No 1034 No 1033 FiF a 69 No 1049 No 1052 No 1054 FiF a 71 No 1055 No 1058 FiF a 73 No 1079 No 1084 FiF a 74 No 1094 No 1095 No 1099 Nol Nol FiF a No I No I No I No I No I No I No I No I No I FiF a No I No I No I FiF a No I FiF a No I No I No I No I 10 16 77 68 85 71 86 72 83 84 85 Jon Edvardsson Contributions to Program and Specification based Test Data Generation 2002 Anders Arpteg Adaptive Semi structured Information Extraction 2002 Andrzej Bednarski A Dynamic Programming Approach to Optimal Retargetable Code Generation for Irregular Architectures 2002 Mattias Arvola Good to use Use quality of multi user applications in the home 2003 Lennart Ljung Utveckling av en projektivitetsmodell om organisationers f rm ga att till mpa projektarbetsformen 2003 Pernilla Qvarfordt User experience of spoken feedback in multimodal interaction 2003 Alexander Siemers
146. inated by some other constraint 2 3 Markov Decision Processes 41 This guarantees that no constraint from the optimal set of constraints is re moved 42 Chapter 2 Preliminaries Part II Decision Theoretic Troubleshooting of Heavy Vehicles 3 Troubleshooting Framework This chapter is on the framework for troubleshooting described in Section 4 We will formally define the troubleshooting model and the troubleshooting problem in Sections 3 2 and 3 3 We will also define a set of assumptions that can be applied when modeling the troubleshooting process for heavy vehicles in Section B 4 When describing the Diagnoser in Section 5 we will present a new way to represent and use the non stationary Dynamic Bayesian Networks for troubleshooting In SectionD 6 we present the Planner There we will show how the troubleshooting problem can be modeled and solved as a Stochastic Shortest Path Problem SSPP Many solvers for SSPP s benefit from using search heuristics New heuristics applicable for the troubleshooting problem are presented in Section 3 6 3 In Section 3 6 4 we will show how certain actions can grouped together to make the planning process more efficient without losing optimality In Section 3 7 we will study what the consequences will be if we relax some of the assumptions previously made in Section 3 4 thus creating a more general framework 3 1 Small Example Here we will introduce a small sample system that is used
147. ing the feature variables in a partial order such that F gt F if F must be disassembled before Fj and F lt F if F must be assembled before F Let pa F C F be the only set of features such that for every F F pa F F gt F EE F gt Ej and F lt F Similarly let ch F C F be the largest set of features such that for every E Fj ch F F F E lt E Fi lt Eu and F gt E The partial ordering corresponds to a Directed Acyclic Graph DAC where the nodes are feature variables and each feature F has the parents pa F and the children ch F This DAG is called the assembly graph The assembly graph for the example in Figure 3 7 a is shown in Figure 3 7 b For each F c F there exists at least one action that has the effect F D Such an action will have no other preconditions than F A and F D for all F pa F Also there exists at least one action that has the effect F A Such an action will have no other preconditions than F D and F A for all F ch F Composite Actions The assembly graph can be used to generate an optimal sequence of actions to fulfill the preconditions of any other action If we want to perform a certain action a but its precondition is not fulfilled in the current system state s we 82 Chapter 3 Troubleshooting Framework amp e p e e E5 h em er b E B e Fs Fe ON MU a In Assumption 6 the features depend on each b The
148. ing the Assumptions 87 The distribution for the set of recent repair events is updated as following P r er Bns Y pag r eltti Bns P rt e1 t Bns rcOg where P r r et B will only be dependent on the latest event eftt and P et 1 x elt B P r e Bas P et ett Bns The equation 3 50 can be computed from 3 24 and 3 48 and the previous distribution for the set of recent repair events The Diagnoser can also handle a model where Assumption 10 is relaxed and there is chance that components break down during operation In the area of reliability engineering a common model for the failure rate of components is to model component breakdowns with an exponential distribution 22 Fail ures i e transitions from a non faulty mode NF to a faulty mode F may occur continuously and independently of each other during operation A parameter Ac specifies the failure rate of a component C where 1 Ac can be interpreted as the mean time between failures The probability that a specific component is faulty at time t given that the system is operated for T time units between the times t 1 and t is dependent on the mode of Ct as P r e 1 B 3 50 P C F cf wt r 1 e 7 if Ct NF 1 otherwise Operating the system twice with the durations 1 and 7 is the same thing as operating the system once with the duration T 72 P C S F c 2 wt 11 w 25 P C S F e 5
149. into a static two layer Bayesian network that can be used instead of the explicit nsDBN to answer the queries needed by the Diagnoser in the framework The main contributions of this thesis are the new planning algorithm Iter ative Bounding LAO IBLAO and the improved search heuristics IBLAO is a new efficient general anytime search algorithm for e optimal solving of 131 132 Chapter 6 Conclusion problems formulated as Stochastic Shortest Path Problems In the case study we saw that IBLAO finds troubleshooting plans with higher quality than the other state of the art planning algorithms in less time We also saw that the new heuristics improves the speed with which high quality solutions can be found When compared to previous methods for troubleshooting that are based on look ahead search the expected cost of repair is already consistently improved when decisions are made after only 1 second of planning time using the trou bleshooting framework presented in this thesis When 10 seconds of planning time is allowed the performance is within 0 1 for the tested cases In the au tomotive industry it is important to reduce the repair and maintenance costs Any improvement in the expected cost of repair can yield great savings for the service workshops and vehicle owners Bibliography 1 Stefania Bandini Ettore Colombo Giuseppe Frisoni Fabio Sartori and Joakim Svensson Case Based Troubleshooting in the Automotive Con text
150. ion Assurance for Software Security 2005 Andreas K ll vers ttningar av en managementmodell En studie av inf randet av Balanced Scorecard i ett landsting 2005 He Tan Aligning and Merging Biomedical Ontologies 2006 Artur Wilk Descriptive Types for XML Query Language Xcerpt 2006 Per Olof Pettersson Sampling based Path Planning for an Autonomous Helicopter 2006 Kalle Burbeck Adaptive Real time Anomaly Detection for Safeguarding Critical Networks 2006 Daniela Mihailescu Implementation Methodology in Action A Study of an Enterprise Systems Implementation Methodology 2006 J rgen Skageby Public and Non public gifting on the Internet 2006 Karolina Eliasson The Use of Case Based Reasoning in a Human Robot Dialog System 2006 Misook Park Westman Managing Competence Development Programs in a Cross Cultural Organisation What are the Barriers and Enablers 2006 Amra Halilovic Ett praktikperspektiv p hantering av mjukvarukomponenter 2006 Raquel Flodstr m A Framework for the Strategic Management of Information Technology 2006 Viacheslav Izosimov Scheduling and Optimization of Fault Tolerant Embedded Systems 2006 H kan Hasewinkel A Blueprint for Using Commercial Games off the Shelf in Defence Training Education and Research Simulations 2006 Hanna Broberg Verksamhetsanpassade IT st d Designteori och metod 2006 Robert Kaminski Towards an XML Document Restructuring Framework 2006 Jiri Trnka Prere
151. ken can be determined from s A partial plan i will only begin if some component C NF where j gt i i e with the probability p An observable component will only be repaired if it is faulty ie with the probability p and we will thereby be finished if C was the only remaining faulty component i e with the probability p If more faulty components exist we will continue to the next partial plan with probability p If an observable component Cj is not faulty but some other component C 4 NF where Z j gt Z i then with the probability p we will perform the actions in A the lower path in Figure 3 5 For an unobservable component C instead of observing it we will perform a sequence of actions that repairs it and makes a function control with the probability pm The probability of exiting to a goal state and the probability of continuing to the next partial plan will be the same as in the case of an observable component 80 Chapter 3 Troubleshooting Framework If there are collateral repair effects a component may become repaired prematurely and the expected cost V s may become lower than hgxeg 5 therefore Mfixeq gt Visor s 2 Vz s for all states s S All the costs gu c ge c e and c are independent of the system state and can thereby be computed off line For a system state s bw f r the probabilities p 5 pi p p and p can be computed in O C b time If the components ar
152. king torque by letting oil flow through a rotor driven by the vehicle s propeller axle causing friction The kinetic energy is thereby converted into thermal energy in the oil that is cooled off by the cooling system of the truck At full effect and high engine speed the retarder can generate as much torque as the engine Figure 5 1 shows the retarder and how it is attached to the gearbox and Figure 5 2 shows a schematic of the retarder The central component of the retarder is the torus which consists of two parts a rotor 1 and a stator 2 109 110 Chapter 5 Case Study Hydraulic Braking System Figure 5 1 The retarder is an auxiliary braking system here shown attached to the gearbox N jk N FSS NN S N lt N N N N N N N N N N N LX e I TL J gt 7 E PME 4 O 2 a G A rr INNNNYNW NSNWONNWAWY iw y f j f j f j I f j cy f f R Figure 5 2 Schematic of the retarder 5 3 The Model 111 The rotor is connected to the retarder axle 3 and the stator is fixated to the retarder housing By injecting oil into the torus friction is created between the rotor and stator which is converted to braking torque on the propeller shaft 4 in the gear box This friction heats up the oil which is circulated through a cooler 8 by the pump 5 The amount of braking torque is proportional to the engine speed and the amount of oil in the system When t
153. kturering ansvarsf rdelning och anv ndarinflytande En komparativ studie med utg ngspunkt i tv informationssystemstrategier 1994 Lars Poignant Informationsteknologi och f retagsetablering Effekter p produktivitet och region 1994 Gustav Fahl Object Views of Relational Data in Multidatabase Systems 1994 Henrik Nilsson A Declarative Approach to Debugging for Lazy Functional Languages 1994 Jonas Lind Creditor Firm Relations an Interdisciplinary Analysis 1994 Martin Sk ld Active Rules based on Object Relational Queries Efficient Change Monitoring Techniques 1994 P r Carlshamre A Collaborative Approach to Usability Engineering Technical Communicators and System Developers in Usability Oriented Systems Development 1994 Stefan Cronholm Varf r CASE verktyg i systemutveckling En motiv och konsekvensstudie avseende arbetss tt och arbetsformer 1994 Mikael Lindvall A Study of Traceability in Object Oriented Systems Development 1994 Fredrik Nilsson Strategi och ekonomisk styrning En studie av Sandviks f rv rv av Bahco Verktyg 1994 Hans Ols n Collage Induction Proving Properties of Logic Programs by Program Synthesis 1994 Lars Karlsson Specification and Synthesis of Plans Using the Features and Fluents Framework 1995 Ulf S derman On Conceptual Modelling of Mode Switching Systems 1995 Choong ho Yi Reasoning about Concurrent Actions in the Trajectory Semantics 1995 Bo Lagerstr m Successiv
154. l states then G7 must also be a solution graph for G and therefore corresponds to a complete policy 7 for G Figure shows an example of a subgraph G to the search graph G shown in Figure and Figurep 6 d shows an example of a solution graph for G that is also a solution graph for G Since the subgraph is arbitrary there may also be leaves that are not goal states In this case G can be said to correspond to a partial policy 7 for G which can lead to non goal states for which no action is specified LAO can expand such a partial policy by specifying actions for non goal leaves thereby incrementally expanding G until its solution graph is also a solution graph for G without necessarily exploring all of G A state s in a solution graph G is evaluated with the evaluation function 2 9 f h s if s is a leaf state in G T E Tz s f s otherwise where h s is an admissible heuristic estimate of the optimal expected cost such that 0 lt h s lt Va s If zt is a complete policy then f s Vz s since in each leaf h s Vz s 0 It is possible to have complete policies in which it is possible to reach states from which a goal state is unreachable However the expected cost of such a policy is infinite AlgorithmB shows the LAO algorithm LAO is initialized with an explicit search graph G C G consisting only of the initial state sy and no hyperedges The current policy 7 is initially undefined therefore the solution graph
155. l troubleshooting plan or an optimal MDP policy The duration of an operation event or a function for computing the next belief state in POMDP s Set of constraints on the belief state space 143 144 e e T Us Gg w mn o a a ADAN 0 0 ET Appendix A Notation The fringe states of a search graph An operation event or a function for computing observation probabilities in POMDP s Outcome space An action An optimal action The assembled mode of a feature variable A set of actions A belief state A belief state describing the state at the time of the last operation event A belief state space A Bayesian network A non stationary dynamic Bayesian network Time slice t of the dynamic Bayesian network B A set of belief states A fault mode of the component variable C or a cost function The cost of the action a An assignment of the fault modes of the component variables C A component variable A set of component variables The disassembled mode of a feature variable An event An event that occurred at time f A sequence of events The sequence of events that occurred between time 1 and t A set of sequences of events the effects of an action or the set of edges of a graph A feature mode of the feature variable C or an evaluation function A lower bound evaluation function An upper bound evaluation function An assignment of the feature modes of the feature variabl
156. led or removed The other features are not as intuitive The top node F represents whether the vehicle is inside the workshop or not The vehicle must be outside when the vehicle is test driven and when troubleshooting is ended The feature variable F represents whether the cab of the truck is tilted or not and F5 represents whether safety supports for the vehicle frame are in place or not which is a requirement when actions under the vehicle are performed The feature vari ables Fs Fg represents different fluids that can be drained There are 10 observation variables that do not have an action that ob serves them These are Diagnostic Trouble Codes DTC s and observations that the driver can make The values of these observations are given to the troubleshooter when troubleshooting starts 114 Chapter 5 Case Study Hydraulic Braking System Table 5 1 All available actions for the retarder ag Stop 434 Check for air leakage a Replace oil filter az Replace temp sensor coolant a3 Replace temp sensor oil a4 Replace gasket gearbox side as Replace magnet valves ag Replace proportional valve az Replace pressure sensor oil ag Replace air tube ag Replace air valves a10 Replace control valve a11 Replace accumulator a12 Replace bearing 413 Replace pump 414 Replace iron goods 415 Replace radial gasket retarder 416 Replace gasket retarder side 417 Replace radial gasket gearbox aig Replace cables ECU 419 Replace
157. ler expected cost can always be found if we allow all actions and remove the requirement of performing the function control We will extend this heuristic to create an upper bound heuristic for the trou bleshooting problem specified in this thesis where actions have preconditions and multiple components can be faulty at the same time Figure 3 5 depicts a partial plan for observing and repairing a component C The plan begins in a system state where the feature variables have the values f and ends in a goal state or a system state where the feature variables have the values f First the component is observed However it is possible F f does not satisfy the preconditions for the action that observes C Therefore we must first per form a sequence of actions such that those preconditions can be satisfied e g we may have to assemble or disassemble certain features Let A be such a sequence of actions that also includes the observing action When the actions in A are performed a system state where F f is reached If C is non faulty a sequence of actions Af is performed to take the system to a state where F fj 4 If C is faulty then it is repaired by a sequence of actions AT and then a function control is made by a sequence of actions AE If the function control indicates that no more components are faulty then the sequence of actions AT is performed that takes us to a system state where the feature variables are that of a
158. lgorithms the plans created using IBLAO have con sistently higher quality and they are created in shorter time The case study shows that the troubleshooting framework can be applied for troubleshooting systems from the heavy vehicles domain The algorithm IBLAO has previously been published in 87 Parts of the work on the heuristics have been published in 86 88 89 Parts of the work on the troubleshooting framework have been published in 58 85 89 Parts of the work on the case study have been published in 57 89 16 Chapter 1 Background 2 Preliminaries This chapter is intended to introduce the reader to concepts and techniques that are central to this thesis In particular different types of Bayesian networks and Markov Decision Processes that can be used to model the troubleshooting problem are described 2 1 Notation Throughout this thesis unless stated otherwise the notation used is as follows Stochastic variables are in capital letters e g X The value of a stochastic variable is in small letters e g X x means that the variable X has the value x Ordered sets of stochastic variables are in capital bold font eg X X1 Xn The values of an ordered set of stochastic variable is in small bold letters e g X x means that the variables X X Xn have the values x Dc xx Variables or sets of variables are sometimes indexed with time e g X x means that the variable X has t
159. like to thank my supervisors at Link ping Professor Patrick Doherty and Dr Jonas Kvarnstr m for the academic support and the restless work in giving me feed back on my articles and this thesis I would also like to thank my supervisor at Scania Dr Mattias Nyberg for giving me inspiration and guidance in my research and for the thorough checking of my proofs Further I would like to thank my colleagues at Scania for supporting me and giving my research a context that corresponds to real problems encoun tered in the automotive industry I would also like to thank Per Magnus Ols son for proof reading parts of this thesis and Dr Anna Pernestal for the fruitful research collaboration Finally I would like to give a special thank to my wife Sara for her loving support and encouragement and for her patience during that autumn of thesis work when our son Aron was born iv Contents 1 1 Background 3 LT 4 A ce AN MN ee te bed 5 1 2 1 Performance Measures 6 13 Solution Methods ers ss ss ss ss sa 6 13 1 TheDiagnosisProblem 7 CL 9 14 Troubleshooting Framework o o o oo 12 15 Contributions 14 2 Preliminaries 17 TIL 17 T PI 18 UA E dern avi Beek ec wore 20 eh oe eee Oh ee ears 22 JETTA ox eme AUR Ge UR Ron teh qx ATE 2 24 Inference in Bayesian Networks 27 23 Markov Decision Processes c n 28 vi 231 TheBasicMDP
160. locked fuel pump is 0 1 Also even if both battery and the fuel pump are OK the engine may still be unable to start with a probability of 0 05 From this description a Bayesian network Beyz can be created that has the variables X Xengines Xbatterys Xpump and the two edges Xpatteryr Xengine and Xpump Xongine The graph and conditional probability tables for Beyqjare shown in FigureP 1 The joint probability distribution represented by B 1jis Xengine Xbattery Xpump P Xengines Xpattery Xpump starting OK OK 0 684 starting OK blocked 0 starting dead OK 0 starting dead blocked 0 not starting OK OK 0 036 not starting OK blocked 0 08 not starting dead OK 0 18 not starting dead blocked 0 02 When answering a query P X Y the structure of the network can be used to determine which variables in X that are conditionally independent given Y These variables are said to be d separated from each other 53 We will use the same definition of d separation as in Jensen and Nielsen 40 Definition 2 2 d separation A variable X X of a BN X E O is d separated from another variable X X given Y C X if all undirected paths P C E from 20 Chapter 2 Preliminaries Xj to X are such that P contains a subset of connected edges such that e the edges are serial i e all edges are directed the same way and at least one intermediate variable belongs to Y e the edges are diverging i e the edges diverge fr
161. lt P e e e Bus Y bE e P Xox y r t e c B 3 31 cc Oc When e is some other type of event then the effect ett that generated it cannot generate any other event Therefore the probability of having e given eft must be one Updating bo After Events As events occur the belief state at the last operation event is updated and bt is computed from b rf and the last event e t 66 Chapter 3 Troubleshooting Framework Corollary 3 2 Update after observation Let et be an observation event Xt 1 y Given that bt and rt are known then i n B pH e PP ee B 3 32 Y bj c P X x y r c e B tEOc Proof Using Definition 3 6 identify that bit c P Ctw c le 1 t Xx HH y Bus HH ute tw c elt B _ P X x C c el B 4 P C cle ns 3 33 PAA gle B Further identify that P X 5 x Cf c el Bis Y PU x CH Ce c e BuOP C Sc C Soe Ba cc Oc 3 34 Since e is not an operation event the time tw ue to the same time as t 1 w By applying 3 22 and then Theorem B 1 on 3 34 we get P ea veoe t Bus PE exc rey c C See Bus P X x y r c c e B 3 35 The final result 3 32 is obtained by inserting 3 35 into 3 33 and applying Corollary B 1 and DefinitionD 6 Analogously as for Corollary B 1 when Assumption Blapplies 3 32 can be simplified into g PeP 0 e B CHO E POC xp 6 6 B did If t
162. mation 1998 Pawel Pietrzak Static Incorrectness Diagnosis of CLP FD 1999 Tobias Ritzau Real Time Reference Counting in RT Java 1999 Anders Ferntoft Elektronisk aff rskommunikation kontaktkostnader och kontaktprocesser mellan kunder och leverant rer p producentmarknader 1999 Jo Skamedal Arbete p distans och arbetsformens p verkan p resor och resm nster 1999 Johan Alvehus M tets metaforer En studie av ber ttelser om m ten 1999 No 754 No 766 No 769 No 775 FiF a 30 No 787 No 788 No 790 No 791 No 800 No 807 No 809 FiF a 32 No 808 No 820 No 823 No 832 FiF a 34 No 842 No 844 FiF a 37 FiF a 40 FiF a 41 No 854 No 863 No 881 No 882 No 890 FiF a 47 No 894 No 906 No 917 No 916 FiF a 49 FiF a 51 No 919 No 915 No 931 No 933 No 938 No 942 No 956 FiF a 58 No 964 No 973 No 958 FiF a 61 No 985 No 982 No 989 No 990 No 991 Magnus Lindahl Bankens villkor i l neavtal vid kreditgivning till h gt bel nade f retagsf rv rv En studie ur ett agentteoretiskt perspektiv 2000 Martin V Howard Designing dynamic visualizations of temporal data 1999 Jesper Andersson Towards Reactive Software Architectures 1999 Anders Henriksson Unique kernel diagnosis 1999 P r J gerfalk Pragmatization of Information Systems A Theoretical and Methodological Outline 1999 Charlotte Bj rkegren Learning for the next project Bearers and barriers in knowledge
163. n tenance and repair would lead to large savings for the fleet owner due to time savings and for the retailer because of reduced expenses 1 2 Problem Formulation We will generalize from heavy vehicles and look upon the object that we trou bleshoot as a system consisting of components Some of these components may be faulty and should then be repaired We do not know which components that are faulty However we can make observations from which we can draw conclusions about the status of the components The troubleshooting task is to make the system fault free by performing actions on it that gather more in formation or make repairs The system is said to be fault free when none of the components which constitute the system are faulty We want to solve the troubleshooting task at the smallest possible cost where the cost is measured in time and money To do this we want to use a system for computer assisted troubleshooting called a troubleshooter that receives observations from the outside world and outputs recommendations of what actions should be performed to find and fix the problem The user of the troubleshooter then performs the actions on the system that is troubleshot and returns any feedback to the troubleshooter The troubleshooter uses a model of the system to estimate the probability that the system is fault free given the available information When this esti mated probability is 1 0 the troubleshooter considers the system to be
164. n Francisco 1988 Mor gan Kaufmann 16 Johan de Kleer and Brian C Williams Diagnosing Multiple Faults Artifi cial Intelligence 32 1 97 130 1987 17 Johan de Kleer and Brian C Williams Diagnosis with Behavioral Modes In Readings in Model based Diagnosis pages 124 130 San Francisco 1992 Morgan Kaufmann Bibliography 135 18 Johan de Kleer Alan K Mackworth and Raymond Reiter Characterizing Diagnoses and Systems Artificial Intelligence 56 2 3 197 222 1992 19 Thomas Dean and Keiji Kanazawa A model for reasoning about persis tence and causation Computational Intelligence 5 3 142 150 1990 20 Rina Dechter Bucket Elimination A Unifying Framework for Several Probabilistic Inference In Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence UAI 96 1996 21 Mark Devaney and William Cheetham Case Based Reasoning for Gas Turbine Diagnostics In Proceedings of the 18th International Florida Artificial Intelligence Research Society Conference FLAIRS 05 2005 22 B S Dhillon Engineering maintenance a modern approach CRC Press 2002 23 Edsger W Dijkstra A note on two problems in connexion with graphs Numerische Mathematik 1 269 271 1959 24 Richard O Duda Peter E Hart and David G Stork Pattern classification Wiley second edition 2001 25 Gal Elidan Bayesian Network Repository Retrieved from http www cs huji ac il galel Repository Nov
165. n its previous value and cannot be the parent of a persistent variable Observations are typically modeled with non persistent variables e g the outcome of an observation is dependent on the status of another component Instant and Non Instant Edges The edges in an nsDBN for troubleshooting are also separated into two classes instant and non instant An instant edge always connects a parent variable to its child within the same time slice This means that a change in value in the parent has an instantaneous impact on the child An instant edge typically oc curs between a variable representing the reading from a sensor and a variable representing the measured quantity e g a change in the fuel level will have an immediate effect on the reading from the fuel level sensor 2 2 Bayesian Networks 25 A non instant edge connects a child variable in one time slice to a persistent parent variable in the first time slice after the most recent operation of the system If no such event has occurred it connects to a persistent parent variable in the first time slice of the network Non instant edges model dependencies that are only active during operation For example the dependency between a variable representing the presence of leaked out oil and a variable representing a component that may leak oil is modeled with a non instant edge if new oil can only leak out when the system is pressurized during operation Transitions There are three types of
166. n of Iterative Bounding LAO 105 and goals as well as the average plan depth of the optimal solution for each problem is listed below Problem roverl rover2 rover3 rover4 rover5 rover No of fluents 68 68 68 68 68 119 No of actions 100 100 100 100 100 235 No of goals 1 1 1 1 3 3 Average depth 5 6 5 6 33 7 5 16 18 33 We will evaluate the algorithms in the same way as in the previous section for six problem instances from the rovers domain with increasing difficulty The lower bound heuristic will be the full observability heuristic hy which is a better heuristic than the hmin for this domain The upper bound will be a constant value of 10000 The results are shown in Tables 4 3H4 5 For the first four problems we only show the results for e 0 001 since these problems were easily solved by all algorithms For the more difficult problems we show the results when the algorithms have found solutions with provable error bounds of 0 1 0 01 and 0 001 respectively We see that the weighted variant of IBLAO is the fastest for all prob lems and all error thresholds except the tightest error thresholds where the unweighted variant of IBLAO is slightly faster However for the larger thresholds the difference between the unweighted and the weighted variant of IBLAO is significant This is because the upper bound heuristic is a constant so the upper bound cannot be reduced until a complete path t
167. nas L wgren Supporting Design and Management of Expert System User Interfaces 1989 Ola Petersson On Adaptive Sorting in Sequential and Parallel Models 1989 Yngve Larsson Dynamic Configuration in a Distributed Environment 1989 Peter berg Design of a Multiple View Presentation and Interaction Manager 1989 Henrik Eriksson A Study in Domain Oriented Tool Support for Knowledge Acquisition 1989 Ivan Rankin The Deep Generation of Text in Expert Critiquing Systems 1989 Simin Nadjm Tehrani Contributions to the Declarative Approach to Debugging Prolog Programs 1989 Magnus Merkel Temporal Information in Natural Language 1989 UIf Nilsson A Systematic Approach to Abstract Interpretation of Logic Programs 1989 Staffan Bonnier Horn Clause Logic with External Procedures Towards a Theoretical Framework 1989 Christer Hansson A Prototype System for Logical Reasoning about Time and Action 1990 Bj rn Fjellborg An Approach to Extraction of Pipeline Structures for VLSI High Level Synthesis 1990 Patrick Doherty A Three Valued Approach to Non Monotonic Reasoning 1990 Tomas Sokolnicki Coaching Partial Plans An Approach to Knowledge Based Tutoring 1990 Lars Str mberg Postmortem Debugging of Distributed Systems 1990 Torbj rn N slund SLDFA Resolution Computing Answers for Negative Queries 1990 Peter D Holmes Using Connectivity Graphs to Support Map Related Reasoning 1991 Olof Johansson Improving Implementati
168. ndencies within the first time slice Of and the dependencies between per sistent variables and their copies in the next time slice after a transition after operation OY For subsequent time slices these parameters are reused e g in 2 2 Bayesian Networks 27 time slice 2 of Example 2 5 P X3 X X2 0 Xi X2 Definition 2 4 nsDBN An nsDBN is a tuple Bs Xp Xnp Ej Eni OM 0 where X are the persistent variables X are the non persistent variables and E and E are the instant edges and non instant edges in the first time slice respectively The parameters O specify the conditional probability distribu tions for all variables in the first time slice so that Xp U Xnp Ej U Eri 90 is an ordinary BN The parameters O specify the conditional probabilities for the transitions after operation Let Bj be an nsDBN and let e be a sequence of events that has occurred then Bys el is the Bayesian network that is obtained by adding new time slices to the nsDBN using the corresponding transition rule for each event in 1 t e 2 2 4 Inference in Bayesian Networks The process of answering a query P X Y is called inference The probability distribution over X is inferred from the BN model given the evidence Y The inference can be exact or approximate For general discrete Bayesian networks the time and space complexity of exact inference is exponential in the size of the network i e the number of entries
169. ng for Efficient Off board Diagnosis Forfattare Author Hakan Warnquist Sammanfattning Abstract This licentiate thesis considers computer assisted troubleshooting of complex products such as heavy trucks The troubleshooting task is to find and repair all faulty components in a malfunctioning system This is done by performing actions to gather more information regarding which faults there can be or to repair components that are suspected to be faulty The expected cost of the performed actions should be as low as possible The work described in this thesis contributes to solving the troubleshooting task in such a way that a good trade off between computation time and solution quality can be made A framework for troubleshooting is developed where the system is diagnosed using non stationary dynamic Bayesian networks and the decisions of which actions to perform are made using a new planning algorithm for Stochastic Shortest Path Problems called Iterative Bounding LAO It is shown how the troubleshooting problem can be converted into a Stochastic Shortest Path problem so that it can be efficiently solved using general algorithms such as Iterative Bounding LAO New and improved search heuristics for solving the troubleshooting problem by searching are also presented in this thesis The methods presented in this thesis are evaluated in a case study of an auxiliary hydraulic braking system of a modern truck The evaluation shows that the new
170. noser 63 for the query of the probability that X has the value x at time t given el i e P X x X5 x Xi 8 e 571 Ba e P X x Xp x X x B 3 18 Proof In the case that el is the observation of a persistent variable the equiva lence is trivial since X Xj Assume now that X is non persistent We have evidence on all persistent variables in time slices t and tw and all paths from X to any variable in another time slice is either serial or diverging at a persistent variable in time slice t or tw Therefore according to rae oo in Bj el the variables in xi Uxte d separates X from all variables in all time slices except t see Definition 2 There can be no evidence on any other non persistent variable in time slice t since the nsDBN has one time slice for each event Therefore P X x X x Xj x e 7 Bus e P X x Xf x Xl x Bns e 3 19 The conditional probabilities of all non persistent variables are the same in all time slices therefore P X Zx X5 x Xi x Bu e f P X x X x X 8 Bys e 8 20 where e is the dummy event described in Definition 3 5 Using 3 17 in Definition B 5 and 3 20 we get P X x Xi x Xi x Bus e P X x Xp x Xp x B 3 21 and by applying 3 19 to 3 21 we get the final result P X x X x Xp x e Bu e P X x Xp x X x B
171. nosis of GAPLog Programs 1997 Gunilla Ivefors Krigsspel och Informationsteknik inf r en of ruts gbar framtid 1997 Jens Olof Lindh Analysing Traffic Safety from a Case Based Reasoning Perspective 1997 Jukka M ki Turja Smalltalk a suitable Real Time Language 1997 Juha Takkinen CAFE Towards a Conceptual Model for Information Management in Electronic Mail 1997 Man Lin Formal Analysis of Reactive Rule based Programs 1997 Mats Gustafsson Bringing Role Based Access Control to Distributed Systems 1997 Boris Karlsson Metodanalys f r f rst else och utveckling av systemutvecklingsverksamhet Analys och v rdering av systemutvecklingsmodeller och dess anv ndning 1997 Marcus Bj reland Two Aspects of Automating Logics of Action and Change Regression and Tractability 1998 Jan Hakegard Hierarchical Test Architecture and Board Level Test Controller Synthesis 1998 Per Ove Zetterlund Normering av svensk redovisning En studie av tillkomsten av Redovisningsr dets re kommendation om koncernredovisning RR01 91 1998 Jimmy Tjader Projektledaren amp planen en studie av projektledning i tre installations och systemutveck lingsprojekt 1998 Ulf Melin Informationssystem vid kad aff rs och processorientering egenskaper strategier och utveckling 1998 Tim Heyer COMPASS Introduction of Formal Methods in Code Development and Inspection 1998 Patrik H gglund Programming Languages for Computer Algebra 19
172. nosis of incipient faults In Proceedings 17th International Workshop on the Principles of Diagnosis DX 06 2006 66 S J Russell and Norvig Artificial Intelligence A Modern Approach Second Edition Prentice Hall 2003 Bibliography 139 67 Scott Sanner Robby Goetschalckx Kurt Driessens and Guy Shani Bayesian Real Time Dynamic Programming In Proceedings of the 21st In ternational Joint Conference on Artificial Intelligence IICAI 09 pages 1784 1789 2009 68 U K Sarkar P P Chakrabarti S Ghose and S C Desarkar Improving greedy algorithms by lookahead search Journal of Algorithms 16 1 1 23 1994 69 C Saunders A Gammerman H Brown and G Donald Application of Support Vector Machines to Fault Diagnosis and Automated Repair In Proceedings of the 11th International Workshop on the Principles of Diagnosis DX 00 2000 70 Scania CV Scania at INTERMAT 2009 New engine range meets 2011 emission standards Press release http www scania com 2009 71 Scania CV Scania Multi Service Retrieved from https mppv scania com Site November 2010 72 Scania CV Scania Repair amp Maintenance contract Retrieved from http www scania com products services services workshop services November 2010 73 Ross D Shachter Bruce D Ambrosio and Brendan Del Favero Symbolic Probabilistic Inference in Belief Networks In Proceedings of The 8th Na tional Conference on
173. o Oo P C O C9 O9 E and P E C9 O9 E for all t N The distributions of C O and E are only dependent on the prior distribution P Co Oo and all events up to time t E The probabilistic dependency model can as in this thesis be realized using non stationary Dynamic Bayesian Networks nsDBN s that are described in Section 2 3 Example 3 3 Probabilistic Model of Sample System In the sample system components do not spontaneously break during troubleshooting and observa tions are only dependent on the mode of the components Therefore in the nsDBN all component variables are modeled as persistent variables and and all observation variables are modeled as non persistent The initial nsDBN is shown in Figure 3 2 In this BN C C3 have no parents and P C4 4 NF 0 001 P C2 4 NF 0 001 and P C3 4 NF 0 004 This means that the Oil Pressure Sensor fails four times as often as the pump and the gasket The oil level will be drained if the Gasket is leaking so P C4 low C leaking 1 The oil level may also be low for other unknown reasons and therefore P C4 low C NF 0 002 The dependency between C4 and C is modeled as non instant since changes in the mode of the gasket will not have an instantaneous effect on the oil level If the pump is working and the oil level is normal the oil pressure should be normal However if either the pump fails or the oil level becomes low then pressure will be
174. o a goal state is found For unweighted IBLAO this happens only short before a complete solution is found which consequently is an optimal solution Therefore the performance for high error thresholds is almost the same as the performance for the lower thresholds Weighted IBLAO avoids this by first finding a suboptimal solution using the weighted heuristic and then gradually improving the solution However the many adjustments of the weight causes the weighted variant of IBLAO to perform more backups but this is counterweighted by the fewer number of expansions A constant upper bound is less problematic for the RTDP based algorithms because the trials are depth first and therefore many possibly suboptimal paths to a goal state are found early However because of the many choices of actions the trials become less efficient since each path becomes less likely to be part of an optimal solution Therefore even though they make few back ups a much larger portion of the search space is explored 106 Chapter 4 Planning Algorithm Table 4 3 Comparison of algorithms on the problems from the rovers domain rover1 Va expansions backups time wIBLAO 0 001 170 0 5 20 0 010 IBLAO 0 000 170 0 5 20 0 010 ILAO 0 000 170 0 5 16 0 010 BRTDP 0 000 170 0 5 10 0 010 FRTDP 0 000 170 0 5 20 0 010 VPI RTDP 0 001 170 0 5 10 0 010 rover2 Va expansions backups time wIBLAO 0 001 230 0 38
175. o b a is the probability of reaching the belief state b by performing 4 in the belief state b where o is an observation such that tio b a b 2 3 3 Stochastic Shortest Path Problems A stochastic shortest path problem SSPP is a problem that can be modeled with an MDP where we want to reach one of a set of goal states from a given initial state 6 Performing an action is associated with a cost and the actions may have stochastic outcomes An SSPP can be used to encode many problems where a plan of actions leading to a goal state is sought One such problem is the problem of computer assisted troubleshooting SSPP s correspond to MDP s where all rewards are non positive and some states are absorbing i e the reward for performing any action in an absorbing state is zero and we will end up in the same state with probability 1 0 The absorbing states are the goal states that we want to reach and the non positive reward function encodes the cost of performing actions in each state For simplicity we will model the cost of performing actions directly with a cost function Definition 2 10 Cost Function The cost function is a function c S x A gt R such that c a s is the cost of performing the action a in the state s Definition 2 11 Stochastic Shortest Path Problem A Stochastic Shortest Path Problem is a tuple S A P C 0 Sy where S A p c is an MDP so is the initial state and Sy is t
176. o solve a simplified ver sion of the problem In Bonet 8 a heuristic for SSPP s called the hj j heuristic is created through a relaxation where it is assumed that we can choose action outcomes freely Then the problem becomes an ordinary shortest path problem that can be solved optimally with algorithms such as A 32 or Dijkstras algo rithm 23 However this relaxed problem cannot in general be solved in poly nomial time since the size of the search graph for this shortest path problem is exponential in the number of possible actions If we have a troubleshoot ing problem where Assumption 11 holds then for any state where there is a non zero probability that no component is faulty the heuristic would at most return the cost of making a function control that has a positive outcome When the SSPP is a belief MDP we can create a heuristic where the relax ation is to create a corresponding SSPP under the assumption of full observ ability and solve that simpler SSPP instead 78 The cost of solving the relaxed problem for each underlying state is weighted with the probability of that state in the belief state When applied to the troubleshooting problem this is equiv alent to assuming the existence of a single observing action of zero cost that completely determines the values of all component variables For each possi ble outcome of this observing action we can quickly calculate a short sequen 74 Chapter 3 Troubleshooting Framework
177. observability heuristic hg gives a measure of what must at least be spent repairing faulty components while the entropy heuristic hent gives a measure of what must at least be spent gaining more information of the true state In Sun and Weld these two heuristics are combined when the troubleshooting problem is solved using look ahead search However a heuristic h hj hent would not be an admissible lower bound because the heuristics are not completely independent since repair events also reduce the entropy For look ahead search this is not a problem but for the SSPP for troubleshooting we require the heuristics to be admissible To create an admissible heuristic combining both hjo and hen we must dis regard any entropy that could be removed by the repairs in the calculation of heni Let H c be the amount of entropy that is reduced by repairing the faulty 3 6 Planner 75 components in c in a system state with maximal entropy Then a combined heuristic omp can be defined as hcomb 8 lig 5 max 0 H s Y b c Ale mincy a 343 ccOc Theorem 3 3 Let s be any system state in an SSPP for troubleshooting and let 7 be an optimal policy for the SSPP Then i s lt Vr s Proof In any system state s the faulty components in c must be repaired with the probability b s This will cost at least c c f and reduce the entropy in the state with at most H c Because the entropy is zero in all goal states the remaining entrop
178. of Electronic Control Units ECU s and sensors in vehicles has increased more than tenfold 49 With this trend towards more complex vehicles it is becoming more diffi cult even for an experienced workshop mechanic to have an intuitive under standing of a vehicle s behavior A misunderstanding of the vehicle s behavior can for example lead to replacing expensive ECU s even if they are not respon sible for the fault at hand Faults may depend on a combination of electrical logical mechanical thermodynamic and chemical processes For example suppose the automatic climate control system ACC fails to produce the cor rect temperature in the cab This can be caused by a fault in the ECU controlling the ACC but it can also be caused by a damaged temperature sensor used by the ECU The mechanic may then replace the ECU because it is quicker How ever since this is an expensive component it could be better to try replacing the temperature sensor first In this case the mechanic could be helped by a system for computer aided troubleshooting that provides decision support by pointing out suspected faults and recommending suitable actions the mechanic may take Computers are already used as tools in the service workshops In particu lar they are used to read out diagnostic messages from the ECU s in a vehicle and to set parameters such as fuel injection times and control strategies The di agnostic messages Diagnostic Trouble Codes DTC s c
179. oisy or distributions can be used for causal Bayesian networks and for a variable with n parents only O n parameters needs to be set to create a noisy or CPT Let X be a two valued stochastic variable where Ox x x1 and let Y Y be the parents of X in the BN where Oy Y o Yim and Mj Qy 1 Then in the leaky noisy or distribution n P X x1 Yi V1m Mery Yn Yn m 1 1 00 I di 5 1 i 1 112 Chapter 5 Case Study Hydraulic Braking System Oil temperature S b PENES Su C 5 Early disengagement ine e Ko Oil on cooler S No DTC unplausible Go coolant temp DTC unplausible 3 oil temp Leakage magnet valve Leakage Prop valve ey DTC unplausible oil pres Leakage Oil Prop valve Oe Leakage air tube 8 Leakage air valves e Response Q Ze Y Sg g S KOM L 2 Ret Oil leve Oil on noise shield Cables broken at Ret Q Sa Cable broken at BCUCS X A Oe DTC ECU 6 ts Y e connectors DTC ECU internal Figure 5 3 The nsDBN diagnostic model for the retarder 5 8 The Model 113 where Ies dm gt 0 Gi 0 1 otherwise and the parameters 09 0 1 0 y are chosen so that 09 P X x1 Y1 Vig r Yn Vno and Oj P X x1 Y1 yip lt Yi Yim lt r Yn Yn The leaky noisy or distribution should be interpreted as follows Each variable Y may cause X to have the valu
180. old To perform well in an on line setting this threshold is dynamically changed starting with a high value that is successively reduced as better solutions are found The most recent bounds on the optimal solution cost are always avail able and the user may use this information to decide when to stop the search Algorithm 5 shows the IBLAO algorithm Throughout this algorithm whenever a state s is visited for the first time a lower bound f and an upper bound f of the optimal expected cost are calculated such that f s lt Vre s lt fu s using the heuristic functions h and h respectively In line p an initial search graph G N is created consisting only of the initial state sy The outer loop in lines 3H15 continues indefinitely until stopped by the user In line lA the error threshold is initialized to be a factor a lt 1 times the current error bound so in the initial state The computation of the error bound is described in Section 4 1 2 The inner loop in lines 5SHI4 is similar to the LAO algorithm Section 2 3 4 Algorithm B where fringe states are expanded until a partial policy is found such that the initial state is solved within the current required bound i e amp so The solution graph for the lower bound policy 7 is Gr Ni 7 The set G consists of each leaf state s in G where s gt and conse quently s is not yet solved within the current error bound If b G
181. om a variable Z in the path and Z Y or e the edges are converging i e the edges meet at a variable Z in the path and Z E Y The property of d separation is symmetric i e if X is d separated from X given Y then X is d separated from X given Y The property of d separation is useful because it enables us to ignore the part of the network containing X when answering the query P X Y Con sider Example If we have no evidence for any variable then Xbattery 18 d separated from Xpump given Y since the path between them is con verging at Xengine and Xengine Y This means that we can for example compute P Xpattery Xpump simply by computing P xpatiery However if we have evidence for Xengine then Xbattery and Xpump are not d separated given Y Xengine Then if we for example want to compute P XhatterylXengine We must consider Xpymp L P Xengine Xbatteryr Xpump P Xbattery P Xpump P x epee QUE om battery engine Y P nlk 7 1 1 t j i kattery Xpump P battery P Xpump Ybattery pump EQ XpatteryrXpump 2 2 1 Causal Bayesian Networks If there is an edge between two variables X and X j and the variables are such that the value of X physically causes X to have a certain value this edge is said to be causal 54 E g a dead battery or a blocked pump causes the engine to not start If all edges in a BN are causal we say that the BN is a causal Bayesian network Itis often easier to model a physic
182. ome from an On Board Diagnosis OBD system that runs on the vehicle Ideally each DTC points out a component or part of the vehicle that may not function properly However often it is the case that a single fault may generate multiple DTC s and that the same DTC can be generated by several faults The OBD is primarily designed to detect if a failure that is safety critical affects environmental performance or may immobilize the vehicle has occurred This information is helpful but not always specific enough to locate exactly which fault caused the failure The mechanic must therefore also gather information from other sources such as the driver or visual inspections In order for a computer assisted troubleshoot 1 2 Problem Formulation 5 ing system to be helpful for the mechanic it must also be able to consider all of these information sources Another important aspect of troubleshooting is the time required to resolve a problem Trucks are commercial vehicles When they break down it is partic ularly important that they are back in service as soon as possible so that they can continue to generate income for the fleet owner Therefore the time re quired to find the correct faults must be minimized Many retailers now sell repair and maintenance contracts which let the fleet owner pay a fixed price for all repair and maintenance needs 84 A computer assisted trou bleshooting system that could reduce the total expected cost and time of mai
183. omponents The true diagnosis is however not known but we can get feed back in the form of observations that can give us information of which diagnoses are likely to be true Such a state is said to be partially observable An MDP with partially observable states is a Partially Observable MDP POMDP 12 Definition 2 7 Partially Observable MDP A Partially Observable MDP is a tuple S A O r p w where S and A are finite S A r p is an MDP O is a set of possible ob servations and w O x S x A 0 1 is a function where w o s a is the probability of making the observation o given that action a is performed in state s 2 3 Markov Decision Processes 31 Since the true state is not known our knowledge of this state is represented as a probability distribution over the state space In the POMDP framework this distribution is called the belief state b Definition 2 8 Belief State A belief state is a function b S 0 1 where b s denotes the probability that the state s is the true state The set B is the space of all possible belief states A POMDP policy is then a function from belief states to actions ie a function zt B A When an action a is performed in a belief state b and an observation o is made the next belief state b is computed for each state s as 12 b s w o s a Y p sys a b s nto b a 2 4 s succ a s where 7 is a function that gives the proba
184. on may cause the network to grow exponentially 52 Approximate Methods If the BN is large it may be necessary to do approximate inference Many of the methods for approximate inference depend on some randomization pro cess such as sampling from the prior distribution and give each sample some weight based on their importance to explaining the evidence These kinds of methods are often used for DBN s in real time applications such as robotics see e g Thrun et al 80 2 3 Markov Decision Processes The troubleshooting problem is a decision process where actions may be cho sen freely by the decision maker to achieve the goal of repairing the system but the actions may have stochastic outcomes Markov Decision Processes MDP s provide a powerful mathematical tool to model this This section gives a brief overview of some types of MDP s that are relevant for this thesis For more information on MDP s see e g 60 23 1 The Basic MDP In an MDP a state is a situation in which a decision of what action to perform must be made Depending on the action and the outcome of the action a 2 3 Markov Decision Processes 29 different state may be reached Depending on the decision and the state where the decision is made an immediate positive or negative reward is given The goal is to find a decision rule that maximizes the expected total reward over a sequence of actions Definition 2 5 Markov Decision Process A Markoo Decision Proce
185. on of Graphical User Interfaces for Object Oriented Knowledge Bases 1991 Rolf G Larsson Aktivitetsbaserad kalkylering i ett nytt ekonomisystem 1991 Lena Sr mbick Studies in Extended Unification Based Formalism for Linguistic Description An Algorithm for Feature Structures with Disjunction and a Proposal for Flexible Systems 1992 Mikael Pettersson DML A Language and System for the Generation of Efficient Compilers from Denotational Specification 1992 Andreas K gedal Logic Programming with External Procedures an Implementation 1992 Patrick Lambrix Aspects of Version Management of Composite Objects 1992 Xinli Gu Testability Analysis and Improvement in High Level Synthesis Systems 1992 Torbj rn N slund On the Role of Evaluations in Iterative Development of Managerial Support Systems 1992 Ulf Cederling Industrial Software Development a Case Study 1992 Magnus Morin Predictable Cyclic Computations in Autonomous Systems A Computational Model and Im plementation 1992 Mehran Noghabai Evaluation of Strategic Investments in Information Technology 1993 Mats Larsson A Transformational Approach to Formal Digital System Design 1993 No 380 No 381 No 383 No 386 No 398 No 402 No 406 No 414 No 417 No 436 No 437 No 440 FHS 3 94 FHS 4 94 No 441 No 446 No 450 No 451 No 452 No 455 FHS 5 94 No 462 No 463 No 464 No 469 No 473 No 475 No 476 No 478 FHS 7 95 No 482 No 488 No 489 No 497
186. ons Assumption 2 means that all observation variables can be modeled with non persistent variables Assumption 10 Persistence during Operation Operation does not affect the mode of persistent variables i e for each persistent variable X P 1 ifxt xt P x x operate v 6 en Assumption is a feasible approximation when Assumptions 8 and p hold and the probability of component breakdowns is insignificant unless the duration of operation is very long e g when the system is operated for only a couple of minutes during troubleshooting and the mean time between failures is in the order of months Assumption 11 Function Control Let Ofe C O be observation variables where the outcome space Oo can be separated into two disjoint sets Or and Or such that P C c Oy o 1if o Ong and c Cg and P C c O 0 0 if o Or and c Cg There exists a sequence of actions that can be performed such that the observation variables O f are observed Assumption I1 is valid for systems where perfect fault detection is possi ble i e there is some test that can distinguish between the cases when some component is faulty and no component is faulty 3 5 Diagnoser In Figure 1 2 the Diagnoser computes the probabilities of the possible diag noses and action outcomes In the current framework this corresponds to computing the probability P c e Mp 3 9 for each c Oc and computing the probabilities of action ou
187. ore back ups than the other algorithms but fewer states are expanded This is an expected result because IBLAO backs up all ancestor states to the expanded states while the RTDP algorithms only back up the states on the trajectory of the last trial Since the vehicle is moved back after it hits a wall the ancestor states to the initial state make up almost the entire state space ILAO will try to expand all states that are reachable given the current lower bound policy For block80 almost the entire state space is reach able under the optimal policy Therefore it is not able to return any solution at all before it runs out of memory 1600 MB IBLAO would have this problem too if it expanded all states on the fringe instead of using 4 6 The weighted version of Iterative Bounding LAO is more restrictive with expansions but requires more back ups because of the necessary weight adjustments 104 Chapter 4 Planning Algorithm Table 4 2 Comparison of algorithms on racetrack block80 block80 Va expansions backups time wIBLAO 0 1 981 10898 157913 3 38 0 00 9 61 18642 321675 6 51 0 001 9 59 24594 481827 9 30 IBLAO 01 10 04 12576 227177 4 55 0 01 9 61 17232 318582 6 31 0 001 9 59 25614 475370 9 42 ILAO 0 1 BRTDP 0 1 9 66 21270 110288 2 95 0 01 9 59 33423 193632 4 88 0 001 9 59 41830 270170 6 55 FRTDP 0 1 9 65 26985 175120 3 75 0 01 9 59 41795 295436 5 88 0 001 9 59 56126 447364 8 08 VPI RTDP 0 1 9 69 20490 107640 2 91 0 01 9 59
188. ower bound of the optimal ECR An advantage of this is that the user may use this information to decide whether to use the current recommendation or to allow the search algorithm to continue in hope of finding a better decision As the algorithm is given more computation time it will converge toward an optimal solution In comparison with competing methods the new algorithm uses a smaller search space and for the troubleshooting problem it can make e optimal decisions faster The new heuristic functions that are developed for this thesis can be used by IBLAO and they provide strict lower and upper bounds of the optimal ex pected cost of repair that can be efficiently computed The heuristics extend the utility functions in and by taking advantage of specific characteristics of the troubleshooting problem for heavy vehicles and similar applications These heuristics can be used by general optimal informed search algorithms such as IBLAO on the troubleshooting problem to reduce the search space and find solutions faster than if general heuristics are used The new algorithm is together with the new heuristics tested on a case study of an auxiliary hydraulic braking system of a modern truck In the case study state of the art methods for computer assisted troubleshooting are com pared and it is shown that the current method produces decisions of higher quality When the new planning algorithm is compared with other similar state of the art planning a
189. p 3 1 where e The set C the component variables consists of stochastic variables repre senting the health of components Each component variable C C must be in one fault mode c and one of the fault modes is the no fault case NF e The set O the observation variables consists of stochastic variables rep resenting possible observations that can be made on the system Each observation variable O O must be in one observation mode o e The set F the feature variables consists of non stochastic variables rep resenting parts of the system that may constrain which actions can be performed Each feature variable F F must be in one feature mode f To be able to perform certain actions certain feature variables must be in specific modes e The set A consists of the actions that may be performed The actions are described further in Section e The probabilistic dependency model Mp is a diagnostic model that de scribes the probabilistic dependencies between components observa tions and actions over time This model is described further in Sec tion 8 2 2 Example 3 1 Components Observations and Features of the Sample System From the description of the sample system in Section the components observations and features can be modeled as follows 48 Chapter 3 Troubleshooting Framework Variable Type Modes C Pump Component NE failure C2 Gasket Component NF leaking C3 Pressur
190. p decide if a state has converged or not In both BRTDP and FRTDP states with large difference in lower and upper bounds are given priority in the RTDP tri als In BRTDP the trials are randomized processes while in FRTDP they are de terministic The algorithm VPI RTDP uses a slightly different approach Here successor states are chosen based on an estimate of the expected improvement in decision quality when updating the state s value These algorithms have been shown to converge toward an optimal solu tion fast requiring relatively few backups on several MDP benchmark prob 93 94 Chapter 4 Planning Algorithm lems However in certain problems such as the troubleshooting problem they explore a larger search space and expand more states than necessary For the troubleshooting problem this is troublesome because state expansions require that the Diagnoser makes inference in a Bayesian network Compared to state backups this is a much more computationally intensive operation In this chapter we present a new algorithm for solving SSPP s Iterative Bounding LAO IBLAO It is a general algorithm that is suitable for SSPP s with characteristics similar to those of the troubleshooting problem 4 1 Iterative Bounding LAO The new algorithm is based on LAO 31 IBLAO maintains two sided bounds on the optimal solution cost and uses these to prune search branches when the error bound on the optimal solution cost is below a certain thresh
191. plan and grouped into 5 different problem classes of roughly equal size 12 trivial problems that were all solved in less than 0 05 seconds 12 easy problems that were all solved in less than 0 5 second 11 intermediate problems that were all solved in less than 8 seconds 10 hard problems that were all solved in less than 2 minutes and 11 very hard problems that required more than 2 minutes to solve Two problems in the very hard problem class were not completely solved because the planner ran out of memory When this happened the error bounds on the expected cost of repair were 0 012 and 0 10 respectively Figure 5 5 shows how the problems are partitioned by computation time Table 5 2 shows the averages of the relative error bounds number of expan sions number of backups and computation time over the problems in each problem class This will be used as a baseline for further evaluations The troubleshooting framework has been implemented in Java and all experiments except those in Section 5 4 4Jare run on a 2 40 GHz Intel Core2 Duo P8600 CPU where the Java Virtual machine was allowed a maximum heap size of 1600 MB 5 4 Evaluation 117 Table 5 2 Average results for troubleshooting with Iterative Bounding LAO using optimal settings Problem class Error bound Expansions Backups Comp time s Trivial 0 0003 18 0 215 2 0 01 Easy 0 0009 166 6 2955 5 0 20 Intermediate 0 0009 1371 5 45414 5 4 04 Hard 0 0009 8
192. quisites for data sharing in emergency management 2007 Bj rn H gglund A Framework for Designing Constraint Stores 2007 Daniel Andreasson Slack Time Aware Dynamic Routing Schemes for On Chip Networks 2007 Magnus Ingmarsson Modelling User Tasks and Intentions for Service Discovery in Ubiquitous Computing 2007 Gustaf Svedjemo Ontology as Conceptual Schema when Modelling Historical Maps for Database Storage 2007 Gianpaolo Conte Navigation Functionalities for an Autonomous UAV Helicopter 2007 Ola Leifler User Centric Critiquing in Command and Control The DKExpert and ComPlan Approaches 2007 Henrik Svensson Embodied simulation as off line representation 2007 Zhiyuan He System on Chip Test Scheduling with Defect Probability and Temperature Considerations 2007 Jonas Elmqvist Components Safety Interfaces and Compositional Analysis 2007 H kan Sundblad Question Classification in Question Answering Systems 2007 Magnus Lundqvist Information Demand and Use Improving Information Flow within Small scale Business Contexts 2007 Martin Magnusson Deductive Planning and Composite Actions in Temporal Action Logic 2007 Mikael Asplund Restoring Consistency after Network Partitions 2007 Martin Fransson Towards Individualized Drug Dosage General Methods and Case Studies 2007 Karin Camara A Visual Query Language Served by a Multi sensor Environment 2007 David Broman Safety Security and Semantic Aspects of Equation
193. r example one de cision strategy could be to choose the action that seems to take the longest step toward solving the troubleshooting task without considering what remains to do to completely solve the task 16 33 42 79 Another strategy could be to generate a complete plan for solving the task and then select the first action in this plan 4 B9 It is also possible to make the decision based on previous experience of what decisions were taken in similar situations 43 10 Chapter 1 Background Repair B 40 130 Repair B 40 Repair A 90 Failure 25 140 Test system 1 Sys OK 75 100 Repair A 90 Repair A 90 Repair B 40 140 Test system 1 Sys OK 259 50 Figure 1 1 A decision tree for repairing two components A and B Decision nodes are shown with squares chance nodes are shown with circles and end nodes are shown with triangles Decision Trees and Look ahead Search By considering every available action and every possible action outcome we can choose an action that leads to the most desirable outcome This can be done using a decision tree 66 An example of a decision tree is shown in Figure 1 1 The decision tree has three types of nodes decision nodes chance nodes and end nodes The nodes are joined by branches that correspond to either actions or action outcomes In a decision node we can c
194. ration of vehicles is more complex than the last one and the troubleshooting task becomes more difficult for the mechanic This thesis is about computer assisted troubleshooting of automotive sys tems In computer assisted troubleshooting the person performing the trou bleshooting is assisted by a computer that recommends actions that can be taken to locate and resolve the problem To do this the computer needs to be able to reason about the object that we troubleshoot and to foresee the conse quences of performed actions Theoretical methods of doing this are developed in this thesis Troubleshooting heavy commercial vehicles such as trucks and buses is of particular interest 4 Chapter 1 Background 11 Why Computer Assisted Troubleshooting The trend in the automotive industry is that vehicles are rapidly becoming more and more complex Increased requirements on safety and environmental performance have led to many recent advances especially in the engine brak ing system and exhaust system 14 70 83 These new systems are increasing in complexity For example in addition to conventional brakes a truck may have an exhaust brake and a hydraulic braking system To reduce emissions and meet regulations the exhaust gases can be led back through the engine for more efficient combustion or urea can be mixed with the exhaust gases to reduce nitrogen emissions Such systems require additional control and since the early 1990s the number
195. rem C fail C He NE F fit Of ind C NF 3 8 The Troubleshooting Problem 53 Remove Casing P F3 rem Ol ind C NF 4 y a5 Inspect Pump P Cf fail e 3 0 2002 P Cf NF e 20 7998 7 N Repair Pump Replace Pres Sensor P Ci NF e4 1 P C amp NF el4 1 X y Fit Casing Fit Casing P Ff fite 1 P F fit el5 1 y y aoe System Stop P O ind e 0 004 P O n ind el 5 0 996 d w Replace Pres Sensor Stop P CE NF e 7 1 y Stop Figure 3 3 A troubleshooting plan for the sample system f rstora 54 Chapter 3 Troubleshooting Framework 3 3 2 Troubleshooting Cost Let 7 be a troubleshooting plan for a troubleshooting problem where the se quence of events that has occurred is e The cost of repair CR is the cost of performing a sequence of actions in 7 starting with 7 e until the stop action is encountered This yields a possibly infinite sequence of events el This sequence is not known until after the plan is executed since the events are stochastic and we cannot for certain know the outcomes of the actions in advance CR T ef Y te e nm Jas eli 3 3 where t is the time when the plan starts and 1e is an indicator function for the set Ex ie 1g e life 4 and zero otherwise The indicator function is needed because actions may generate multiple events so there may be multiple time steps between action invocations For example if an action a t
196. roblem as an SSPP Also this new stopping criterion simplifies the relaxation of certain other assumptions For example Assumption 2 re pairable components can unproblematically be relaxed since all components do not necessarily have to be repaired in the goal states The assumption that all repairs are perfect Assumption B can P be re laxed A possible model for imperfect repairs is the following Let p c be the probability that an attempted repair of a component C causes C to enter the mode c Then after a repair event C NF the transition probabilities for the component variable C in the nsDBN for troubleshooting will be P C cle 1 C NF Bns e pl c This means that the intervention on C still breaks the causal relation between C and co and the Diagnoser can still be used as described in Section 3 5 However the set of recent repair events r can no longer be deterministically determined and therefore we must also keep track its distribution Let R be a stochastic variable with the distribution P r e Bys When Assumptionis relaxed a system state will contain R instead of r and is replaced with Y P r e Bps Y P c c o r Bus bi c 3 47 rcOg ccOc 3 24 is replaced with P ef e 71 e Bus Y P e Bus yy be A P X x v r 1 c B rcOg ccOc 3 48 and 3 32 is replaced with t t 5 bie P r r lel Bus PA RA a 5 3 49 reOr d PUREE SRV e B ceOc 3 7 Relax
197. rs specifications 31 46 67 76 For a fair comparison as possible they all use the same data structures for representing states and the same methods for expanding and evaluating states The algorithms are run using a 2 40 GHz Intel Core2 Duo P8600 CPU where the Java Virtual machine is allowed a maximum heap size of 1600 MB For these algorithms the main contributors to the total computation time are the number of backups and the number of state expansions An algorithm that does many backups between expansions may select the states to expand more carefully and thereby reduce the search space while an algorithm that selects states to back up more carefully may explore a larger search space faster The algorithms are compared on problems from two sets of benchmarks publicly available in the literature In Chapter 5 we will also evaluate IBLAO for the troubleshooting problem The first set of benchmark problems is from the racetrack domain 2 which is a common benchmark problem for stochastic shortest path problems This domain has been used for empirical evaluations of many algorithms similar to Iterative Bounding LAO 31 46 67 76 Characteristic for problems from this domain is that their solutions contain many cycles the actions have unit costs the branching factor is low and that new states can be generated quickly The second set of benchmark problems are from the rovers domain which is a benchmark for probabilistic conditional non
198. s an admissible upper bound that corresponds to an executable troubleshooting plan Other actions will only be selected if they improve the upper bound within the planning horizon 5 4 Evaluation 129 Table 5 11 A comparison of the average expected cost of repairs for trou bleshooting when planning time is limited using different planning algo rithms ECR and ECR shows the best known lower and upper bounds of the optimal expected cost of repair Trivial Easy Inter Hard Very mediate hard ECR 1098 0 1146 8 1342 5 1559 0 1846 1 ECR 1097 9 1146 5 1341 7 1557 8 1822 4 wIBLAO 1s 1098 0 1146 8 1342 7 1561 3 1854 1 FRTDP 1s 1098 0 1146 8 1343 5 1564 2 1854 6 BRTDP 1s 1100 4 1146 9 1353 8 1607 8 1870 8 VPI RTDP 1 s 1100 4 1148 3 1348 5 1615 4 1874 6 ILAO 1s 1098 0 1146 9 1351 9 1623 6 1883 8 wIBLAO 10 s 1098 0 1146 8 1342 5 1559 0 1846 6 FRTDP 10 s 1098 0 1146 8 1343 4 1561 4 1850 8 BRTDP 10s 1098 0 1146 8 1342 7 1606 5 1860 6 VPI RTDP 10s 1098 0 1146 8 1342 7 1603 8 1874 0 ILAO 10s 1098 0 1146 8 1343 0 1604 6 1878 5 Not surprisingly the selection strategy based on planning performs the best However even with a short time limit of 1 second the performance is within 0 576 of the best known upper bound of the optimal ECR After a time limit of 10 seconds performance is at most 0 0376 from the upper bound of the optimal ECR When compared with ECRyang the improvement could seem to be marginal However
199. s depend on each other like building blocks This kind of dependency information can for example be drawn from some CAD models following the Standard for the Exchange of Product model data STEP ISO 10303 371147 Assumptions hold for the sample system To remove the pipe the casing must already have been removed In this case the assembled modes of the feature variables are fitted and the disassembled modes are removed If Assumptions 4 6 are true finding a necessary sequence of actions to satisfy the preconditions of any other action can be reduced to a trivial problem This is described in more detail in Section 3 6 4 3 4 3 Assumptions of the Probabilistic Model Assumption 7 nsDBN for troubleshooting A probabilistic model that is an nsDBN for troubleshooting as described in Section can correctly model the dynamics of the system Assumption 8 Persistent components The mode of a component in one time slice is dependent on its mode in the previous time slice and its mode may only change due to an intervention i e a repair or the operation of the system Assumption 8 is valid for systems where the components do not break down or self heal spontaneously unless the system is operated This means that all components can be modeled with persistent variables 58 Chapter 3 Troubleshooting Framework Assumption 9 Non persistent observations Observations are only depen dent on the state of the components or other observati
200. s model can for in stance be derived from training data using data driven methods or from a model of the physical aspects of the system such as bond graphs 65 It is also possible to combine learning techniques with the derivation of a BN from a physical model such as a set of differential algebraic equations 56 Once a BN has been derived it is possible to infer a posterior probability distribution over possible diagnoses given the observations Another technique is to use a logical model and consistency based diag nosis to first find all diagnoses that are consistent with the model and then create the posterior distribution by assigning probabilities to the consistent di agnoses from a prior probability distribution 16 For dynamic models where the behavioral mode of a component may change over time techniques such as Kalman filters or particle filters can be used to obtain the posterior probability distribution over possible diagnoses 5 B1 These methods are approximate and can often be more computationally efficient than Bayesian networks 1 3 2 The Decision Problem Once the troubleshooter knows which the possible diagnoses are it should de cide what to do next in order to take us closer to our goal of having all faults repaired Actions can be taken to repair faults or to create more observations so that candidate diagnoses can be eliminated There are different approaches to deciding which of these actions should be performed Fo
201. s observable i 0 otherwise ol ved c a ues c a if Cj is observable C 1 Laca cla otherwise Furthermore let the ordered set Z be some permutation of 1 C such 3 6 Planner 79 that Z i determines when in order the partial plan for C shall be executed Then we can define a heuristic hjxeq as c8 s if P C NF 1 forall C C givens Negveg S c fixed S co s E pie pic pi P pied pict otherwise i 3 45 where pis Y ble CP c e Oe 31 210 Cj ANF cec pi Lk C eeeO0cG NESIG 10 CjzNF cec pi Y be G ere Oc ANF cec p E ble Cf eceOcG zNEVI 1 C NF cec go r0 CAES GANE ALTO CEN cec Theorem 3 4 Let s be any system state in an SSPP for troubleshooting and let 7 be an optimal policy for the SSPP Then h xea s gt Var s Proof We begin by proving that hjxea s gt Vz s for any system state s Each partial plan i can be exited in two ways Either all components are re paired in which case we exit in a goal state or component i is repaired but more components are faulty in which case we continue with the partial plan i 1 This means that Ze is a solution to the SSPP and that Vaiva S 2 V s Assume that none of the action sequences have any collateral repair effects ie no sequence of actions will make any other repair than the intended one Then the probability that a certain path in 755 4 s is ta
202. sequence of events that can be generated from e t ie a possible outcome of a If we know for each effect of a and we iow the belief state bt then the probabilities of action outcomes can be computed as follows Using standard probability laws we get P e etH gt Mp gt P ef H Hjelt ta Mp ll a P eiti elti et Mp P c el Mp ccOc II JO ll MN 60 Chapter 3 Troubleshooting Framework Because all components are persistent and using Definitionp 8 P t lelt Mp P c e Mp b c therefore n H H H P eft ela Mp Plett ett ef Mp b 1 e 3 15 i 1 cEQc where bt i 1 is computed from b using 3 14 3 5 2 Static Representation of the nsDBN for Troubleshooting Let the probabilistic dependency model Mp be an nsDBN B where B el is the resulting BN from the events el When computing 3 14 finding P ett ci ett B eEt 1 is problematic when e t is an observation event since the observed variable may depend on component variables earlier than t 1 In it is proposed to use a smaller static BN Bt which is equivalent to the nsDBN at time t for queries of the same type as 3 12 i e P ef ett By et P e c B 3 16 The initial BN BY is the same as the initial nsDBN B As events occur the structure of the static BN is updated After a repair event C NF B isa copy of B where all outgoing non instant edges from C are removed After an operation event w
203. single uncon ditional probability of 3 16 That is the pump and or the battery are faulty with the probability 0 28 0 2 0 1 0 2 0 1 and then the engine will fail to start with probability 1 0 If neither is faulty the engine will fail to start with probability 0 05 i e 0 316 0 28 1 0 0 05 1 0 28 Interventions An intervention is when a variable is forced to take on a certain value rather than just being observed If the BN is causal we may handle interventions in a formal way 54 The variable that is intervened with becomes independent of the values of its parents e g if we break the engine its status is no longer dependent on the pump and battery since it will not start anyway When an intervention occurs a new BN is created by disconnecting the intervened vari able from its parents and setting it to the forced value In the troubleshooting scenario interventions occur when components are repaired Since repairs are a natural part of the troubleshooting process we need to handle interventions and thus use a causal Bayesian network Example 2 3 Consider a BN with the variables X that represents whether it has rained or not and Xgrass that represents whether the grass is wet or not 22 Chapter 2 Preliminaries We know that the probability for rain is 0 1 and that if it has rained the grass will be wet and otherwise it will be dry If we observe that it the grass is wet we can draw the conclusion that it
204. sion While this action is executed by the user the Planner has time to come up with the next decision We will formulate the decision problem as a Stochastic Shortest Path Problem SSPP and thereby be able to use any solver for SSPP s to find the plans on which the decisions are based upon 70 Chapter 3 Troubleshooting Framework 3 6 1 Modeling the Troubleshooting Problem as a Stochastic Shortest Path Problem The SSPP as defined in Definition 2 11 is a tuple S A p c so Sy where S is the state space A is the set of possible actions p is the transition probability function c is the cost function s is the initial state and Sy is the set of goal states The transition probability function gives the probability of having a certain action outcome in a certain state A state s S of the SSPP must contain suf ficient information so that the transition probability function can be computed efficiently Using the static representation described in Section 3 5 2 the proba bility distribution over component statuses and the probabilities of action outcomes can be computed from the belief state after the last operation event ba and a list of recent repair events r Therefore it is appropriate that the state contains this information The actions have preconditions depending on the values of the feature variables and effects that can affect the values of feature variables Therefore a state in the SSPP for troubleshooting will also spec
205. ss is a tuple S A p r where S is a state space A is a set of possible actions p S x A gt 0 1 isa transition probability function where Vs a EA fyes p s s a ds 1 and r AxS gt Risa reward function In the general case the state space and the set of possible actions may be continuous but for the application of MDP s used in this thesis we will only consider MDP s where the set of possible actions is discrete and finite The value p s s a specifies the probability that the state s is reached given that the action a is performed in state s Each state that can be reached with a non zero probability corresponds to one possible outcome of the action We will assume that each action will only have a finite number of outcomes in any state Those states that have non zero probability of being reached are specified by the the successor function Definition 2 6 Successor function The successor function is a function succ A x SH 2 such that succ a s s S p s s a gt 0 A graphical representation of a small discrete MDP with two states and two actions is shown in Figure The states are shown as nodes and state transitions as edges State transitions that correspond to the same action being performed in the same state but with different possible outcomes are shown joined with an arc Policies A decision rule for an MDP is called a policy A policy is a function 7 S gt A w
206. tcomes P elthttmalel a Mp 3 10 for each action a and action outcome e 1 Q The probability distribution over possible diagnoses given the current events is called the belief state as it represents our belief of which components pi lina are faulty 3 5 Diagnoser 59 Definition 3 4 Belief state The belief state for a troubleshooting problem C O F A Mp elt 0 Fs Cz is a function bt Oc gt 0 1 b c P c e Mp 3 11 3 5 1 Computing the Probabilities Let e be an event that can be generated from the effect et at time t Then the probability of having e given that e occurs at time t and each e Oc and all previous events el is P e c et 1 ef Mp 3 12 If we know the transition probabilities P cf ef ett Mp 3 13 for all c Oc then when an event e t is generated from an effect c the next belief state bft can be can be computed from 3 12 3 13 and the previous belief state bt as following pl c P c ttettt Mp Y p c a ext Mp P eL Mp tEOc P e e elt ett Mp P e Mp P c c eltt l M L P Y P e et ett ett1 Mp P e e t Mp E cOc P ett1 t ttl y P c c ec e E e a ae a 3 14 rae P SPE el 1 Mo b c cOc Equation is the belief state update after event e Let a be an action that is performed at time t 1 and let ef be the effects of that action Further let eft be a
207. th a new value for the modified feature F Example 3 2 Actions of Sample System Below are the actions for the sample system introduced in Section 3 1 The costs are values that reflect the time to execute the action and the costs of resources consumed when performing the action When any of the actions that repair components a4 44 or change fea ture modes 29112 are performed a single event corresponding to the effect is generated with certainty When an observing action a5 ag is performed one of two events may be generated For example if the action a7 Check Visible Leakage is performed the generated event may either be O4 no or O yes Action Precondition Effects Cost ag Stop Fy fit AE fit 0 a Repair Pump F rem repair C 150 a Replace Gasket Fy rem repair C2 15 a3 Replace Pres Sensor repair C3 100 a Fill Oil Fy fit repair Ca 20 a5 Inspect Pump F rem obs C 10 ag Check Oil Level h fit obs C4 10 az Check Visible Leakage F1 rem AF fit obs O 10 ag Test System F fit obs O3 40 ag Remove Casing F fit Fi rem 25 aig Fit Casing Fi rem Fy fit Fy fit 25 a11 Remove Pipe Fy rem Fy fit Fo rem 40 412 Fit Pipe F gt rem F fit 40 50 Chapter 3 Troubleshooting Framework 3 2 2 Probabilistic Dependency Model The probabilistic dependency model provides a model for the distributions P C
208. th the calculation of the fringe itself as shown in Algorithm 6 and does not increase the computational complexity of finding the fringe We then select those states that have an impact higher than the average e s p s gt Yes I CA 4 6 s eG 4 1 Iterative Bounding LAO 99 Algorithm 6 Algorithm for calculating the set G7 and the likelihoods f s for all states s G7 1 procedure FINDFRINGE G7 Ng Es 2 for each s V7 do p s 0 3 so 1 4 O 9 5 queue so 6 while queue has elements do 7 s first element in queue 8 for each s succ s 71 s do 9 f s p s P s P s s ru s 10 if s gt then 11 if s has successors then add s to queue 12 else 13 add s to 14 end if 15 end for 16 end while 17 end procedure 4 1 4 Weighted Heuristics Just as with A and LAO weighting the heuristic allows Iterative Bounding LAO to make a trade off between solution quality and the size of the ex plored search space A separate evaluation function fw is used for the weighted heuristic For unexpanded states s f s wh s where the weight w gt 1 Using this evaluation function a third policy 75 is defined where TT s arg min Ty fw s acA When a state s is backed up fw is updated as f s Tz 5 fw s During search instead of expanding states in G states are expanded from the solution graph of the weighted policy G7
209. tially the set of constraints Y consists of one constraint a V1 for every action a A where V s r a s for every state s A We can compute the next set of constraint Yr 1 from a previous set of constraints Yr and thereby obtain optimal policies of any length Let Yr be a function O Yr and let Oy be the set of all possible such functions The next set of constraints Y7 can then be obtained from the previous one by adding a constraint a Vr 1 for every a A and every Vr Oy where Vrai r a s y Y w o s a Y pls s a Vr 0 s ocO s esucc a s By letting T oo the expected reward for an optimal infinite horizon POMDP policy can be approximated with arbitrary precision If this is done lor 3 naively the size of Yr would be A 0 1 However not every constraint in Yr is needed Every constraints that is dominated by some other constraint in each point in b B can be removed State of the art POMDP solvers vary in the way in which they remove con straints from Y r For example Point Based Value Iteration PBVI 59 removes all constraints that are dominated by some other constraint in a limited set of belief states in the belief space This is an approximation because a removed constraint could be the dominating constraint in belief states outside this lim ited set of belief states Another algorithm Heuristic Search Value Iteration HSVI 75 removes only those constraints that are point wise dom
210. tion time in seconds or weighted Iterative Bounding LAO using different lower bound heuristics Algorithm Problem Expan Backups Comp No of class sions time s problems hoomb Trivial 18 0 215 2 0 01 12 12 Easy 166 6 2955 5 0 20 12 12 Intermed 1371 5 45414 5 4 04 11 11 Hard 8211 1 343506 1 33 08 10 10 Very hard 42151 6 2850716 2 238 49 9 11 hj Trivial 18 8 229 0 0 02 12 12 Easy 174 4 3191 1 0 23 12 12 Intermed 1508 5 50377 4 4 82 11 11 Hard 8761 1 367878 8 37 69 10 10 Very hard 44611 2 29162544 269 29 9 11 hent Trivial 1085 0 169837 8 1 56 12 12 Easy 16569 6 3200774 3 37 94 12 12 122 Chapter 5 Case Study Hydraulic Braking System the problems that were solved with all algorithms No values are shown for the very hard problem class because none of the other algorithms were able to solve a single problem in that problem class The results show a significant difference in performance between Itera tive Bounding LAO and the other algorithms As for the problems from the Rovers domain described in Section 4 2 2 the deep trials of the RTDP based algorithms are inefficient for the troubleshooting problems The RTDP based algorithms explore deep into areas of the search space that can be proven to be suboptimal through a more shallow search ILAO expands creates a complete policy before it backs up and therefore it may also search in suboptimal areas of the search space longer than necess
211. to demonstrate some of the concepts of the modeling inference and planning in the troubleshooting framework The example will be incrementally expanded as more concepts are 45 46 Chapter 3 Troubleshooting Framework Pressure m e Oil Level Pump Leakage A Gasket Figure 3 1 Schematic of example system introduced In the sample system Figure B 1 oil is pumped through a pipe connected to a smaller pipe through a gasket The system includes an oil pressure sensor and a dipstick to check the oil level There are four different faults which may cause the system to fail In case of a pump failure nominal pressure cannot be maintained This will also happen if the oil level is too low In case of a leaking gasket the oil level will fall However the oil level can also be low for other unknown reasons Leaking oil from a faulty gasket may or may not be visible on the outside of the pipe When the pressure is low a low pressure alarm is raised This alarm will also be triggered in case of a fault in the pressure sensor A mechanic that is troubleshooting this system may repair the system by re filling the oil repairing the oil pump or replacing the gasket or the oil pressure sensor Also the mechanic may gain additional information of the system by observing the oil level searching for a visible leakage or inspecting the pump To reach the pipe an outer protective casing must be removed This must be done before performing
212. transfer within an organisation 1999 H kan Nilsson Informationsteknik som drivkraft i granskningsprocessen En studie av fyra revisionsbyr er 2000 Erik Berglund Use Oriented Documentation in Software Development 1999 Klas Gare Verksamhetsf r ndringar i samband med IS inf rande 1999 Anders Subotic Software Quality Inspection 1999 Svein Bergum Managerial communication in telework 2000 Flavius Gruian Energy Aware Design of Digital Systems 2000 Karin Hedstr m Kunskapsanv ndning och kunskapsutveckling hos verksamhetskonsulter Erfarenheter fran ett FOU samarbete 2000 Linda Asken s Aff rssystemet En studie om teknikens aktiva och passiva roll i en organisation 2000 Jean Paul Meynard Control of industrial robots through high level task programming 2000 Lars Hult Publika Gr nsytor ett designexempel 2000 Paul Pop Scheduling and Communication Synthesis for Distributed Real Time Systems 2000 G ran Hultgren N tverksinriktad F r ndringsanalys perspektiv och metoder som st d f r f rst else och utveckling av aff rsrelationer och informationssystem 2000 Magnus Kald The role of management control systems in strategic business units 2000 Mikael C ker Vad kostar kunden Modeller f r intern redovisning 2000 Ewa Braf Organisationers kunskapsverksamheter en kritisk studie av knowledge management 2000 Henrik Lindberg Webbaserade aff rsprocesser M jligheter och begr nsningar
213. ulty behavior is modeled explicitly or if components may have more than two behavioral modes 17 all possible diagnoses can be represented by a set of partial diagnoses Frameworks for diagnosis such as the General Diagnostic Engine GDE 16 or Lydia can compute such sets of characterizing diagnoses either exactly or approximately Consistency based diagnosis using logical models have been shown to perform well for isolating faults in static systems such as electronic circuits 41 Control Theoretic Approach In the control theoretic approach the system is modeled with Differential AI gebraic Equations DAE 7 77 As many laws of physics can be described using differential equations precise physical models of dynamical systems can be created with the DAE s Each DAE is associated with a component and typ ically the DAE s describe the components behavior in the non faulty case 7 When the system of DAE s is analytically redundant i e there are more equa tions than unknowns it is possible to extract diagnostic information 77 If an equation can be removed so that the DAE becomes solvable the component to which that equation belongs is a possible diagnosis These methods depend on accurate models and have been successful for fault detection in many real world applications 36 63 Recently efforts have been made to integrate methods for logical models with techniques tradition ally used for fault detection in physical models 13
214. urpose of diagnosis can be fault detection or fault isolation For fault detection we are satisfied with being able to discriminate the case where no component is faulty from from the case where at least one component is faulty Often it is important that the detection can be made as soon as possible after the fault has occurred 35 For fault isolation we want to know more specifically which diagnoses are possible Sometimes it is not possible to isolate a single candidate and the output from diagnosis can be all possible diagnoses 18 a subset of the possible diagnoses 26 or a probability distribution over all possible diagnoses 56 81 Consistency Based Approach A formal theory for consistency based diagnosis using logical models is first described by Reiter 61 Each component can be in one of two or more behav ioral modes of which one is nominal behavior and the others are faulty behav iors The system model is a set of logical sentences describing how the compo nents inputs and outputs relate to each other during nominal and faulty be havior A possible diagnosis is any assignment of the components behavioral modes that is consistent with the system model and the information available in the form of observations 8 Chapter 1 Background The set of all possible diagnoses can be immensely large However it can be characterized by a smaller set of diagnoses with minimal cardinality if faulty behavior is unspecified 15 If fa
215. using the rules described in Section 5 3 Only feature events affect 3 6 Planner 71 the feature variables therefore in this case f f4 The initial state sg corre sponding to a troubleshooting problem Ip M 0 go is bwo ro fo where bwo c P C ej Mp for all c Oc and r 0 An action a may have multiple effects which are treated in sequence There fore each outcome of an action with k effects is a sequence of events e e1 x Lets bwi ri fi be the state that is reached when the event e occurs in the states 4 bwi 1 rj 4 fj 1 Further let s sj be the system state that is reached from the state s sg given e Then using Corollary 3 1 we can compute the value returned by the transition probability function p s s a as p sj s070 E bwis e E Plele xi Pelle e B i l c The successor function succ a s defined in Definition 2 6 gives the set of system states that can be reached with the action a from the system state s with non zero probability If the precondition of an action a is not fulfilled in a state s p s s a 0 for all states s 4 s This means that the action will not affect the system state because it cannot be executed Actions The set of actions for the troubleshooting problem and the SSPP are the same Because of the preconditions some actions will have no effect in certain states and they may never be part of any optimal troubleshooting plan
216. utomatic Climate Control system Bayesian Network Bounded Real Time Dynamic Programming Case Based Reasoning Cost of Repair Conditional Probability Distribution Conditional Probability Table Differential Algebraic Equations Directed Acyclic Graph Dynamic Bayesian Network Discrete Event System Diagnostic Trouble Code Expected Cost of Repair Electronic Control Unit Focussed Real Time Dynamic Programming General Diagnostic Engine Heuristic Search Value Iteration Iterative Bounding LAO Improved LAO Algorithm for solving cyclic AND OR graphs Markov Decision Process Non stationary Dynamic Bayesian Network 147 148 NF OBD PBVI POMDP RTDP SSPP VPI RTDP wIBLAO Appendix B Acronyms Not Faulty On Board Diagnosis Point Based Value Iteration Partially Observable Markov Decision Process Real Time Dynamic Programming Stochastic Shortest Path Problem Value of Perfect Information Real Time Dynamic Programming Iterative Bounding LAO using a weight function C The Retarder Model File The format for the retarder model file is in an adapted form of the MSBN format for describing Bayesian networks 25 trouble network Scania Retarder Auxiliary Braking System Components node FC name System status category nonpersistent type discrete 2 Not faulty Faulty Y node C01 4 name Filter oil cooler category persistent type discrete 2 Not faulty clogged Y nod
217. we want to be able to use all available computation time Modeling the problem as an MDP works well together with a Bayesian diagnostic model In this thesis we have a framework for troubleshooting where the trou bleshooter consist of two parts a Planner and a Diagnoser The Planner and the Diagnoser interact to produce recommendations to the user The Diagnoser is responsible for finding the possible diagnoses and the Planner is responsi ble for deciding which action should be performed next A schematic of the troubleshooting framework is shown in Figure 1 2 The user informs the troubleshooter which actions have been performed on the system and what observations have been seen Given this information the Troubleshooter recommends an action to perform next The Troubleshooter uses the Diagnoser to find out what diagnoses are possible and the Planner to create a partial conditional plan of actions that minimizes the ECR given the possible diagnoses During planning the Planner will use the Diagnoser to estimate possible future states and the likelihoods of observations After planning the Troubleshooter will recommend the user to perform the first action in the plan created by the Planner This could be an action that gains more information replaces suspected faulty components or in some other way affects the system When the Planner creates its plans it is under time pressure All time that is spent computing while the user is idling contri
218. where V s Vi s lt e in all states s for an arbitrary small e gt 0 The Value Iteration algorithm is shown below as Algorithm I A function f S gt R called the value function approximates the expected reward of the policy 71 that is returned from the algorithm The value function holds a value for each state and each value is initialized with an arbitrary initial guess as given by the function h S R In each iteration through the lines the values in f will converge further toward the optimal expected reward function V The operation in Mun of updating the value of f for a state s is called a backup of state s In line 12 a policy 7 is created that is greedy in the value function Clearly if f s V7 s for all s S then line 12 is the same as and zr is optimal When the largest change A in the value function for any state after an iteration is smaller than e 1 y 2y then it can be shown that V s VI s lt e for all states s 60 The closer the initial guess is to real optimal expected cost the faster Value Iteration will converge The states are backed up an equal number of times De pending on the order in which the states are backed up convergence toward an optimal policy can be faster or slower It is possible to construct algorithms that are similar to Value Iteration and that back up certain states in the value function more often than other states To guarantee that the value function converges toward
219. with Open Source and Industrial Software 2003 Daniel Karlsson Towards Formal Verification in a Component based Reuse Methodology 2003 Anders Hjalmarsson Att etablera och vidmakth lla f rb ttringsverksamhet behovet av koordination och interaktion vid f r ndring av systemutvecklingsverksamheter 2004 Pontus Johansson Design and Development of Recommender Dialogue Systems 2004 Charlotte Stoltz Calling for Call Centres A Study of Call Centre Locations in a Swedish Rural Region 2004 Bj rn Johansson Deciding on Using Application Service Provision in SMEs 2004 Genevieve Gorrell Language Modelling and Error Handling in Spoken Dialogue Systems 2004 Ulf Johansson Rule Extraction the Key to Accurate and Comprehensible Data Mining Models 2004 Sonia Sangari Computational Models of Some Communicative Head Movements 2004 Hans N ssla Intra Family Information Flow and Prospects for Communication Systems 2004 Henrik S llberg On the value of customer loyalty programs A study of point programs and switching costs 2004 Ulf Larsson Designarbete i dialog karakt risering av interaktionen mellan anv ndare och utvecklare i en systemutvecklingsprocess 2004 Andreas Borg Contribution to Management and Validation of Non Functional Requirements 2004 Per Ola Kristensson Large Vocabulary Shorthand Writing on Stylus Keyboard 2004 P r Anders Albinsson Interacting with Command and Control Systems Tools for Operators and
220. y Identification of Fault Prone Modules 1996 Mikael Ericsson Commenting Systems as Design Support A Wizard of Oz Study 1996 J rgen Lindstr m Chefers anv ndning av kommunikationsteknik 1996 Esa Falkenroth Data Management in Control Applications A Proposal Based on Active Database Systems 1996 Niclas Wahll f A Default Extension to Description Logics and its Applications 1996 Annika Larsson Ekonomisk Styrning och Organisatorisk Passion ett interaktivt perspektiv 1997 Ling Lin A Value based Indexing Technique for Time Sequences 1997 Rego Granlund C Fire A Microworld Supporting Emergency Management Training 1997 Peter Ingels A Robust Text Processing Technique Applied to Lexical Error Recovery 1997 Per Arne Persson Toward a Grounded Theory for Support of Command and Control in Military Coalitions 1997 Jonas S Karlsson A Scalable Data Structure for a Parallel Data Server 1997 Carita bom Videom testeknik i olika affarssituationer m jligheter och hinder 1997 Tommy Wedlund Att skapa en f retagsanpassad systemutvecklingsmodell genom rekonstruktion v rdering och vidareutveckling i T50 bolag inom ABB 1997 Silvia Coradeschi A Decision Mechanism for Reactive and Coordinated Agents 1997 Jan Ollinen Det flexibla kontorets utveckling p Digital Ett st d f r multiflex 1997 David Byers Towards Estimating Software Testability Using Static Analysis 1997 Fredrik Eklund Declarative Error Diag
221. y belong to M and for every states NA Sg and every action a A let the states in succ a s also belong to V Also add to one outgoing edge s succ s a that leads from s to the states in succ s a This results in a graph where all leaves are goal states Figure 2 6 a shows an example of such an AND OR graph The hyperedges are shown as arrows 36 Chapter 2 Preliminaries Algorithm 2 Real Time Dynamic Programming 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 procedure RTDP SSPP h Tstop T tria1 G f so h so to E CPU time while CPU time to lt Tstop do RUNTRIAL so CPU time end while return 7r end procedure procedure RUNTRIAL s t if s G then EXPAND s DOBACKUP s s Es p s m s if s Sg ACPU time t lt T iq then RUNTRIAL s to DOBACKUP s end procedure procedure EXPAND s G GU s for each a A s succ a s do f s h s end procedure procedure DOBACKUP s f s minaca Taf s m s argmin lt 4 Taf s end procedure 2 3 Markov Decision Processes 37 ay lt 0 ay so a1 A e a2 a a2 a EO a The search graph G of a small SSPP b A solution graph Gz for G ay 50 HE e A a2 p C c A subgraph G C G d A solution graph G fpor G where all grap graph Or leaves are also leaves in G thus G7 is also a solution graph for G Figure
222. y must be accounted for This will cost at least H s Ecco b c H c mingea cg a This heuristic can be computed in time linear in the size of the belief state In Section 5 4 we shall see that using this heuristic instead of hj or hent im proves the performance of the Planner Example 3 6 Consider the sample system that is described in Section B 1 and modeled in Section B 2 After making the action ag and the observation Oz indicating a system state s bw r f is reached where r f fit fit and b c c c f 0 0 0 124 200 0 145 0 295 0 500 100 c1 C2 C3 4 NF NF NF NF failure NF NF NF NF leakage NF NF failure leakage NF NF INF NE failure NF failure NF failure NF 5 0 1074 300 NF leakage failure NF 0 245 failure leakage failure NF 0 395 INF NF NF low 0 249 20 failure NF NF low 2 5 107 220 NF leakage NF low 1 2 107 165 failure leakage NF lo 8 0 107 315 NF NE failure low 0 0010 120 ailure NF failure low 1 0 1076 320 NF leakage failure low 5 0 1074 265 failure leakage failure low 5 0 1077 415 o S In this state the 1 heuristic would yield the value 60 corresponding to the repair of C4 using 42 followed by an observation of O3 using ag and having the outcome Os not indicating The entropy in this state H
223. zine Special Issue on Human Centered Robotics and Dependability 2004 82 Volvo Trucks Volvo adds EGR exhaust gas recirculation to its successful 13 litre engine series Press release http www volvotrucks com 2007 83 Volvo Trucks New Volvo I Shift saves fuel Press release http www volvotrucks com 2009 84 Volvo Trucks Service and maintenance agreements Retrieved from http www volvotrucks com trucks global en gb trucks services November 2010 85 H kan Warnquist Mattias Nyberg and Petter S by Troubleshooting when action costs are dependent with application to a truck engine In Proceedings of the 10th Scandinavian Conference on Artificial Intelligence SCAT 08 2008 86 H kan Warnquist Jonas Kvarnstr m and Patrick Doherty Planning as heuristic search for incremental fault diagnosis and repair In Proceedings of the 2nd Scheduling and Planning Applications woRKshop SPARK 09 2009 87 H kan Warnquist Jonas Kvarnstr m and Patrick Doherty Iterative Bounding LAO In Proceedings of the 19th European Conference on Artifi cial Intelligence ECAI 10 2010 88 H kan Warnquist and Mattias Nyberg A Heuristic for Near Optimal Troubleshooting Using AO In Proceedings of the 19th International Work shop on the Principles of Diagnosis DX 08 2008 89 H kan Warnquist Anna Pernest l and Mattias Nyberg Modeling and Troubleshooting with Interventions Applied

Computer-Assisted Troubleshooting for Efficient Off-board

Contents

Download Pdf Manuals

Related Search

Related Contents