Part of issue987.

> The data does not confirm the previously stated claim that 1.+2. = 3. This of
> course does not imply that it wrong in theory, but only that there's more to
> be investigated before we can draw further conclustions.

I think these tasks cannot be minimized further. I think they are the trivially unsolvable tasks that the translator generates when it detects unsolvability during grounding. They have one state variable, which is binary and has a different initial and goal value, and they have no actions.

So it isn't a meaningful difference, but perhaps we should still look at which of the two behaviours we prefer and then decide which one we want. I guess from the definition of causal landmarks, in a known unsolvable task every atom should be a landmark because it is indeed a precondition or goal in every plan (vacuously). But perhaps it doesn't matter that much as long as we make sure that we get infinite heuristic values on tasks that we know to be unsolvable from landmark analysis. (But then if we document that we compute the causal landmarks of the delete relaxation, we should also document this exception.)

It indeed sounds like we should look into the achievers.

What I forgot to mention before: Landmark generation is indeed faster with hm(m=1), but this does not positively impact the overall planner time too much in the current implementation, although hm(m=1) is faster on average (e.g., https://ai.dmi.unibas.ch/_visualizer/?c=eJx9kEtOxDAQRK8SeY3tCSAh5Rzso56kSVryT-3Ob0Zzd2wQZINYul7Zr-S7wiBMmHtHWVTXqIZyXrC9vL3qK2TUzmvcZ1iy6JiEPLguBnfooUTgmj_qs29_quqpUTtIMVwXwfp8chACcl8wVnr8SxPHhCx13we5r8osknJnLZAZPZklUPGaYbY97qVbLgbJhdoxbmEDHu3vQjuCwHnU63PdqXEFZ0-TEWCz36qeMUWW9yNV80sJVuRMMdQdrbnUylA-JvreU-g3CrmQ--OMYZoYJ5DI3-TxCbmsgB0%3D).

Thank you for your inputs. Previously, I did not consider the connection between exhaust limited to causal landmarks and hm(m=1), but it sounds absolutely reasonable. I ran the suggested comparison experiment, here are the results: https://ai.dmi.unibas.ch/_experiments/ai/downward/issue1074/data/issue1074-v2-opt-eval/issue1074-v2-opt-only-causal-compare.html

The data does not confirm the previously stated claim that 1.+2. = 3. This of course does not imply that it wrong in theory, but only that there's more to be investigated before we can draw further conclustions.

For one, the number of landmarks found by the two methods is not always identical. Mostly it is, but there are two tasks in ther mystery domain (prob07 and prob18) where exhaust finds one additional landmark. This is probably a task for the minimizer to help us point out where this difference comes from. Maybe there's a tricky corner case that is dealt with differently in the two methods, but with my current understanding this is probably a bug and should therefore be fixed independent of what we do with the causal landmark filtering.

Another observation is that heuristic values are different even when both configurations yield the same number of landmarks. This means the cost partitionings end up having different results, which can only be the case if the landmarks end up having different achiever sets (assuming the same number of landmarks means that the landmarks are the same atoms). It would surprise me, if they indeed have different achievers, because I thought they were computed the same way independent of which landmark factory was used, but maybe I'm misremembering. This will definitely also require some further digging in the code.

Finally, in terms of coverage the exhaust approach is superior. It solves 4 more problems for both uniform and optimal cost partitioning. Before taking this too seriously, though, we should figure out where the differences come from. I currently trust in Malte's reasoning in the previous message, so I lean towards a faulty implementation, but as of now I'm not ruling out that we've overlooked something on the theory side either. I will think about it some more and investigate the implementation further. Any of your thoughts that might help track this down would also be much appreciated.

Thanks! Interesting and somewhat unexpected, but that's why we run the experiments.

Can you add results for hm(m=1) landmarks, and ideally compare them directly to lm_exhaust without causal landmarks in the comparison view?

The following is from memory, and perhaps I'm forgetting some relevant detail, but here is how I think lm_exhaust, causal landmark removal and hm(m=1) work, roughly:

1. lm_exhaust performs a relaxed exploration for each atom X in the problem to check if it's a landmark; this is done by checking if the relaxed task is unsolvable if we remove actions that achieve X. (With perhaps some special-casing if X is in the initial state.)

2. causal landmark removal performs another relaxed exploration for every atom that has been detected to be a landmark and removes it if it's not a causal landmark; this is done by checking if the relaxed task is unsolvable if we remove actions that have X as a precondition (plus perhaps some special stuff if X is a goal)

3. hm(m=1) landmarks compute the same set of landmarks as 1.+2., but with a specialized algorithm that only does a single relaxed exploration that handles all atoms at the same time. (This is much more expensive than each individual exploration from 1. and 2., but computes everything at once.)

I'd be curious to see how 1.+2. compares to 3. If 1.+2. is just an inferior version of 3., that would add weight to the suggestion of removing 2.

I don't remember if hm(m=1) also computes orderings. If yes, it would make sense to also run a version of it (and compare it to 1.+2.) with orderings disabled to make them even more similar because IIRC 1.+2. does not compute orderings (and that's also what it looks like in the reports).

