Thinking Cap 2: Informed Search and CSP

[Subbarao Kambhampati <rao@asu.edu>]

Here is the second edition of the thinking cap questions:


1. In the standard CSP problms, all variables must be given assignments--and all solutions are of equal cost. We also
considered an "optimizing" variation of CSP, where each constraint has a cost, and a solution violating that constraint
incurs that cost (with costs being additive); the goal is to find the solution with the least cost.

In both cases above, all variables must be assigned values. 

In some problems, we would like to model not assigning any value to a variable--just to keep the solution cost low.
For example, in finding a time for a party for all your friends, you might decide to go ahead without one of your friends,
if he/she is too hard to accommodate. Can you think of how to model such problems within an optimizing CSP? 



2. The "informedness" of a heuristic is not as great an idea as it is touted to be. You will likely find, during your project 1,
that the search with manhattan distance heuristic sometimes does *more* expansions than the search with misplaced tiles
heuristic! In this thinking-cap question you will try to understand why this happens. 

In particular, given a heuristics h2 which is
more informed than h2 (in that forall nodes n, h2(n) >= h1(n)), we can only show that the "interior f-contour" nodes expanded by search
with h1 are also expanded by h2. 

Specifically, consider a node n' such that f2(n') = g(n') + h2(n') <  f*   (where f*, the optimal cost of the goal node, is the same for both
heuristics). So, n' will clearly be expanded by the search with h2. Since h1 <= h2, clearly  f1(n') is also less than f*, and so search with h1 also expands
node n'. This shows that the number of nodes on the interior f-contours for h1 can not be fewer than the nodes on the interior f-contours for h1. (An interior f-contour
is the set of equi-f-value nodes with  f-values less than f*)

The tricky part is that this subsumption doesn't necessrily hold for nodes that are on the "f* contour"--i.e. nodes that have
f1 or f2 equal to f*. Based on the tie-breaking strategy, a subset of these nodes will likely be expanded before the search terminates.
If the subset expanded by h2 is more than that expanded by h1, search with h2 can do more expansions even though it is more informed.

See if you can think of possible reasons why this could happen. [hint: there is a slide in the informed search lecture--with annotation "advanced"--that
gives the insights needed, if you are having trouble..]


rao