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

1. Title:
   08-08 Stocastic Environment Problem
2. Description:

   Unit 8 8 Stocastic Environment Problem

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