> Or maybe we can just announce it together with the changes from the sprint.

Sounds good! I've removed the TODO about the announcement from the summary.

Great to see this merged. I think this is a significant step on the way towards
better landmark code. Many thanks, Jendrik!

Or maybe we can just announce it together with the changes from the sprint.

Merged. I'll send an email to the public mailing list.

Thanks, Jendrik! I left one more comment on bitbucket which we shold take care
of. I don't think the changes since the last experiment require a new experiment
if you have run some basic sanity tests of the affected configurations, so this
looks otherwise ready to merge. :-)

Sometimes, we have to manually click on "Update pull request" (or similar) in 
the top right of the pull request site. Here, the problem was simpler: I forgot 
to push :-)

Notification for comments on commits works as expected, I think. I have never 
had any issues with that.

Specifically, the comments I have in mind are:

- removing a comment and simplifying the control flow by inverting an "if"
- two #includes that look like they are no longer needed
- a question about setup_exploration_queue

(Hope that was all.)

Does notification for comments that directly refer to commits rather than the
pull requests actually work properly?

Hi Jendrik, I only see one commit, with the doc change, but I think there were
other comments about removing comments and similar things. Do you need to push
more commits, or do I need to do something to update the pull request? I tried
looking for things to click, but didn't find any.

I'm done handling your comments.

Experimental results look good! :-)

PS: I think the latest comments were not actually on the pull request, but on
the individual commits, as suggested by Jendrik. I think Jendrik will
automatically get the appropriate email notifications anyway, but this may make
it a bit harder to find the relevant comments for others following the issue on
bitbucket.

I'm done commenting on the pull request. The main thing I'm not yet fully happy
with is the part of the documentation that gives the rationale for why we
diverge from the heuristic from the literature. In addition to adding the
synopsis section with the literature pointers, I would perhaps rephrase the new
note along the following lines:

title of the note: "Differences to the literature":

This heuristic differs from the description in the literature (see references
above) in the set of preferred operators computed. The original implementation
described in the literature computes two kinds of preferred operators:

1. If there is an applicable operator that reaches a landmark, all such
operators are preferred.
2. If no such operators exist, perform an FF-style relaxed exploration towards
the nearest
   landmarks (according to the landmark orderings) and use the preferred
operators of this
   exploration.

Our implementation of the heuristic only considers preferred operators of the
first type and does not include the second type. The rationale for this change
is that it reduces code complexity and helps more cleanly separate
landmark-based and FF-based computations in LAMA-like planner configurations. In
our experiments, only considering preferred operators of the first type reduces
performance when using the heuristic and its preferred operators in isolation
but improves performance when using this heuristic in conjunction with the FF
heuristic, as in LAMA-like planner configurations.

I think where the documentation refers to "the literature", it should be more
specific. If you search for "AAAI Press" on
http://www.fast-downward.org/Doc/Evaluator, you see that for other heuristics we
sometimes give an intro in the heuristic description that describes which
paper(s) a heuristic is based on. I think we should do the same here.

For the inadmissible heuristic, the correct paper may or may not be "Landmarks
Revisited". (We would need to check if this indeed discusses all the aspects
related to preferred operators.) If not, the LAMA journal paper is probably the
best reference, and perhaps both should be cited in any case.

For the admissible landmark heuristic, one important reference is the Karpas &
Domshlak paper on admissible landmarks, and I think our method for optimal cost
partitioning comes from the Keyder et al. paper on the h^m landmarks. (But again
that is something that we ought to verify.)

Update summary: the docs now describe the difference to the original 
implementation.

I took care of your comments and turned Exploration into a stand-alone class, 
i.e., it doesn't inherit from Heuristic anymore. It's probably best to inspect 
the individual commits.

Here are the results:

https://ai.dmi.unibas.ch/_tmp_files/seipp/issue846-v2-lama-first-issue846-base-issue846-v2-compare.html
https://ai.dmi.unibas.ch/_tmp_files/seipp/issue846-v2-bjolp-issue846-base-issue846-v2-compare.html

I don't see any blockers (the Slurm "Exceeded job memory limit" error happens, because I used an old Lab 
version accidentally).

I did a quick review and left some comments on bitbucket. It's refreshing to see
16 lines of green vs. 178 lines of red in the diff. :-) (Not counting the tags
and experiments, of course.)

