CSE150 Week2 Discussion Notes

CSE 150 – Introduction to Artificial Intelligence
Week 1 –Discussion Notes
September 27, 2004

Outline:
1) Boolean Logic and Satisfibility
2) Constraint Satisfaction Problems
3) General Heuristics for CSPs

1) Boolean Logic and Satisfibility

Perhaps the most famous and well-studied problems in computer science is SAT: given a boolean formula, can we find a assign values to the variables so that the formula is satisfied. SAT is a problem that is NP complete. This means that nobody has discover a way to solve the problem with an algorithm that takes polynomial time. (NP stands for Non-Polynomial.) Although, we may not be able to currently solve SAT with an efficient algorithm, in Assignment 2, we will explore a number general heuristics for solving the problem without exploring the entire exponential state space. If you have never been exposed to SAT or NP, don't worry right now. The first thing we need to do is understand boolean logic and the notion of satisfiability.

Our first example a boolean formula is:

f1(a) = a

This formula has one variable 'a' that can be take on values = {0, 1} where 0 means false and 1 means true. The truth table for f1(a) is

a	f1(a)
0	0
1	1

Since there exists an assigment (a = 1) for which f1(a) =1, we say that f(a) is satisfiable. Let's take a look at another example.

f2(a,b,c) = (a OR c) AND ( b OR ¬c)

For boolean function f2(a,b,c) , there are three variables {a,b,c} and we make use of three operators {AND, OR, and ¬}. The '¬' operator is the 'NOT' operator. Sometimes AND is refered to as a conjunction and OR is refered to as a disjunction. The function f2(a,b,c) has 4 literals. A literal is variable or a negated variable in the boolean equation. The truth table for f2(a,b,c) is as follows

a	b	c	(a OR c)	¬c	( b OR ¬c)	f2(a,b,c) = (a OR c) AND ( b OR ¬c)
0	0	0	0	1	1	0
0	0	1	1	0	0	0
0	1	0	0	1	1	0
0	1	1	1	0	1	1
1	0	0	1	1	1	1
1	0	1	1	0	0	0
1	1	0	1	1	1	1
1	1	1	1	0	1	1

The fucntion f2(a,b,c) is satisfiable since there is at least one satisfying assignment. (In fact, there are four satisfying assignments, {(0,1,1), (1,0,0), (1,1,0), (1,1,1)}.) Note that there are 2^3 = 8 possible assignments. That is, if we have n variables, there will be 2^n possible states. This means that state space is exponential in the number of variables. Since the state space is exponential, it will be hard (or even impossible) to come up with an algorithm to solve the problem in polynomial time.

Both f1(a) and f2(a,b,c) are example of a special class of boolean formulas called "Conjunctive Normal Form"or CNF. This simply means we have a conjunction of disjucntions. A disjunction , also called a clause, is a group of literals that have be "ORed" together. The conjunction is a group of clasues that have been "ANDed" together. In our example, our clauses are { (a OR c), (b or ¬c)} and our entire forumla is the conjunction.

Lets look at one more example of CNF Boolean formulas and Non-CNF Boolean formulas.

CNF = { f3(a,b,c) = a AND b AND c , f4(a,b,c) = (a OR b OR c), f5(a,b,c,d,e) =(a OR b OR c) AND ( ¬a OR c OR ¬d OR e)}
Non-CNF = { f6(a,b,c) = (a AND b) OR (¬b AND c), f7(a,b,c) = a AND (b OR c AND ¬a)}

A subset of CNF formula, called 3-CNF, is a CNF forumla were each of the clauses contain no more than 3 literals. For example, the third example of a CNF formula, f5(a,b,c,d,e), is not a 3-CNF formula since the second clause ( ¬a OR c OR ¬d OR e) has four literals.

Now we will look at a 3-CNF boolean formula that is not satisfiable.

f8(a,b,c) = (a OR ¬b OR c) AND (¬a OR c) AND (b) AND (¬a OR ¬c) AND (a OR ¬b OR ¬c)

a	b	c	(a OR ¬b OR c)	(¬a OR c)	( b)	(¬a OR ¬c)	(a OR ¬b OR ¬c)	f8(a,b,c)
0	0	0	1	1	0	1	1	0
0	0	1	1	1	0	1	1	0
0	1	0	0	1	1	1	1	0
0	1	1	1	1	1	1	0	0
1	0	0	1	0	0	1	1	0
1	0	1	1	1	0	0	1	0
1	1	0	1	0	1	1	1	0
1	1	1	1	1	1	0	1	0

