We have now seen a conceptual model for planning,

namely, the state transition system. This helped us formulize the problem we

are trying to solve in planning. A technique that is used almost

everywhere in planning, and in many other areas of AI is called search.

And this is what we will be looking at next.

Before we go in to the details of search algorithms, I briefly want to talk about

the types of problems we will see on this course.

Namely, toy problems versus real-world problems.

Toy problems are characterized by a description that is concise and exact.

The description being concise allows me to describe the problem in one slide

quickly. The description being exact means there

shouldn't be too much ambiguity about what the problem is trying to do.

Toy problems are often used for illustration purposes,

for example, on this course. They are also used to compare the

performance of different search algorithms.

Toy problems have two interesting properties.

Namely they are rich and simple. By rich, we mean they're anything but

trivial to solve. And by simple, I mean, they can be

described easily and precisely. Real-world problems tend to be very

different. To begin with, there is no single

agreed-upon description for most real-world problems.

That means if we were to use real-world problems in this course, I would spend a

lot of time describing what the actual problems is and describing the details

that need to be addressed in each problem.

However, toy problems are good as mental exercises.

But real-world problems, people care about the solutions of those.

The missionaries and cannibals problem we have seen earlier clearly falls into the

category of toy problems. Now, before we go into search algorithms,

we need to characterize what constitutes a search problem, and here are the four

components that characterize a search problem.

The first component is the initial state. This is simply the state of the world

from which we start our search. In the missionaries and cannibals

problem, this was the state where all the missionaries and all the cannibals and

the boat were on the left-hand side of the river.

Next, we need a set of possible actions. Not every action will be applicable in

every state, so we will also need to define the

applicability conditions for actions in states.

We can define the actions through a successor function.

A successor function maps a state into a set of pairs of actions and state.

So, for each state of the world, the successor function maps it to all those

actions that are applicable, together with the states that result from

the action being applied in the original state,

and leading us to this new state. Together, the successor function and the

initial state span a state space which corresponds roughly to the states

transition graph we have seen earlier. The state space is a directed graph with

states as nodes and actions as labels on arcs.

The third component of a search problem is the goal.

This can be either an individual state, in which case, we have just one unique

goal state, or in general, we can have a function that tests whether a given state

is a goal state or not, which allows us to have many different goal states.

A solution to a search problem is simply a path in the state space from the

initial state to a gold state. The final component of a search problem

is the path cost function. This simply assigns a cost value to each

possible path in the state space. we use this when we're doing optimal

search. When we're looking for an optimal path,

we're looking for the path with the lowest cost.

A simplification that is often used in planning is that each action has a fixed

cost and that the cost of a path is simply, the sum of the step cost,

the cost of each action. Now, you will have noticed that there are

some similarities between what we've just defined and stay transition systems, and

the next quiz will give you little time to think about those similarities and

differences. Going back to the missionaries and

cannibals example, let's try to define this as a search problem.

So, we need to define the four components, which were the initial state

which was given to us as part of the problem.

And the third component was the goal state which was also given to us as part

of the problem. Then, the fourth component is the path

cost function. And there, we simply assume that every

step has the same cost. So, the only thing that is slightly more

complex is the successor function. And we can define this as a table as

shown here. So, what this table does is simply

enumerate all the mappings of states to set of action state pairs.

What we have on the left-hand side is a state.

So, this is the initial state as defined in the problem.

And I'll decipher this for you quickly. This has two components.

It says, what's on the left-hand side and what's on the right-hand side.

On the left-hand side, we have the three missionaries, we have the three

cannibals, and the boat. And on the right-hand side, we have no

missionaries and no cannibals initially. So, that is the initial state.

We describe everything that's on each side of the river.

This is mapped to three pairs. One, two, three.

each of which consists of an action and another state.

So, let's look at the first one. In the first case, we ship two cannibals

across the river. And this gives us, on the left-hand side,

three missionaries, one cannibal, because we ship two cannibals across.

On the right-hand side, zero missionaries, and two cannibals, plus the

boat, which is also now on the right-hand side.

Altogether, we see there are three different pairs here because, there are

three applicable actions in the initial state.

In the next row, we have a different state.

