English subtitles

← 08-08 Stocastic Environment Problem

Unit 8 8 Stocastic Environment Problem

Get Embed Code
2 Languages

Showing Revision 1 created 11/28/2012 by Amara Bot.

  1. [Norvig] Now let's move on to stochastic environments.
  2. Let's consider a robot that has slippery wheels
  3. so that sometimes when you make a movement--a left or a right action--
  4. the wheels slip and you stay in the same location.
  5. And sometimes they work and you arrive where you expected to go.
  6. And let's assume that the suck action always works perfectly.
  7. We get a belief state space that looks something like this.
  8. Notice that the results of actions will often result in a belief state
  9. that's larger than it was before--that is, the action will increase uncertainty
  10. because we don't know what the result of the action is going to be.
  11. And so here for each of the individual world states belonging to a belief state,
  12. we have multiple outcomes for the action, and that's what stochastic means.
  13. And so we end up with a larger belief state here.
  14. But in terms of the observation, the same thing holds as in the deterministic world.
  15. The observation partitions the belief state into smaller belief states.
  16. So in a stochastic partially observable environment,
  17. the actions tend to increase uncertainty,
  18. and the observations tend to bring that uncertainty back down.
  19. Now, how would we do planning in this type of environment?
  20. I haven't told you yet, so you won't know the answer for sure,
  21. but I want you to try to figure it out anyways, even if you might get the answer wrong.
  22. Imagine I had the whole belief state from which I've diagrammed just a little bit here
  23. and I wanted to know how to get from this belief state
  24. to one in which all squares are clean.
  25. So I'm going to give you some possible plans,
  26. and I want you to tell me whether you think each of these plans will always work
  27. or maybe sometimes work depending on how the stochasticity works out.
  28. Here are the possible plans.
  29. Remember I'm starting here, and I want to know how to get to a belief state
  30. in which all the squares are clean.
  31. One possibility is suck right and suck, one is right suck left suck,
  32. one is suck right right suck,
  33. and the other is suck right suck right suck.
  34. So some of these actions might take you out of this little belief state here,
  35. but just use what you knew from the previous definition of the state space
  36. and the results of each of those actions
  37. and the fact that the right and left actions are nondeterministic
  38. and tell me which of these you think will always achieve the goal
  39. or will maybe achieve the goal.
  40. And then I want you to also answer for the fill-in-the-blank plan--
  41. that is, is there some plan, some ideal plan, which always or maybe achieves the goal?