Welcome to this morning's AI-1 lecture.

We are looking right now at goal-based agents.

And if you remember

that had this white spot that is the performance element.

What are we going to do?

And so we think of this algorithm

that we're seeing the tree search algorithm as the component

that given some actions of the agents and some states of the agent and possibly some

of a cost function or something like this and a goal.

How do we chain up actions to reach a goal?

And we've defined in full mathematical detail what a search problem is.

And now we're going to give the algorithm for that.

So we're completing the agent in a way.

And so we've looked at tree search algorithms.

And they're a whole class of algorithms.

They only differ in the way they handle their fringe.

Remember the fringe was when we unroll

and that's what tree search does

when we unroll

the state space induced by the search problem into a tree

tree of nodes labeled with states.

Then the fringe is all the unexpanded nodes

the ones we've seen in expansion but which

we haven't expanded yet.

The tree search algorithm is systematic in the fact that it never expands a node twice.

It doesn't have to.

It would be redundant.

It can expand

and that's important

a state twice in the sense that it can expand a node

in the tree that has never been expanded but has been expanded

a node that has the

same state label has been expanded.

That is okay.

And so we're handling the fringe in these algorithms.

The fringe is something

think of it as a data structure that knows when it's empty

because if it's empty, our algorithm will just say fail.

We haven't found, we've expanded the whole tree, nothing is left.

The fringe is empty.

We have to fail.

We have nothing.

There is a way the fringe or the strategy must know how to actually produce the next

node to be expanded, and that's going to be the main thing which we're going to change.

And the strategies.

And the fringe needs to know how to insert a couple of nodes.

So if you were to implement this algorithm

for instance

for a specific strategy like

the breadth first search strategy