On second thought, I'd prefer not to make this change right now, since it will
mess with the merging of Silvan's landmark factory refactoring, which is ready
to be integrated very soon (TM).

Instead, I've opened a new issue: issue231. Nosy yourself if interested.

This one is done. Thanks, everyone! :-)

Yes, we can change the return value to a bool and I'm happy for you to do
that. Indeed this function's main raison d'etre is to compute preferred
operators. Many of the landmark functions don't have very suitable names for
legacy reasons :(

"why we compute it all" => "why we compute it *at* all"

The RPG search thing should go -- it also has a crash bug currently, I think.
See issue168.

Silvia: if the caller of plan_for_disj only cares about solvable or not, I think
it should return a bool instead of relaxed plan size. Are you fine with that? (I
can make the change myself, just want to be sure if there are further
implications.) I assume we also need to compute the relaxed plan there for its
preferred operators? (Otherwise I wouldn't know why we compute it all if we
don't care about its length or cost.)

We can also get rid of LandmarksGraphRpgSearch - it's a failed attempt at finding 
interesting landmarks.
Does anyone think it's worth keeping?

No, the two methods that return "relaxed_plan.size()" are fine like that.
Well, at least the one method (plan_for_disj) I can say for sure is fine.
The only thing its return value is used for is to check whether we're in a
dead end or not.

The other method (compute_ff_heuristic_with_excludes) has appearently been
added by Erez. It is called by the function "relaxed_plan_length_without" in
LandmarksGraph, and since *length* is in the name of that function I'm
assuming it's using plan length and not plan cost on purpose (but I haven't
looked into what it does).

Erez, this function "relaxed_plan_length_without" in LandmarksGraph is only
used by the derived class LandmarksGraphRpgSearch. I'd prefer it if you
could get rid of this function in LandmarksGraph and directly call
"compute_ff_heuristic_with_excludes" from LandmarksGraphRpgSearch. There's
no use in having something in the super class LandmarksGraph if it's only
used by one of the subclasses. We can reduce code lines and improve
readability by getting rid of that unnecessary redirection.

Merged.

(Silvia, if the question in my msg1292 points at a problem, please open a new
issue for this.)

> I have also found two more spots in the code where the relaxed plan
> should be made static (and cleared) if we do want to go with the
> static version: in "compute_ff_heuristic_with_excludes" and
> "plan_for_disj".

These two methods return "relaxed_plan.size()". Don't they need to take action
costs into account? What is their return value used for?

Ok, I've turned the relaxed plan into an instance variable and added the
clearing. I've opened a separate issue for the h-value problem (Issue230).

> Thanks for checking this, Malte. Indeed I seem to have forgot to clear
> the relaxed plan at the end of the function "compute_ff_heuristic". Do
> you want to add this, or shall I? The relaxed plan was made static
> because you suggested this in msg539 of issue127 to save time compared
> to the dynamic memory allocation.

I know, but this was not meant to be the "proper" solution, just a quick
localized change to test the speed impact of the reallocations. Using an
instance attribute is a better soluton. (As a reference,, you can see how this
issue was resolved for the additive heuristic.)

> I have also found two more spots in the code where the relaxed plan
> should be made static (and cleared) if we do want to go with the
> static version: in "compute_ff_heuristic_with_excludes" and
> "plan_for_disj".

Indeed (but again: an instance variable is better -- the day where we want to
support multiple cores in Fast Downward might not be far off, and other people
have already changed in in this way).

> As for 1): the search prints "Completely explored state space" before
> stopping when I run it, so I don't think we need to worry. Also,
> running the search with A* and the lmcut heuristic finds a solution of
> cost 5, suggesting that this is the optimal cost.

Sounds good. I guess the output line about "continuing search" is a bit
misleading then, though, and it might be good to adapt it.