And we, again, define what can be done in this state, these are the two actions,

and the resulting states that we get if we apply these actions.

This is actually, the same state that we've looked at just now.

This state here became the state there. So, we need to do this for the whole set

of states that are available for the whole states base.

Which means we need to go through a whole list of states and define where we can go

from these states. And if we had completed this table, we

had defined the whole state-transition function and this concludes the

definition of the surge problem. In contrast to this toy problem, we will

now look at a real-world problem, namely, touring in Romania.

What you see here is a rough map of the country with some of its major cities.

To define touring Romania as a search problem,

we again have to define the four components of a search problem.

So, let's start with the initial state. Suppose we are in the city of Arad,

that's where we start our tour of Romania.

The next thing we need to define are the possible actions that we can take in this

problem. Since we are looking at a map, it

suggests that we can drive from one city to another.

But presumably, when you're touring a country, that's not all you want to do.

You probably also want to do some sight seeing, or you need a hotel, so you need

to check into that hotel, you need to book a hotel.

there are many different types of actions that you want to do when you tour a

country and you can see, this is a real world problem.

We already have the first problem, deciding what the possible actions are.

The same applies for the goal. When you're going on holiday somewhere,

to tour a country or a region, what is your actual goal?

Well, presumably, you want to end up in the same state that you started off,

namely, at home. So, that can't really be the goal.

You want to have something else that you need to describe as your goal, something

that happens along the way. But it's very hard to describe because

this is a real-world problem. What is the little bit easier is probably

the cost that is associated with each action and that will mostly be time and

money. As a side remark, the touring in Romania

problem is taken from a famous AI textbook, by Russell and Norvig. And if

you want to learn more about search, I recommend that you have a look at this

book. The reference to this book will be given

on the course website. So, what you have just seen is that

problem formulation is itself a complex problem.

And its the problem of defining the four components of a search problem.

In problem formulation, we have to decide what actions we want to consider and what

states we want to consider in the world. Probably the most difficult decision

there is, at what level of abstraction are we looking at the world?

What detail do we want to take into account and what detail do we want to

omit? So, looking at the touring Romania

examples, we could define actions that describe how we drive a car that, say, we

have to turn a steering wheel by one degree left or right and we have to move

our foot from one pedal to the other. But this would probably give us too much

irrelevant detail and there's a lot of uncertainty involved in that, too.

So, we probably don't want to go to that lower level of detail.

Also, if we try to solve our problem at that level of detail, we would come up

with a solution plan that has many, many steps.

If we define the problem at a higher level of abstraction,

say, we consider actions that drive us immediately to another big city.

Then, we have the problem that we need to decide how to execute such an action when

we come to plan execution. Also, if this is the level of abstraction

we consider driving to another city, we can't really talk about things we do

in between, between two cities. So, deciding at what level of abstraction

we model our actions and states is probably the most important decision in

problem formulation. But to help us with problem formulation,

there are number of assumptions that search engines and planners often make

and if we take those in to account during problem formulation, we may have a much

easier task. The first assumption is that we have a

finite number of world states. This implies that we cannot have

continuous variables in those states, as this would automatically give us an

infinite number of states. Then, we will assume that the world is

fully observable. Which means everything that is relevant

to us in the state of the world can be seen and will be known to the algorithm

to our planner that we're using. The next assumption is that the actions

that were using are deterministic, which means each action has one well-defined

outcome. There's no uncertainty which state we'll

be in after we apply an action. The final assumption is that the world is

static. Which means, there are no events so

nothing happens that we don't do. Only the actions that we do modify the

state of the world. So, these are assumptions about the

environment, but we will also make some other assumptions that are useful for

planning. The first one is that we have restricted

goals. And that means that our goals are either

given to us as a single state that we want to be in or a set of states that are

all gold states. The second assumption is that the

solution we are looking for is a sequential plan, so a solution is a

linear list of actions. There's no parallel activity in our plan.

We shall also not consider time explicitly but only implicit, which means

activities will not have a duration for the time being.

And the final assumption is that we're doing offline planning, that is, the

state transition system which underlies our planning process is not changing

while we're doing the planning. Okay, time for another quick quiz to give

you time to think about this.