And-Or-Graph-Search.md

AND-OR-GRAPH-SEARCH

AIMA3e

function AND-OR-GRAPH-SEARCH(problem) returns a conditional plan, or failure
 OR-SEARCH(problem.INITIAL-STATE, problem, [])

---

function OR-SEARCH(state, problem, path) returns a conditional plan, or failure
 if problem.GOAL-TEST(state) then return the empty plan
 if state is on path then return failure
 for each action in problem.ACTIONS(state) do
   plan ← AND-SEARCH(RESULTS(state,action), problem, [state | path])
   if plan ≠ failure then return [action | plan]
 return failure

---

function AND-SEARCH(states, problem, path) returns a conditional plan, or failure
 for each s_i in states do
   plan_i ← OR-SEARCH(s_i, problem, path)
   if plan_i = failure then return failure
 return [if s₁ then plan₁ else if s₂ then plan₂ else ... if s_n-1 then plan_n-1 else plan_n]

---

Figure ?? An algorithm for searching AND-OR graphs generated by nondeterministic environments. It returns a conditional plan that reaches a goal state in all circumstances. (The notations [x | l] refers to the list formed by adding object x to the front of list l).