Tuesday, January 27, 2009

Vacuum Contingency Problem Graph?

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.

1 comment:

  1. Hi Adam:

    After 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

    ReplyDelete

Note: Only a member of this blog may post a comment.