Title make LandmarkGraph constant after creation
Priority wish Status resolved
Superseder Nosy List clemens, jendrik, malte, salome, silvan, thomas
Assigned To clemens Keywords
Optional summary
This is part of meta issue987.

Created on 2021-01-20.12:28:55 by clemens, last changed by clemens.

This is part of meta issue987.
File name Uploaded Type Edit Remove
issue988-210126_satisficing-main-issue988-total_time-lama-first.png clemens, 2021-01-26.19:02:07 image/png
msg10231 (view) Author: clemens Date: 2021-03-22.13:49:41
Florian had a look and changed the dependencies. See issue891 for a discussion.
msg10218 (view) Author: malte Date: 2021-03-19.20:32:27
We have a pull request related to this issue to fix a security vulnerability in Pillow, used in the issue experiments. Can whoever created the experiment (Clemens?) have a look at the pull request?
msg9939 (view) Author: salome Date: 2021-01-29.11:08:05
The merge caused a build failure on the buildbot due to warnings in the debug build. I fixed the warnings and also added a note in the wiki ( on how to enforce -Werror in your setup.
msg9936 (view) Author: salome Date: 2021-01-29.09:47:11
Done and done, thanks Malte and Silvan for the help!
msg9916 (view) Author: malte Date: 2021-01-28.20:55:14
We forgot to make an entry to Can someone add one?

Also, should we add this to the workflow page? It is easy to forget, this is not the first time.
msg9899 (view) Author: silvan Date: 2021-01-28.18:44:19
I opened issue1000 for this. Yay!
msg9897 (view) Author: malte Date: 2021-01-28.18:37:41
I had a look at the experimental results and also a (not very thorough) look at the pull request.

Performance (score_total_time) drops: -1.91 for BJOLP and -4.78 for LAMA-first. This is more than a little bit, and I would be happier if we had a closer look at performance in a followup issue. I see from msg9815 that Clemens and Florian already had a look, but really, a -4.78 must have some kind of clear explanation.

I did not immediately see a performance problem, but the diff in the pull request was also at times a bit confusing too look at due to the nature of the changes involved. The code introduces a map for "forward_orders", which is usually too slow of a data structure to use in performance-critical parts of the code. But I didn't investigate if forward_orders is used in performance-critical parts of the code. I also saw a few places where I wasn't sure about the amount of recomputation we do, but it's probably a better idea to do some profiling to see where we lost the performance and then look at that code more closely.

Can we open a followup issue for this, with the goal of recovering most or all of the 1.91/4.78 points lost?
msg9879 (view) Author: salome Date: 2021-01-28.12:33:08
The issue is merged. We also have a follow-up issue (issue993) where we want the LandmarkGraph object to be constructed in one shot, which enables us to make the graph fully constant.
msg9857 (view) Author: silvan Date: 2021-01-27.13:48:44
Looks good to merge.
msg9855 (view) Author: clemens Date: 2021-01-27.13:08:12
Alright, thanks for the explanantion!

So is there anything missing to finalize this issue?
msg9854 (view) Author: silvan Date: 2021-01-27.12:38:30
You would need to only specify one revision for the experiment, then use exp.add_fetcher and exp.add_report(...) to achieve the same manually. But we usually opt to re-run the base version in every experiment to avoid introducing any bias.
msg9853 (view) Author: clemens Date: 2021-01-27.12:04:00
I added the tags and changed the experiments accordingly.

I have one question related to these tags, but actually about the comparative reports. I don't know what would be the appropriate place to ask this, so I'm asking here. When setting up the experiments, I looked at a lot of examples where the comparative report compares the issueXY-base with some taged revision. Since issueXY-base remains the same for all tested versions of issueXY, it's not necessary to rerun the experiments for the base-revision. Is there a way to compute this only once for all versions and computing comparative reports based on that run? I know there's the option to fetch properties with lab, but I couldn't figure out how this would work for an IssueExperiment (which provides the function to add a comparative report).
msg9852 (view) Author: silvan Date: 2021-01-27.11:24:28
Ah, right, they are not permanent.

@Clements, to expand (because Thomas asked in issue990):

With use tags to tag revisions we want to test. That is, the "main" revision would be the revision from which you branch away, and it would be called "issue990-base". Then, whenever you want to run experiments, you tag the version you want to test by using tag "issue990-v1" etc. 

See for the correct workflow.
msg9850 (view) Author: malte Date: 2021-01-27.11:17:03
Please change the tags before merging. This is fortunately one of the things that is not so difficult in git. :-)
msg9846 (view) Author: silvan Date: 2021-01-27.11:03:42
Clemens, something I forgot to mention previously, for future: in the experiments, we usually use tags like issue988-base, issue998-v1 etc. for comparing revisions. I think you used "main" and "issue998", which is not enough when we have several iterations.
msg9827 (view) Author: silvan Date: 2021-01-27.08:08:52
Add link to meta issue.