For a more thorough review, it would be good to see if more code could be
removed now, but that's not something that can be seen from the diff, and my
mental map of the landmark code is poor. I think more cleanup can and should be
done, but it doesn't have to be done in this issue as long as we don't lose
track of it.

So if the experiments are fine, this looks OK to merge.

I like the plan :-)

I prepared a pull request at
https://bitbucket.org/jendrikseipp/downward/pull-requests/103 and experiments for 
lama-first and bjolp are running.

Thanks, Jendrik! I think the whole data management of the landmark heuristic
should be changed drastically. These sets of landmark nodes should not exist in
the first place.

Perhaps it's not advisable to look too closely at individual parts of the code
at this point because what is a bottleneck now might no longer be a bottleneck
once we've looked into this, and also things that are currently not bottlenecks
might become ones.

I suggest we defer whether or not we can get rid of the pref option until we've
improved the computation of the lmcount heuristic in general. This is something
we have staved off for a long time because there were so many pieces involved,
but once the heuristic no longer depends on the Exploration class, I think
cleaning up the heuristic might become feasible.

So my suggestion for a plan would be:

1. Get rid of the complex preferred operators (this issue).
2. Improve the computation of lmcount as a whole (not yet an issue, I think).
3. Consider whether we can get rid of the pref option (not yet an issue in
itself, I think, but it's the last missing piece in the option caveats issue we
already have).

I looked into this briefly and made a profile for BJOLP with pref=simple 
(attached). It seems the bulk of the extra time is spent converting the 
BitsetView to an std::unordered_set<const LandmarkNode *> (20% of the total 
time). I think it could make sense to avoid this conversion, maybe by 
introducing a wrapper class that holds the BitsetView and a reference to the 
landmark graph and can compute all the relevant information without allocating 
extra memory. However, a quick test with admissible=false spends much less time 
in the convert_to_landmark_set() function, so I doubt this change helps much 
once the heuristics know whether the search wants preferred operators.

> Regarding the "pref" setting, I think we could try to make computing the
> preferred operators faster with the goal of removing the "pref" setting and
> computing preferred operators unconditionally. I see several possible
> improvements that could make the code faster. Should I open an issue for this?

Please do if you want to work on it in the near future or know someone else who
does. I'd rather not open one if we don't have immediate plans to act on it.

I think even with a very good implementation, we will probably still want to
disable preferred operators for admissible landmark heuristics, but speeding the
computation up will be useful in any case.

Perhaps a better way to get rid of the pref option in the future would be to
improve the communication between the search code and heuristics code so that
heuristics know whether or not preferred operators are needed. This doesn't
actually sound difficult to implement.

> I don't think it's really necessary to announce the change on downward-dev
> since everybody who's interested in this had the chance to add themselves
> to the nosy list when the issue was created, but I'll send a mail
> nonetheless :-)

From speaking to others in the group, I think there are a few people who are a
bit too busy to always consider the new issue emails very thoroughly, but still
appreciate being kept in the loop for "important" changes. Of course the
question is where to draw the line.

> I'll also write an announcement for the public mailing list regarding the
> changes during the sprint.

Great! I'm happy to help with it if you'd like help, e.g. review the email for
completeness.

I agree that it's probably best to only do the change in the issue title here.

Regarding the "pref" setting, I think we could try to make computing the 
preferred operators faster with the goal of removing the "pref" setting and 
computing preferred operators unconditionally. I see several possible 
improvements that could make the code faster. Should I open an issue for this? 

I don't think it's really necessary to announce the change on downward-dev since 
everybody who's interested in this had the chance to add themselves to the nosy 
list when the issue was created, but I'll send a mail nonetheless :-)

I'll also write an announcement for the public mailing list regarding the changes 
during the sprint.

Thanks! I would say the lama-first-no-ff experiment is as expected and explains
why the "complicated" preferred operators were included in the heuristic. But it
basically achieves this by mixing in bits of the FF heuristic, and if you do
that, you might as well actually using bits of the FF heuristic explicitly as a
second heuristic, so that's not a reason to keep the complex landmarks around.

The BJOLP experiment shows that the overhead of computing the preferred
operators unnecessarily is quite substantial, so removing the "pref" option
would certainly be premature.

