This issue has been resolved with commit 84e75130

No, I agree about merging version 3. We are fixing a bug, and having the natural orders in there is good even if we do not currently benefit from them.

Thanks Clemens! 

Malte, did these experimental results change your mind wrt merging this issue?

I would also choose version 3 because it preserves the orderings that were used in the past (and fixing their type). Since they are correct (as you've shown), I think there's no real reason to throw them away. It is true that currently, natural orderings aren't used anywhere. Though, there might as well be use cases where we are interested in those orderings in the future (see for example our ICAPS 2021 paper on cyclic ordering dependencies of landmarks).

Malte, Clemens and I had a code review meeting and determined a few issues with the code, in particular with the deletion of landmark nodes (which was linear in the number of landmarks before issue1004-v2 and became quadratic in it). This is fixed in issue1004-v4, and statistic output has also been added.

issue1004-v3 (sorry for the confusing versioning, issue1004-v4 really is a predecessor of issue1004-v3) additionally implements the following: when a disjunctive landmark is replaced by a simple one, we keep all incoming orderings as natural (rather than greedy necessary) orderings. To see that this is correct, assume that L1={a}, L2={a,b1,...,bn} and L3={c} are landmarks and L3-gn->L2 a greedy necessary ordering. Since L1 \subseteq L2, we know that first(L2) <= first(L1) and due to the greedy necessary ordering we know that first(L3) < first(L2) (greedy necessary orderings are stronger than this, but this property suffices here). Hence first(L3) < first(L1), which is exactly the definition of natural orderings.

I conducted experiments with these two versions and compared to a baseline that is equivalent to issue1004-base with the exception that I added the same statistics output ("issue1004-base-with-stats"). Results can be found here:

https://ai.dmi.unibas.ch/_tmp_files/tkeller/issue1004-v3-v4-optimal-compare.html
https://ai.dmi.unibas.ch/_tmp_files/tkeller/issue1004-v3-v4-satisficing-compare.html

As expected, version 3 doesn't lose any orderings anymore (there are some differences, but all are due to trucks and citycar) but still suffers from the same increase in expansions in the parcprinter domain (this is because natural orderings aren't considered in the "needed again" computation, but greedy necessary ones are).

Version 3 tends to be slightly slower because it takes longer to generate the landmark graph, but the time differences vary a lot between different configurations (and in the case of seq-opt-bjolp, it even gets a little faster). However, the coverage difference between v3 and v4 is small (v4 has coverage of +1 for seq-opt-bjolp-opt and of +2 for lama-first-pref).

In our code review meeting, we decided that the code should be merged. The question is now which version to use. I suggest to stick with version 3 even though it is a bit slower and even though we don't really use the natural orderings at the moment. Are there other opinions?

Thanks Clemens, that's what I expected.

Malte, could you please have a look at this?

> I assume there is some non-determinism in the domin. Can someone confirm this?

Yes, I also observe varying numbers of landmarks in the citycar domain for issue383. There, my changes shouldn't affect the amount of generated landmarks, only the orderings and how the status of landmarks is updated during search.

Here is the link to the pull request for this issue:

https://github.com/aibasel/downward/pull/28

Experiment results can be found here:

https://ai.dmi.unibas.ch/_tmp_files/tkeller/issue1004-v1-v2-optimal-compare.html
https://ai.dmi.unibas.ch/_tmp_files/tkeller/issue1004-v1-v2-satistificing-compare.html

Some observations:

- The decrease in the number of disjunctive landmarks is due to consequence 3. described in my previous post. The total number of landmarks is stable except for the citycar domain in the satisficing configurations, but the fact that the numbers between the two configurations also don't match (which they should, they only differ in the usage of preferred operators which does not affect landmark generation), I assume there is some non-determinism in the domain. Can someone confirm this?

- The only domain where orderings are lost is the parcprinter domain. In this case, it also affects the number of expansions. 

- The changes in memory and time usage look acceptable to me.

- The changes in coverage also look acceptable to me: seq-opt-bjolp-opt loses 1 instance (+1/-2), lama-first gains 1 instance (+1/-0) and lama-first-pref gains 3 (+3/-0).

We identified a bug that occurs when a disjunctive landmark L is replaced by a simple landmark L' \subset L. Before addressing the issue, the LandmarkNode object that represents L was turned into L' by simply associating L' with the existing object and by deleting all outgoing orderings of the LandmarkNode object.

The issue comes from keeping incoming orderings: in the example instance attached by Clemens, two landmarks L1={at(rover1, waypoint0)} and L2={at(rover1, waypoint1), at(rover1, waypoint2) at(rover1, waypoint3)} and a greedy necessary order L1->L2 are generated. Later in the landmark generation process, a landmark L3={at(rover1, waypoint2)} is computed, which replaces L2 as a landmark and, due to keeping the incoming orderings, leads to a greedy necessary ordering L1->L3 which is not a greedy necessary ordering (in fact, rover1 cannot even reach waypoint2 from waypoint0).

The implemented fix no longer keeps and alters the LandmarkNode object in the case of replacing a disjunctive landmark with a simple one but deletes the disjunctive LandmarkNode object (along with all of its orderings) and creates a new simple LandmarkNode object. This should have the following consequences:

1. The simple LandmarkNode object is inserted into the open_landmarks queue of the landmark factory, and the algorithm hence checks for landmarks that achieve the new simple landmark. I assume this doesn't mean that landmarks can be generated that were not generated before because any landmark found by the landmark factory for a simple landmark {a} must also be found for a disjunctive landmark {a, b1,...,bn}. If this assumption is correct, the number of landmarks generated by the landmark factory should remain the same.

2. It is possible that the number of landmark orderings decreases.

3. A minor bug that counts the number of disjunctive landmarks is fixed along with this (see comment in line 201 in the file landmark_graph.cc in revision issue1004-base)

Sorry for the empty initial message...

I noticed obscure behavior in one of my experiments for cycle-covering and found that there seems to be a problem with greedy-necessary landmark orderings generated by the LandmarkFactoryRpgSasp class. Specifically, there is a a landmark L for which two greedy-necessary orderings L1->L and L2->L exist (see LM5 in rovers-output.txt). The output was generated for the PDDL task attatched to the initial empty message.

It cannot be that both of these orders are correct, because the facts of L1 and L2 are mutex. (A greedy-necessary order L->L' denotes that L must hold in right before L' becomes true for the first time.)