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

Question

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.

Answer 1

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.

Answer 2

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.)