# Why is And-Or-Graph-Search called a search algorithm?

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.

• Why do you insist that a search algorithm must find only one thing? Dec 7, 2014 at 0:54
• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! Dec 7, 2014 at 10:51
• David Richerby, because wikipedia says that a search algorithm is "an algorithm for finding an item [as opposed to multiple items] with specified properties among a collection of items." Of course, Wikipedia could be wrong or I could be misinterpreting it, so that's why I'm asking here. Oddly, Dictionary.com has a different definition, evidencing that Wikipedia's definition is wrong. Dec 7, 2014 at 17:00
• Raphael: Done. I didn't realize it was an issue. Dec 7, 2014 at 17:29
• @Kyth'Py1k Wikipedia is describing, in general terms, what search algorithms are. You shouldn't read that as a literal formal definition like you'd read "NP is the set of problems decided by [...]" Dec 8, 2014 at 16:51

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.

You are parsing Wikipedia's definition too closely. And-Or Graph Search is an algorithm. An algorithm is allowed to return, for instance, a list of data values. (If you want to get pedantic, a list is an item: it is a value of type list.)

• But And-Or Graph Search doesn't find a value of type list. It finds many states that are goal states, but it never actually combines them into a single list. Do you instead mean that the algorithm searches for a conceptual set of goal states, even though the algorithm never actually combines them into a physical single list in memory? If that's the case, then I suppose that means minimax, expectimax, expectiminimax, value iteration, and policy iteration are search algorithms to, as they at each state search through the space of actions to find whichever one maximizes expected utility. Dec 7, 2014 at 23:11
• @Kyth'Py1k, yes, that's right. You're parsing the definition too closely. It's not meant to be taken that seriously. Whether the algorithm combines them into a list or not is irrelevant trivia. Another way to think about it: An algorithm is a systematic series of steps to achieve some computational goal. Anyway, "algorithm" is an intuitive concept, so don't get too caught up in the wording of the definition in Wikipedia.
– D.W.
Dec 8, 2014 at 3:29