Still not sure about what should be the default for "pref". One option could be
a setting that makes it true iff admissible=false is passed, but that is perhaps
too subtle.

I suggest we can go ahead with the change in the issue title, but I think we
should first write to downward-dev to alert people of this semantics change and
give them a chance to comment/complain.

When making this change, we should make sure that the documentation explains
this difference in behaviour to the heuristic described in the original papers
on this, and we should mention this change in the forthcoming announcement to
the public fast-downward list. (Is that announcement still forthcoming? ;-) I
don't think we should delay it much longer while the sprint is still somewhat
fresh in our memory.)

We should also make sure that the lmcount heuristic actually no longer uses the
Exploration class because otherwise we haven't really gained much in terms of
code complexity.

Here are the results of the other two experiments:

https://ai.dmi.unibas.ch/_tmp_files/seipp/issue846-v1-bjolp.html
https://ai.dmi.unibas.ch/_tmp_files/seipp/issue846-v1-lama-first-no-ff.html

Thanks, Jendik!

The cost of computing and then ignoring the "simple" preferred operators is
lower than I thought. Not so low that I would immediately suggest discarding the
"pref" option by computing preferred operators unconditionally, but this
certainly gives us food for thought.

I think there is a substantial amount of code surrounding the landmark heuristic
that is in need of a performance review, so I think we shouldn't jump to
conclusions from these results. In particular, it may be possible that we will
be able to speed up the main heuristic computation substantially, in which case
the preferred operator computation might become more of a bottleneck than it
currently seems to be.

All these reservations aside, this looks interesting. If the BJOLP results show
similar trends, we might consider enabling preferred operators for lmcount by
default, which might already make this much less of a caveat than the current
default of disabling them. (I think the main issue right now is how easy it is
to forget that you need to set pref=true. Forgetting to set pref=false might be
less of an issue if the runtime difference between the two settings is small.)

Here are the results for the first of the three experiments:
https://ai.dmi.unibas.ch/_tmp_files/seipp/issue846-v1-lama-first-ignore-pref.html

Thanks, Jendrik! That looks encouraging. I think we could get rid of the
expensive preferred operators, If it weren't for the maintenance domain (which
perhaps really deserves a closer look at some point), it would even have better
coverage than pref=false.

What do you (plural) think?

In a perfect world, we would like to compute the simple preferred operators
always, as in the other heuristics that use preferred operators, so that we can
get rid of the "pref" option and hence get rid of the OptionCaveat page.

To see how far away we are from that, can you run another experiment where we
compare:
- pref=none
- pref=simple
- pref=simple, but not actually using the lmcount heuristic's preferred operators?

Just the "lama-first" variant is enough, I don't think we need the anytime
version, though it might give us a little bit of extra information if you prefer.

Also, can you run bjolp on the optimal tasks with pref=false and pref=simple, so
that we can get an idea of the overhead we would get there if preferred
operators were always computed?

Finally, can you run something like lama-first, but *without* the FF heuristic,
i.e., only using the landmark heuristic, with
- pref=none
- pref=simple
- pref=all
? That should give us a bit more of an idea how useful these preferred operators
are in isolation. (I expect that here pref=all might win, which is fine. We can
still get rid of it. If someone wants FF-style preferred operators, they can use
the FF heuristic for that.)

If it turns out that we cannot afford to always compute preferred operators,
another way to get rid of the OptionCaveat page is to make the "pref" flag
automatic, i.e., automatically figure out somehow whether preferred operators of
the heuristic are going to be used and compute them iff they will be used. This
would require some additional plumbing in the search algorithms, evaluators and
perhaps in the open lists. I don't think it would be terribly complicated, but
it would be nice if we could avoid it.

I implemented your suggestion and ran two experiments:

https://ai.dmi.unibas.ch/_tmp_files/seipp/issue846-v1-lama-first.html
https://ai.dmi.unibas.ch/_tmp_files/seipp/issue846-v1-lama.html

I had a quick look at the code, and this looks easy to try out.

The key method is LandmarkCountHeuristic::compute_heuristic in
landmarks/landmark_count_heuristic.cc. It currently looks like this:

==================================================================================================

