Original subtitles

You should now understand what we mean by planning in AI. Next, we will formalise

this understanding of planning by means of a conceptual model for planning. This

conceptual model will be a state-transition system.

Before I introduce the conceptual model that underlies planning,

I want to talk to you about conceptual models in general and why they are a good

idea. So, what is a conceptual model?

A conceptual model is a theoretical device for describing the elements of a

problem. What this means is it helps us to

formalize the problem we are trying to solve.

This is good for a number of things. For example, we can explain the basic

concepts with this model so it helps us to define what the objects are that we

are manipulating during problem solving. It also helps us to clarify some

assumptions. What constraints are imposed by this

model is clarified by writing down such a model.

We can also use it to analyze requirements, so we can look at the

representations we need to develop to represent the objects that we're

manipulating during problem solving. Also, we can prove semantic properties

with a theoretical device like this. The most important properties for algortithms

we're interested in our soundness and completeness and they require a semantic

foundation which is given by a conceptual model.

What a conceptional model isn't good for, is developing efficient algorithms and

other computational concerns. So, we cannot immediately derive planners

from the conceptual model. But the conceptual model we are using and

planning is called a state-transition system.

Formally, a state-transition system is defined as a 4-tuple consisting of four

components, S, A, E, and gamma. I will now explain these components in

turn. The first component, S, is a finite or

recursively innumerable set of states. So, these are all the possible states the

world can be in. The set can be finite or recursively

innumerable, which means infinite. But in most of the examples we'll be

looking at, we have only finite sets of states so don't worry about the second

part for now. The second component is a set of actions.

Actions are the things an agent can do to change the state of the world.

The third component is a set of events. Events can happen in the world and are

not under the control of an agent, but events, too, can change the state of the

world. The fourth and most complex component of

a state-transition system is the state-transition function, gamma.

Gamma takes two things. It takes a state, a state of the world as

input, and it takes an action or event. So, this second component is the union of

all the actions and events and one of those is the second argument to the

state-transition function. The result of applying the

state-transition functions then, is another set of states.

So, this notation here, 2 to the s, just denotes the power set of all possible

states. Which means an element of the set is,

itself, a set. A set of world states.

So, the state-transition function takes a state, an action or event and gives us

all the possible states that may be the result of applying this action, or this

event happening. We can now use this definition to define

some other concepts formally. For example, applicability, we can say

that an action A is applicable in a state S, if gamma of S and A is not empty so if

there is at least one state that is the result of applying this action in the

given state. And when we apply an action A in a state

S, this will take our state-transition system to a new state S prime.

And S prime must be an element of gamma of S and A.

Another way to look at a state-transition system is to view it as a graph.

Suppose we are given a state-transition system S, A, E, and gamma,

then we can define a directed labeled graph G, that consists of nodes NG and

edges EG. The nodes of this graph are simply the

world states that are possible in this state-transition system.

NG is equal to S. And the edges in this graph correspond

directly to state transitions defined by the state-transition function.

So, we have an arc from a node, s, to another node, s prime.

So, this is and edge in this graph and that is labeled with label u, which is

either an action or an event, if and only if.

The state s prime is the result of applying u in s.

u can be action or event so we have a transition from here to here with label

u. So, a state-transition graph consists of

nodes that correspond to world states and edges that correspond to state

transitions. Let me illustrate a state-transition

system with a very old problem that has been used many times in AI,

the missionaries and cannibals problem. In this problem we have a river.

And on one side of the river we have three missionaries and three cannibals

initially. The missionaries are black triangles and

the cannibals are red circles here. There is also a boat available and in

this boat, can be up to two people. And they can use this boat to cross the

river. Now, the problem is, if the cannibals

ever outnumber the missionaries on either of the banks of the river, then the

missionaries will get eaten by the cannibals.

And we don't want that. So, you can see in the initial state,

there's an equal number of missionaries and cannibals on one side and no

missionaries or cannibals on the other side, so there's no problem.

The planning problem now is to come up with a sequence of actions that carries

all the missionaries and cannibals safely across the river, to the other side.

This system can be described by a state-transition system.

And if you're not familiar with this type of system, I would advise you to now try

to define this as a state-transition system.

Specifically, you are trying to see what are the world states that are possible

here, what are the actions and what are the events that can happen in this

problem. The state-transition function is best

defined as a graph. And, if you've sit down for about half an

hour, I'm pretty sure you can come up, come up with a graph that describes the

whole state-transition graph for this problem.

So, if you want to do this little exercise, you need to pause the video

now. So, here is my version of the

state-transition graph for the missionaries and cannibals problem.

To define this as a state-transition system, we have to define the four

components. The first component is the set of states

S. And that can be defined as the different

world states we see here. And these are all the squares,

rectangle that are drawn here. there are sixteen different world states

and they are denoted by these rectangles. So, this is the initial state, as we've

seen in the previous slide, where all the missionaries and cannibals are on the

left-hand side of the river. And over here on the right, we have the

