h(S1)<h(S4)<h(int<h(S2)<h(S3)<h(S5)=h(S6) Maximize Utility h h(init) Init A h(s1) h(S2) h(S3) S1 S2 S3 B h(S4) S5) h( s6 S4 S5 S6 Plan head: A. B Finding a better state: Plateaus h(S7)<h(S6)=h(S8)..=h(S10)<h(S11)<h(S12) S1S6/". C S7 Sa h(s8)(sob(s9) h(S10 h(s11) h(S12) S10 12 Perform breadth first search from the current state to states reachable by action applications, stopping as soon as a strictly better one is found
Init h(init) S1 h(S1) S2 h(S2) S3 h(S3) S4 h(S4) S5 h(S5) S6 h(S6) h(S1) < h(S4) <h(init) < h(S2) < h(S3) < h(S5) = h(S6) A B Plan Head: A, B Maximize Utility h S10 h(S10) S11 h(S11) S12 h(S12) Finding a better state: Plateaus Perform breadth first search from the current state, to states reachable by action applications, stopping as soon as a strictly better one is found. S7 h(S7) S8 h(S8) S9 h(S9) C S6 h(S6) D h(S7) < h(S6) = h(S8) . . . = h(S10) < h(S11) < h(S12)
Enforced Hill-climbing (cont) The success of this strategy depends on how informative the heuristic is FF uses a heuristic found to be informative in a large class of bench mark planning domains The strategy is not complete Never backtracking means that some parts of the search space are lost If FF fails to find a solution using this strategy it switches to standard best-first search (e. g, Greedy or A* search) Outline Introduction to ff FF Search Algorithm FF Heuristic Fn FF Example AppendiX: HSP
Enforced Hill-Climbing (cont.) The success of this strategy depends on how informative the heuristic is. FF uses a heuristic found to be informative in a large class of bench mark planning domains. The strategy is not complete. Never backtracking means that some parts of the search space are lost. If FF fails to find a solution using this strategy it switches to standard best-first search. (e. g., Greedy or A* search). Outline Introduction to FF FF Search Algorithm FF Heuristic Fn FF Example Appendix: HSP