Issue383

Title Reasonable orders in landmark graph not always generated
Priority bug Status chatting
Superseder Nosy List florian, gabi, jendrik, malte, salome, silvan
Assigned To Keywords
Optional summary

Created on 2013-06-21.15:36:04 by salome, last changed by jendrik.

Messages
msg6124 (view) Author: jendrik Date: 2017-01-15.22:02:56
Sure, I added it to the agenda.
msg6123 (view) Author: malte Date: 2017-01-14.21:02:52
> Coverage goes down by a lot, especially in miconic-fulladl, parcprinter and
sokoban.
> Interestingly, miconic-fulladl is the domain that looks really good in the
> total_time plots. It seems that a lot of tasks are now detected as unsolvable
(see for example
>
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue383-v1.html#error-miconic-fulladl).

miconic-fulladl does actually have unsolvable tasks, but not that many. I think
there are 11. So this means that the change is not correct, and we will probably
have to defer this until we actually understand it better.

> Maybe we have to let this issue rest until we can look at the landmark code as
a whole.
> Let's hope its not another 3.5 years.

Jendrik, can you add revising the landmark code to the agenda for the next Fast
Downward meeting that I can attend? I think it would be good to start making a
refactoring plan.
msg6122 (view) Author: malte Date: 2017-01-14.12:52:51
> Another thing that surprised me in the results was that lama-first has the
> same coverage as seq-sat-lama-2011. I thought lama-first is the first step
> of seq-sat-lama-2011. Are the other steps not helping, or just not showing
> up in the report?

Lama is an iterated search configuration, so the later steps are only run after
the first step has succeeded. Their purpose is to find solutions of higher quality.
msg6121 (view) Author: florian Date: 2017-01-14.11:08:13
Unfortunately, this was not the easy fix, I hoped it would be.

(still all results in one report, sorry)
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue383-v1.html
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue383-v1-total_time-lama-first-issue383-base-issue383-v1.png
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue383-v1-total_time-seq-sat-lama-2011-issue383-base-issue383-v1.png

Coverage goes down by a lot, especially in miconic-fulladl, parcprinter and sokoban.
Interestingly, miconic-fulladl is the domain that looks really good in the
total_time
plots. It seems that a lot of tasks are now detected as unsolvable (see for example
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue383-v1.html#error-miconic-fulladl).

Looks like this is the same issue mentioned in msg2522 and msg2543.

Another thing that surprised me in the results was that lama-first has the same
coverage as seq-sat-lama-2011. I thought lama-first is the first step of 
seq-sat-lama-2011. Are the other steps not helping, or just not showing up in
the report?

Maybe we have to let this issue rest until we can look at the landmark code as a
whole.
Let's hope its not another 3.5 years.
msg6113 (view) Author: silvan Date: 2017-01-13.11:55:45
> I don't really understand the code either. Silvan, Salomé and Manuel have been
> involved in it more recently, and perhaps they have an idea if the change makes
> sense, although this is probably a part of the code none of us really
> understands. :-)

The recent work mainly consisted in pure code refactoring, but did not deal with
changing the semantics. Unfortunately, I also don't understand what the code
should do (or what reasonable order should do).
msg6110 (view) Author: malte Date: 2017-01-13.01:48:50
I don't really understand the code either. Silvan, Salomé and Manuel have been
involved in it more recently, and perhaps they have an idea if the change makes
sense, although this is probably a part of the code none of us really
understands. :-)

This cannot affect our optimal configurations since these don't use reasonable
orders, so I guess the worst thing that can happen if we break this is that we
make LAMA-style configurations a bit less efficient, which is something we can
test experimentally. (Potential bugs for optimal configurations are a larger
worry because we might we break admissibility by deriving wrong orders, and
ostensibly optimal configurations performing non-optimally is a worse sin than
bad performance.)

