Title improve search statistics
Priority wish Status resolved
Superseder Nosy List erez, jendrik, malte
Assigned To Keywords
Optional summary

Created on 2012-11-05.15:09:22 by malte, last changed by malte.

msg10194 (view) Author: malte Date: 2021-03-18.14:27:06
I am closing this because we haven't touched this for 9 years, so it does not seems to be pressing. If someone is interested in working to improve these statistics, they should feel free to reopen.
msg2375 (view) Author: malte Date: 2012-11-05.17:27:49
Hi Erez, you're right, this is underspecified. And I agree: the most obvious way
to count generated states before the last f-layer is to keep track of a vector
or map of f-value counters (which might be interesting in the first place).

I suggest to defer this until after the search algorithm cleanup. I just wanted
to have this in the tracker since it came up in a discussion with Martin and
some of the Freiburgers and I didn't want to forget it.
msg2374 (view) Author: erez Date: 2012-11-05.17:05:55
I can do that, but we first need to define this precisely.
In LM-A* or path-A* (with a heuristic that is path-dependent), do we count the 
first value for each state? the last value? 
Should we count each state only once, or should we count each value?

Also, unless there's some trick I'm missing, this means we would need to keep a 
vector of f-values, each with a count of the number of states generated with 
that value. We could merge the f-value that were proven closed, but there might 
be several open f-values.
msg2373 (view) Author: malte Date: 2012-11-05.15:09:22
Search statistics should be clearer, more comprehensive and more relevant.

For example, in A* search, it would be useful to count the number of states that
were generated with values less than the optimal solution cost C*, since this is
a nice, mostly algorithm-independent measure for the effort of proving the lower

We currently only compute this number for *expansions* ("expansions until last
jump"). We also count "evaluations until last jump", but if I recall correctly,
this has a different semantics: this counts all states that were evaluated
before expanding a state on the last f layer. That's not the same as the number
of states before the last f layer: a state before the last f layer can of course
have successors on or beyond the last f layer.
Date User Action Args
2021-03-18 14:27:06maltesetstatus: chatting -> resolved
nosy: + jendrik
messages: + msg10194
2012-11-05 17:27:49maltesetmessages: + msg2375
2012-11-05 17:05:55erezsetnosy: + erez
messages: + msg2374
2012-11-05 15:09:22maltecreate