At the forefront of Artificial Intelligence

An Introduction to Constraint Satisfaction Programming

Constraint Satifaction Programming (CSP) is a field of Artificial Intelligence that looks at, well, satisfying constraints! Basically, a program is given a problem and a list of constraints that the system must adher to. A classic example of this that any teacher will be able to relate to: timetabling! You have a problem (getting as many students in the classes they want as possible), and the constraints lie in what rooms are available, what students have clashing classes, what teachers are available.

Timetabling is an incredibly complex CSP problem, so let us look at a much easier problem. Look at the diagram below at try and choose letters that are lexically before (a is lexically before b) each other. The arrows show which way the constraints apply, and you must find letters that satisfy all constraints:

Even using trial-and-error, it shouldn't take too long to figure out a solution. Your solution should look something like the figure below. Notice that the constraints are all satisfied, and there is only one solution to this problem. Often, there are multiple solutions (or none) to any given problem.

Congratulations, you have completed your first CSP problem. Of course, computers aren't used to figure out these sort of problems. Nor can computer use a "trial-and-error" sort of algorithm - well they could, but it'd be incredibly inefficient on the scale of problems they are normally assigned to tackle. We shall now look at the main algorithm that is used to reduce down the possibilities to get a possible list of solutions.

More Complex CSP and Arc Inconsistency

If we look at a more complex version of our example we used before, we can things quickly get unmanageable. The example below is still fairly easy to solve, but it takes a while and is prone to mistakes being made when done manually (trust me).

How would you go about solving something like this? Probably most people would start by removing any letters that would obviously not work. For example, in the "A,F,M,D" or "A,I,D,T" nodes, it is obvious that 'A' would never work, therefore you might start off by crossing this off your diagram. Most of us would keep randomly doing this until we couldn't do it anymore.

Arc Inconsistency

This is exactly how the arc inconsistency algorithm (AIA) works, but on a more formalized basis. The AIA goes something like this:

WHILE labels are removed
   Iterate through nodes
       Iterate through labels (letters)
          If the label is inconsistent with all labels
          at a connected node, remove it.
       end
   end
end

The bolded line is the most important: so, if a label (letter in our case) is inconsistent, or doesn't follow fit the constraints for any of the connecting labels, then remove it. Let us look at the first two iterations, with deleted nodes labelled in red:

First Iteration:


E,G,R,U:  R & U do not come before a, f, m or d.
A,F,M,D:  A & D do not come after  e, g, r or u.
I,E,N,F:  None are removed.
H,C,Q,B:  None are removed.
A,I,D,T:  A & D do not come after e, g, r, u, i, e, n or f!




Second Iteration:


E,G:      None are removed.
F,M:      None are removed.
I,E,N,F:  E & F do not come after f or m.
H,C,Q,B:  C & B do not come after f or m.
I,T:      I does not come after i or n.

You'll find that the third iteration won't yield any more redundancies, so you have your solution! In fact, there are a lot of solutions for this problem.

Node
 1     e   e   e   e   g
 2     f   f   f   m   m
 3     i   n   n   n   n
 4     h   h   q   q   q
 5     t   t   t   t   t

Remember, just because you've reduced all the redundancies, it doesn't mean that you can mix and match the remaining letters. For example, by choosing 'M' for node #2, you can only use 'N' for node 3 and 'Q' for node 4.

As you can tell, even relatively simple CSP problems are mundane and time-consuming to solve. If constraints go beyond simple unary and binary relationships (such as timetabling that could involve perhaps 10 different time constraints), you cannot easily visualize the data. Therefore, computer armed with the arc inconsistency algorithm can plow through the redundancies and generate a list of solutions relatively quickly.

Conclusion

Now how is all of this artificial intelligence? As it stands, it probably isn't all that smart, but most program geared at CSP style problems are aimed at the very tough problems like air traffic control (a massive version of timetabling...in realtime!) which requires immense computation. Unfortunately, computers are not yet fast and efficient enough to deal with the information that is constantly flowing into the program to dynamically schedule everything, therefore certain shortcuts or "have-to-do"s perhaps even "best-worst" options have to be found and selected by the program to enable good enough answers in the time available. This can require a good deal of heuristic programming and other AI techniques depending on the application. CSP with execution time as an additional constraint!

Submitted: 19/04/2001

Article Toolbar

BibTeX entry