Project 1: comparing manhattan and misplaced tiles--Just howpredictive is informedness

[Subbarao Kambhampati <rao@asu.edu>]

Those of you who are at a stage where you are running experiments
comparing the manhattan and misplaced tile heuristics may find that in
som cases, manhattan distance heuristic, which is known to be more
informed, may actually expand _more_ nodes than misplaced tiles
heuristic. 

The following is an explanation of why this is possible despite what
we know, and also tells a little additional statistics that you can
keep track of to check if my explanation is right. 



Let f* be the f-value of the optimal goal node. Then

#Nodes expanded by A* search =

   # Nodes whose f-value is strictly less than f*
    +
  Some subset of nodes whose f-value is equal to f*

  =
  # interior fringe nodes expanded (nI)
   +
  # nodes on the goal fringe expanded (nG)

Now, if you have two admissible heuristics  h1 and h2 such that

forall n h1(n) >= h2(n)

then you are guaranteed that every node that is an interior expanded node for
h1 will also be an interior expanded node for h2

(if n  was an interior node expanded when h1 was used, then
  g(n) + h1(n) < f*         

since h2(n) is always less than or equal to h1(n)

 we also have 

 g(n) + h2(n) < f*

so n is also expanded for A* search with h2)

This guarantee doesn't hold for the nodes on the goal
fringe--i.e. nodes whose f values are equal to f*

There are several reasons why the number of nodes on the goal fringe that are
expanded by h1 may be larger than those expaned by h2

1. There may be more nodes which have f = f* when h1 is used as
   against when h2 is used.

2. The heuristic h1 may actually be a pathologically bad heuristic
   that gives every node the same value C such that C is below the 
   perfect heuristic value but above that of the h2 value. In this
   case even though h1 is more informed, you know that it is pretty
   useless in terms of distinguishing between different nodes--it may
   wind up having a MUCH LARGER number of nodes on its goal fringe and
   thus its nG is much larger than that of h2 (even though its nI is
   smaller than that of h2). 

3. Even if there are same are fewer nodes on the goal fringes, the way
   you break ties may wind up fortutously favoring h2 instead of h1
   (just for the nodes on the goal fringe).


In some cases, 1 and 2 can ensure that h1 winds up expanding so many more
nodes on goal fringe compared to h2 that its dominance in terms of
interior node expansion gets wiped out. 

On the __average__ however, this variation is likely not to change the
relation between h1 and h2, because 1 will typically not be a factor
for most resonable heuristics, and the effect of fortuitous
tie-breaking in 2 gets evened out if you search on large enough number
of problems. This is why we say that informedness is a good measure of
relative search complexity. 


*******This gets us to a way in which you can check the theory even on
       the instances where you find total node expansions not to be in
       accordance with informedness

1. Keep track of the f-values of the expanded nodes.
2. when you reach the goal node, you know its f-value, which is f*
3. Using f*, you can split the set of expanded nodes into those with f
   value strictly less than f* and those which have f-value equal to
   f*.
4. You should find that the number of expanded nodes with f < f* is
   always lower or equal to the num nodes expanded by misplaced tiles
  4.1. The times when the total nodes expanded by manhattan is
  _larger_, it will be because the num nodes with f=f* expanded by
  manhattan is bigger than that expanded by misplaced tiles.

****************************************
  
Perhaps the guy who brought this question up can verify this and let
me know.

Rao
[Sep 13, 2000]