4-2. Introduction to Planning

In this new notation, instead of writing plans as a linear sequence of, say, suck, move right, and suck, I’m going to write them as a tree structure. So we start off in this belief state here, which we’ll diagram like this. And then we do a suck action. And we end up in a … Read more

And the answer is that any plan that would work in the deterministic world might work in the stochastic world, if everything works out okay. And all of these plans meet that criteria. But no finite plan is guaranteed to always to work. Because a successful plan has to include at least one move action. … Read more

Now let’s move on to stochastic environments. Let’s consider a robot that has slippery wheels, so that sometimes when you make a movement, a left or a right action, the wheels slip and you stay in the same location. And sometimes they work and you arrive where you expected to go. And let’s assume that … Read more

We’ve been considering sensorless planning in a deterministic world. Now, I want to turn our attention to partially observable planning, but still in a deterministic world. Suppose we have what’s called local sensing. That is our vacuum can see what location it is in, and it can see what’s going on in the current location, … Read more

The answer is, that the state of knowing that your current square is clean corresponds to this state, this belief state with four possible world states. If I then execute the right action followed by the sack action, then I end up in this belief state, and that satisfies the goal. I know I’m in … Read more

This is the belief state space for the sensorless vacuum problem. So we started off here. We drew the circle around this belief state, so we don’t know anything about where we are. But the amazing thing is if we execute actions, we can gain knowledge about the world even without sensing. So let’s say … Read more

Here’s a state space diagram for a simple problem. It involves a room with two locations, the left we call A and the right we call B. And in that environment there’s a vacuum cleaner, and there may or may not be dirt in either of the two locations. And so that gives us eight … Read more

Now why do we have to intervene in planning and execution? Mostly because of properties of the environment that make it difficult to deal with. The most important one is if the environment is stochastic, that is if we don’t know for sure what an action is going to do. If we know what everything … Read more

Here’s an example of tracking the predict update cycle. And this is in a world in which the actions are guaranteed to work as advertised. That is, if you suck, you clean up the current location, and if you move right or left, the wheels actually turn and you do move. But, we can call … Read more

Now some people like manipulating trees. And some people like a more sort of formal mathematical notation. So if you’re one of those, I’m going to give you another way to think about whether or not we have a solution. And let’s start with the problem solving where a plan consists of a straight line … Read more

And the answer is we have an unbounded solution, if every leaf in the plan, ends up in a goal. So if we follow through the plan no matter what path we execute based on the observations. And remember, we don’t get to pick the observations, the observations come into us and we follow one … Read more

So let’s say we perform that search, we had a big search tree, and then we threw out all the branches except one. And this branch of the search tree does itself have branches, but this branch of the search tree, through the belief state, represents a single plan, not multiple possible plans. Now what … Read more

Now I’ve told you what a successful plan looks like, but I haven’t told you how to find one. The process of finding it can be done through a search just as we did in problem solving. So remember in problem solving we start off in a state, and it’s a single state, not a … Read more

You remember our problem solving work. We have a state space like this and we’re given a start space and a goal to reach and then we’d search for a path to find that goal and maybe we find this path. Now, the way a problem solving agent would work is first it does all … Read more