What would a graph look like if we had non-deterministic actions and an inaccessible environment, ie a contingency problem?
My initial thoughts are that it would be very simple, consisting of two states and a new action "Sense" which would detect if both rooms were clean. If this action succeeded, it would proceed to the final state otherwise it would sit in the first state and continue stumbling around.
(You can probably make this cleaner, but I'm just giving an example of how many details I think are abstracted out for this kind of problem)
Assuming a random sequence of commands, this is about as dumb and inefficient as it can be. However it does handle the Murphy's Law case, where the vacuum actually dirties the carpet.
I'm curious to know what other people think the graph would look like, and how, if possible, you could start to optimize given the contingency problem.
Hi Adam:
ReplyDeleteAfter today's class, I added an example of state-space graph with non-deterministic actions to the slides (right after the multiple initial state and deterministic dynamics example).
The problem with your example is that a pure "sense" action doesn't change the world state but only the agent's belief state.
In the medicate example I sent this morning, before the "sense red-tongue" action, the agent is in the belief state containing two states:
BS: { S1:{disease; red-tongue}
S2:{~disease; ~red-tongue}
}
When you do the sense action
Sense(red-tongue}
it *splits* the belief state BS:
For Yes case, the Belief state is
just the singleton set {S1}
and for the No case, the belief state is just the singleton set {S2}
In otherwords, sensing is used to reduce state uncertainty, not to change the state.
[In the "going to bathroom in a new place during night" example discussed in the class, you reduced state uncertainty by *changing* state (as we did with Iraq--while we were not sure if there are WMDs or not, after a bunch of bombing, we know there aren't WMDs--even if there are also fewer other life forms left..)
Rao