aima.core.search.nondeterministic

Class AndOrSearch

java.lang.Object

aima.core.search.nondeterministic.AndOrSearch

public class AndOrSearch
extends java.lang.Object

Artificial Intelligence A Modern Approach (3rd Edition): Figure 4.11, page 136.

 
 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 si in states do
      plani <- OR-SEARCH(si, problem, path)
      if plani = failure then return failure
   return [if s1 then plan1 else if s2 then plan2 else ... if sn-1 then plann-1 else plann]
 
 

Figure 4.11 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 object x to the front of the list l.)

Note: Unfortunately, this class cannot implement the interface SearchForActions (core.search.framework.SearchForActions) because SearchForActions.search() returns a list of Actions to perform, whereas a nondeterministic search must return a Plan.

Author:

Andrew Brown

Field Summary

Fields

Modifier and Type	Field and Description
protected int	expandedNodes

Constructor Summary

Constructors

Constructor and Description
AndOrSearch()

Method Summary

Modifier and Type	Method and Description
Plan	andSearch(java.util.Set<java.lang.Object> states, NondeterministicProblem problem, Path path) Returns a conditional plan or null on failure; this function is equivalent to the following on page 136:
Metrics	getMetrics() Returns all the metrics of the node expander.
Plan	orSearch(java.lang.Object state, NondeterministicProblem problem, Path path) Returns a conditional plan or null on failure; this function is equivalent to the following on page 136:
Plan	search(NondeterministicProblem problem) Searches through state space and returns a conditional plan for the given problem.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

expandedNodes

protected int expandedNodes

Constructor Detail

AndOrSearch

public AndOrSearch()

Method Detail

search

public Plan search(NondeterministicProblem problem)

Searches through state space and returns a conditional plan for the given problem. The conditional plan is a list of either an action or an if-then construct (consisting of a list of states and consequent actions). The final product, when printed, resembles the contingency plan on page 134. This function is equivalent to the following on page 136:

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

Parameters:

problem -

Returns:

a conditional plan or null on failure

orSearch

public Plan orSearch(java.lang.Object state,
                     NondeterministicProblem problem,
                     Path path)

Returns a conditional plan or null on failure; this function is equivalent to the following on page 136:

 
 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
 
 

Parameters:

state -

problem -

path -

Returns:

a conditional plan or null on failure

andSearch

public Plan andSearch(java.util.Set<java.lang.Object> states,
                      NondeterministicProblem problem,
                      Path path)

Returns a conditional plan or null on failure; this function is equivalent to the following on page 136:

 
 function AND-SEARCH(states, problem, path) returns a conditional plan, or failure
   for each si in states do
      plani <- OR-SEARCH(si, problem, path)
      if plani = failure then return failure
   return [if s1 then plan1 else if s2 then plan2 else ... if sn-1 then plann-1 else plann]
 
 

Parameters:

states -

problem -

path -

Returns:

a conditional plan or null on failure

getMetrics

public Metrics getMetrics()

Returns all the metrics of the node expander.

Returns:

all the metrics of the node expander.