Before merging this, check that the following two configurations report the same 
number of evaluations (see msg7006):

--heuristic h=lmcut() --search astar(h)
--heuristic h=lmcut() --search astar(h, lazy_evaluator=h)

Once this issue is done, update issue207.

Since the new implementation now *always* notifies all path-dependent evaluators
about new paths (even if they are not set as lazy evaluator), Malte suspected
that setting a path-dependent evaluator as lazy evaluator is not as important as
was setting the mpd option earlier. Basically the only thing the lazy evaluator
does for path-dependent evaluators is to delay expansion if it was inserted with
too low heuritistic value; but even if we expand the state earlier the heuristic
values of the children will be more accurate since it has all path information.
On the other hand, if mpd was not set to true before the change, this additional
path information was lost.

We ran another experiment testing the influence of setting the lazy evaluator:

http://ai.cs.unibas.ch/_tmp_files/simon/lazy-or-not.html

If we do not set lazy evaluator, we do less expansions until we reach the last
f-layer, but overall we do more expansions. However, not setting the lazy
evaluator results in a small time gain. My explanation is that we reach the last
f-layer faster because we might expand states leading to the last f-layer faster
(since we expand them "too early". However, once we reach the last f-layer all
"too early" expanded states would not need to be expanded at all and thus cause
more expansions. But it still does not seem to justify the overhead in terms of
search time.

The issue is resolved and merged.

I'm done commenting on the pull request and experiment. I left a few small
comments on bitbucket, but otherwise this looks fine to merge.

I have added this issue to the review queue.

We have a first implementation for the issues and ran some preliminary experiments:

http://ai.cs.unibas.ch/_tmp_files/simon/issue198-v1-opt-issue198-base-issue198-v1-compare.html

As mentioned earlier it is expected that evaluations and expansions change for
path-dependent heuristics. This is because we no longer know the exact h-value
the node had when inserted into the open list, but only the last cached h-value
(see msg6870 for details).

I think in general the results look promising. I find it interesting that the
new implementation often needs less evaluations and expansions, since we are
more likely to expand nodes that could be expanded later.

Thanks for your detailed clarifications! We'll try to find a solution that 
doesn't change the semantics of "evaluations" for any type of heuristic. I'll 
leave some more comments on Bitbucket.

I think your suggestion conflates "path-dependent" and "lazy".

They are two separate concepts, and I think getting rid of the conflation
between them is one of the major steps forward we've been making with the
changes that Salomé has been working on.

A "path-dependent" evaluator is one that needs to be informed about the
transitions explored by the search algorithm.

A "lazy" evaluator is one that, upon expanding a state, gets a chance to
reevaluate the node and may then decide to trigger postponement of the expansion.

We can have heuristics that are lazy, but not path-dependent. For example, see
the AAAI 2012 paper by Zhang and Bacchus, Section "Lazy Heuristic Evaluation in A*".
AAAI Press link: 
https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/5190

We can have heuristics that are path-dependent, but not lazy, such as the
original landmark heuristic by Silvia and Matthias before Erez's multi-path
dependence addition.

I think making this conceptual distinction clear is a big advantage of the new
code. (I'm not sure how clear this currently is from our documentation, both
external and user-visible.)


Also, regarding this:

> path-dependent heuristics always mark the cache as dirty anyway before
> re-evaluating a state. Therefore, the heuristic value is never retrieved
> from the cache for path-dependent heuristics.

I don't think this is correct. It is true for our current implementation of
lmcount, but unless there is something I missed (I only did a quick search
within the code for "dirty"), there is no reason why other path-dependent
heuristics (or cleverer implementations of lmcount) would need to behave the
same way. It is the heuristic's decision whether or not it wants to invalidate
the cache.


Regarding this:

> The semantics of "evaluations" currently is "number of first evaluations and
> re-evaluations, excluding cache retrievals".

The intended semantics is "number of times the heuristic function is computed",
where by "computed" I mean as opposed to looked up from one of the two kinds of
caches we have (evaluation contexts and heuristic caches). I think this a
meaningful measure because we often have expensive heuristics, so the number of
evaluations is often the measure that dominates our runtime (while cache
retrieval falls more under "search overhead").

> What we propose is to change the semantics of "evaluations" *for a lazy_evaluator*
> to "number of first evaluations and re-evaluations, *including* cache retrievals".

There are two things I don't like about this:

1) The metric would then have a different meaning depending on whether or not a
heuristic is evaluated lazily or not, even though exactly the same heuristic
computations take place.

2) To me, the suggestion implies a model where "lazy evaluator" is a property of
the class (i.e. some heuristics are lazy, others are not), but that's not the
idea. The idea is that the user can decide for themselves which heuristics they
want to evaluate lazily and which ones they don't.

For example, compare the following two calls:

--heuristic h=lmcut() --search astar(h)
--heuristic h=lmcut() --search astar(h, lazy_evaluator=h)