> Regarding 2): the landmark heuristic may not be zero in a goal state
> due to reasonable orderings. But interestingly, h doesn't drop to 0
> even if we don't use reasonable orderings, e.g. with the call
> ./downward --heuristic
>"hlm,hff=lm_ff_syn(lm_rhw(reasonable_orders=false,cost_type=2,lm_cost_type=2))"
--search "lazy_greedy(hlm, hff, preferred=(hlm, hff))" < output
> So there might indeed be something weird going on...

Can you look into that, too, maybe opening another issue?

Thanks for checking this, Malte. Indeed I seem to have forgot to clear
the relaxed plan at the end of the function "compute_ff_heuristic". Do
you want to add this, or shall I? The relaxed plan was made static
because you suggested this in msg539 of issue127 to save time compared
to the dynamic memory allocation.

I have also found two more spots in the code where the relaxed plan
should be made static (and cleared) if we do want to go with the
static version: in "compute_ff_heuristic_with_excludes" and
"plan_for_disj".

As for 1): the search prints "Completely explored state space" before
stopping when I run it, so I don't think we need to worry. Also,
running the search with A* and the lmcut heuristic finds a solution of
cost 5, suggesting that this is the optimal cost.

Regarding 2): the landmark heuristic may not be zero in a goal state
due to reasonable orderings. But interestingly, h doesn't drop to 0
even if we don't use reasonable orderings, e.g. with the call
./downward --heuristic
"hlm,hff=lm_ff_syn(lm_rhw(reasonable_orders=false,cost_type=2,lm_cost_type=2))"
--search "lazy_greedy(hlm, hff, preferred=(hlm, hff))" < output
So there might indeed be something weird going on...

OK, I got "output.sas" and "all.groups" from issue127, ran the preprocessor, and
then did before and after Silvia's fix

$ ./downward ipc seq-sat-lama-2011 < output

(This uses a LAMA-like configuration, the main difference being that it starts
with a search iteration that ignores action costs.)

Before Silvia's fix, this only evaluates about one state per second. After
Silvia's fix, this solves the problem; it finds four progressively better plans
of costs 21, 20, 7, and 5, then terminates.

However, the output looks like this:

Best heuristic value: 676/676 [g=0, 1 evaluated, 0 expanded, t=58.84s]
Best heuristic value: 675/676 [g=1, 2 evaluated, 1 expanded, t=58.84s]
Best heuristic value: 674/676 [g=2, 3 evaluated, 2 expanded, t=58.84s]
Best heuristic value: 673/676 [g=3, 5 evaluated, 4 expanded, t=58.85s]
Best heuristic value: 672/676 [g=4, 7 evaluated, 5 expanded, t=58.85s]
Best heuristic value: 669/676 [g=5, 9 evaluated, 6 expanded, t=58.85s]
Best heuristic value: 668/676 [g=6, 35 evaluated, 10 expanded, t=58.87s]
Best heuristic value: 667/676 [g=7, 37 evaluated, 11 expanded, t=58.87s]
Best heuristic value: 664/676 [g=8, 39 evaluated, 12 expanded, t=58.88s]
Best heuristic value: 662/676 [g=9, 43 evaluated, 13 expanded, t=58.88s]
[...]
Best heuristic value: 11/676 [g=609, 9393 evaluated, 6227 expanded, t=82.7s]
Best heuristic value: 10/676 [g=610, 9395 evaluated, 6229 expanded, t=82.71s]
Best heuristic value: 9/676 [g=611, 9396 evaluated, 6230 expanded, t=82.71s]
Best heuristic value: 8/676 [g=612, 9397 evaluated, 6231 expanded, t=82.72s]
Best heuristic value: 7/676 [g=613, 9398 evaluated, 6232 expanded, t=82.72s]
Best heuristic value: 6/676 [g=614, 9399 evaluated, 6233 expanded, t=82.73s]
Best heuristic value: 4/676 [g=615, 9400 evaluated, 6234 expanded, t=82.73s]
Best heuristic value: 3/676 [g=616, 9401 evaluated, 6235 expanded, t=82.73s]
Best heuristic value: 2/676 [g=617, 9403 evaluated, 6237 expanded, t=82.74s]
Best heuristic value: 1/676 [g=618, 9404 evaluated, 6238 expanded, t=82.75s]
Solution found!