int LandmarkCountHeuristic::compute_heuristic(const GlobalState &global_state) {
    State state = convert_global_state(global_state);

    if (task_properties::is_goal_state(task_proxy, state))
        return 0;

    int h = get_heuristic_value(global_state);

    // no (need for) helpful actions, return
    if (!use_preferred_operators) {
        return h;
    }

    // Try generating helpful actions (those that lead to new leaf LM in the
    // next step). If all LMs have been reached before or no new ones can be
    // reached within next step, helpful actions are those occuring in a plan
    // to achieve one of the LM leaves.

    BitsetView landmark_info =
lm_status_manager->get_reached_landmarks(global_state);
    LandmarkSet reached_lms = convert_to_landmark_set(landmark_info);

    int num_reached = reached_lms.size();
    if (num_reached == lgraph->number_of_landmarks() ||
        !generate_helpful_actions(state, reached_lms)) {
        set_exploration_goals(global_state);

        // Use FF to plan to a landmark leaf.
        vector<FactPair> leaves = collect_lm_leaves(
            ff_search_disjunctive_lms, reached_lms);
        if (!exploration.plan_for_disj(leaves, state)) {
            exploration.exported_op_ids.clear();
            return DEAD_END;
        }
        OperatorsProxy operators = task_proxy.get_operators();
        for (int exported_op_id : exploration.exported_op_ids) {
            set_preferred(operators[exported_op_id]);
        }
        exploration.exported_op_ids.clear();
    }

    return h;
}

==================================================================================================

The key features of this are:

- The test of "use_preferred_operators", which aborts early without computing
operators if we have set pref=false.

- The call and return value of "generate_helpful_actions", which computes the
"simple" helpful actions and returns true if any were generated and hence helps
control whether or not the "difficult" (FF-based) landmarks are computed.

There is an additional test there regarding "num_reached ==
lgraph->number_of_landmarks()" that mainly has to do with reasonable action
orderings and that I would suggest to ignore for now.

So I would suggest that we (temporarily, for this issue) replace
"pref=false/true" with an enum with values like "none" (the current false),
"all" (the current true) and "simple" (computing the ones from
generate_helpful_actions, but not the FF-based ones from inside the large "if"
block) and then run an experiment.

I would say the most interesting configurations (apart from this setting) are
again lama-first and lama.

In issue839 we noted that letting the lmcount heuristic compute preferred 
operators, i.e., lmcount(..., pref=true), leads to fewer expansions but slows 
down the search (msg7775, item 4). As a result, coverage for pref=false is higher 
than for pref=true. We therefore want to change how the lmcount heuristic 
computes preferred operators, speed up this computation and always enable it. 
Quoting Malte in msg7768 for background and details:

===============================================================================

Background for why the pref=true option of the landmark heuristic exists:

In our code, heuristics don't know whether preferred operators are going to be
needed or not, so heuristics like h^FF and h^add compute them whether or not
they are going to be used. This is OK because the overhead is not very large,
especially for h^FF, and it is very unusual not to use preferred operators 
anyway.

For the landmark heuristic, computing preferred operators can be expensive, and
hence we only want to do it if they end up being used. Hence the pref=true
option to enable the computation of preferred operators. If and for what the
preferred operators are going to be *used* is a different matter controlled by
the search algorithm, not the heuristic. It is currently very easily possible to
compute the preferred operators and not use them, or use them but not compute
them (= using the empty set of preferred operators) [...]. Hence why we consider 
this an option caveat.

The basic idea of what preferred operators for the landmark heuristic are (not
sure if it is implemented exactly like that) is as follows:

1. If there is an applicable operator that reaches a landmark, all such
operators are preferred.

2. If no such operators exist, conduct an FF-style relaxed exploration towards
the nearest landmarks (according to the landmark orderings we have) and use the
preferred operators of that.

No #1 should be cheap, but no #2 is expensive because it needs to conduct a
relaxed exploration that would otherwise not be necessary. It also carries a
high cost in code maintenance. The landmark heuristic needs to include a way to
compute something like the FF heuristic internally *just* for #2 of the
preferred operator computation. So it would be great to be able to get rid of
that. Rather than ripping out preferred operators entirely, I think it would
make a lot more sense conceptually to only rip out #2, but keep #1 and have it
done always, like other preferred operator computations.

[...]

===============================================================================