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