We believe the purpose of this issue is served with the integration of issue1036. I hereby mark this issue as resolved. There is however one part of the discussion that might still be relevant for future reference: We would like to investigate in which cases it makes sense to generate a reasonable ordering, as touched upon in msg1150. I've opened issue1104 for this purpos and mentioned the connection to this issue.

I've been checking on some of our planner configurations and was surprised that
we don't use reasonable orders in BJOLP. I think we discussed a while ago that
and how reasonable orders can be used for admissible heuristics, but never acted
on it.

Adding this comment and changing the title of the issue as a reminder to look
into this later.

When we look into this, we need to revisit the way that the orderings are
handled by the heuristics.

In the code we don't make a distinction between reached and accepted, we only 
keep track of something we call reached, but is really the accepted landmarks.

The code that keeps track of this is still more or less the same as in the 
original LAMA (at least, the logic is the same) - once a landmark becomes true, 
we check if all of its parents are also reached (according to the same 
definition), and if so, add it to reached. 
You can have a look at this in LandmarkStatusManager::update_reached_lms(...)

So if I understand Silvia correctly, that means the planner still has this 
problem.

Sure, we can point out that it should have been done differently.

> If you're going to write an errata for the paper, note that it's not
> enough to fix the definition in the text... what would also be
> required is to correct the planner code so that it implements the new
> definition and then rerun all the experiments. I don't think we want
> to do this :)

Surely if it's a technical error it should be pointed out even if we don't want
to rerun the experiments?

> If we want to fix this in the planner, we'll have to know for each
> state which landmarks have been true at least once on the path to this
> state. Do we already keep track of this information (e.g. to
> distinguish between using first achievers and all achievers for a
> landmark in the cost partitioning for the admissible LM count
> heuristic), or is this something that would need to be added?

As far as I can tell, we only keep track of the reached landmarks, but not of
the accepted landmarks. Erez knows more about this and can probably usefully
comment on the code -- I don't think I can.

Addressing the "theory" question: we wrote in the AAAI paper that "an
accepted landmark is required again if it is not true in s and it is
the greedy-necessary predecessor of some landmark which *is not
accepted*." This should rather be "...and it is the greedy-necessary
predecessor of some landmark which *has never been true*". By using
the former rather than the latter definition in our heuristic, we're
treating all greedy-necessary orderings as if they were necessary
orderings. The result of that is that the heuristic may sometimes
regard a landmark as required again even though we're not actually
sure it's really required again.

If you're going to write an errata for the paper, note that it's not
enough to fix the definition in the text... what would also be
required is to correct the planner code so that it implements the new
definition and then rerun all the experiments. I don't think we want
to do this :)

If we want to fix this in the planner, we'll have to know for each
state which landmarks have been true at least once on the path to this
state. Do we already keep track of this information (e.g. to
distinguish between using first achievers and all achievers for a
landmark in the cost partitioning for the admissible LM count
heuristic), or is this something that would need to be added?

Wow, it's been 7 months since the last update to this issue.

I think it would be good if we could wrap our head around this conceptually for
the journal paper, and decide if anything else needs to be done from an
implementation perspective.

Can someone who understands the landmark code better than me tell me which of
the concerns raised in msg1125 and msg1150 are now resolved and which are still
valid?

Regarding implementation choices, we should write down somewhere in the code
what the tradeoffs are (how to define reasonable orders w.r.t. simultaneous
achievement, and the two possibilities for implementing the sufficient
criterion, as well as which one we implemented and that we haven't tested the
other one). Basically, it should contain enough information to allows us to
close this issue without losing significant information.

Silvia mentions that the theory of this was wrong, too:

    I noticed that this is already wrong in the definitions of the AAAI-08 and
    JAIR papers.

Silvia, can you elaborate what exactly is wrong where, and how to fix it?
Regarding the AAAI paper, I'd like to add an erratum to my webpage, and we
should add a TODO into the journal paper that notes that this is wrong elsewhere
and why, and in which cases it can cause trouble (maybe quoting the example in
this issue).

Addendum: Results here:

