Today in class, we saw graphs for the single-state problem and multiple-state problem "The vacuum world." The professor also mentioned that in a contingency situation, a tree or subgraph would be used.
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.