I'm fine with the results as they are and suggest to merge and close this issue.
msg9815 (view) Author: clemens Date: 2021-01-26.19:02:07
I did some profiling together with Florian to get a deeper understanding of the reason for the increased runtime. Unfortunately, we did not find a reasonable explanation. The attached scatterplot shows that outliers exist in both directions. Testing locally, we often could not reproduce the difference. Even more, the roles were sometimes inversed, i.e., if a task took significantly longer on the grid with the new implementation, locally it was faster than the old implementation.

Our suggestion is to accept the overall (small) loss in runtime in favor of a cleaner implementation. If someone else is willing to spend more time looking into this, I'd be happy to help. At the moment, however, I'd rather dedicate that time to tackle other issues of the landmark code.
msg9812 (view) Author: silvan Date: 2021-01-26.16:01:17
Well, the larger the runtime in absolute terms, the larger the diff if something will be more expensive. But yes, it might be worth to have a look at where the runtime is lost.

Btw., please refresh the site before posting next time -- in my previous message, I assigned you to the issue and changed the status from in-progress to reviewing, but unfortunately this is not updated in your browser necessarily, so now you set this back again :)
msg9811 (view) Author: clemens Date: 2021-01-26.15:58:27
Ups, sorry. The link for lama-first is

There, one fewer task is solved with the new implementation. It is also in termes, specifically termes-sat18-strips/p15.pddl. I find it somehow concerning, that the previous implementation solved the task in 1540s, which means the updated code needs at least 260s more.
msg9810 (view) Author: silvan Date: 2021-01-26.15:54:21
You pasted the same link twice.

I already looked at the code and I'm now happy with it. 

Regarding the changes in search time: there are some somewhat larger changes in termes-opt, but other than that, the results in optimal planning are fine for me.
msg9809 (view) Author: clemens Date: 2021-01-26.15:45:25
The following changes are included in the pull request:
- move status of landmark to the LandmarkStatusManager class
- extract LandmarkStatusManager::dead_end_exists() from LandmarkStatusManager::update_lm_status(..)
- move computation of LM-count value to the heuristic itself
- give LandmarkGraph access to the TaskProxy (practically, this enables LandmarkGraph::dump() to be called without VariablesProxy, additionally it makes sense for the graph to know for which task it is created)
- change LandmarkGraph::dump() output to DOT format to enable visualization of graphs

Experimental results for alias "seq-opt-bjolp" (optimal planning) be found at

Experimental results for alias "lama-first" (satisficing planning) can be found at

Generally speaking: coverage is merely unaffected, runtime increases, and memory-usage decreases.
msg9792 (view) Author: clemens Date: 2021-01-22.10:49:08
I added issue989 to improve readability.
msg9790 (view) Author: clemens Date: 2021-01-22.10:44:34
We discussed that there are several things we could do to make the code more readable (e.g., change variable names, move implementation to source file).

We suggest to do this in a new issue that onlz does these things to make reviewing easier.
msg9789 (view) Author: clemens Date: 2021-01-22.10:41:28
I created a pull request at Silvan volunteered to review this afternoon.
msg9784 (view) Author: malte Date: 2021-01-21.13:44:08
@Salomé: if you think the class is pointless, remove it. But generally speaking it is considered good practice not to have too many responsibilities in one class, and if something can be cleanly separated from the rest of the heuristic, it is often worth putting into its own class. Even if the heuristic is the only user and we don't intend other users for the time being (i.e., the status manager is an implementation detail of the heuristic). But then it should be clear that this is part of the heuristic. (For example, the class could be defined and implemented inside the CC file of the heuristic. There's a balance between having too many files and files that are too long.)

