As discussed offline, I worked on this further based on Moritz's work and think
it's now ready to merge. Performance looks very good, as discussed with Raz,
Jörg and Moritz offline.

Some further cleanup should happen soon and the documentation will need to be
updated, but it's ready to be merged in its current state. I'll defer the
documentation update and update of the downward-seq-opt*.py and configs scripts
for now since the shrink strategy names will change again soon.

Please note that "max_states" and "max_states_before_merge" are now options of
the shrink strategies, not of "mas(...)", since the shrink strategies are now in
full control of when and how to shrink.

More work needs to be done, but that can go into issue261.

Thanks everyone, especially Raz and Moritz!

Added a new patchset.

Changes:
* reverted the normalization decision-logic
* changed the condition when to use map in ShrinkFH
* Malte's change of pruning shrink strategy

> After correcting the configs, mas-1 was back to normal.

Important: the same change needs to be made in the following files in src/search:

- downward-seq-opt-fdss-1.py
- downward-seq-opt-fdss-2.py
- downward-seq-opt-merge-and-shrink.py

Ideally we should use the symbolic names for the merge/shrink strategies there.
I think we even say in our documentation that the numeric numbers are deprecated
and will change.

Thanks a lot for the analysis! Can you add a comment to the additional normalize
call that mentions this performance difference in mas-2? (It would be good if it
also spelled out what mas-2 is -- I can never remember.)

> Try changing the merge strategy in downward_configs.py to 6 and see if that gets
> us back to the old results. Sorry for the confusion!
> 

After correcting the configs, mas-1 was back to normal, but mas-2 was
not. After reverting to the old when-to-normalize logic, mas-2 was back
to normal too.

Moritz, the performance issue is very likely this:

>  I swapped the meaning of two of our rarely/never used merging strategies
>  (MERGE_LINEAR_LEVEL, MERGE_LINEAR_REVERSE_LEVEL) to make nomenclature more
>  consistent.

I was quite wrong about the "rarely/never" used there -- our mas-{1,2}
strategies use these.

Try changing the merge strategy in downward_configs.py to 6 and see if that gets
us back to the old results. Sorry for the confusion!

We should make a note to also update the seq-opt-downward-....py scripts, and
ideally change to the (new) symbolic names for these. I think the correct
strategy to use is the one that is now called "MERGE_LINEAR_REVERSE_LEVEL".

> I'm currently trying to find out where the problem is.

I would say that the most likely changes are the changes to the logic in
MergeAndShrinkHeuristic::build_abstraction and the changes to when exactly
normalize() is called. Once you can pinpoint this, let me know!

Looks good! I still have to properly review the Shrink* classes. The raz_* files
look in much much better shape now. I don't quite fully understand some of the
logic within MergeAndShrinkHeuristic::build_abstraction, but that's a
comparatively small thing.

Moritz, I just pushed a small change to your repository: the forced shrinking
step to get rid of unreachable/irrelevant states now uses ShrinkFH instead of
ShrinkBisimulation, and it passes num_states as the length bound rather than
special-casing a value of 1. Changing the bound cleans up the misleading output,
and changing the class makes this massively faster in some cases. For example,
the solution time in Airport #08 with default parameters reduces from 423.46s to
64.94s on my machine.

Something has gone wrong in one of the revisions since 41ce08a50f69.

Coverage for the raz_ipc configs on the ipc08_opt suite dropped from 127
to 114 for the first config, from 126 to 110 for the second. 

After I addressed the first round of comments, everything was still
fine. The cause of error seems to be not enough memory.

I'm currently trying to find out where the problem is.

I uploaded a new patch set to the rietveld issue.

Changes:
* see inline comments
* removed unused methods
* moved are_bisimilar* - methods into a common base class of shrink dfp
and shrink bisimulation

I swapped the meaning of two of our rarely/never used merging strategies
(MERGE_LINEAR_LEVEL, MERGE_LINEAR_REVERSE_LEVEL) to make nomenclature more
consistents. This is just a warning in case someone wants to do an exhaustive
comparison of the old and new code and is puzzled by the changes in performance
of these strategies. (I don't think there's a need to do a performance study of
these two strategies, though.)

I would suggest waiting until the current round of refactoring is merged.
It'd be great if we could do this soon though, since Jörg will be visiting for
the next 10 days to work on the M&S journal paper.

> We can remove the strategies using the mixing parameter, as well as all the
> other unused methods you mentioned.

@Moritz: "grep mix raz_*.{h,cc}" will probably find (almost?) all relevant
portions of code.

Malte - So should I wait a bit longer before starting work on issue253 so it would 
be on the re-factored code?

I've now read most of the source files, but actually mainly the old ones (raz_*)
since they hadn't really been reviewed before.

