All language subtitles for 01_2.0_Week_2_Introduction_4-43_

Welcome to week 2 of the AI planning
course.

We've already learned a lot of things in
week 1.

For example I've introduced to you the
basic planning problem which is the

problem we are addressing in this course.
I've also told you about a technique that

is used in many places in AI but
specifically it's very important to

planning and that technique is search.
Then we've met some of our friends the

duck worker robots an example we will be
using throughout the course.

This was followed by my colleague Austin
Tate telling you about practical planners

and applications where these are used.
But planning is not just about finding

plans there is also a context to planning
and this is for example what happens

before a planning mainly the assignment
of tasks to Planners.

And after planning, the plan execution
which is very important.

Then, we've also seen that there is a
range of techniques that are used in

planners today.
That was pretty much what we've learned

in Week 1.
And now I want to talk a little bit about

the website.
I've already seen a lot of you have used

the social platform that comes with this
course, which you can see here.

And I would like to encourage you to use
the discussion forums.

To bring up any questions, any issues,
that you have with the course material

and hopefully some of the the community
that uses this forum will answer those

questions for you or we, the instructors,
can help as well.

In this week's first segment we'll be
looking at informed search or more

specifically the A* search algorithm.
A* is a search algorithm just like the

ones we've seen last week.
It takes an implicit graph and searches

it in its basic form as a tree.
Shown here is the search tree generated

by the A* algorithm for the touring
Romania problem where the task is to get

from Arad to Bucharest.
What is new here, is that the algorithm

uses a number to guide its search, and
this number expresses how far from the

search node the algorithm thinks the
current node is.

This is called a heuristic.
And this heuristic is used to compute

some evaluation function that tells the
algorithm which node to expand next.

In this graph, we see the numbers here
which are the value of this evaluation

function.
So, what this algorithm does is use an

informed search strategy, as opposed to
the uninformed search strategies we've

seen so far.
And probably the best known informed

search strategy in the A start algorithm
which is what we will see in the first

segment this week.
In this week's second segment we will be

seeing our first planning algorithm which
is the forward state space.

Search/g algorithm.
This uses the search technology we've

seen in the previous segment.
As you will see in detail, this algorithm

is actually very simple.
It takes a planning problem as input,

which is these three components you see
here.

And then starts a loop where it starts
from the initial state and builds up a

plan starting from an empty plan.
That will satisfy the goal.

The first thing it does is the goal test,
which is just what we've seen in our

search algorithm.
So this is the goal test here.

And then generates all the applicable
actions in the current state.

If there are none, then of course we have
failed.

Otherwise it just chooses one of the
applicable actions.

That is our new action that we apply in
our state.

Then we go to a new state by going
forward from our current state.

And extend our plan with this current
action.

And we go through this loop, until we
have reached a goal state.

And therefore we have found a plan that
achieves our goal.

But before we get to this algorithm, we
will see a formal definition of what

constitutes a planning problem.
And most importantly we will see the

scripts representation for operators,
which is the set O here, which describes

an operator as something consisting of
preconditions and effects.

That's what we will look at later this
week.

So now it's time to get into the material
for week 2.

Week 1 was fairly lightweight, and you've
seen an informal introduction to

planning.
In Week 2, we will see the material a lot

more technical.
We will introduce algorithms, and you

will have something to implement, if you
want.