Erez added the comment as part of issue153, I merged this. Marking this one is
closed.

(Of course, more general dead-end detection methods remain interesting for the
future, but I think this is outside the scope of this issue.)

It's now pushed as branch issue153
(forgot to check that push worked before, needed --new-branch, sorry).

> At least until the conjunctive landmarks are added (ala the ECAI '10
> paper) ;). We have some students adding DCK as landmark info, and
> the peculiarity of the dead-end detection is a good thing to know.

They have actually been added yesterday. :-) Hence my "unless we consider..."
comment.

If you want to try this out, note that the command-line options for the
landmarks code have changed significantly. Erez has updated the wiki to reflect
the changes, but the most recent name changes are not yet in the code, so right
now the documentation is not fully correct (but will be soon).

>
> > Ahh, makes sense. Bummer, the full-on LM dead-end detection capabilities
> > could be quite strong.
>
> For what it's worth: all our landmarks are delete-relaxation landmarks
> (well,
> unless we consider the new h^m landmarks code), and hence a LM-based
> dead-end
> detection code cannot in principle be stronger than checking relaxed
> reachability of the goal from the current state.
>

  At least until the conjunctive landmarks are added (ala the ECAI '10
paper) ;). We have some students adding DCK as landmark info, and
the peculiarity of the dead-end detection is a good thing to know.

  Thanks.
   Cheers

> Ahh, makes sense. Bummer, the full-on LM dead-end detection capabilities
> could be quite strong.

For what it's worth: all our landmarks are delete-relaxation landmarks (well,
unless we consider the new h^m landmarks code), and hence a LM-based dead-end
detection code cannot in principle be stronger than checking relaxed
reachability of the goal from the current state.

This can already be achieved, at the cost of some extra computation, by using
the maximum of the LM heuristic and h^max.


I'll look into merging Erez's changes (= comment).

Erez, I see no new code from you for either this or issue153.
Have you pushed your changes to bitbucket?

Ahh, makes sense. Bummer, the full-on LM dead-end detection capabilities
could be quite strong.

  Cheers

On Mon, Dec 6, 2010 at 8:10 PM, Silvia Richter <
downward.issues@googlemail.com> wrote:

>
> Silvia Richter <<anonymized>@gmail.com> added the comment:
>
> Christian, what you describe is exactly the behaviour one would like/expect
> (in my opinion) from a dead-end detection, but the implementation is not
> really doing this. For landmarks that are not initially true it is not
> testing reachability *from a given state*, but rather reachability from the
> initial state.
> The current implementation may be useful in those cases where X is true in
> the initial state and later made false, as described by Erez. But in
> general
> (for landmarks that are not true in the initial state) the current
> implementation will never detect a dead-end in a later state, given a
> solvable task.
>
> I agree with Malte that at least a comment should be added to the code
> explaining that this dead-end detection only works for some special cases,
> and what they are.
>
> _______________________________________________________
> Fast Downward issue tracker <downward.issues@gmail.com>
> <http://issues.fast-downward.org/issue42>
> _______________________________________________________
>

I think Silvia answered better than I could.

I added a comment to the code, this should be integrated with issue153 soon.

Christian, what you describe is exactly the behaviour one would like/expect
(in my opinion) from a dead-end detection, but the implementation is not
really doing this. For landmarks that are not initially true it is not
testing reachability *from a given state*, but rather reachability from the
initial state.
The current implementation may be useful in those cases where X is true in
the initial state and later made false, as described by Erez. But in general
(for landmarks that are not true in the initial state) the current
implementation will never detect a dead-end in a later state, given a
solvable task.

I agree with Malte that at least a comment should be added to the code
explaining that this dead-end detection only works for some special cases,
and what they are.

> Can you add a brief comment to the code (ideally in the emil-new branch
> so that it doesn't get lost when merging) that explains this?

Update (and sorry to interrupt Christian's question, which I'll leave to Erez or
Silvia to answer since I don't know this code): now that this branch *has* been
merged, any changes for this should be on a branche named issue42 branched off
the tip of default, as usual.

> About dead-end detection - consider the following:
> X is a goal, it is true in the initial state, and has no achievers.
> Some action A has X as a delete effect. Then using landmark dead-end
> detection, we can detect that applying A leads to a dead-end.
> We might be able to test this a bit more efficiently, but I think this is a
> good thing to have.

What if X was a landmark...wouldn't the landmark dead-end detection (LDD) help 
in the cases you reach a state that hasn't seen the landmark yet, and X is not 
reachable from the current state? Or does the LDD not consider reachability of 
landmarks left to achieve?

> Almost -- relaxed unreachable operators are never generated. The "Horn
> exploration" grounding algorithm in the translator already makes sure that
> they're not instantiated.

...but: there can of course be cases of operators that are relaxed reachable
from the initial state but not from the current state. In cases where we do a
relaxed reachability analysis anyway in every state (e.g. when using the LAMA-FF
synergy), it might be feasible to compute the "possible achievers for this
state" and use them for action partitioning. But:

 1) I think we do some optimizations to stop early in this computation which
    we could then not do anymore, and
 2) We currently don't do Lama-FF synergy together with action cost
    partitioning.

