We graduated from straight-on search procedures which have the main characteristic that the

states are atomic and black box, meaning we cannot look into them. We graduated from

that to algorithms where we use a factored state representation and the state representation

is essentially we have a couple of slots and the values are some from some kind of usually

in our case discrete domains. Anything you can do by filling out fixed forms intuitively.

And this allows us to guide the search as we'll see much better. There will still be

research in AI there's no real way of getting around search but we'll have a search and

we'll have search algorithm that are that take advantage of the fact that we can look

into the states. So our main example or one of the main examples was scheduling problems

like this one where we have features like when, where, who, I don't know, those kind

of things. And that led us to the idea of having a constraint satisfaction problem which

is really we're giving ourselves a set of slot names which we will call variables and

all of them range over their own domains. Just like imagine if you will a form with

drop-down menus where we have a finite number of values that are acceptable and the values

might really be different per slot. That's the idea. Another example is Sudoku where

the variables are essentially the cell names and the domains all are the same having digits

from 1 to 9 and we have a couple of constraints that say what we can actually fill in or not

fill in and here it's you can't have duplications on any diagonal rows or columns or blocks.

The constraints is usually what makes the whole thing fun and difficult. The example

we'll use most because it's so simple is map coloring in Australia. Again we have a couple

of variables each one of these seven or so territories and the values are the colors

and the constraints are no co-coloring if there's a common border that's longer than

a point. We looked at all of this. We quickly convinced ourselves that if you do things

naively then you're in trouble. Quite generally for many of these things we have extremely

powerful constraint solvers and you may remember that I told you about this story about the

prologue and the Singapore Harbor. The main thing there was that you use something called

constraint logic programming which is essentially programming where instead of trying to make

things equal remember when we did programming with our finger on the blackboard we always

try to make things equal. What you do in constraint logic programming is that instead of trying

to make things equal which is a constraint of course you allow other constraints as well

and what you do is you just basically whenever there's a constraint that comes up you feed

it to the constraint logic to the constraint solver and the constraint solver basically

says yes or no saying essentially there are solutions other than there are no solutions.

If there are solutions you can actually do the prologue step and if there are no solutions

you fail. It's kind of a generalization of these equality constraints. Can I make those

things the same by substitution to much, much richer and much more interesting domains?

So the thing in this logic program that solved the problem for Singapore Harbor was essentially

to cleverly put some of the problem into a high level description of the world of Singapore

Harbor and part of the problem into constraints. And you can imagine that we have all kinds

of constraints that if there's a ship in a position there cannot be another ship there

that's different from this one and if something is moving out you have to have enough places

free and those kind of things. Those are things that can be very well expressed in constraints

and that led to the efficient solution mainly because we have extremely good constraint

solvers. And how those work that's what we're going to look at. Okay other applications

usual, timetabling, scheduling, frequency assignment and we're going to look at the

basic notions now and then kind of refine those. And the idea is that the first time

kind of in constraints you have essentially two ways of solving these problems. One is

to have basically search at the state level as we had before but we can look into the

states and guide the search better. And it turns out that, and that's what we'll do

then, is that you have another option that you have very good, that you can actually