(I didn't check what the option is actually called.) In one case, lazy
evaluation is enabled for h, in the other it isn't. But the number of LM-Cut
evaluations we actually perform should be the same in both cases (due to the
caching), and that is what the current "evaluations" statistic is intended to
report.

To be clear, that is what I *hope* should happen, without having studied the
code a lot or actually experimented with it. It would be good to quickly verify
this.


If my motivations here are still unclear, I suggest that we might want to
continue the discussion offline, for efficiency.

And whatever the outcome of the discussion, we should explain these concepts in
the code and/or user documentation.

I thought about this again and tried to concretize things a bit:

The semantics of "evaluations" currently is "number of first evaluations and re-
evaluations, excluding cache retrievals".

For a "normal" heuristic, this equals "number of distinct evaluated states".
For a lazy_evaluator, this equals "number of paths to evaluated states".

What we propose is to change the semantics of "evaluations" *for a lazy_evaluator* 
to "number of first evaluations and re-evaluations, *including* cache retrievals". 
This shouldn't change the semantics, since path-dependent heuristics always mark 
the cache as dirty anyway before re-evaluating a state. Therefore, the heuristic 
value is never retrieved from the cache for path-dependent heuristics. Is this 
correct?

We need to have a good think about how to redesign the statistics, but until we
do that, I would suggest not making drastic changes that affect the planner
statistics. Changing the semantics of "evaluated" from "number of distinct
evaluated states" to "total number of calls to the evaluate function" sounds
like a very drastic change to me. For now I'm in favour of whatever behaviour is
closest to the current behaviour.

I don't think we should block this issue until we've found a good answer to the
statistics problem, because it is a rather hairy problem. And until we have a
good answer for statistics, I think it's prudent to leave the statistics pretty
much as they are.

If that leads to some ugliness in handling statistics for this issue, we can
flag this up as something we need to reconsider later when looking at statistics
properly. In some sense that would actually be good because it might help us
come up with a good design for the statistics question when we finally find time
to look into it.

Jendrik and me discussed the reevaluate_and_check_if_changed method again and we
were wondering what the intended semantics of the evaluation counter should be.
Currently it states how many times an actual heuristic computation needed to be
done; but could we instead not count cache retrievals as evaluations as well? It
would encapsulate heuristics better since the evaluation context does not need
to know anymore if the heuristic was actually recomputed (and we could also get
rid of the EvaluationContext count_evaluation getter and setter methods used in
EvaluationContext::get_result).

The reevaluate_and_check_if_changed method would then only return 1 bool
specifying whether the value has changed or not (and be renamed to
"check_if_value_changed" or similar).

I'm done with this round of comments. I can have a look again later, if you like.

I created a pull request:
https://bitbucket.org/salome_eriksson/fd-issue198/pull-requests/1/issue198/diff

Instead of specifying the mpd option, a "lazy_evaluator" can now be passed to
"A*" search which will be reevaluated on states before they get pulled out on
the open list. Furthermore, all path-dependent evaluators will now always be
notified of state transitions, regardless of whether or not a lazy evaluator is set.

Note that the expansion order can change with the new implementation: Since we
removed last_key we have no way of knowing with what h-value a node was inserted
into the open list. We only know if the h-value of the state changed between the
last time we evaluated that state and when we (possibly) reevaluate the state
when pulling it out of open.
For example: a state was the first time inserted with g=4,h=3. Then it was
reached over a different path and inserted with g=3,h=3 (at this point the
heuristic is not reevaluated). When we remove the node with g=3,h=3, h gets
reevaluated to lets say 5 and the node will be reeinserted with g=3,h=5. When
the node with g=4,h=3 gets removed, the heuristic will not be reevaluted since
no new path to the state has been found. The old code would however still see
that it was inserted with h=3 but now has h=5 and it would reinsert the node
with g=4,h=5, while the new code will expand the node at this point.
I did run some preliminary tests that suggest that this change does not hit
performance much, but we should keep this in mind when evaluating the actual
experiments.

I wish I had the time to do it... But I would 
be happy to help (maybe by reviewing the 
change).

I had a look into the mpd code a while back already, so I'd be interested in
tackling it.

Anyone interested in tackling this? It's somewhat in the way of completing the
Evaluator/Heuristic unification, and I think the current sprint would be a good
opportunity to come up with a solution. I think that now that the h values are
no longer stored messily by the search, we are in a much better position to
resolve this than we used to be.

We stumbled over heuristics[0] again yesterday. The only remaining code that still 
uses heuristics[0] is the multi-path-dependence code. This code also uses the 
last_key_removed hack. We believe that both hacks could be removed by passing a 
dedicated heuristic that is evaluated instead of using these two hacks. This 
heuristic could replace the "mpd" parameter.

See also issue339.

Our search algorithms currently do some special-casing of heuristics[0], which
causes various problems. For example, the max evaluators and sum evaluators
don't work properly; see e.g. issue181 and issue182.

This needs to be fixed by rethinking the way that the search algorithms store
data about the search space.