[Solved]: Why is And-Or-Graph-Search called a search algorithm?

Problem Detail: 

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.

Asked By : Kelmikra

Answered By : Robert Mattmüller

You can view And-Or Graph search as a search algorithm in two ways:

• As search in the state space: Here, the "items" from the Wikipedia definition are the states, and an "item with specified properties among a collection of items" is a goal state. With And-Or Graph search, finding one such item is generally not enough. Under this view, the definition on Wikipedia is a bit too narrow.

• As search in the space of partial conditional plans: Here, the "items" are partial conditional plans, and an "item with specified properties among a collection of items" is a total conditional plan, i.e., a partial conditional plan with the specified property that it is guaranteed to reach a goal state after a finite number of steps. Unlike a total conditional plan, a partial conditional plan may contain leaf nodes that are neither goal nodes nor have an associated action in the plan. Search steps in this search space are extensions of partial conditional plans by one action, i.e., these steps take a partial plan P and return a new partial plan P' that is like P, but with one non-goal leaf replaced by a valid action assignment to that leaf node.

Both views are legitimate, and the second one is perfectly consistent with the Wikipedia definition.

The analogous distinction in regular graph search would be between searching for a goal state and searching for a path to a goal state.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33955