Note that f8(a,b,c) contains 3 variables, 5 clauses, and 11 literals. This function is not satisfiable since there exists no assignment to the three variables such that the f8(a,b,c) = 1.

The SAT problem is, given a boolean function, is there a satisfying assignment. The 3-SAT problem is, given a 3-CNF boolean formula, is there a satisfying assignment. (FYI - Any boolean function can be transformed to a 3-CNF boolean formula in polynomial time. See Introduction to the Theory of Computation by Michael Sipser for this result.)

2) Constraint Satisfaction Problems (CSP)

In chapters 3 and 4 of AIMA, we studied uninformed and informed search. These problem could be represented as a search graph in which each state can be thought of as a Black Box. That is, we could move to and from adjacent states without considering anything about the nature of our current state. In chapter 5, the authors intoduce the concept of a Constraint Satisfaction Problem (CSP). Each state in a CSP consists of a set of variables X1,..., Xn. Each variable Xi can take on one value from it domain Di. For example, a domain might be a set of colors (i.e.{green, red, blue, yellow})or the integers between 1 and 10. Both these domain examples are finite and discrete. Durring our search, we will assign a value to a variable. A complete assignment is when all of the variables have been assigned a value.

Associated with each CSP, is a set of contraints, or relationships between variables. Our goal is to find a satisfying assignment with does not violate any of the constraints.

Common Examples of CSP include
* k-Queens problem
* Cryptarithmatic Problems
* Map Coloring Problem - (as know as the k-coloring problem.)
* SAT and 3SAT

For 3SAT , the CSP formulation is as follows:
    Problem:     Does the 3-CNF boolean formula have a satisfying assignment?
    Variables: boolean variables - a,b,c,d, ...
    Domain:      {0, 1} where 0 corresponds to false, 1 corresponds to true
    Constaints: Clauses of the 3-CNF formula must be individually satisfied

As with any search problem, we can solve the problems using an uninformed search algorithm such as BFS or DFS. However, do the exponential nature of picking variables, the branching factor caused by using BFS will quickly become unmanagable. Therefore we will focus on DFS. Using DFS on the following function:

f9(a,b,c) = (a OR ¬b OR c) AND (¬a OR c) AND (b) AND (¬a OR ¬c)

will result in the following search tree:
Boolean Search Tree

The starting state '{0,1}, {0,1},{0,1}' is the complete domain for the three variables. We start the depth-first search by assigning the first variable to the first possible value of the first variables domain. That is, we assign 0 to a. In the above graph, we denote an assignment using bold font.

We continue assigning variables until we violate one of our constraints. For example, after expanding our third node by assiging 0 to b, the third clasue '(b)' is violated. The algorithm will then backtracks by assigning 1 to b.

This continues until we have a complete assignment that satisfies all the contstraints. Note that the depth of the tree is always equal to the number of variables since we always assign on variable at each depth. You should check that the assignment a=0, b=1, and c=1 is a satisfying assignment.

3) General Heuristics for CSPs

Unlike informed search algorithms, where we used domain specific heuristics to solve hard search problem, CSP can be solved using general heuristics. (Assignment 2 will focus on some of these general heuristics.) For example, in example in the previous section, the third constraint '(b)' must be satisfied by assigning the variable b = 1. If we were to assign this variable first, we may reduce the number of nodes that we need to expand.

The goal our our general heuristics are to:
1) Figure out which variable to assign next.
2) Figure out which value we should assign to the next variable.
3) If we find a path that fails to find a Satisfying assignment, how far can we backtrack.

Some heuristics include
* Variable Picking - Pick the variable that has the least number of possible values.
* Value Picking - Pick the value for a variable that keeps the most number of possible values for all the other variables

As we assign value to variable, we may also want to keep track of how the assignment will affect the other variables based on the constraints. This is called constraint propagation. One specific constraint propagation heuristic is called:
* Forward Checking - When we assign a variable, delete value from the domains of the other variables based on the contstraints.

If we had the boolean equation:

f10(a,b,c) = (¬c OR b) AND (¬b OR ¬a) AND (c)

using both the Variable Picking and the Forward Checking would lead us right to a satisfying assignment:

	a	b	c
1	{0,1}	{0,1}	{1}
2	{0,1}	{1}	1
3	{0}	1
4	0

1. First we assign c =1 since it has the smallest domain. (Variable Picking).
2. Next we must eliminate 0 from the potential values of b since we need to satisfy the constraint (¬c OR b). (Forward Checking)
3. Then a cannot equal 1 since b =1 and we must satisfy (¬b OR ¬a). (Forward Checking)

If you run this example using our basic DFS algorithm, you will find that the algorithm will expand many more nodes.