@Clemens: can this method currently be called without changing the code (i.e., is it currently accessible through the user interface)? If not, feel free to change it. Otherwise, we maybe need to discuss a bit. In general, we try to split things up into smaller issues, but with this being "debug output only" and the fact that we'll have massive changes in the landmark code anyway, I see nothing wrong with combining this with the other changes in the issue.
msg9782 (view) Author: clemens Date: 2021-01-21.13:24:14
Another thing I'd like to change is the output when calling LandmarkGraph::dump(). Specifically, I suggest to use the DOT format in order to enable visualizing the graph. Should I add a new issue for this or can we do this as part of this issue?
msg9781 (view) Author: salome Date: 2021-01-21.13:18:17
Looking closer into the code we were wondering whether or not we want to keep the class LandmarkStatusManager. Its purpose is to store and update the information about reached landmarks (for all states in a PerStateBitset), and to compute which landmarks are needed again. Since currently only the lmcount heuristic uses that information, we could also put this functionality directly into the heuristic. However, it might not be a good idea if we want to support other heuristics based on landmarks in the future (i.e. we probably would need to reintroduce the class again).
msg9769 (view) Author: clemens Date: 2021-01-20.12:28:55
The LandmarkGraph class currently tracks the status of landmarks. Namely, the status of LandmarkNodes is changed during search. This functionality belongs to the heuristics using it and should be moved accordingly.
Date User Action Args
2021-03-22 13:49:41clemenssetmessages: + msg10231
2021-03-22 13:49:16clemenssetmessages: - msg10230
2021-03-22 13:48:47clemenssetmessages: + msg10230
2021-03-19 20:32:27maltesetmessages: + msg10218
2021-01-29 11:08:05salomesetmessages: + msg9939
2021-01-29 09:47:11salomesetmessages: + msg9936
2021-01-28 20:55:14maltesetmessages: + msg9916
2021-01-28 18:44:19silvansetmessages: + msg9899
2021-01-28 18:37:41maltesetmessages: + msg9897
2021-01-28 12:33:09salomesetstatus: reviewing -> resolved
messages: + msg9879
2021-01-27 13:48:44silvansetmessages: + msg9857
2021-01-27 13:08:12clemenssetmessages: + msg9855
2021-01-27 12:38:30silvansetmessages: + msg9854
2021-01-27 12:04:00clemenssetmessages: + msg9853
2021-01-27 11:24:28silvansetstatus: in-progress -> reviewing
assignedto: clemens
messages: + msg9852
2021-01-27 11:17:03maltesetmessages: + msg9850
2021-01-27 11:03:42silvansetmessages: + msg9846
2021-01-27 08:08:52silvansetstatus: reviewing -> in-progress
assignedto: clemens -> (no value)
messages: + msg9827
summary: This is part of meta issue987.
2021-01-26 19:02:07clemenssetfiles: + issue988-210126_satisficing-main-issue988-total_time-lama-first.png
messages: + msg9815
2021-01-26 16:01:17silvansetstatus: in-progress -> reviewing
assignedto: clemens
messages: + msg9812
2021-01-26 15:58:27clemenssetstatus: reviewing -> in-progress
assignedto: clemens -> (no value)
messages: + msg9811
2021-01-26 15:54:21silvansetstatus: in-progress -> reviewing
assignedto: clemens
messages: + msg9810
2021-01-26 15:45:26clemenssetmessages: + msg9809
2021-01-22 10:49:08clemenssetmessages: + msg9792
2021-01-22 10:44:34clemenssetmessages: + msg9790
2021-01-22 10:41:28clemenssetmessages: + msg9789
2021-01-21 13:44:08maltesetmessages: + msg9784
2021-01-21 13:24:14clemenssetmessages: + msg9782
2021-01-21 13:18:17salomesetmessages: + msg9781
2021-01-20 12:28:55clemenscreate