Rather than $\mathbf{Result}(s, a)$, it is $\mathbf{Results}(s, a)$, which returns a set of possible states. Now a solution is a contingency plan, like a game against nature.
Why is sensing needed in a nondeterministic environment?
You need to know the outcomes of your actions in order to know how to proceed according to your contingency plan.
Describe the And-Or @algorithm for search in nondeterministic algorithms, and describe its key differences with minimax (in the “game against nature” view).
OR nodes: The agent has the choice of action (OuR choice)
AND nodes: The environment chooses the action outcome (us AND THEM)
function AndOrGraphSearch(problem) return solution/failure:
# We get to make the first choice
return OrSearch(problem.InitialState, problem, [])
function OrSearch(state, problem, path) returns solution/failure:
# If we are making a choice, we just need to find one action that
# works.
if problem.GoalTest(state):
return empty plan
if state is on current path:
# There's a loop
return failure
for each action in problem.Actions(state):
# Otherwise, see if we can find a solution by performing
# any of the actions
plan = AndSearch(results(state, action), problem, [state] + path)
if plan != failure:
return [action] + plan
return failure
function AndSearch(states, problem, path) return solution/failure:
# If nature is making the choice, we need to find a plan for every
# possible state nature puts us in.
for each s_i in states:
plan_i = OrSearch(s_i, problem, path)
# Even one possibility of failure means we're not guaranteed
# a solution.
if plan_i = failure:
return failure
return [
if s_1 then plan 1
...
else if s_{n-1} then plan n-1
else plan n
]
Differences with minimax:
Games against nature might last forever; in minimax if the opponent could force a cycle then this would be a draw. The algorithm can be modified to produce cyclic plans.
Is it true that every problem in a nondeterministic environment can be solved by an acyclic plan?
Sometimes search in non-deterministic environments leads to plans which involve a cycle. In an adversarial environment, this would be bad news since the opponent could force a game to go on forever. But in the “game against nature” view of non-deterministic search, what’s sometimes a reasonable assumption to make?
The goal can be reached if each nondeterministic outcome occurs eventually.
Here’s a search tree generated by a few steps of And-Or search in the erratic vacuum world:
Here $\mathbf{Suck}$ applied to a dirty square will either clear one square or both, and $\mathbf{Suck}$ applied to a clean square might deposit dirt. Highlight the plan the algorithm would construct, and then write it down.
