about the question regarding conformant planning...

[Subbarao Kambhampati <rao@asu.edu>]

There was a question (by Gregory?) as to whether it makes sense to compute h* for conformant planning problems since conformant planning's initial state can be any of the states.   I said no, but can't explain it without a big digression in the class.

Here is the digression. Conformant planning corresponds to the relaxation of yet another assumption--that of observability. While conformant planning's initial state can, at worst, be any one of the states, you would never really know which particular state you are in. The search here is in the space of *belief states* where a belief state is a set of states. You will say a belief state is a goal state if every one of the states in the belief state satisfy the goal condition. 

Thus, conformant planners need the ability to compute distance not between states but rather between belief states. That poses its own interesting issues--see http://rakaposhi.eas.asu.edu/dan-jair-pond.pdf  (especially the figure 3 and associated discussion). 

We will get to it when we talk about partial observability.

Rao