That 1.+2. does better than 1. is not necessarily expected, but can make sense because of poor cost partitioning or because of overhead when we have many landmarks that are ultimately not useful. But if it is a decent set of landmarks worth keeping around, then the way we compute it seems really stupid. Like Clemens wrote, it's quite pointless to go over every atom and first run the check in 1. and then the check in 2., rather than running the check in 2. immediately.

Here are the results from my experiments: https://ai.dmi.unibas.ch/_experiments/ai/downward/issue1074/data/

There are (currently) three reports:
- v1-sat containing lama-first with and without preferred operators
- v1-anytime containing full lama
- v1-opt containing the cross product of {exhaustive, rhw} landmark generation and {uniform, optimal} cost partitioning

Notably, filtering for causal landmarks seems to fail on tasks with conditional effects, so much fewer problems are solved over the entire benchmark suite. I've removed those runs to clean up the reports, though.

Generally, removing the non-causal landmarks seems to have a positive effect, so I'm not so sure anymore we actually want to remove this option. As Malte has said in the offline meeting, though, this performance increase might be caused by the lower number of landmarks rather than the fact that all considered landmarks are causal. If so, one could also simply drop half of the landmarks that were found (independent of whether they are causal or not) to achieve a performance increase. We did not test this hypothesis, but I can well imagine it holds.

To give more details on the results:
- Most domains have non-causal landmarks, so the change affects many problems.
- lama-first (with and without preferred operators) finds lower cost plans in most problems of the Miconic domain, but no other domains.
- In lama-first, the search time score improves by 1-2 points while the overal time score decreases by 11-12 points in total (indicating that precomputation is more expensive but pays off a little bit when focussing on the search).
- lama-anytime also finds cheaper plans in Miconic. Other domains show different costs as well, but this might as well be grid noise, as the differences are small and may be due to finishing fewer or more search iterations which we have observed in the past for other issues.
- With exhaustive landmark generation, dropping all non-causal landmarks again leads to solving 15-17 tasks more, depending on the cost partitioning strategy. If this is the main reason to keep this option, we could also consider building it directly into the exhaustive landmark generation, which now does two independent reachability analysis (if I remember correctly). I think it should be possible to simply only exhaustively produce all causal landmarks instead of also producing non-causal ones and dropping them again later.
- seq-opt-bjolp also seems to be slightly faster with only causal landmarks, but gaining not even 1 scoring point in search time.

These are just a few observations. Is there something you would like to know in more detail? How should we continue with this issue? I generally like the idea of removing the option completely since doing so makes the code simpler and there is no configuration for which we currently recommend using this option. However, I'm hesitant to do this as the experiments show improved performance if the option is turned on.

In an offline meeting yesterday, Florian, Malte, Salomé and I discussed the option to get rid of the "only causal landmarks" support instead of moving it to its own factory. This is motivated by the fact that there is no good reason to remove non-causal landmakrs ("side effects") as they still denote correct information and should be handled correctly by the landmark progression. Further, removing all non-causal landmarks from a landmark graph seems to be a rather expensive operation, so doing this might do more harm than good.

I am hijacking this issue to do some experimentation on whether any configuration benefits from the option that is currently implemented before we make any concrete decisions.

Some landmark factories provide an option to ensure that the returned landmark graph only contains causal landmarks (i.e., landmarks that either hold in the goal or make the relaxed planning task unsolvable when removing all actions satisfying the landmark in their precondition). This option is applied in the form of a post-processing step, removing all non-causal landmarks from the landmark graph. We have recently implemented similar post-processing steps (e.g., reasonable orderings) as a separate landmark factory instead of an option. It takes as an input the result of another landmark factory and outputs the processed (in this case filtered) landmark graph. On the command line call, this results in a nested set of landmark factories rather than adding a set of options. We would like to implement the post-processing for causal landmarks in this style as well.