RE: my availability tomorrow

[Subbarao Kambhampati <rao@asu.edu>]

At 07:25 AM 10/21/2003, you wrote:

> Hi, I have two questions:
>
> (1) Administrivia Question: Is there any restriction on what
> resources
> we can use during the test?  For example, are printed-out
> homework
> solutions considered acceptable?


yes


> (2) AI-question: I
> know you addressed this in class, and I know there
> was even supposedly a slide on this, but I looked (even for hidden
> slides) and wasn't able to track anything down.  So my questions
> are:
>
> Say you have three heuristics h*, h1, and h2.
> - if the "shape" of, say, h1 is very close to the shape of h*
> do we then
> say that h1 has high "informedness", regardless of the actual
> distance
> between h1 and h*?

no--informedness is a technical defintion having to do with whcih value
is bigger.
Given two admissible heuristics h1 and h2, h1 is more informed than h2 if
for all nodes
h1(n) >= h2(n)




> - suppose h1 has a
> very close shape to h*, and that h2 is simply a
> straight line but for every state input is closer to h*.  Which is
> a
> better heuristic? (I say h1 is better because h2 is simply adding a
> constant to every g-value which ultimately doesn't tell us any
> information)


h2 is more informed. h1 may be better in practice. The reason is that
more informed heuristics 
are guaranteed to expand fewer nodes whose f value is less than f*. This
doesn't say anything about the nodes
expanded whose f value is _equal to_ f*.  The heuristics  of
type h2 tend to put a whole bunch of nodes in the 
f=f* level. Since they have to expand, on the average, half of them,
before they find the goal node, they can wind up expanding
more nodes over all than h1 (despite the fact that h2 expands fewer
interior nodes). 


> - suppose we leave h1
> and h2 where they are, and then we begin to
> "tweak" h2 so that it is increasingly similarly-shaped to
> h*.  Is there
> guaranteed to be some point at which h2 is sufficiently similarly
> shaped
> to h* that h2, despite being not quite as similarly-shaped as h1 is
> still a better heuristic?

Quite possible. 

> - finally, is it
> accurate to say that a "better" heuristic is simply one
> that finds the optimal goal state in fewer iterations?

yes


> Thanks very much for
> your time and assistance!
>
> Josh
>
> -----Original Message-----
> From: Subbarao Kambhampati
> [mailto:rao@asu.edu]
> Sent: Monday, October 20, 2003 10:29 PM
> To: cse471-f03@parichaalak.eas.asu.edu
> Subject: my availability tomorrow
>
> I will be available in my office most of the day--trying to complete
> setting this darned exam (the draft I have seems
> to be too easy--need to work to make it worth all your time ;-)
>
> The exam will be open-book and open notes
>
> Rao