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.
|