Issue1072

Title Landmark Count ignores conjunctive landmarks for preferred operators
Priority bug Status chatting
Superseder Nosy List clemens, jendrik, malte, salome, silvan, simon
Assigned To Keywords
Optional summary
Part of issue987.

Created on 2022-12-21.13:51:07 by clemens, last changed by malte.

Summary
Part of issue987.
Messages
msg11031 (view) Author: malte Date: 2023-02-21.16:45:04
I'm not so worried about what happens in mk_acyclic_graph.

The whole idea of making the landmark graph acyclic is bad in the first place, and we should work on getting rid of this soon. In the meantime, some changes of behaviour within that function are not a concern to me.

(This is just a comment on this specific aspect; I did not look at experimental results more generally. Let me know if I should, or more generally if you're waiting for me to do something/comment on something.)
msg11017 (view) Author: clemens Date: 2023-02-14.15:21:19
To give some more context: The function *mk_acyclic_graph* (I'm very unhappy with that name, by the way, but also by the idea of the function itself of course) explores the landmark graph starting from every node one after the other (skipping those nodes for which it previously found that it cannot be part of any cycle). It marks nodes encountered as visited and procedes until a previously visited node is encountered. If this happens, it removes the first weakest ordering on the path from the visited node back to itself. Hence, this choice depends on the order in which these landmark nodes are considered/expanded and this might change in the different versions due to the use of an unordered set as the data structure. The reason why a different amount of orderings is removed is, because cycles can overlap in the set of orderings they consist of, and hence it is possible to get rid of multiple cycles at once by removing a single ordering. Since the choice by the implemented algorithm is greedy and it simply removes the first-weakest ordering, this does not have to be the same number over all for two different versions.
msg11016 (view) Author: simon Date: 2023-02-14.15:02:56
In the new line of experiments (v3) Clemens and I looked into the difference of 
orderings. For domains like trucks we waved it of as part of the translator non-
determinism. 
However, blocksworld for example is not affected by that but has different 
numbers of orderings. We found that the step which makes the landmark graph 
acyclic uses an unorederd set. We checked it locally for probBLOCKS-10-0.pddl to 
confirm that the set is the same. We assume that the different order in the set 
removes the landmark-orders differently resulting in a different LM-graph with 
more or fewer edges.
msg11011 (view) Author: simon Date: 2023-02-10.17:30:11
The current version has some form of hierarchy such that if a operator to a simple landmark can be preferred (due to them being interesting) only operators to simple landmarks are preferred. Disjunctive ones only if no simple was found.

In the PR: https://github.com/aibasel/downward/pull/149 conjunctive landmarks are now able to become interesting if the option is set. Also the hierarchy can be controlled. 

We did some experiments https://ai.dmi.unibas.ch/_experiments/ai/downward/issue1072/data/ 
It seems that the use of the hierarchy does not cause any benefit that is significant over the noise.

As we did not see any reason to have this hierarchy in the first place the goal is to remove it. Additionally, the conjunctive landmarks should be always used if the landmark factory produces them.

A further cleanup of the code is needed and a followup experiment, too.
msg10899 (view) Author: clemens Date: 2022-12-21.13:51:07
The lmcount heuristic ignores conjunctive landmarks when computing preferred operators. In particular, *lgraph->get_node(fact)* returns a nullpointer when there is neither a simple landmark for *fact* nor a disjunctive landmark including *fact*. We should discuss how to derive preferred operators also for conjunctive landmarks and not just let these cases silently fall through. 

(This came up when working on issue1070.)
History
Date User Action Args
2023-02-21 16:45:04maltesetmessages: + msg11031
2023-02-14 15:21:19clemenssetmessages: + msg11017
2023-02-14 15:02:56simonsetmessages: + msg11016
2023-02-10 17:30:11simonsetnosy: + simon
messages: + msg11011
2022-12-21 13:51:07clemenscreate