Hence, I'm also fine with merging this after an experiment. I suggest testing
with lama-first and with seq-sat-lama-2011. Because the latter is anytime, they
would need different reports, I think. (For the anytime configurations, many of
our attributes don't make sense.)

More long-term, we definitely need to clean up the landmark code. But I think
this is more something for a "task force" than for the review queue. If someone
is interested in this, I suggest we discuss the topic further once I'm back in
office.
msg6091 (view) Author: florian Date: 2017-01-12.11:50:49
I prepared a pull request for the proposed change but I really don't understand
what the code is supposed to do (the patch only recreates the control flow from
6 years ago). Malte, should I put this into the review queue? Or is someone else
familiar enough with this part of the code to review it?

https://bitbucket.org/FlorianPommerening/downward-issues/pull-requests/33/issue383/diff
msg6077 (view) Author: malte Date: 2017-01-11.18:58:09
Thanks! Regarding your suggestion, a change that makes the code deterministic is
certainly welcome if it doesn't screw too much with performance. :-)
msg6076 (view) Author: florian Date: 2017-01-11.18:55:43
The revision is 4f49059e7a0f ("Integrating emil-new branch").
msg6075 (view) Author: malte Date: 2017-01-11.18:54:11
Hi Florian, can you give the global revision ID? "630" is a local revision ID of
your repository. For example, in one of my repositories, "630" is global revision
bd51e9c0fbee ("scripts: separate preprocessing from search in experiments"),
which I assume isn't the right one. (It only touches some Python scripts.)
msg6073 (view) Author: florian Date: 2017-01-11.16:35:25
I had a look at the file history. The "return" statement that causes the
non-deterministic behavior here originated in revision 630. Before that revision
the control flow was different and maybe this change was unintended. Here is the
simplified control flow before and after revision 630:

Before revision 630:
for (LandmarkNode *node : nodes) {
    if (!obedient_orders && node->is_true_in_goal()) {
        A;
    } else if (!node->is_true_in_initial_state()) {
        B;
    }
}

After revision 630:
for (LandmarkNode *node : nodes) {
    if (node->is_true_in_initial_state())
        return;

    if (!obedient_orders && node->is_true_in_goal()) {
        A;
    } else {
        B;
    }
}

Both versions are different from the fix in msg2496 (replacing return by
continue) for landmarks that are true in the initial state *and* the goal state.
For them, the code "A;" was executed in the old version but is not executed with
return or continue. I don't really understand what the code does, so I don't
know if the old code did the right thing, but maybe this difference is worth
looking at.
msg6072 (view) Author: florian Date: 2017-01-11.15:40:56
This issue came up again in the evaluation of issue688.

If I understood the discussion below correctly, there are two problems: the loop
looking for reasonable orders breaks at a non-deterministic time, and if the
loop is run for all landmarks then it produces a secondary bug. Does this mean
that we would get the secondary bug also if we are unlucky with the
non-deterministic order? If so, I would suggest to fix the non-determinism
first, so we get the secondary bug deterministically and then open a new issue
for the bug.
msg2545 (view) Author: malte Date: 2013-07-23.14:10:53
> I tried adding the condition that the edge type needs to be bigger than
> reasonable to "if (!reached[parent_p->get_id()])", and then it could solve the
> tasks sokoban-opt08-strips/p01.pddl

With this change, would reasonable orders still have any effect on the search,
i.e., are they used for anything else?

Generally speaking, I think the use of orderings needs to be reviewed and
rethought a bit more globally. I would suggest an offline discussion.
msg2543 (view) Author: salome Date: 2013-07-21.14:18:48
After some searching we discovered that the solver wrongly reports dead ends in
certain states because it says a landmark is not reached yet even if it is true
in the current state. The function update_reached_lms in
landmark_status_manager.cc checks for landmarks that are true in the current
state if they are leaves and only if they are they are counted as reached. Leaf
means that all parents of this landmark are reached already.

What we suspect is that with reasonable orderings this doesn't work anymore,
since (at least to my understanding) reasonable orderings do not necessarily
apply. So if a solution needs to go against a reasonable order, it will end up
in a dead end since the landmark with this reasonable order will always have an
unsatisfied parent-landmark. Is this correct?

I tried adding the condition that the edge type needs to be bigger than
reasonable to "if (!reached[parent_p->get_id()])", and then it could solve the
tasks sokoban-opt08-strips/p01.pddl
msg2522 (view) Author: gabi Date: 2013-06-25.18:36:04
We found some sokoban tasks that are incorrectly classified as unsolvable with
this change, so I backed it out of default.
msg2505 (view) Author: malte Date: 2013-06-24.20:34:55
Brief note to avoid duplicated effort: I'll start a small experiment for this.
msg2504 (view) Author: malte Date: 2013-06-24.18:03:25
Actually, no point in comparing BJOLP here, as it doesn't use reasonable orders.
msg2503 (view) Author: malte Date: 2013-06-24.17:40:10
Same comments as for issue289 applies:

Given the nastiness of the landmark code, I think it'd be good to see a
before/after experiment for all LM generation changes. The two configurations
I'd suggest checking are:

- ipc seq-sat-lama-2011 on all tasks
- ipc seq-opt-bjolp on all optimal tasks without axioms/conditional effects
msg2499 (view) Author: gabi Date: 2013-06-24.11:53:29
Resolved. Thanks Salomé!
msg2496 (view) Author: salome Date: 2013-06-21.15:36:03
When running experiments for issue289 I discovered that on some problems in the
scheduling domain there was a significant difference in expansions between my
fix and the original version, even though both versions found the exact same
landmarks and thus should behave exactly the same. Sometimes the fix has 10
times more expansions or is even not solvable while the other version has below
100'000 expansions.

I backtracked the error to the generation of reasonable orderings: The function
approximate_reasonable_orders in landmark_factory.cc loops over all landmarks
and searches for reasonable orders. As soon as a landmark is true in the initial
state, the function is exited altogether without checking the rest of the
landmarks. Since we cannot know in which order the Landmarks are passed (it
iterates through a set of Landmark pointers) this leads to non-deterministic
behavior.

I think there should rather be a continue statement instead of exiting the
function, as it is just above when checking for disjunctive landmarks. I tried
this out on two problems already and it seems to work, but I will test this further.
History
Date User Action Args
2017-01-15 22:02:56jendriksetmessages: + msg6124
2017-01-14 21:02:52maltesetmessages: + msg6123
2017-01-14 12:52:51maltesetmessages: + msg6122
2017-01-14 11:08:13floriansetmessages: + msg6121
2017-01-13 11:55:45silvansetmessages: + msg6113
2017-01-13 01:48:50maltesetmessages: + msg6110
2017-01-12 11:50:49floriansetmessages: + msg6091
2017-01-11 18:58:09maltesetmessages: + msg6077
2017-01-11 18:55:43floriansetmessages: + msg6076
2017-01-11 18:54:11maltesetmessages: + msg6075
2017-01-11 16:35:25floriansetmessages: + msg6073
2017-01-11 15:40:56floriansetnosy: + florian
messages: + msg6072
2013-07-23 14:10:53maltesetmessages: + msg2545
2013-07-21 14:18:48salomesetmessages: + msg2543
2013-06-25 18:36:04gabisetmessages: + msg2522
2013-06-24 20:34:55maltesetmessages: + msg2505
2013-06-24 18:03:25maltesetmessages: + msg2504
2013-06-24 17:40:10maltesetstatus: resolved -> chatting
messages: + msg2503
2013-06-24 11:53:29gabisetstatus: unread -> resolved
nosy: + gabi
messages: + msg2499
2013-06-24 11:24:16silvansetnosy: + silvan
2013-06-21 18:57:33jendriksetnosy: + jendrik
2013-06-21 15:37:58maltesetnosy: + malte
2013-06-21 15:36:04salomecreate