CSE 150 Lecture Notes, January 15, 2004

CSE 150 LECTURE NOTES

Thursday January 15, 2004

ANNOUNCEMENTS

Do go to section on Friday this week to get advice about the current assignment.

HOW TO INVENT ADMISSIBLE HEURISTICS

Take the original problem and relax some of the demands so that it is possible to solve the easier problem without search. Use the cost of the solution to the relaxed problem as the underestimate of the actual solution cost.

For the 8-puzzle, the rule is that we can move a tile from position x to position y if (1) x and y are adjacent, and (2) y is blank. Heuristic h1 ignores both constraints, while heuristic h2 ignores the second constraint.

This relaxation idea above is an example of what is called meta-level knowledge. It is knowledge about other knowledge. Meta-level knowledge can be the most valuable type of knowledge, because it is the most general-purpose.

Many AI programs have similar architectures: they consist of a fixed reasoning algorithm based on search, which is guided by problem-specific information represented in some explicit fashion. In this case the algorithm implementation can be called an inference engine and the problem-specific information is called a knowledge base.

Different inference engines work with different levels of knowledge. The output of one AI program can be knowledge for use by another program.

"EFFECTIVE" BRANCHING FACTOR

We can measure the performance of a heuristic function and empirically predict the running time of a search algorithm by computing the effective branching factor of search using this algorithm/heuristic combination.

Suppose the solution to problem P is found by algorithm A at depth d, after expanding k nodes.

Definition: The effective branching factor b(P,A) is the solution for b of the equation k = 1 + b + ... + b^d = (b^(d+1) - 1)/(b - 1). This is approximately the dth root of k since k = O(b^d).

Effective branching factor is the best way to compare a (P,A) combination. Percentage speedup is meaningless when comparing algorithms that take exponential time.

Any algorithm that takes time polynomial in d, say O(d^m) where m is fixed, will have effective branching factor tending to 1 as d tends to infinity. Proof: log b = log (d^m)^(1/d) = (m/d) log d = m (log d)/d. Now (log d)/d -> zero from above as d -> infinity and m is constant`, so log b -> 0 from above as d -> infinity, and therefore b -> 1 from above.

CONSTRAINT SATISFACTION PROBLEMS (CSPs)

A CSP is a state-space search problem where each state consists of a value for each of a set of variables. A goal state is one that satisfies a conjunction of constraints.

We will restrict attention to CSPs with a finite number of variables each with a finite (hence discrete) domain. Some examples are:

Cryptarithmetic problems such as SEND + MORE = MONEY.
The n-queens problem: On an n by n chess board, place n queens so that no queen is on the same row, column, or diagonal as any other.
Propositional satisfiability: Assign true or false to each of k Boolean variables so that a sentence is true. The special case where the sentence is a conjunction of clauses of length 3, i.e. a disjunction such as (x | ¬y | z), is called 3SAT, a well-known NP-complete problem
Map coloring.

A constraint is a legal subset of the cross-product of the domains of a certain number of variables. The arity of a constraint is the number of variables involved. Map coloring and the n-queens problem both involve only binary constraints, and much research has only considered binary constraints. The fact that one version of the map-coloring problem is also NP-complete shows that handling binary constraints is not fundamentally easier.

APPLYING DFS TO CSPs

We can apply the general search algorithm to a CSP as follows. We need to say what the states are, and then give an initial state, a set of operators for expanding a state, and a predicate for recognizing goal states. Let's say that a state consists of some variables with single values assigned to them, and some unassigned variables. Then:

The initial state will be the state where each variable is unassigned.
An operator assigns a value to one currently unassigned variable
A state is a goal state if all variables are assigned values and all constraints are satisfied.

The maximum depth of the search tree is the number of variables n, and all goal nodes are at this depth, so applying DFS is safe, i.e. sound and complete.

This algorithm is called generate-and-test, because each state is fully instantiated before it is tested. (Assigning a value to an unassigned variable is called instantiating the variable.) The rest of our analysis of CSPs will look at improvements to it, staying within the same framework as much as possible.

Incremental consistency checking is the idea that each constraint should be checked as soon as the variables involved have been assigned values. If any constraint is not satisfied at a node in the search tree, then the entire subtree rooted at this node cannot contain a solution, so the node should not be expanded, and search should continue with a sibling node. This refinement of DFS is called backtracking search.