After we've addressed the comments on Rietveld, I'm happy with those files apart
from one thing: I think methods Abstraction::are_bisimilar and
Abstraction::are_bisimilar_wrt_label_reduction belong into ShrinkBisimulation,
or maybe a new common base class of ShrinkBisimulation and ShrinkDFP if they are
also needed in ShrinkDFP. Moritz, do you think this would be possible?

This might mean that these methods will need access to some of the internal data
of Abstraction. For this purpose, some const accessors to the relevant data
could be added. I'm not sure if they should really be public in the long run
(maybe we should communicate this info to the shrink strategies in some other
way), so maybe keep them in a separate block from the other public methods with
a comment that these are only intended to be used by the shrink strategies.

We can remove the strategies using the mixing parameter, as well as all the other 
unused methods you mentioned.

Raz, do you mind if we get rid of the merge strategies that use the mixing
parameter? These strategies seem a bit hard to motivate for me.

Some cleanup: The following unused methods should be removed, both from the *.h
and *.cc file. (Raz, if you disagree, please speak up.)

In operator.{h,cc}:
- PrePost::operator== (along with the comment above it)
- Operator::get_distance_from_op,
  Operator::have_same_op_name,
  Operator::affect_a_common_variable
  along with the comment above them

In raz_abstraction.{h,cc}:
- Abstraction::add_relevant_reducible_op_pairs,
  Abstraction::are_greedy_bisimilar (currently commented out),
  Abstraction::reduce_operators (currently commented out)

In raz_mas_heuristic.{h,cc}:
- MergeAndShrinkHeuristic::approximate_added_transitions,
  MergeAndShrinkHeuristic::get_ops_to_reduce,
  MergeAndShrinkHeuristic::get_distance_from_op


The comment block with the HACK HACK HACK comment in operator.h next to the
operator == and operator != methods of Prevail should also go -- these two
methods are fine to keep.

I've made a first round of comments. So far, I have only commented on the files
that were changed, but I haven't yet read the files that are new. Will start
doing that next.

@Raz:

Can you check out the code block at
   http://codereview.appspot.com/4819063/diff/1/src/search/raz_mas_heuristic.cc
and tell us if the code block from line 417 (using the line numbering in the
right half) starting with "if (abstraction_count == -2) {" is still needed? Did
we use this in the experiments we report?

(Ideally, add a comment straight in the review tool. You should be able to sign
in with your regular Google account; double click on the code to add a comment.
It will only be published when you later hit "m" or click on the "publish+mail"
link.)

I've started to go through the code. It's generally a good idea not to make too
many independent changes at once, so I've opened issue261 for things that should
be changed, but not right now.

> Hi, so should I wait for this to be done before tackling 253?

How about the following: give me a few days to merge this, say, until the end of
your weekend. If it's not done by then, it's better to work on issue253 on the
current code and merge later.

Hi, so should I wait for this to be done before tackling 253?

OK, I'll look into it ASAP, hopefully tomorrow.

OK, I'll look into it ASAP, hopefully tomorrow.

> Hi Moritz, just to be clear: is this ready to be merged from your perspective?

Yes - if you principally agree with the new shrink-strategy structure.

And I think we should get the shrink-strategy refactoring out of the way
before I do anything further related to the mas-heuristic, so I have a
reliable base. Also, since this is the only major structural change I
had planned, finishing this part would make it possible to resolve some
of the new issues (250, 253, 255).

Hi Moritz, just to be clear: is this ready to be merged from your perspective?
Then I'd do a more careful code review than for something which is more like
work in progress.

Created a Rietveld issue: http://codereview.appspot.com/4819063/

Experimental results:
Synopsis:
*The new fh-strategies have improved coverage in parcprinter, otherwise
there's no difference. 
*The new dfp-strategies lose 1 or 2 problems in coverage. We talked
about this previously and should probably resolve issue250 before
looking into this further.
(*The default fh-strategy is quite good when using max_states=1000)

Details:

