Good morning.

We are looking at constraint satisfaction problems.

Remember, constraint satisfaction problems are search problems, i.e.

the thing that is

the goal-based agents do.

But in this case, we represent the world state in a factored manner, i.e.

we have a set of

attributes of the world

measurable thing that can tell us something about the state

of the world, and those have values.

So the problems in the algorithms we're trying to solve is that we have a bunch of variables

those have domains of possible values

and we're trying to find variable assignments

total variable assignments that give every variable a value such that the constraints

are something that comes from the world model such that the constraints are actually met.

Map coloring

in this case Australia

is a paradigmatic example.

We have a map

we have to give it a coloring such that no two

in this case territories

that share a border that's longer than a point cannot share a color.

So we model this problem by having one variable for every territory.

The values of all

the possible values given in the domains for all of these are the three

colors green

blue

and red.

And the solution of this eventually is the assignment of values to all variables.

The search algorithm we're taking is basically we're searching not over the states

we're

searching over variable assignments, partial variable assignments.

We start with the empty assignment here

and here the actions are adding one color

and

we kind of gradually process adding more and more colors

and after in this case seven

assignments

we have a total assignment that is either consistent with the constraints

hooray

or we've convinced ourselves by systematic search that there cannot be any consistent

assignment.

We're using just backtracking search

we don't need iterative deepening because with a finite

number of variables the search space is finite.

That's the overall set up.

And the nice thing was that we could do informed search with heuristics

we looked at the minimal

remaining variables

the least constraint