An algorithm in Artificial Intelligence: A Modern Approach for planning in stochastic, fully observable environments is called And-Or-Graph-Search, implying that it's a search algorithm. However, I don't see how it is one. Wikipedia defines search algorithms as, "an algorithm for finding an item with specified properties among a collection of items," but And-Or-Graph-Search doesn't do that. It instead finds multiple items (goals states) in order to guarantee it will reach a goal state no matter what the results of its stochastic actions are.
So, why is it a search algorithm?
Here's its pseudo-code:
function AndOrGraphSearch(problem) returns a conditional plan, or failure OrSearch(problem.initialState, problem, ) function OrSearch(state, problem, path) returns a conditional plan, or failure if problem.GoalTest(state) then return the empty plan if state is on path then return failure for each action in problem.Actions(state) do plan = AndSearch(Results(state, action), problem, [state | path]) if plan does not = failure then return [action | plan] return failure function AndSearch(states, problem, path) return a conditional plan, or failure for each si in states do plani = OrSearch(si, problem, path) if plan = failure then return failure return [if si then plani else if s2 then plan2 else . . . if sn-1 then plann-1 else plann]
AndOrSearch is 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 notation [x|l] refers to the list formed by adding the object x to the front of list l.)
The function is from the book Artificial Intelligence: A Modern Approach.