http://www.informatik.uni-freiburg.de/~helmert/exp-lama-combined-eval-d-abs.html
http://www.informatik.uni-freiburg.de/~helmert/exp-lama-combined-eval-p-abs.html

The new config is the one called WORK-WORK-WORK-lama. You can see it's slightly
better than the "noreas" configs. It has lower coverage than the configs that
ignore costs, but that's to be expected.

OK, experiments are completed and solve (a few) more problems than the
corresponding LAMA version without reasonable orders, so this looks good.

Also, I cannot reproduce the failures of the pure LM-count heuristic on simple
Woodworking instances any more.

I'm demoting the priority of this and changing the title to reflect what still
needs to be done (after the IPC).

The queue is empty right now, so I'll start two more experiments with planner
versions that treat costs slightly differently, but I think we can stop messing
with the code for the IPC (also since there's very little time left and it'd be
good to spend that on more pressing things).

Experiments with the changed definition are running.

I've incorporated Silvia's suggestion of commenting out case 3. of
"inconsistent" and pushed the change. However, I have not closed the branch yet
since I think we should also explore the alternative solutions for this (maybe
not before the IPC though -- I have very very few cycles to spare at the moment).

Just checking whether any op has a AND b as effects sounds like a good solution
to me, but we'd have to change the code to make that test efficient.

A natural solution would be to include that info in the causal graph, which
already contains something like that info anyway. We'd have to change it so that
existence of edges of particular types (precond->eff, eff->eff) can be
efficiently queried and that the different causes for edges in the causal graph
can be distinguished.

Quoting from an email by Silvia:

Comment out or remove lines 628--640 in the landmarks_graph.cc file. (That is
case 3. in the interferes() function.)

Explanation:
As described in the LAMA paper on page 20, a reasonable order is added between A
and B if
(i) B is needed at the same time or after A, and
(ii) achieving B before A would mean having to make it false again in order to
achieve A.

We want to have that cases where A and B are both first achieved at the same
time no longer induce a reasonable ordering. So, we change (ii) to say

(ii modified) A and B are not achieved simultaneously and achieving B before A
would mean having to make it false again in order to achieve A.

At the moment, (ii) is approximated to hold if
(I) A and B cannot both be true at the time when A is first achieved, or
(II) B is false one timestep before A is first achieved

The solution now, I think, is to scratch (II). If A and B become true together
for the first time, then (II) can hold and (at the moment) thus justify a
reasonable order. By scratching (II) we avoid this.

Of course, if we do this we may also lose some reasonable orders that we'd
actually like to have (i.e., where A and B do not become true together). But I
can't think of a way of fixing our problem without potentially losing some
desirable orderings as well.
An alternative would be to test for each reasonable order currently generated by
the code whether an operator exists that can make A and B true at the same time,
and if that's the case, not generate the order.

The first solution would lose desirable orders if there exists a landmark X that
is ordered greedy-necessarily before A and is inconsistent with B. The second
solution would lose desirable orders if there's an operator that achieves both A
and B.
Do you have an intuition in which of the two cases we'd lose more desired
orders? I'm leaning towards the first solution because I'd think that case
happens less frequently, but we could experiment with both if you think it's
worthwhile.

> I see everyone's online now.
> Should we have a skype chat?

We did. :-) The resolution was for Silvia to look into adapting the computation
of reasonable orders so that it creates strict orders, not non-strict ones.

If that turns out to be difficult, a good alternative would be to allow
accepting A and B in the same state if the only order that connects them is a
reasonable order.

Silvia will send me a patch once this is ready. Actually, the best thing would
be to attach it to this issue. I think you can do this with hg diff, hg export,
or hg bundle. The last one is probably strongest in including all hg-relevant
metadata such as log messages and author names. If you use diff or export,
please use the --git option which enables a more useful patch format.

I see everyone's online now.
Should we have a skype chat?

Thanks for the analysis! Which concrete solution do you advocate for the IPC?
It'd be good to have this implemented within the next one or two days.

