CSE 250A LECTURE NOTES

ANNOUNCEMENTS

NOTES ON THE FIRST PROJECT

Reminder: A* and related search algorithms are "offline" since the agent uses search to "imagine" an optimal path, and only afterwards executes the optimal path.

A* is not fully offline: the agent cannot explicitly "see" in a global way the entire state space.  Rather, the state space becomes revealed to the agent one state at a time as the search algorithm proceeds: see Figure 3.13.  The initial state is known explicitly.  A complete map is available implicitly; running the search algorithm makes this map explicit.

For the first project:

• You should choose a single, specific information retrieval goal, e.g. "find documents in postscript" or "find resumes less than one week posted in the last week."
• You should design a simple, appropriate online search algorithm.
• Separately, you should design a simple but intelligent heuristic function that guides the search algorithm.  Pay attention to the issue of "present value" versus "future value" as explained in the sample report from last year.
• You should implement the algorithm effectively from a systems perspective, e.g. you must deal with time-out issues.
• You should do careful experiments that show the usefulness of your algorithm+heuristic+implementation compared to a less intelligent approach.
• The experiments should be conclusive, i.e. you should persuade the reader that the results generalize to different but similar tasks, and to large search spaces.

APPLYING DFS TO CSPs

• 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.

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.
 
 

FORWARD CHECKING

In other words, each time the domain of one variable is narrowed down, all inconsistent values should be removed from the domains of the all other variables.

Let's consider a special case of constraint propagation called forward checking.  As soon as all the variables except one of a constraint have been assigned values, all values of the remaining variable that are inconsistent should be removed from its domain.

For the 4-queens problem, suppose the queens are placed column by column, so the domain of each variable consists of the four alternative rows.  Let the leftmost queen be placed in the lowest row.  Then the inconsistent values for the remaining variables are indicated by x marks:
 

			x
		x
	x
Q	x	x	x

If the next queen is placed in the second column as follows, then more values for the third and fourth variables become inconsistent, as shown in red:
 

		x	x
	Q	x	x
	x	x
Q	x	x	x

There are no feasible values now for the third variable, so the algorithm backtracks and tries the remaining alternative value for the second variable:
 

	Q	x	x
		x
	x		x
Q	x	x	x

The alternative assignment now leaves a single possible value for the third variable:
 

	Q	x	x
		x	x
	x	Q	x
Q	x	x	x

This assignment for the third variable makes the last remaining value for the fourth variable inconsistent (shown in green), so the algorithm backtracks to the third variable, then to the second variable, and finally to the first variable:
 

		x
	x
Q	x	x	x
	x

This leads to solution with no further backtracking:
 

	Q	x	x
	x	x	Q
Q	x	x	x
	x	Q	x

Notice that each time we backtrack, values that were considered inconsistent can no longer be said to be inconsistent, so these values must be added back.  It is helpful to use a true functional programming language such as ML, where the data structure representing each set of remaining values is not updated destructively.

Also note that the idea of forward checking is applicable to constraints of any arity.  As soon as k-1 variables involved in a constraint of arity k have been instantiated, we check each value of the last variable for consistency.
 
 

ARC CONSISTENCY

Definition: The arc (Vi, Vj) is arc-consistent if for every value x in the current domain Di of Vi, there exists some value y in the current domain Dj of Vj such that (x, y) is permitted by the binary constraint on Vi and Vj.

Arc consistency is not symmetric in general.  Consider two neighboring countries in a map, say V1 and V2, whose current domains are { red} and { red, blue }.  Then (V1, V2) is arc-consistent but (V2, V1) is not arc-consistent.

An arc (Vi, Vj) can always be made consistent by deleting those values from Di for which the condition is false.  Let this procedure be called Revise(Vi, Vj).  Formally the procedure is as follows:

procedure Revise(Vi, Vj):
    for each x in Di do {
        for each y in Dj do if (x, y) is consistent then next x;
        remove x from Di
        }

THE AC-3 ALGORITHM