OK, the last thing that remained to be done here is check if the bug in
LandmarksGraph::interferes() in any way affected the optimal LM heuristics (in
which case we'd have to check the impact).

I looked at the code, and LandmarksGraph::interferes is only called from
LandmarksGraph::approximate_reasonable_orders. So I'm closing this one.

The test in collect_ancestors is correct as it stands, since this method is
only called when approximating reasonable and obedient-reasonable orderings,
where obedient-reasonable orderings are derived from reasonable orderings
(collect_ancestors with "use_reasonable" set to true), but no further
orderings are derived from the obedient-reasonable orderings. (Even if
obedient-reasonable were included in the test, this would make no difference
since they don't exist at that point in time yet.)

The "interferes" test does not affect the LAMA heuristic, since there,
"required again" is defined as "false at the moment and greedy-neceessary
predecessor of an unachieved landmark". So "interferes" plays no role there.
I'm not sure about different implementations, e.g. the optimal landmark
heuristic. Could be that "required again" is computed differently there.

I'd rather look at the code some other time, since I only have 2 days to go
till the submission deadline of my thesis. Might get around to it today, but
no promise.

OK, fixed. Does the "interferes" test affect anything other than computation of
reasonable orders? In particular, is this a threat to the correctness of the
"required again" computations?

I've committed my attempt to clean this up to the issue122 branch, where it
kind-of fits since it's also about cleanups (and extensions) of the landmark
code. The commit that is supposed to clean up the edge names is here:
http://hg.fast-downward.org/rev/c11630203a5c

Can you have a look to see if this looks correct? If yes, and if the thing I
mentioned in msg666 below is also correct, we can mark this issue as resolved.

I think you are correct in both cases, Malte.

The test in
// 3. Exists LM x, inconsistent x, b and x->_gn a

must have been overlooked (not updated) when the change of meaning for "n"
occured. Since we don't have necessary orderings anymore, this test should
only trigger for greedy-necessary orderings.

Another thing: in LandmarksGraph::collect_ancestors, there is a test

    if (edge == gn || edge == n || (use_reasonable && edge == r))

Is it correct that obedient reasonable orders are not considered here?

There is a similar test in LandmarksGraph::approximate_reasonable_orders:

============================================================================
                        if ((edge == gn || edge == n
                             || (obedient_orders && edge == r)) &&
                            &parent != node_p) {      // find predecessors or
parent and collect in
                                                      // "interesting nodes"
============================================================================

I assume that here the test is correct because natural orderings *are* used in
this context according to what Silvia wrote earlier. Correct?

The following code is from LandmarksGraph::interferes.

============================================================================
        // 3. Exists LM x, inconsistent x, b and x->_gn a
        const LandmarkNode &node = *node_a;
        for (hash_map<LandmarkNode *, edge_type, hash_pointer>::const_iterator it =
                 node.parents.begin(); it != node.parents.end(); it++) {
            edge_type edge = it->second;
            for (int i = 0; i < it->first->vars.size(); i++) {
                pair<int, int> parent_prop = make_pair(it->first->vars[i],
                                                       it->first->vals[i]);
                if ((edge == n || edge == gn) && parent_prop != b && inconsistent(
                        parent_prop, b))
                    return true;
            }
        }
    }
============================================================================

The "edge == n" case in the test "(edge == n || edge == gn)" looks wrong to me
since the comment above refers to greedy-necessary orderings, and "n" here means
"natural" (not "necessary").

Am I correct that this should be changed and the test should only trigger for
necessary or greedy-necessary orderings?

By '"n" landmarks', I meant '"n" ordering', of course.

The "ln" orderings are indeed used in a few places -- what is used nowhere,
apparently, are the "n" landmarks. Can you confirm that "n" orderings should
never be generated, or is that a problem with the code?

"ln" stands for "look-ahead necessary". That's a legacy name, and is
indeed terrible. These orders are created by doing a one or more step
lookahead during the backchaining, but of course they should be named
in the way they're used later, not according to how they are created.
These orders are "natural", and should be called that. I had done that
in the emil-new branch at some point, if I remember correctly, so that
change could possibly just be ported.

Natural orderings are useful for deriving reasonable orderings and
they make the computation of preferred operators more efficient (e.g.,
the pref. ops. computation can ignore a landmark if it has a natural
predecessor that hasn't been achieved yet). So, natural orderings
should not be abolished.

Right, that much is correct (and msg236 is wrong).

However, there are still a few problems with the code:

1) Even though necessary orders are greedy-necessary, they are not handled that
way. Only LMs stored as "greedy-necessary" (gn) are ever treated as required
again; ones stored as "necessary" (n) are not considered in
LandmarkStatusManager::check_lost_landmark_children_needed_again. So this test
would need to be changed, e.g. by replacing "==" with ">=".

2) Correct me if I'm wrong, but it looks like the landmark type "n" is never
actually used. Then why have it?

3) What does "ln" stand for? Natural order? If yes, that's a terrible named and
should be changed. (FWIW, n and gn are terrible names, too. These should all be
spelled out.)

4) Also, the point about having to document that the ordering of the values
matters still stands.

Actually, necessary ordering are stronger than greedy necessary (a special case), 
and so the ordering is fine. 
I am closing this issue.

Assigning this to Erez. Erez, can you look at this, especially the third point
in the previous message?

In chasing some oddities in the emil-new branch, I noticed that the numerical
values for the various landmark ordering types are ordered in the wrong way.
Since "higher-value" orderings replace "lower-value" orderings, the most useful
orderings should have the highest value. The most useful orderings (unless I'm
mistaken) are greedy-necessary orderings, yet the highest numerical value is
assigned to necessary orderings.

We should:
* change the numerical values
* document next to the definition of the enum that and why the actual values matter
* analyze the impact of this on the relevant configs of LAMA and Erez's
admissible landmark heuristic

(The third one here is the tough one -- hence I haven't applied the fix for this
yet.)