So you all have read the chapter "Beyond Classical Search" which talks about search strategies to use when we have non-deterministic actions,
and partial observability or unobservability.
You saw that the first two can be handled by And-Or search--first in the space of states while the second in the space of belief states. The third can be done
by normal A* search in the space of belief states.
The chapter is somewhat coy on what you will have to do regarding heuristics. Afterall, we spent a lot of time talking about heuristics for A* in the space of states. How about for these beasts? This is what I want you to think about.
To think of something concrete, consider the scenario of searching in a 2-D space (which possibly has obstacles). Now, if we consider deterministic actions and full observability in this space, we basically just have A* search. A good adminissible heuristic is "straight line-distance".
Now, suppose you are still in the same space but
1. Your actions are not deterministic (but you have full observability)
2. You have partial observability
3. You have no observations
In each of the scenarios above, explain how you can use and/or generalize the straightline distance heuristic.
Please write your thoughts as comments to this question on the blog.
thanks
Rao
Subscribe to:
Post Comments (Atom)
1.] For an agent with non-deterministic actions in a fully observable environment, one needs to calculate the heuristic values associated with all the outcomes of an action. This heuristic value coupled with the probability of an action producing outcome(s) with a smaller value of the heuristic will determine the overall value of the action. Using these overall values the search will select one of the branches connected by OR relation in an AND-OR graph.
ReplyDelete2.] In partially observable environments, since one is searching through a space of belief states the straight-line distance heuristic will have to be applied to each member state in the belief state resulting from an action. This in turn will result in all member states having an associated heuristic value. To choose an action now one will have to examine the members of the belief states produced by all applicable actions. The action that takes the agent to a belief states which has maximum number of member states with a smaller "straight-line distance" should be chosen.
3.] In case of unobservable environments the above argument in 2 still holds, with the only difference that now the number of member states in a belief states will increase.
Please correct me if I am wrong.
That all seems logical, or at least it makes sense to me. I think Nishant hit the nails on their heads rather succinctly. Well played.
ReplyDeleteI came up with the same ideas as Nishant while analysing the scenario with obstacles.
ReplyDeleteSince he explained the solutions accordingly, I will not write the same thing and have people read it again.
Let's see if someone else found another interesting strategy.
a)
ReplyDeleteFor an agent with non-deterministic actions in a fully observable environment:
Each action creates a set of possible outcomes. We could then calculate a straight line distance for each outcome. Next we could sum the distances and also average them. If we have a probability distribution for the possible outcomes we could calculate a weighted sum of the all of the outcome's distances. So here we have three possible heuristics, the total sum cost, the average cost and the weighted sum cost.
b) & c)
For an agent with deterministic actions in a partially observable environment:
Each action results in a set of possible belief states. We could then calculate a straight line distance for each possible belief state. Next we could sum the distances and also average them. So here we have two suggested heuristics, the total sum cost and the average cost.
At each stage of the search, the heuristic can be combined with the current node's cost to calculate a total score for each possible OR branch under consideration in an AND-OR tree. The lowest total score will indicate which branch is taken first. Depending on the map, one heuristic may prove more efficient than the others.
I'm not sure why Nishant want's to find the action with the maximum number of belief states. I figure that the heuristic mentioned above that sums all possible costs works to penalize branches with greater uncertainty while the calculated average rewards paths with greater uncertainty. It seems that paths with greater uncertainty would take longer to calculate.
An agent in a non-deterministic world, does not have a distribution for the possible outcome of its actions, because in the case that it had, it would turn into a stochastic world. So in this case, it should not be possible to consider probabilities.
ReplyDeleteNishant did not want to find the action with maximum number of belief states, but the one that having the same number of belief states as other action, had more belief states with smaller SLD so that it is more probable that after the action, we are in a belief state with small SLD. (Or at least, I understood that :) )
Anyways, in class this approach was shown by Rao as invalid, becuase in the case of having a belief state with infinite SLD and the rest small, was not better than another action with all belief states having 1000.