suggesting that one of the heuristic values never improves. I'm not sure which
heuristic it is, but is it possible that it's the FF heuristic, and that the
reason it doesn't get better is that the relaxed plan is not cleared between
differerent invocations of the heuristic? At least I don't see where it would be
cleared, and now that it's static...

(Actually, as an aside, I'd prefer to have it as an instance attribute rather
than making it static, so that we don't run into problems if we should ever
decide to parallelize things.)

Also,

1) It's not clear to me why the search stops after finding the solution of cost
5. Does it really prove that there is no cheaper one? It rather looks to me like
it doesn't actually continue the search. Can someone look into this?

2) Shouldn't the goal state have a heuristic value of 0, not 1? Looks to me from
the about above like it never finds a state with h=0.

Silvia fixed this, and I've merged and pushed the change.

Can someone else look into testing this?

The other heuristics should be fine w.r.t. issue127; I remember looking at them.
I *thought* I also looked at the LAMA/FF synergy stuff, but apparently not. :-(
Silvia, if you can prepare a patch I can merge it once I'm back in Freiburg
(around this weekend).

The slowness of the LAMA/FF synergy is due to issue127. As per Malte's msg541 on
that issue, the bug had been fixed only for the additive heuristic, but it
concerns several other heuristics as well (including the FF heuristic
implementation that is used in the LAMA/FF synergy). The regular FF heuristic
has apparently been fixed in the meantime, not sure about the other heuristics
mentioned in msg541 (CG and cea). I've implemented the fixes described in msg539
for the LAMA/FF synergy and that greatly speeds up the search.

I think reasonable orders are slow because there are already almost 149,641 
edges in the landmark graph, so I'm not too worried about that.

I also see a significant slowdown when using the LAMA/FF synergy, but I'm afraid 
I don't know where to start with that.

I think using normal action costs is a problem, because there are many 0 cost 
actions in this problem, and the landmark code does not handle that well (as is 
documented in some TODO comments in the code).

Silvia - can you take a look?

Hmm... I was *sure* I checked that. With a more copious amount of closing
parentheses, that algorithm works and seems to evaluate nodes quite fast.

However, if I run the task with LM-FF-Synergy, search is terribly slow.
For example, try this:

./downward-1 --heuristic
"hlm,hff=lm_ff_syn(lm_rhw(reasonable_orders=true,cost_type=2,lm_cost_type=2))" 
--search "lazy_greedy(hlm, hff, preferred=(hlm, hff))" < output

It takes almost 30 seconds to start search and then about 1 second per
evaluation. Without reasonable orders, search starts much earlier, but is then
just as slow. Even worse, when removing the cost_type and lm_cost_type options,
search doesn't seem to get started at all!

However, lmcount(rhw()) and ff() individually are both quite fast, suggesting a
problem with the synergy. Silvia or Erez, can one of you look into this? This
may very well be a nasty bug in our LAMA competition entry, in which case it'd
be good to fix this soon.

> ./downward-1-debug < output --search 'lazy_greedy(lmcount(lm_rhw())'

There is a closing parenthesis missing at the end. Since Moritz anyway rewrites
the parser at the moment, this will probably be resolved in the near future.

I will probably not be able to look into this within the next month, but
I"ll have a look if it has time.

Actually, Gabi, can you have a look at this, too? I get a segmentation fault from

./downward-1-debug < output --search 'lazy_greedy(lmcount(lm_rhw())'

which seems to come from the option parsing code according to gdb.
Is there anything wrong with that command line?

This is a spin-off of issue127.

Silvia, do you think you can look into this?
If not, please assign back to "- no selection -".

Not sure if this is really a bug, but I'd like to know what is going on there.
Landmark generation on the task from issue127 takes a very long time and LAMA
search is extremely slow (it takes 250 seconds to get to 100 evaluated states),
and I'd like to know why.

(The task on which this happens is "output.sas"/"all.groups" from issue127.)