Constraint Satisfaction Problems - 1 in AI

Instructional Objective

The students will be introduced to the class of constraint satisfaction problems.
They will learn how to express different constraint formally.
They will learn how to model CSP problems as search problems, and how DFS can be used with backtracking to solve these problems.
They will learn how to cast different CSP problem to search problems.

Introduction

Many problems in AI are types of constraint satisfaction problems.

Satisfiability
Scheduling
Timetabling
Supply chain management
Graph colouring
Machine vision
Puzzles

Constraint Satisfaction Problems

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 xj such that every constraints satisfied

Colouring as CSP

Can we colour all 4 regions with 3 colours so that no two adjacent regions are 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

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

N-Queens as a CSP

Chessboard puzzle

- 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

Formal Definition of Constraints

A constraint Cijk.... involving variables xi, xj, xk ...
- is any subset of combination of values from Di, Dj, Dk ....
- i.e. Cijk ... ⊆ Di x Dj x Dk...
- indicating the allowed set of values
A number of ways to write constraints:
- e.g. if D1 - D2 = {1,2,3} ...