Discussion question on Conformant and Contingent search (add your comments on the blog)

[Subbarao Kambhampati <rao@asu.edu>]

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