gold state. And in this gold state, all the

missionaries and cannibals are on the right-hand side of the river.

And the second component of a state-transition systems are the actions

that are possible. In this case, there are five different

actions. And I've denoted them here with the

labels that occur on the different state transitions.

So, there's two types of actions, namely, actions with one person in the

boat, and actions with two people in the boat.

The actions with one person in the boat are the ones where we have one missionary

or one cannibal in the boat, or we can have two people in the boat.

This can be two missionaries, two cannibals or one missionary and one

cannibal. It's denoted here by 1m1c.

So, these are the five possible actions that we have to to do something in this

system. I don't need to denote where the boat is.

Because the boat can only cross from one side of the river to the other.

The set of events is empty for the state-transition system.

And finally, the state-transition function is defined by all the arcs that

make up the, the lines between the different state here.

Note in this specific problem, all the arcs are bidirectional.

Which means, with the same action, we can go to one state and then back to the

original state. So, this is one arc here, and this is

one, this is one. And all these arcs together make define

the state-transition function. And that concludes the definition of the

state-transition system. A state-transition system is useful

because it describes all the possible ways in which our system may evolve as a

result of applying actions or events happening.

But what we want to do is solve planning problems and the solution to a planning

problem is a plan. And by a plan, we mean a structure that

gives appropriate actions that we can apply in the initial state of our problem

such that it gets us to a different state in which our objective that we're trying

to achieve, as part of the planning problem, will be achieved.

A simple example of such a structure would be to have a sequential list of

actions that we need to perform in order. A more complex structure could be a

function that maps states to actions so that when we are in a given state, we can

use that function to decide what action to apply.

A plan implicitly describes a path through, through our state-transition

graph. So, when we execute a plan, we expect to

end up in a state in which our objective is satisfied.

There are different types of objectives that can be defined for planning, and I

will give you some examples now. The simplest way to define an objective

is simply to have a gold state. This can be an individual gold state that

is named, we've seen this in the missionaries and

cannibals problem, or it can be a set of gold states that

means one of those states is one that we want to reach.

An objective can also include some constrains on itermediate state through

which we're passing on the way to the goal, for example, we can have states

that we don't want to go through that we need to avoid as part of the objective.

A more complex objective could also come with a utility function for each state

and tells us that we have to maximize the utility on our way to the goal.

As you can see, an objective can be quite complex.

A completely different view of an objective would be to not try achieve

something but to perform a given task. So, a good example of this is when you

are going on a holiday. You're not really trying to change the

state of the world. You want to end up back in the same state

where you started. But you want to do something in the time

where you go on holiday. And that's a task that needs to be

performed. Probably, the most common reason for

solving planning problems is that we want to execute the resulting plans.

And here is the model for how planned execution might actually work.

So, we have a planner that is given a description of the state-transition

system that tells the planner how the world may evolve.

We're also giving this planner the initial state.

That is, the state in which the world is in and some objectives that tell the

planner where we want to be. The planner then solves this planning

problem and generates a plan which is passed to the controller for execution.

The controller takes this plan and executes the actions in this plan.

So, it has to extract the next action to be executed and passes this to the

system. The execution of the action then changes

the state of the actual system that we're trying to manipulate.

For example, the real world. And hopefully, our system is consistent

with the description of the system that was given to the planner to generate the

plan that we're now executing. But the system is not only changed by the

actions we are taking that are controlled by the controller, it is also changing

because of events that are happening. For the controller to take appropriate

actions, it usually needs to know what state the system is actually in and to do

so it has observations which are going from the system to the controller.

We model observations through the observation function eta which maps a

state to set up observations that can be made in the state.

Quite often, the world is not fully observable, and in this case, the set of

observation does not allow us to immediately infer which state we are in.

So, a given set of observation makes it possible that we are in a number of

states, and this is what is called the belief state of the controller.

Now, the model we've just seen is not very realistic, because the real world on

which we are executing our plans is often different from the description of the

state-transition system that we are giving to our planner.

So, those two are not identical. The reason is that this description we're

giving to the planner is an abstraction. It leaves out many details about the real

world which make planning possible. And then, when we execute the plan,

things may go wrong because the two models are not the same.

A more realistic model is called dynamic planning, in which planning and execution

are actually interleaved. What is different in this model is that

the controller has to do something called plan supervision and that means, it has

to detect when observations differ from expected results.

So, it expects the world to be in a certain state as a result of an action,

but it can observe that it isn't. What it can do, in this case, is plan

revision. That is, we take the existing plan and

try to change it in some way to take into account the new state.

This can be done by the controller for very simple cases or it has to be done by

the planner for more complex cases. In this case, the controller has to pass

an execution status back to the planner, so that the planner can generate a new

plan that is passed to the controller. And that takes into account the change

that has happened. In the worst case, the planner will have

to re-plan that is, it will have to create a completely new plan from scratch

for the given problem. Dynamic planning then, closes the loop

between the planner and execution by passing back the execution status to the

planner for replanning or plan repair.