2. Constraint Satisfaction Problems

Let’s consider the optimizations we just discussed. For this half colored map, which region should we fill in next in order to minimize backtracking? There might be multiple answers here. But choose one of these optimizations and choose the region that matches with that.

I guess we’ve already seen one optimization. >> How so? >> Well, if I choose the least constraining value for Queensland, we would not have had to back up. Let me show you. We started with Western Australia being orange. Then the Northern territory was green. Since Queensland is not next to Western Australia, I … Read more

So which algorithm are we going to show first to solve constraint satisfaction problems? >> Well the stupid one first of course. >> I had to ask. >> Then we’ll add intelligence as we need it. >> Okay, we’ll use simple search. States are defined by the values assigned so far. >> The initial state … Read more

Besides unary and binary constraints, we could have constraints that involve 3 or more variables or soft constraints like the fact that I prefer to teach on a Tuesday/Thursday schedule. Problems with preference constraints are called constraint optimization problems and are with solving linear programming. >> There are lots of examples of constraint satisfaction problems. … Read more

Here is one possible set of answers. Answers could vary depending on where you started coloring in the map. We had four colors, at minimum, to color in this map because of all the adjacent regions in the center.

Now try this map coloring problem. Color each region by typing in a number to represent your color. For example type the number one to represent color number one, two for color number two, and so on. What is the minimum number of colors needed for this map?

Anyway, unary constraints restrict the value of a given variable, like saying Tasmania can’t be purple. >> Binary constraints relate, at most, two variables. We can represent those with a constraint graph. >> Here’s a constraint graph for our Australia coloring problem. Nodes are the variables, like Western Australia, South Australia, Queensland, etc. Arcs show … Read more

Map coloring is another classic example of constraint satisfaction. >> We are trying to color this map of Australia, using the minimum number of colors as possible. But making sure that no neighboring regions have the same color. >> I guess if they had the same color, it would be hard to tell where one … Read more

Speaking about saving time through deep searching another powerful trick is to look at the structure of the problem and see if we can decompose it to several independent problems. >> For example, Tasmania is independent of the rest of the Australia problem. We can solve it separately. >> Which takes a level off our … Read more

Here’s the answer. We have several islands on this map, so they can have any of the three colors. However, K2 is constrained to only one color, green, because of the two bordering regions. Finally, the entire network is arc consistent, because we don’t have any regions without a possible color. [BLANK_AUDIO]

Here’s a map where we’ve colored in two regions for you. Given this state in the map coloring, propagate through the constraints to make each variable arc consistent. Check the boxes to indicate which color is possible in each region. Finally, is the entire network arc consistent?

However, I noticed we could’ve stop our search earlier. >> How? >> At this step we said the Northern Territory in South Australia both had to be blue. >> So? >> But this two regions are adjacent. We know they can’t both be blue. >> I see, for checking propagates information from assigned to unassigned … Read more

Our next optimization is forward checking. Basically for each unassigned variable. We are going to keep track of the remaining legal values. >> I get it. So, if we ever make a decision that causes an unassigned variable to not be able to have a value. We stop our search and back up. >> Right. … Read more

Here are two possible answers. This region is holding a green region and an orange region, so it only has two options for colors. Compared to all other regions, this is the minimum remaining values of those regions. For this region, we can pick the least constraining value which is green in this case. Because … Read more

Here at Atlanta we are homes the world’s busiest airport. They have five runways and 2,500 arrivals and departures per day. >> Have you ever wondered how they schedule all those flights? Those runways are putting out a plane every 30 seconds. >> Wow, it turns out this is an example of a classic AI … Read more