Now it's called search traditionally, but I think "exploration" is a better name for it.
We start out at home, and in this case our home is where we have two glasses.
Zero and zero are the values for how full the glasses are.
Then we start to explore.
One way we could explore is to fill one of the glasses
Then we're at this state--say we're at 0 and 4--
but we know that there are other actions in which we could explore in other directions.
Now we could take one of the other states and explore from there in other directions.
We have lots of choices going forward of this huge space that we're exploring.
Now, somewhere out in this space--and we don't know which direction it is--
is this goal state, which has 6 and then actually any amount in the other glass.
We're trying to reach that, and we're distinguishing this part of the state space as a goal.
So I drew this as one, but really it's a collection of states in that every state that has 6 on one side
and anything on the other should be considered part of this collection of goals.
We're trying to search forwards towards that.
One reason I like to call it an exploration problem is because we can think of going forward,
exploring a new land, and part of that exploration is that we've got a frontier.
Here's all the states that are the farthest out that we've gone.
If we want to make progress towards the goal,
then we're probably going to have to step from one of the frontier nodes farther out.
We've separated the set of all possible states into the goal state, the frontier states,
and the previously explored states.
Then you can see that the way to make progress is to say let's take one of the frontier states
and expand that, and we have the advantage here of being a computer
that an individual explorer doesn't have.
An individual explorer has to take one path,
and if they decide they've gone in the wrong direction, they have to go all the way back.
A computer can store lots of states in memory.
Computer exploration is more like a collection of explorers all collectively expanding the frontier.
Our next move can be to say we'll take one of these explorers, say the one in this state here,
and say now tell me what's next.
You've got 6 actions from there. Where do they go to?
Maybe some of them explore the world and generate new states that we haven't seen before.
Maybe some of them go to a state that we already know is on the frontier.
Maybe some of them regress backwards into previously explored territory.
But we can keep on going, expanding out our frontier until eventually
the frontier keeps on expanding.
When it overlaps the goal, then we've got a solution.
Now, in exploration problems like this, there are two problems that we have to worry about.
One problem is that there is no solution at all, that the goals are not connected to the to start state.
So there's no path from here to there.
Then what we want to do is do the exploration we need and report back that it's impossible.
We want to find out that it's impossible.
Then the other problem is if there is some path that eventually makes it to the goal,
We want to make sure that we find that in a reasonable amount of time.
That means we want to be efficient about the way we explore the space.
It also means that we don't want to get stuck in an infinite loop.
Now, if there is a finite number of states and they are connected,
then we should be able to find the path.
But if we aren't clever, we may miss the solution even though it's possible to find it.
For example, if we had a strategy that says first I'm going to explore in this direction--
say this is pouring from cup x into cup y--
and then I go in this direction, pouring from cup y back in to cup x,
and then I pour the water back again--so I'm continually just taking water
and pouring it between two different cups back and forth,
those are all legal steps to take, but I'm ending up with an infinitely long path
and I'm not making any progress.
We'd like to come up with a strategy for exploration,
and the strategy corresponds to deciding which path to expand next.
Strategy is always there's some path--let's say this one--
and we say that's the one we're going to explore from next.
To avoid this type of infinite loop, here's some possibilities.
One possibility would be don't reverse an action.
If you come from state A to state B, don't allow the action that goes immediately back to state A.
Another strategy would be to say always take the shortest path first.
Out of all the paths that you've built so far,
when we go to choose which one we're going to expand next,
always choose one of the shortest ones.
That way we might start to build up an infinitely long path,
but at least we won't continue it. First we'll do another one before we do that one.
Then another strategy would be don't re-explore.
That is, if we're on the frontier--let's say we're here on the frontier--
and we have a move that moves us back out of the frontier into the previously explored zone,
then we should not allow that path.
My question is check all the strategies that would eventually lead us to the goal.
Don't worry about the efficiency of getting to the goal,
but which one will eventually get us there and won't get stuck in an infinite loop.