Title Implement Heuristic Caching
Priority wish Status resolved
Superseder Nosy List erez, florian, jendrik, malte, salome
Assigned To salome Keywords
Optional summary

Created on 2010-08-05.16:01:16 by erez, last changed by salome.

msg4664 (view) Author: salome Date: 2015-10-22.10:53:27
The issue is now merged.
msg4663 (view) Author: malte Date: 2015-10-21.12:06:51
OK, with the follow-up change for iPDB, I have no further comments. From my
perspective, this is ready to merge.
msg4658 (view) Author: malte Date: 2015-10-19.15:06:29
Thanks! The only results that look a bit odd to me are the ones for iPDB, where
the number of evaluations increases significantly, and runtime also increases
very much in some tasks. Do we know why this is the case? Maybe it's related to
the comments for the PDB heuristics I made on Bitbucket?

Apart from this, it all looks good to me. I quickly went over the code on
Bitbucket. As you say, there are some rough corners at the moment, but I think
it's still a big step into the right direction.
msg4657 (view) Author: salome Date: 2015-10-19.14:49:22
I ran experiments with the merge from issue544 now, here are the results:

Comparison reports:

Relative Scatterplots for search time and memory:

I think the results look ok, although I'm not entirely happy with the search
time. There are also two small things in the code that maybe could be done
better, but I commented on them in the pull request already.
msg4312 (view) Author: malte Date: 2015-07-02.15:49:40
OK, as mentioned elsewhere I'd wait with the code review until we have
experimental results, so let's wait for issue544 then. I think it should be
merged very soon.
msg4309 (view) Author: salome Date: 2015-07-02.14:40:36
There might be an explanation for the different expansions in some
configurations: As far as I could tell all configurations with different
expansions use some kind of relaxed planning, and issue544 shows that using
preferred operators with delete-relaxation heuristics leads to non-determinism.
I would suggest that I run the experiments on these configurations again once
issue544 is fixed.
msg4308 (view) Author: salome Date: 2015-07-02.11:32:08
Since the first point of this issue has been done already and provides a nice
interface for storing arbitrary per-state information in heuristics I
implemented steps 2 and 3 now. The pull request is here:

Each Heuristic has a PerStateInformation where it can caching heuristic
estimates. There is also a flag which allows to turn off caching (e.g. for blind
heuristic this would make sense). The .h field in SearchNode is also gone now.
You can access the h values for a certain state with help of an
EvaluationContext (which will either (re)calculate the value if it is not stored
or dirty, or return the cached value)

I started some experiments as well, the satisficing results are already done:
(a zip archive with all reporst is here:

I am somewhat confused why the expansions are different in some domains, I think
my changes should not change the number of expansions (the number of evaluations
can be different when reopening because the old code recomputed the heuristic
estimate while the new code takes the cached value if caching is enabled). I
will take a look into this.
msg419 (view) Author: erez Date: 2010-08-05.16:01:16
We want to implement heuristic caching as follows:
1. Each state will be assigned an id by SearchSpace. These will be consecutive.
2. Each heuristic will have a vector, where the heuristic value for
each state will be saved (according to the id)
3. Then we can get rid of the .h field of SearchNodeInfo, and reuse heuristics 
much better
Date User Action Args
2015-10-22 10:53:27salomesetstatus: in-progress -> resolved
messages: + msg4664
2015-10-21 12:06:51maltesetmessages: + msg4663
2015-10-19 15:06:29maltesetmessages: + msg4658
2015-10-19 14:49:22salomesetmessages: + msg4657
2015-07-02 15:49:40maltesetmessages: + msg4312
2015-07-02 14:40:36salomesetmessages: + msg4309
2015-07-02 11:32:08salomesetmessages: + msg4308
2015-03-06 12:21:27jendriksetnosy: + jendrik
2015-03-02 14:08:18floriansetnosy: + florian
2014-12-15 08:10:26salomesetstatus: chatting -> in-progress
nosy: + salome
assignedto: erez -> salome
2010-08-05 16:01:16erezcreate