A∗ Wars: The Fight for Improving A∗ Search for Troubleshooting
Contents
1. lt BOLD on pini P an gt a OF ae TDP f Cas TP I Sr Pole S Polt i I P b i 2 j 1 eco 6 7 cay PPI 1 P b2 f P b1 f z 1 _ P b f j l i a L P218 Pbl z 1 A P b f j 1 1 as required This is not surprising if we look at the expression inside the parenthesis of Equa tion 6 the corresponding events are B fixes f Bg fixes f if B did not fix f etc up to none of the actions fixed f These events form a sample space When x 1 then Ca P a f Ca so in all cases lt Ca which completes the proof Remark It is quite straightforward to show that ECR is not monotone when the model in cludes questions 3 Pruning based on efficiency and ECR We recently investigated the effect of a prun ing method based on efficiency Ottosen and Jensen 2008 By considering two adjacent actions in an optimal troubleshooting sequence the following has been proved about the effi ciency Jensen et al 2001 Theorem 3 Lets Aj An be an opti mal sequence of actions with independent costs Then it must hold that ef Ajje gt ef Ainle for alli 1 n 1 In Figure 2 it is illustrated how the theorem can be used for pruning If we have the order ef Ai gt ef A2 gt ef A3 at the root we know that A3 should never be the first action Fur thermore after performing A we2. f and the efficiencies of the two actions are 0 9 and 0 8 respectively We get ECR eUf SHORE UE ECR Aj A2 Ca Pa f Cas 1 01 1 11 Not only is ECR easy to compute it also has the following property Vomlelova and Vom lel 2003 Theorem 1 Under Assumption 2 4 the heuris tic function ECR is admissible that is ECR e lt ECR e Ve E For a class of heuristic functions A is guaran teed to have found the optimal path to a node when the node is expanded Hart et al 1968 Definition 5 A heuristic function h is mono tone if h n lt e n m h m whenever m is a successor node of n Remark Monotonicity is equivalent to the often used and seemingly stronger consistency prop erty h n lt c n m h m Vn m Henceforth we let A denote the performed action on the edge from a node n to a successor node m in the search graph Proposition 1 For the heuristic function ECR under Assumption 1 and 4 monotonicity is equivalent to ECR e lt Ca P a e ECR e Proof We have c n m P e Ca and P e P an e P e and so the common factor P e cancels out Theorem 2 Under Assumption 1 4 the heuris tic function ECR is monotone Proof The idea is to express ECR e in terms of ECR e To do that we consider the complement of the set fa A which is the set of all faults that A cannot fix For
3. gt ef Agl e gt ef Ag e Theorem 3 implies that we can prune the nodes ending in a square and so we are left with only three pos sible sequences Ay A2 A3 Ai A3 A2 and Ag A3 A1 After A has discovered the last node in these three sequences the three paths are subject to coalescing NP hard However A still has difficulties in finding a solution for models with much lower average dependency that is the average size of fa over all actions Remarkably enough we found that when the average dependency went down from 3 towards 1 then the running time increased many times In the following we de scribe a hybrid method for models with an av erage dependency well below 3 Figure 3 shows an example of the search tree explored by A in our hybrid approach Near the root node A is often forced to create a branch for each successor node However as we get closer to the goal nodes branching is more likely to be avoided The branching can be avoided O SO ne hey O me aS mae O O Q O Sage Q O O O O O Figure 3 An example of what the search tree looks like in our hybrid approach For some nodes the normal A branching is avoided and near goal nodes this branching is almost avoided for all nodes We can see that it might happen that the algorithm has to investigate all successors of a node even though the path down to that node was explored without branching because we are able to determine the op
4. know that A should never be the second action We call this efficiency based pruning In summary the theorem was very easy to ex ploit during the expansion of a node by keeping the actions sorted with respect to efficiency and by passing that information in the parent node However the results where a bit disappointing since it only gave a speed up of a factor of 2 4 We have since then tried to extend the idea by considering three adjacent actions instead of two We call this ECR based pruning Figure 2 shows an overview of the pruning process If we consider an arbitrary subset of three actions Ay A2 and A3 we would normally need to com pare six different sequences However if we have calculated the efficiencies of the three actions at the local root node with evidence e Theo rem 3 leaves us with only three possible candi dates After the three sequences are expanded the paths are coalesced into a single node in the search graph Now imagine that A is about to expand A3 in the sequence A1 A2 A3 We determine if the current node expansion is optimal by comparing it with the ECR of the sequence A2 A3 A1 There is no need for comparing Ai A2 A3 with A1 A3 A2 since Theorem 3 has pruned the latter If we expand the se quence A2 A3 A1 first the analysis is similar and we compare with the best of the two other sequences again the best sequence is found by applying Theorem 3 There is no way to avoid ca
5. A Dep Time 3 0 33 56 11 48 12 27 2 9 42 11 12 42 21 97 2 8 62 14 15 08 27 52 2 7 45 03 14 38 21 61 2 6 29 86 10 20 12 39 2 5 86 52 22 20 29 61 2 4 31 55 12 39 12 00 2 3 65 19 19 11 21 28 2 2 80 56 21 28 29 38 2 1 50 28 18 72 9 78 2 0 83 75 27 70 20 05 1 9 62 88 16 77 10 64 1 8 127 59 35 09 18 72 1 7 102 17 25 36 14 42 1 6 133 17 39 14 25 41 1 5 122 08 27 59 0 92 1 4 164 84 41 16 4 25 1 3 139 89 39 44 0 13 1 2 168 42 38 13 0 00 1 1 160 42 39 42 0 00 1 0 159 95 38 08 0 00 5 Discussion We originally investigated Theorem 2 because monotonicity plays an important role in promis ing bidirectional A methods Kaindl and Kainz 1997 However a bidirectional A for trouble shooting is very difficult because there is no ap parent way to start a search from the goal nodes using ECR The hybrid A approach seems very promis ing We still need to determine how large a de pendency set that it pays off to solve We ex pect that it will be most beneficial to solve small dependency sets by brute force whereas depen dency sets of medium size can be solved by a recursive call to hybrid A Acknowledgements We would like to thank the reviewers for their valuable and detailed feedback References Rina Dechter and Judea Pearl 1985 Generalized best first search strategies and the optimality af a J ACM 32 3 505 536 P E Hart N J Nilsson and B Raphael 1968 A formal basis for the heur
6. A Wars The Fight for Improving A Search for Troubleshooting with Dependent Actions Thorsten J Ottosen and Finn V Jensen Department of Computer Science Aalborg University 9220 Aalborg Denmark Abstract Decision theoretic troubleshooting combines Bayesian networks and cost estimates to ob tain optimal or near optimal decisions in domains with inherent uncertainty We use the well known A algorithm to find optimal solutions in troubleshooting models where dif ferent actions may fix the same fault We prove that a heuristic function proposed by Vomlelov and Vomlel is monotone in models without questions and we report on recent work on pruning Furthermore we experimentally investigate a hybrid approach where A is combined with a method that sometimes avoid branching The method is based on an analysis of the dependency between actions as suggested by Koca and Bilgic 1 Introduction Imagine that you have a device which has been running well up to now but suddenly it is mal functioning A set of faults F describes the pos sible causes to the problem To fix the problem you have a set A of actions which may fix the problem and a set Q of questions which may help identifying the problem Each action or question S has a positive cost Cg e possibly depending on evidence e Your task is to fix the problem as cheaply as possible In this paper we do not consider questions When actions in a model can remedy sets of faults that ove
7. each f F fa An Bayes rule conditioned yields 1 P f Pale because P a e Uf 1 If we restrict ECR to a subset of faults X we shall abuse notation and write it P fle fEex ECR e ECR e Uf In particular we must have ECR 2 ECR e F fa An ECR e fa An We can furthermore define AF ECR e F fa An ECR e F fa An which is an extra cost because all faults in F fa A are more likely Similarly Afa An ECR e fa An ECR e fa An is the cost lost or gained because A has been performed and can no longer repair the faults fa A We can then express ECR e by ECR ECR Afa An AF 3 The constant ECR factors implies AF P fle fe F fa An P f e ECR e Uf Exploiting Bayes rule as explained above and Equation 2 we get AF Leste 1 ECR F fa An eatery 1 ECR e ECR e fa An Inserting into Equation 3 yields ECR ECR ECR e fa An ECR e fa An 1 i REA 7 ECR e ECR e fa An _ ECR e a Pla jer EORale fa An Bia feny ERE lAn and we rearrange the equation into ECR P man e ECR e ECR fa An A P an e ECR fa An By Proposition 1 we have to prove A lt Ca Because of Bayes rule and A
8. istic determination of minimum cost paths IEEE Trans Systems Sci ence and Cybernetics SSC 4 2 100 7 Finn V Jensen Uffe Kj rulff Brian Kristiansen Claus Skaanning Jiri Vomlel and Marta Vom lelov 2001 The sacso methodology for trou bleshooting complex systems Artificial Intelli gence for Engineering Design Analysis and Man ufacturing 15 321 333 J Kadane and H Simon 1977 Optimal strate gies for a class of constrained sequential problems The Annals of Statistics 5 237 255 Hermann Kaindl and Gerhard Kainz 1997 Bidi rectional heuristic search reconsidered Journal of Artificial Intelligence Research 7 283 317 Eylem Koca and Taner Bilgi 2004 A trouble shooting approach with dependent actions In Ramon L pez de M ntaras and Lorenza Saitta editors ECAI 2004 16th European Conference on Artificial Intelligence pages 1043 1044 IOS Press Thorsten J Ottosen and Finn V Jensen 2008 Better safe than sorry optimal troubleshooting through A search with efficiency based pruning In Proceedings of the Tenth Scandinavian Confer ence on Artificial Intelligence pages 92 97 IOS Press M Vomlelova and J Vomlel 2003 Troubleshoot ing Np hardness and solution methods Soft Computing Journal Volume 7 Number 5 pages 357 368 Marta Vomlelova theoretic troubleshooting 18 2 267 277 2003 Complexity of decision Int J Intell Syst
9. lculating the full ECR of both sequences and we have to traverse the search graph down to the root and up to the first node of the second path Furthermore this traversal means that we have to store child pointers in all nodes and we also need to keep all expanded nodes in memory This more than doubles the memory requirement In conclusion the method turned out to slow down A In a model with 19 action and 19 faults Theorem 3 pruned 989k nodes whereas the ECR based pruning prevented a mere 3556 expansions out of about 41k possible Theorem 2 also explains why the effect of the pruning is so small if A is guided by a mono tone heuristics and expands a node then the op timal path to that node has been found Hart et al 1968 This means that the sub trees out lined with dotted edges in Figure 2 are never explored unless we really need to explore them Should we discover a non optimal sequence first that path is not explored further until coalescing happens 4 An A hybrid approach Troubleshooting with dependent actions was proved NP hard by reduction from the exact cover by 3 sets problem Vomlelov 2003 Therefore troubleshooting in models where each action can repair three or more faults is Figure 2 An overview of the pruning process for any subset of three actions At the root of the subtree we have evidence e and the actions are sorted with respect to efficiency and we have ef Ai e
10. lgo rithm The cost of the shortest path from s to n is denoted g n and from n to t it is denoted h n Finally the evidence gathered about actions from s to n is denoted e e C e Definition 3 A heuristic function h is ad missible if h n lt h n Vn When A is guided by an admissible heuristic function it is guaranteed to find an optimal so lution Hart et al 1968 Vomlelova and Vomlel 2003 have sug gested the following heuristic function for use in troubleshooting Definition 4 Let denote the set containing all possible evidence The function ECR gt RT is defined for each e as ECR e nS P e fEF Remark In Vomlelov and Vomlel 2003 the factor P e is left out However the factor ensures that the decomposition in Equation 1 takes the simple form f n ECR e ECR e SS g n h n where ECR e is the ECR for the sequence defined by the path up to n We also define ECR e XC P f e ECR e Uf fEF The optimal cost ECR e U f is easy to cal culate under Assumption 2 4 the optimal se quence is found by ordering the actions in A f e with respect to descending efficiency Kadane and Simon 1977 Example 2 Assume the fault f can be repaired by two actions A and Ag and that P a f 0 9 and P ag f 0 8 Furthermore let both actions have cost 1 Since instantiating the fault node renders the actions conditionally indepen dent P a e Uf P a
11. ng a node if the most efficient action belongs to a dependency set of such a small size we find the first action in that de pendency set If the dependency set consists of one or two actions this calculation is trivial If the dependency set has three actions we find the first by comparing the three candidate se quences as we discussed in Section 3 Otherwise we simply expand the node as usual by inspect ing all successors Table 4 shows the results of three versions of A We can see that the hybrid approach is somewhat slower for models with an average dependency between 2 and 3 This is because the hybrid approach spends time investigating the size of the dependency set of the most ef ficient action but it rarely gets to exploit the benefits of a small dependency set For an aver age dependency between 2 1 and 1 6 the hybrid approach becomes superior and below 1 6 it be comes very fast Table 1 Results for the hybrid approach in models with 20 actions and 20 faults The aver age dependency ranges between 3 and 1 and each action is usually associated with 1 to 3 faults The time is measured in seconds A is A with coalescing pruning A is A plus efficiency based pruning and hybrid A is the hybrid approach based on pruning A Al ready at an average dependency around 2 1 we see that the hybrid method wins Method A pruning A hybrid
12. odel with dependent actions We have some initial evi dence and in the course of executing actions we collect further evidence We write ef to de note that the first i actions have failed e C et and we have by assumption P e 1 because fi fy fs f4 a3 F 0 20 0 25 0 40 0 15 Figure 1 Left a simple model for a troubleshooting scenario with dependent actions The dotted lines indicate that the faults f to f4 are states in a single fault node F A1 A2 and Ag represent actions and parents of an action node A are faults which may be fixed by A Right the quantitative part of the model the device is faulty When action A has failed we write A 7a whereas A a means that it has succeeded We often abbreviate P A a as P 7a The presence of the fault f is written F f but we often abbreviate the event sim ply as f Furthermore we write P e Uf when we really had to write P e U f The set of faults that can be repaired by an action A is denoted fa A For example in Figure 1 we have fa A2 f2 f3 In models where actions can have P ale 1 fa is a dynamic en tity which we indicate by writing fa e The set of remaining actions is denoted A e and A fle C Ale is the set of remaining actions that can fix f When there are no questions a trouble shooting strategy is a sequence of actions s Ai An prescribing the process of re peatedly perf
13. orming the next action until the problem is fixed or the last action has been per formed To compare sequences we use the fol lowing definition Definition 1 The expected cost of repair ECR of a troubleshooting sequence s Ai An with costs Ca is the mean of the costs until an action succeeds or all actions have been performed ECR s S Ca e P e i 1 We then define an optimal sequence as a se quence with minimal ECR Also ECR is the ECR for an optimal sequence of the actions A e given e Example 1 Consider a sequence for the model in Figure 1 ECR A2 A3 A1 Ca P a2 Ca P a2 7a3 Ca Ca P ag Ca P az G P a3 a2 Ca is 7 4 14 14 5 1 1 55 Tay e A crucial definition is that of efficiency Definition 2 The efficiency of an action A given evidence is P A a Ca e 2 Monotonicity of the heuristic function ECR A and AO is a best first search algorithm that works by continuously expanding a fron tier node n for which the value of the evaluation function f n g n h n 1 is minimal until finally a goal node t is ex panded The cost between two nodes n and m m reachable from n is denoted e n m and the function g n is the cost from the start node s to n whereas h n is the heuristic function that guides or misguides the search by estimating the cost from n to a goal node t ef Ale If h n 0 A degenerates to Dijkstra s a
14. rlap we say that the model has dependent actions Finding an optimal solution in models with dependent actions is of great practical importance since dependent actions can be expected to occur in many non trivial do mains However all non trivial troubleshooting scenarios have been shown to be NP hard this includes models with dependent actions Vom lelova 2003 Two different approaches have previously been used for finding optimal strategies Jensen et al 2001 describes a branch amp bound algo rithm whereas Vomlelov and Vomlel 2003 de scribes an AO algorithm The AO algorithm can be used for models with questions but since a model without questions does not lead to AND nodes in the search tree we only need to consider the simpler A algorithm Hart et al 1968 Dechter and Pearl 1985 for models with dependent actions We can summarize our troubleshooting as sumptions as follows Assumption 1 There are no questions Assumption 2 There is a single fault present when troubleshooting begins This implies that we can have a single fault node F with states f F Assumption 3 Actions are conditionally in dependent given evidence on the fault node Assumption 4 The cost of actions Ca e is independent from evidence e We use the following notation The model provides for all A A and f F probabili ties P f e P A and P A f where is evi dence In Figure 1 is shown a simple m
15. ssumption 3 we have P an e P e P an f Ple P a n e P fle P an e P a f So we get a gt f fa An ECR e Uf P fje P an f ECR e u f 5 Because of the single fault assumption we only need to prove that lt Ca We now index the actions in A f e as follows P B b f 3 P Biy1 Cpg g Cp i bi 1 f i 1 Vi In this ordering we have An Bz The inequal ities generalizes to P B b f ee P B b f Cp Vj gt i 4 In particular this is true for j x which we shall exploit later Assume we have N dependent actions in A f e The first term of is then By N t 1 Cp 2o Cs J PCb If 5 i 2 j 1 Assume that x gt 1 we shall deal with 1 later then the second term of 6 is ECR e Uf ECR Bj P a f ECR e U f P an f ECR P an f x l1 i 1 Cp af 2 Cae Ul P b f ae z Cp I p PCab 4 1 Pea j E Bz 1 Bz 1 We see that the last term is also represented in Equation 5 and therefore cancels out We get 6 Cp L P man f x l1 i l1 1 P 7an1f C Cr PCIE i 2 j x 1 Can Pb If j l where the last term is a leftover from Equation 5 Using P a e 1 P ale and Equation 4 we get 5 Cp P an f P an f dCs Leco p Fiw Trc I
16. timal next step of the remaining sequence see below This leads us to the following definitions Definition 6 A dependency graph for a trou bleshooting model given evidence e is the undi rected graph with a vertex for each action A A e and an edge between two vertices A and Ag if fa A e N fa A2 F 0 Definition 7 A dependency set for a trouble shooting model given evidence e is a connectivi ty component in the dependency graph given e Definition 8 A dependency set leader for a troubleshooting model given evidence e is the first action of an optimal sequence in a depen dency set given Dependency sets are important because the order of actions in the same dependency set does not change when actions outside the set are per formed This property has been exploited in the following theorem Koca and Bilgi 2004 Theorem 4 Suppose we are able to calculate the dependency set leaders Then the globally optimal sequence is given by the following algo rithm 1 Construct the dependency sets and retrieve the set leaders 2 Calculate ef for all set leaders 3 Select the set leader with the highest ef and perform it 4 If it fails update the probabilities and con tinue in step 2 Our hybrid approach then simply works by finding the optimal sequence in dependency sets of a fairly small size For this work we have re stricted us to sets of a size lt 4 At any point before expandi
Download Pdf Manuals
Related Search