PPT Slide

(very) Quick overview of CSP/SAT concepts

• Constraint Satisfaction Problem (CSP)
  • Given
    • A set of discrete variables
    • Legal domains for each of the variables
    • A set of constraints on values groups of variables can take
  • Find an assignment of values to all the variables so that none of the constraints are violated

• SAT Problem = CSP with boolean variables

• TCSP = CSP where variables are time points and constraints describe allowed distances

x,y,u,v: {A,B,C,D,E}

w: {D,E} l : {A,B}

x=A ??w?E

y=B ??u?D

u=C ??l?A

v=D ??l?B

N

1

: {x=A}

N

2

: {x=

A & y =

B }

N

3

: {x=

A & y =

B & v = D }

N

4

: {x=

A & y =

B & v = D & u = C }

N

5

: {x=

A & y =

B & v = D & u = C & w= E }

N

6

: {x=

A & y =

B & v = D & u = C & w= D }

x

¬

A

y

¬

B

v

¬

D

w

¬

E

w

¬

D

u

¬

C

A solution:

x=B, y=C, u=D, v=E, w=D, l=B

Previous slide

Next slide

Back to first slide

View graphic version