Artificial Intelligence
Download
Report
Transcript Artificial Intelligence
Artificial Intelligence
Constraint
Programming 1
Ian Gent
[email protected]
Artificial Intelligence
Part I :
Constraint
Programming 1
Constraint Satisfaction Problems
Constraint Satisfaction Problems
CSP = Constraint Satisfaction Problems
AI exams, CSP =/= Communicating Sequential Processes
A CSP consists of:
a set of variables, X
for each variable xi in X, a domain Di
Di is a finite set of possible values
a set of constraints restricting tuples of values
if only pairs of values, it’s a binary CSP
A solution is an assignment of a value in Di to each
variable xi such that every constraint satisfied
3
Who Cares?
Many problems can be represented as CSP’s
e.g. scheduling, timetabling, graph coloring, puzzles,
supply chain management, parcel routing, party arranging
…
Many Constraint Programming toolkits available
CHIP
ILOG Solver [expensive commercially]
Eclipse [free academically]
Mozart [available as rpm for Linux]
4
Colouring as CSP
Can we colour all 4 nodes
with 3 colours so that no
two connected nodes the
same colour?
Variable for each node
All Di = { red, green, blue}
Constraint for each edge
all constraints of the form
xi xj
Solution gives a colouring
It’s a binary CSP
5
SAT as a CSP
Variable in CSP for each variable/letter in SAT
Each domain Di = {true, false}
Constraint corresponds to each clause
disallows unique tuple which falsifies clause
e.g. (not A) or (B) or (not C)
not < A = true, B = false, C = true >
Not binary CSP unless all clauses 2-clauses
6
N-Queens as a CSP
Chessboard puzzle
e.g. when n = 8…
place 8 queens on a 8x8 chessboard so that no two attack
each other
Variable xi for each row i of the board
Domain = {1, 2, 3 … , n} for position in row
Constraints are:
xi xj
xi - xj i-j
xj - xi i - j
queens not in same column
queens not in same SE diagonal
queens not in SW diagonal
7
Constraint Satisfaction Problems
CSP = Constraint Satisfaction Problems
AI exams, CSP =/= Communicating Sequential Processes
A CSP consists of:
a set of variables, X
for each variable xi in X, a domain Di
Di is a finite set of possible values
a set of constraints restricting tuples of values
if only pairs of values, it’s a binary CSP
A solution is an assignment of a value in Di to each
variable xi such that every constraint satisfied
8
Formal Definition of Constraints
A constraint Cijk… involving variables xi, xj, xk …
is any subset of combinations of values from Di, Dj, Dk …
I.e. Cijk... Di x Dj x Dk …
indicating the allowed set of values
Most constraint programming languages/toolkits
allow a number of ways to write constraints:
e.g. if D1 = D2 = {1,2,3} …
{ (1,2), (1,3), (2,1), (2,3), (3,1), (3,2) }
x1 x2
CtNeq(x1,x2)
I’ll use whatever notation seems right at the time
9
More Complex Constraints
Constraints don’t need to be simple
+
=
D
G
R
O
E
O
N
R
B
A
A
E
L
L
R
D
D
T
Cryptarithmetic: all letters different and sum correct
Variables are D, O, N, A, L, G, E, R, B, T
Domains:
{0,1,2,3, … , 9} for O, N, A L,E,R,B,T
{1,2,3, … , 9} for D, G
How do we express it?
10
Donald + Gerald = Robert
We can write one long constraint for the sum:
100000*D + 10000*O + 1000*N + 100*A+ 10*L + D
+ 100000*G + 10000*E + 1000*R + 100*A+ 10*L + D
= 100000*R + 10000*O + 1000*B + 100*E+ 10*R + T
But what about the difference between variables?
Could write D =/= O, D=/=N, … B =/= T
Or express it as a single constraint on all variables
AllDifferent(D,O,N,A,L,G,E,R,B,T)
These two constraints
express the problem precisely
both involve all the 10 variables in the problem
11
Search in Constraints
The basics of search are (guess what) the same as
usual
Depth first search is the most commonly used
What toolkits (Solver, Mozart … ) add is
propagation during search done automatically
In particular they offer efficient implementations of
propagation algorithms like
Forward checking
Maintaining Arc consistency
12
Forward Checking
The simplest good propagation is Forward Checking
The idea is very simple
If you set a variable and it is inconsistent with some other
variable, backtrack!
To do this we need to keep up to date the current
state of each variable
Add a data structure to do this, the current domain CD
Initially, CDi = Di
When we set variable xj = v
remove xi = u from CDi if some constraint is not
consistent with both xj = v, xi= u
13
Forward Checking
For implementation, we have to cope with undoing
the effects of forward checking after backtracking
One way is to store CDi on the stack at each depth in
search, so it can be restored
expensive on space
very easy in languages which make copies
automatically, e.g. Lisp, Prolog
Another is to store only the changes to CDi
then undo destructive changes to data structures on
backtracking
usually faster but can be more fiddly to implement
14
Forward Checking, example
Variables x, y
Dx = Dy = {1,2,3,4,5}
Constraint x < y - 1
Initially CDx = CDy = {1,2,3,4,5}
If we set x = 2, then:
the only possible values are y = 4, y = 5
so set CDy = {4,5}
If we set x = 4, then
no possible values of y remain, I.e. CDy = { }
retract choice of x = 4 and backtrack
15
Heuristics
As usual we need efficient variable ordering
heuristics
One is very important, like unit propagation in SAT:
If any CD is of size 1
we must set that variable to the remaining value
More generally, a common heuristic is “minimum
remaining value”
I.e. choose variable with smallest size CD
motivated by most constrained first, or also some
theoretical considerations.
16
Next time
Arc Consistency
Special kinds of constraints, like all different
Formulation of constraint problems
How to organise a party
17