Configurations:
("mas-1", "--search
'astar(mas(max_states=1,merge_strategy=5,shrink_strategy=shrink_bisimulation(true, false)))'"),
("mas-2", "--search
'astar(mas(max_states=200000,merge_strategy=5,shrink_strategy=shrink_dfp(Enable_Greedy_Bisimulation)))'"),
("mas-3", "--search 'astar(mas(shrink_strategy=shrink_fh(Low, Low)))'"),
        ("mas-4", "--search 'astar(mas(shrink_strategy=shrink_fh(High,
Low)))'"),
("mas-5", "--search 'astar(mas(shrink_strategy=shrink_random()))'"),
("mas-6", "--search 'astar(mas(shrink_strategy=shrink_fh(High,
High)))'"),
("mas-7", "--search 'astar(mas(shrink_strategy=shrink_dfp(Default)))'"),
("mas-8", "--search
'astar(mas(shrink_strategy=shrink_bisimulation(false,false)))'"),
("mas-9", "--search 'astar(mas(max_states=1000))'")

Reports:
-base:
http://dl.dropbox.com/u/9599789/downward/mg-mas-base-various-eval-d-abs.html
http://dl.dropbox.com/u/9599789/downward/mg-mas-base-various-eval-p-abs.html

-new:
http://dl.dropbox.com/u/9599789/downward/mg-mas-new-various-eval-d-abs.html
http://dl.dropbox.com/u/9599789/downward/mg-mas-new-various-eval-p-abs.html

Concerning the plan_valid part: I thought I had removed this attribute in favor 
of the plan_invalid attribute, but apparently I had not. It is changed now and 
plan_invalid becomes true if a plan is found and at least one found plan can not 
be validated by the validator. If something strange still occurs in the 
experiments, please report back.

OK, I will wait for that.

I've added a new issue for the assertion fail, including what I think is
the reason: 
http://issues.fast-downward.org/issue250

I'm currently in the middle of trying to add better action-cost support
to the Low/High-FH-strategies, maybe merge when that is done?

Thanks for the analysis! The detailed results look good. I think we can and
should merge your changes then, and treat this segfault as a separate issue. 

Should I go about merging your changes now, or would you prefer it if I waited
until you are completely done with the M&S refactoring? Either option would be
fine with me.

Regarding the segfault/assertion failure, can you open a separate issue for
this? The report should contain the info on which tasks it fails and the
complete set of m&s parameters. Do all segfaults occur with the same merge
and/or shrink strategies?

The same assertion also fails in the base version.

Ran it with downward-debug, gives an assertion fail:

next variable: #64
shrink by 183334 nodes (from 200000 to 16666)
Size of collapsed groups =25566
Simplification was not f-preserving -- must recompute distances.
size of abstraction after shrink: 25566, Threshold: 16666
downward-1-debug: shrink_dfp.cc:41: virtual void
ShrinkDFP::shrink(Abstraction&, int, bool): Assertion `abs.size() <=
threshold || threshold == 1' failed.
Peak memory: 519960 KB
caught signal 6 -- exiting
Aborted

> Moritz, I'd like to have a look at what goes on in ParcPrinter. How can I access
> the two versions you compared? I guess "base" is the current default branch in
> the master repository?

Yes, and the "new2" version is here:
https://bitbucket.org/mogron/fast-downward/src/1dad5d6a2327/src/search/

> Can you also generate and upload the per-task results (...-eval-p-abs.html)?

Attached. The problematic task is parcprinter-27, run log attached. It
quits with a signal 11, a segfault I think.

The base version of WORK-mas-2 also gets some "signal 11"s - 5 in 240
runs. The new version gets 7 in 240 runs, but on different tasks. 

The error is not deterministic. I ran the task thrice now (using the
"new2" version), and it crashed at three different points - one of them
after the initialization of the mas-heuristic was finished:
[...]
Best heuristic value: 239779 [g=1031095, 5456821 evaluated, 748775
expanded, t=957.06s]
Peak memory: 913492 KB
caught signal 11 -- exiting

Moritz, I'd like to have a look at what goes on in ParcPrinter. How can I access
the two versions you compared? I guess "base" is the current default branch in
the master repository?

Can you also generate and upload the per-task results (...-eval-p-abs.html)?

Jendrik, the "plan_valid" sections indeed look strange. Do you know what's going
on here?

Current status:

I factored out the Shrinking Strategies. I made a first experiment today
comparing the resulting version to the original, using the two configs
in raz_ipc() and the suite ipc_08_opt_strips. The reports are attached
("mg-mas-base..." is for the old version). There seem to be no
significant differences in performance, although in the new version one
of the parcprinter problems is not solved. 

I don't understand the plan_valid-section - the numbers for the old
version are greater than the coverage numbers.

Currently, the shrink strategies are parametrized as follows:
shrink_bisimulation(greedy, memory_limit)
greedy(bool): 
memory_limit(bool): 

shrink_dfp(style = DEFAULT)
style({DEFAULT, ENABLE_GREEDY_BISIMULATION}): what kind of dfp strategy

shrink_fh(highlow_f, highlow_h)
highlow_f({HIGH, LOW}): start with high or low f values
highlow_h({HIGH, LOW}): start with high or low h values

shrink_random: missing

Calling this a "bug" since the current state of affairs with two copies of the
code (unused_* and raz_*) is so ugly that it is a release blocker. There are
also some comments in operator.h and operator.cc (search for
[raz-ipc-integration]) that need to be revisited.