I'm not sure if we should generally accept both parent and child landmarks
at the same time if they become true simultaneously. While this would be ok
for reasonable orderings, it is not so for natural, greedy-neccessary or
necessary orderings. Those state that A must be true *strictly before* B in
any valid plan, not at the same time, and we'd lose accuracy if we did not
enforce this knowledge during the search. For example, there might be an
operator that achieves A and B together but leads to a dead-end area of the
search space, whereas in order to reach the goal, we must achieve A strictly
before B. In this case, there exists a strictly-before ordering (natural or
greedy-necessary or necessary) which could be detected. (I'm not sure our
current procedures would find this ordering, certainly not RHW. But at least
in theory this is an issue.)

I'd agree with Malte that conceptually, the alternative approach is better:
not generate any reasonable orderings A-->B in the case where they could
possible be achieved together (i.e., if there exists an operator that can
achieve A and B simultaneously).

I have just realised a further problem of th RHW procedure, and that
concerns the introduction of natural orderings in the post-processing step.
Here, we generate an ordering A-->B if B is not part of the restricted
relaxed planning graph that never adds A. But this includes the case where A
and B could become true simultaneously. So in this case as well, we should
not generate such an ordering if the two could possibly become true at the
same time.

One thing that is furthermore really bad in Malte's example is that LM4 is
considered required again. It is ordered greedy-necessarily before LM1,
which means it must be true one time step before LM1 becomes true *for the
first time*. But once LM1 has been true, we cannot infer that LM4 must be
true again before LM1 becomes true the second time. I noticed that this is
already wrong in the definitions of the AAAI-08 and JAIR papers. It should
be

(a) LM4 is required again if its ordering before LM1 is *necessary*, not
just greedy-necessary
(b) if the ordering is just greedy-necessary, then LM4 is required again
only if LM1 has never been true (rather than: LM1 has not been accepted yet)

We don't have necessary orderings in the code, so (a) is not an issue, but
should be kept in mind. We should fix (b). But if we implement the solution
regarding the reasonable orderings, then every landmark will be accepted the
first time it becomes true (right?), which automatically solves (b).
Otherwise, we'd have to keep track of which landmarks have already been
true, in addition to which landmarks have already been accepted.

I pushed a branch issue202, which contains the change that a landmark is also 
achieved if it's parents are achieved simultaneously.
This solves the small problem Malte created, but I have not run any further 
performance tests.
Malte - if you can, please try it more thuroughly.

This is the issue that Jorg raised (I think about a year ago), and we actually 
had a slide about it in our tutorial:
---------------------------------------------------------------------
The definition of reasonable orderings allows an ordering A ->r B
if A and B become true simultaneously.
Two solutions:
1. Accept a landmark if it has been made true at the same time as its
predecessor (Buffet and Hoffmann, 2010)
2. Modify the definition of reasonable orderings to disallow such
orderings
-----------------------------------------------------------------------
I think we can do (1) easily enough.

> The part that is intuitively wrong here is the way that the reached set
> is defined, not the dead-end detection, so it's worth thinking about
> whether that can be fixed in any way.

A simple solution would be to allow reaching A and B simultaneously even if A
-->r B. I faintly remember that Silvia discussed precisely this at some point,
although I don't know if it was in the LAMA paper or just in our discussions
while it was written.

A better solution might be to not generate reasonable orderings between A and B
in cases where they can be simultaneously made true in the first place.

In both cases, we need to think about whether this fixes the general problem or
just this particular case of it. I remember that Silvia explained how LAMA
sometimes returned a nonzero heuristic value for the goal; this probably
resolves some interesting cases of this, but probably not all of them.

On 07.01.2011 20:00, Erez Karpas wrote:
> 
> Erez Karpas <batman@gmail.com> added the comment:
> 
> I still need to go over this some more, but one immediate thing would be to
> cancel the dead end detection of lm count.
> When used with FF, this should not matter (I think).
> I'll look into this tomorrow.

Note the word I put in parentheses: :-)

    So far for the analysis. Now the big question is: how to fix this?
    Any (principled) ideas?

I don't think this is terribly urgent, so I suggest we think about it a
bit more before implementing something.

The part that is intuitively wrong here is the way that the reached set
is defined, not the dead-end detection, so it's worth thinking about
whether that can be fixed in any way.

