Artificial intelligence

Home Orange Blue Green Pink

AI & constraint programing, a brief introduction

Artificial intelligence ?

What people mean by intelligence in the context of computer sciences, in the context of a philosophical definition, or in a daily, casual context are very different things.
In the context of computer science, the term artificial intelligence covers the vast area of the designing of algorithms and programs aiming to solve or propose suitable solutions to problems a natural intelligence might commonly face. These are often problems where an optimal solution doesn't exist or cannot be calculated in a reasonable time. Artificial intelligence programs may sometimes include learning processes : the decision making algorithm is parameterized and encapsulated in another algorithm which tries to improve or adapt these using trial-and-error like techniques.

Constraint Satisfaction Problems ?

Constraint satisfaction problems (or CSP) are the type of problems you encounter when trying to solve the n queens problem, or when you play mastermind or soduku.
In these games, one must try to find solutions that satisfy a set of constraints defining the problem. You are often able to rapidely check whether a given solution satisfies all constraints, but it is very hard to efficiently find a solution that doesn't break any constraints (the set of possible solutions being so vast you can't realistically try them all).
These problems arise commonly in concrete real-life situations. For example, imagine you have to manage the utilisation of classrooms in a university building. Your problem might sound something like :
"Prof A must teach geometry in two slots of 3 hours a week, he can't teach on fridays, his students aren't free on monday afternoons, he needs a room that can hold 40 students, he needs a room with a beamer at least once a week;" Multiply this by 5 professors, 20 groups of students, and only three rooms, only one of which has a beamer. You are left with two solutions :
A/ Spend your week end figuring out a solution which will, inevitably become obsolete once Prof A. realises he meant to tell you he can actually teach on fridays but absolutely not on tuesdays, because that's when he's playing golf with Prof B., who, it turns out, forgot to tell you that he'll need the computer room on tuesday afternoons;
OR
B/ Save your week ends and design a procedure to efficiently and automatically solve this kind of CSP problems.
For the second options, you will need a few CSP notions.

A few CSP notions

Variables, domains, constraints
A CSP is defined by a set of variables, a set of domains and a set of constraints.

To each variable is associated a domain. A variable's domain is the set of values this variable may take. For example the values {orange, blue, green, pink} may be values which constitute the domain of a variable named "color".

We call instanciation of a variable the action of attributing to this variable a specific value from its domain.
for example : "color = blue" is an instanciation.

A constraint is a relelation between n variables. A constraint is said to be satisfied when the variables it involves are instantiated, and the relation specified in the constraint is verified.
For example "X>Y" is a constraint.
If "X=2" and "Y=1", this constraint is satisfied.
One way to define a constraint is to explicitely list all n-uplets of values which constitute an instanciation of the n variables involved and which satisfy the constraint.
A binary constraint links only 2 variables. Any CSP can be equivalently transformed into a binary CSP.

A suitable solution to a CSP is an instanciation of all its variables to values in such a way that all constraints are verified.

For example a binary CSP may be defined by :
Variables : {color,letter,number}
Domains :
color : {red, green, blue, yellow}
letter : {A,D,G}
number : {1,2,3,5,7}
binary contraints (accepted pairs of values) :
C1 between 'colour' and 'letter' :
{ {red,A} , {red,D} , {red,G} , {green,A} , {green,D} , {yellow,D} , {yellow,G} }
C2 between 'colour' and 'number' :
{ {red,1} , {green,2} , {green,7} , {blue,3} , {blue,5} , {yellow,1} }
C3 between 'number' and 'letter' :
{ {A,1} , {A,3} , {A,5} , {D,3} , {D,5} , {D,7} , {G,1} , {G,5} }

Important criterias describing a CSP are :
Number of variables.
Domain average sizes and variances.
Constraint density which is the ratio between the number of constraints and the maximum number of constraints possibly linking the variables.
Constraint satisfiability, which is the ratio between the number of acceptable n-uplets of values and the maximum number of n-uplets describing the states of two variables.
Number of solutions (if known).

Constraint propagation, domain reduction, consistencies
The CSP described in the graph above is very small, and, on quick examination, certain deductions arise imediately. For example, you cannot instantiate the colour variable to blue, because that would make it impossible to find a letter value to satisfy the colour-letter constraint.
This is due to the fact that the colour-letter constraint is not arc-consistent.
Reaching node, arc, or path consistencies is a way to ensure that this type of simple deductions have been used to eliminate some values from variable domains, making the problem more easily solvable.

More ?

prunus domestica

A universal turing machine, is an algorithms that create algorithms that solve solvable problems.
Minimising your maximum loss in a game can sometimes be obtained by playing randomly.
Constraint programing techniques will teach you to prune trees more efficiently, and that failing fast is a good way to succeed.

deep blue

Alan Turing

Home Orange Blue Green Pink