Title Explore ways to generate reasonable and/or weak orderings
Priority wish Status chatting
Superseder Nosy List clemens, jendrik, malte, salome, silvan, thomas
Assigned To Keywords
Optional summary
Part of issue987.

Created on 2023-08-02.16:57:06 by clemens, last changed by malte.

Part of issue987.
msg11271 (view) Author: malte Date: 2023-08-07.19:42:27
I want to emphasize the point in the last paragraph. I think that the way we currently mix strict and non-strict orderings is ugly and feels arbitrary. This should be fixed one way or the other. It may be a good idea to discuss this point in a live (physical or virtual) meeting first.
msg11256 (view) Author: clemens Date: 2023-08-02.16:57:06
After resolving issue1036, we have a principled and sound way to deal with reasonable orderings. This brought up an ancient discussion from issue202 which reasonable orderings should be generated in the first place. For example, for two landmarks A and B which both hold in the initial state, it is always true that there are reasonable orderings A-->B and B-->A. However, we don't think there is any information to be exploited from such orderings by a heuristic. Hence, when created and not removed at any point, these orderings are an overhead during search because they require memory and potentially time when looping over all orderings. With the sound reasonable ordering progression from our paper (Landmark Progression in Heuristic Search, ICAPS 2023), it is worth investigating which orderings are actually useful and whether we have more ideas for creating useful reasonable orderings apart from the technique originally proposed by Hoffmann et al. In any case, we open this issue so we can close issue202 which served a different objective. I believe msg1150 might be the main takeover from that issue to add to this discussion.

In this context, we would also like to consider the option of replacing reasonable orderings by the simpler concept we started to call weak orderings. Currently, this ordering type does not exist in Fast Downward and we do not have a proper theory how to generate them. The way we did in the paper "Exploiting Cyclic Dependencies in Landmark Heuristics" (ICAPS 2021) was using the reasonable ordering factory and dropping the orderings where both landmarks have common achievers.

Moreover, it might be interesting to consider strict and non-strict versions of *all* landmark ordering types. This question arises from time to time because reasonable orderings allow the special case where A and B are added at the same time (a generalization of the aforementioned case where both hold initially), whereas all other ordering types do not allow this. I used to believe achieving both A and B at the same time should not be allowed for any ordering type, but maybe we find some examples where this could actually be useful. For example, if they are added together in some cases but not in others (i.e., along some trajectories but not along all), then the ordering information could still be interesting.
Date User Action Args
2023-08-07 19:42:27maltesetmessages: + msg11271
2023-08-04 08:44:39thomassetnosy: + thomas
2023-08-02 16:58:39salomesetnosy: + salome
2023-08-02 16:57:06clemenscreate