I still need to go over this some more, but one immediate thing would be to
cancel the dead end detection of lm count.
When used with FF, this should not matter (I think).
I'll look into this tomorrow.
On Jan 7, 2011 8:16 PM, "Malte Helmert" <downward.issues@googlemail.com>
wrote:
>
> Malte Helmert <helmert@informatik.uni-freiburg.de> added the comment:
>
> OK, I see what happens here, but I need your help in deciding how to
> fix this, since I don't understand the ideas behind everything
> properly here.
>
> Sorry this is long, but please both of you read it and try to follow
> it closely.
>
> Let me first explain the example problem. In the SAS+ encoding (file
> "output"), it has three state variables, all of which are binary.
> (There's no need to look at the PDDL -- it probably is more confusing
> than helpful since the chosen SAS+ encoding is not immediately obvious
> from it.) Let's call the variables v0, v1, v2 and write a state like
> 100, 011 etc., giving the three variable values in sequence.
>
> The initial state is 111. The goal states are all states of the form
> **0, i.e., where v2=0.
>
> There are three operators:
>
> op1 has precondition v0=1 and assigns v0 and v1 to 0.
> Symbolically: op1: 1** => 00*
>
> op2 has precondition v0=0 and assigns v1 to 0.
> Symbolically: op2: 0** => *0*
> (It turns out this operator is completely useless, but somehow I need
> it to make this example fail. This may either be due to a subtlety in
> the landmarks generation or it is somehow translator-related)
>
> op3 has preconditions v0=0 and v1=0 and assigns v2 to 0.
> Symbolically: op3: 00* => **0.
>
> The (reachable part of the) state space of the problem looks like
> this:
>
> 111 ==op1=> 001 ==op3=> 000
>
> where 111 is the initial state and 000 is the only reachable goal
> state.
>
> Additionally, there are self-loops in state 001 with op2 and in state
> 000 with op2 and op3.
>
> As you can tell from the graph, all facts in this problem are
> landmarks (they all must be set to 1 initially, and they all must be 0
> in the only reachable goal state), and the planner does detect this.
> So there are exactly 6 landmarks, all of them fact landmarks.
>
> In my planner run, the landmark IDs are associated with the different
> facts as follows:
>
> LM0: v2=0 (the goal)
> LM1: v0=0
> LM2: v1=0
> LM3: v2=1
> LM4: v0=1
> LM5: v1=1
>
> The landmark graph looks as follows (ASCII art; view in fixed-width
> font):
>
>
> LM5 ---> LM2 -------> LM0 <--- LM3
> ^ \ ^
> | \ |
> | \ |
> | -----> LM1
> | ^
> | |
> | |
> LM4------------
>
> All orderings are greedy-necessary except for the ordering from LM2 to
> LM1, which is reasonable.
>
> The greedy-necessary orderings all make sense. I don't know the LM
> stuff well enough off-hand to understand how exactly it generates
> those, but they do satisfy the formal definitions.
>
> In particular, LM1 (v0=0) and LM2 (v1=0) are gn-ordered before LM0
> (v2=0) because the only operator that achieves LM2 has LM1 and LM2 in
> its precondition.
>
> LM3 (v2=1) before LM0 is obvious anyway because LM3 is initially true,
> LM0 is initially false, and LM3 the negation of LM0, hence must hold
> when LM0 is first made true.
>
> Finally, LM4 (v0=1) before LM1 (v0=0) and LM2 (v1=0) makes sense
> because LM4 is initially true and it is the precondition of the only
> operator which is initially applicable (op1), and LM1 and LM2 are the
> effects of this operator.
>
> This leaves the reasonable order from LM2 (v1=0) to LM1 (v0=0). I
> don't understand reasonable orders well enough to understand why that
> is there, but one thing that the LAMA paper observes is that if two
> facts are always first added simultaneously, then the definition
> postulates reasonable ordering between them in both directions. This
> is the case here: indeed, v0 and v1 always have the same value in all
> reachable states. Hence, maybe the planner discovers the ordering LM1
> => LM2 and also LM2 => LM1 and then arbitrarily keeps only LM2 => LM1
> in its cycle-breaking code.
>
> Now for what happens during search. I've added some tracing output,
> with which the relevant part of the code looks like this
> {{explanations embedded in double braces}}:
>
> =========================================================================
> Discovered 6 landmarks, of which 0 are disjunctive and 0 are conjunctive
> 7 edges
> Initializing landmarks count heuristic...
> 3 initial landmarks, 1 goal landmarks
> Conducting lazy best first search, (real) bound = 2147483647
>
> {{Now it dumps the first state to evaluate, which is the initial
> state.}}
>
> var0: 1
> var1: 1
> var2: 1
>
> {{Now it dumps which of LM0, ..., LM5 are considered reached in this
> state.}}
>
> not reached: 0
> not reached: 1
> not reached: 2
> reached: 3
> reached: 4
> reached: 5
> {{This makes sense: LM3, LM4, LM5 are initially true; the others are
> not.}}
>
> dead_end: 0
> {{This state, the initial state, is not a dead end. Correct.}}
>
> Best heuristic value: 3 [g=0, 1 evaluated, 0 expanded, t=0s]
> {{This h value also makes sense for the initial state. There are three
> unreached landmarks (LM0, LM1, LM2), and the problem is unit cost.
> We don't do cost partitioning.}}
>
> {{We now dump the next state to evaluate.}}
> var0: 0
> var1: 0
> var2: 1
> {{This makes sense: the state is 001, the only successor of 111.
> We now dump the reached landmarks for this state.}}
> not reached: 0
> not reached: 1
> reached: 2
> reached: 3
> reached: 4
> reached: 5
> {{OK, this output above is the first thing that puzzles me a bit. Of
> course, LM3, LM4 and LM5 are still reached, and additionally LM2 is
> now reached, which also makes sense. But why is LM1 not reached?
> From my weak understanding of how the orderings work, I guess this
> is because it has a landmark ordered before it, LM2, which was not
> reached in the parent state, and hence LM1 cannot be considered
> reached. However, LM2 was reached *simultaneously* with LM1.
> That reminds me that Silvia and I had long discussions about the
> matter of simultaneous achievement of landmarks in the context of
> the LAMA paper, and maybe this is where we see these theoretical
> considerations in action.
>
> Let's look at what we can infer from the given reached set.}}
> required again (lost children): 4
> {{OK, given the above, this may make sense. There is a
> greedy-necessary ordering from LM4 to LM1, and LM4 is not true in
> the current state. Since we have not accepted LM1, LM1 is also
> considered not reached. Therefore, LM4 is considered "required
> again". Makes sense -- the problem here is that LM1 should really
> have been accepted.}}
> OOPS2!
> LM 4: v0=1 [0 parents, 2 children, min_cost = 1, shared_cost = 0, 0
> forward_orders, 0 first_achievers, 0 possible_achievers]
> dead_end: 1
> {{Now the dead-end detection kicks in: we have a required-again
> landmark LM4. However, LM4 doesn't have any achievers at all. There
> is a dead-end check for such situations, which triggers here.}}
> Completely explored state space -- no solution!
> =========================================================================
>
> So far for the analysis. Now the big question is: how to fix this?
> Any (principled) ideas?
>
> _______________________________________________________
> Fast Downward issue tracker <downward.issues@gmail.com>
> <http://issues.fast-downward.org/issue202>
> _______________________________________________________

OK, I see what happens here, but I need your help in deciding how to
fix this, since I don't understand the ideas behind everything
properly here.

Sorry this is long, but please both of you read it and try to follow
it closely.

Let me first explain the example problem. In the SAS+ encoding (file
"output"), it has three state variables, all of which are binary.
(There's no need to look at the PDDL -- it probably is more confusing
than helpful since the chosen SAS+ encoding is not immediately obvious
from it.) Let's call the variables v0, v1, v2 and write a state like
100, 011 etc., giving the three variable values in sequence.

The initial state is 111. The goal states are all states of the form
**0, i.e., where v2=0.

There are three operators:

op1 has precondition v0=1 and assigns v0 and v1 to 0.
Symbolically: op1: 1** => 00*

op2 has precondition v0=0 and assigns v1 to 0.
Symbolically: op2: 0** => *0*
(It turns out this operator is completely useless, but somehow I need
it to make this example fail. This may either be due to a subtlety in
the landmarks generation or it is somehow translator-related)

op3 has preconditions v0=0 and v1=0 and assigns v2 to 0.
Symbolically: op3: 00* => **0.

The (reachable part of the) state space of the problem looks like
this:

111 ==op1=> 001 ==op3=> 000

where 111 is the initial state and 000 is the only reachable goal
state.

Additionally, there are self-loops in state 001 with op2 and in state
000 with op2 and op3.

As you can tell from the graph, all facts in this problem are
landmarks (they all must be set to 1 initially, and they all must be 0
in the only reachable goal state), and the planner does detect this.
So there are exactly 6 landmarks, all of them fact landmarks.

In my planner run, the landmark IDs are associated with the different
facts as follows:

LM0: v2=0 (the goal)
LM1: v0=0
LM2: v1=0
LM3: v2=1
LM4: v0=1
LM5: v1=1

The landmark graph looks as follows (ASCII art; view in fixed-width
font):


LM5 ---> LM2 -------> LM0 <--- LM3
          ^ \          ^
          |  \         |
          |   \        |
          |    -----> LM1
          |            ^
          |            |
          |            |
         LM4------------

All orderings are greedy-necessary except for the ordering from LM2 to
LM1, which is reasonable.

The greedy-necessary orderings all make sense. I don't know the LM
stuff well enough off-hand to understand how exactly it generates
those, but they do satisfy the formal definitions.

In particular, LM1 (v0=0) and LM2 (v1=0) are gn-ordered before LM0
(v2=0) because the only operator that achieves LM2 has LM1 and LM2 in
its precondition.

LM3 (v2=1) before LM0 is obvious anyway because LM3 is initially true,
LM0 is initially false, and LM3 the negation of LM0, hence must hold
when LM0 is first made true.

Finally, LM4 (v0=1) before LM1 (v0=0) and LM2 (v1=0) makes sense
because LM4 is initially true and it is the precondition of the only
operator which is initially applicable (op1), and LM1 and LM2 are the
effects of this operator.

This leaves the reasonable order from LM2 (v1=0) to LM1 (v0=0). I
don't understand reasonable orders well enough to understand why that
is there, but one thing that the LAMA paper observes is that if two
facts are always first added simultaneously, then the definition
postulates reasonable ordering between them in both directions. This
is the case here: indeed, v0 and v1 always have the same value in all
reachable states. Hence, maybe the planner discovers the ordering LM1
=> LM2 and also LM2 => LM1 and then arbitrarily keeps only LM2 => LM1
in its cycle-breaking code.

Now for what happens during search. I've added some tracing output,
with which the relevant part of the code looks like this
{{explanations embedded in double braces}}:

=========================================================================
Discovered 6 landmarks, of which 0 are disjunctive and 0 are conjunctive
7 edges
Initializing landmarks count heuristic...
3 initial landmarks, 1 goal landmarks
Conducting lazy best first search, (real) bound = 2147483647

{{Now it dumps the first state to evaluate, which is the initial
  state.}}

  var0: 1
  var1: 1
  var2: 1

{{Now it dumps which of LM0, ..., LM5 are considered reached in this
 state.}}

not reached: 0
not reached: 1
not reached: 2
reached: 3
reached: 4
reached: 5
{{This makes sense: LM3, LM4, LM5 are initially true; the others are
  not.}}

dead_end: 0
{{This state, the initial state, is not a dead end. Correct.}}

Best heuristic value: 3 [g=0, 1 evaluated, 0 expanded, t=0s]
{{This h value also makes sense for the initial state. There are three
  unreached landmarks (LM0, LM1, LM2), and the problem is unit cost.
  We don't do cost partitioning.}}

{{We now dump the next state to evaluate.}}
  var0: 0
  var1: 0
  var2: 1
{{This makes sense: the state is 001, the only successor of 111.
  We now dump the reached landmarks for this state.}}
not reached: 0
not reached: 1
reached: 2
reached: 3
reached: 4
reached: 5
{{OK, this output above is the first thing that puzzles me a bit. Of
  course, LM3, LM4 and LM5 are still reached, and additionally LM2 is
  now reached, which also makes sense. But why is LM1 not reached?
  From my weak understanding of how the orderings work, I guess this
  is because it has a landmark ordered before it, LM2, which was not
  reached in the parent state, and hence LM1 cannot be considered
  reached. However, LM2 was reached *simultaneously* with LM1.
  That reminds me that Silvia and I had long discussions about the
  matter of simultaneous achievement of landmarks in the context of
  the LAMA paper, and maybe this is where we see these theoretical
  considerations in action.

  Let's look at what we can infer from the given reached set.}}
required again (lost children): 4
{{OK, given the above, this may make sense. There is a
  greedy-necessary ordering from LM4 to LM1, and LM4 is not true in
  the current state. Since we have not accepted LM1, LM1 is also
  considered not reached. Therefore, LM4 is considered "required
  again". Makes sense -- the problem here is that LM1 should really
  have been accepted.}}
OOPS2!
LM 4: v0=1 [0 parents, 2 children, min_cost = 1, shared_cost = 0, 0
forward_orders, 0 first_achievers, 0 possible_achievers]
dead_end: 1
{{Now the dead-end detection kicks in: we have a required-again
  landmark LM4. However, LM4 doesn't have any achievers at all. There
  is a dead-end check for such situations, which triggers here.}}
Completely explored state space -- no solution!
=========================================================================

So far for the analysis. Now the big question is: how to fix this?
Any (principled) ideas?

I'm attaching output and all.groups so that you can precisely follow the
explanation of what goes wrong here.

OK, I found something that looks like a minimal failing example: three state
variables, three operators, three reachable states. There's a solution of length
2, but --search 'lazy_greedy(lmcount(lm_rhw(reasonable_orders=true)))' fails.
Problem attached.

OK, this is already present in the very first trunk revision that includes the
landmark code (r118) if we enable reasonable orders there by changing the code.

OK, this bug is ancient. The earliest version where I can reliably reproduce the
failure is r144, from October 20th 2009 (!) I don't think it was actually
introduced in this issue; what this issue did was enable reasonable orders which
were disabled before. So the true cause must be even older.

The LM-count heuristic fails to solve Woodworking instance #01, even though it
is solvable. For example, it is solved when disabling reasonable orders.
Transcript:

~/tmp/downward/ipc/src/search$ make debug && X=01 &&
../translate/translate.py
../../benchmarks/woodworking-sat08-strips/p$X.pddl &&
../preprocess/preprocess < output.sas && ./downward-1-debug --search
'lazy_greedy(lmcount(lm_rhw(reasonable_orders=true)))' < output
[...]
Simplifying transitions... done!
Initializing Exploration...
Reading invariants from file...
done
Generating landmarks using the RPG/SAS+ approach
approx. reasonable orders
approx. obedient reasonable orders
Removed 0 reasonable or obedient reasonable orders
Landmarks generation time: 0.00308396s
Discovered 23 landmarks, of which 0 are disjunctive and 0 are conjunctive
39 edges
Initializing landmarks count heuristic...
13 initial landmarks, 7 goal landmarks
Conducting lazy best first search, (real) bound = 2147483647
Best heuristic value: 130 [g=0, 1 evaluated, 0 expanded, t=0s]
Best heuristic value: 100 [g=30, 2 evaluated, 1 expanded, t=0s]
Best heuristic value: 90 [g=50, 4 evaluated, 3 expanded, t=0s]
Best heuristic value: 80 [g=60, 6 evaluated, 5 expanded, t=0s]
Completely explored state space -- no solution!
Actual search time: 0s
Initial state h value: 130.
Expanded 242 state(s).
Reopened 0 state(s).
Evaluated 484 state(s).
Evaluations: 484
Generated 1892 state(s).
Search time: 0s
Total time: 0s
Peak memory: 4348 KB