So this is probably not worth the bother -- just thought it might make sense to
mention it for completeness.

> About dead-end detection - consider the following:
> X is a goal, it is true in the initial state, and has no achievers.
> Some action A has X as a delete effect. Then using landmark dead-end
> detection, we can detect that applying A leads to a dead-end.
> We might be able to test this a bit more efficiently, but I think this is a
> good thing to have.

That makes sense, but it is a bit subtle. Can you add a brief comment to the
code (ideally in the emil-new branch so that it doesn't get lost when merging)
that explains this?

> About using only reachable operators for possible achievers - that sounds
> like a  great idea, but I think the preprocessor already eliminates those
> actions (Malte - am I right?)

Almost -- relaxed unreachable operators are never generated. The "Horn
exploration" grounding algorithm in the translator already makes sure that
they're not instantiated.

About dead-end detection - consider the following:
X is a goal, it is true in the initial state, and has no achievers.
Some action A has X as a delete effect. Then using landmark dead-end detection, 
we can detect that applying A leads to a dead-end. 
We might be able to test this a bit more efficiently, but I think this is a good 
thing to have.


About using only reachable operators for possible achievers - that sounds like a 
great idea, but I think the preprocessor already eliminates those actions (Malte 
- am I right?)

I remain doubtful of this dead-end detection, since as far as I can see it
relies on the possible and first achievers of a landmark that are calculated
only once, in the beginning, when the landmark graph is built. 

In every newly reached state, the status is updated for all landmarks (in
LandmarkStatusManager::update_lm_status()). For a landmark that hasn't been
accepted yet, a dead end is declared if the landmark has no first achievers.
However, in a solvable task every landmark must have some first achiever that is
reachable from the initial state, otherwise it couldn't be a landmark, right?
(Same with the possible achievers.) Thus, I can't imagine this dead-end test to
ever find a dead end in solvable tasks. In particular, since the sets of first
and possible achievers never change for a landmark, it doesn't seem to make
sense to test their size against 0 *in every state* rather than only once. The
only thing that can change over time is whether a landmark is accepted or
required again, but since the possible achievers are a superset of the first
achievers, the test becomes less likely to succeed (i.e. find a dead end) once a
landmark gets accepted. Thus, as far as I can see the test will never find a
dead end for a landmark in a later state if it hasn't found a dead end for that
landmark in the initial state.

So, it seems to me this dead-end detection could at most be useful for the
initial state, i.e. as a test for solvability of the task. But a test for
solvability should probably be implemented in a better way, before calculating
landmarks, and should only be run once.

Or am I misunderstanding something here, Erez?

Also, I'd suggest that when calculating the possible achievers, we should
exclude unreachable operators, like we do for the first achievers. I.e., for the
possible achievers we should do the same as for the first achievers except that
we'd use an *unrestricted* RPG when testing reachability for the possible
achievers, whereas we use the *restricted* RPG (that excludes the landmark) when
testing reachability for the first achievers (to see whether the first achievers
can be reached *before* the landmark). This change could potentially improve the
cost partitioning, as it decreases the number of possible achievers. Are they
used anywhere else? We should check, but since unreachable operators are not
actually possible achievers I think this change can only lead to improvement. If
you agree, I can open a new issue for that.

Silvia, can you have a look at this (svn diff -c 3454) and set the status back
to "resolved" if you're OK with the change?

I fixed the dead-end detection bug (dead ends are only detected for non-derived
predicates). Otherwise, this causes a divide by zero when doing cost partitioning.

I also check the impact of removing dead ends in freecell, and it looks like
there is no impact there.

Marking as nosy since the question of deadend impact in search is something I'm
currently investigating for ICAPS 2010 (in the context of it's effectiveness in
primitive dtg's and composed abstractions).

I think (although I've never actually tested it) that the dead-end detection is
one of the reasons for the good results the admissible landmarks heuristic has
in freecell.
One simple solution is to only do this for facts that are not derived predicates.
I'll look into this when I have some time.

> Hmm, is there a problem with the tracker's email address?

Apparently not, never mind.

Hmm, is there a problem with the tracker's email address?

The dead-end detection in the landmark_status_manager was buggy, and I have
taken it out. It reported a dead end if no possible achievers existed for a
landmark. However, that is wrong as a landmark can also become true by other
means, namely if it is a derived variable and the landmark is its default value.
This bug lead to reporting dead ends for all tasks in psr-middle, for example.

Do we need a dead-end detection in the landmark heuristic? If this is desired,
we should think about implementing it differently.