Done.

issue795 deals with discussing alternative options for computing temporary
products than using the same non-perfect shrinking as the merge-and-shrink
heuristic.

Yes, please merge!

Thanks for the reviews in many iterations!

Here is the reproduction of the coverage values reported in the paper that was
still missing:

                          Prefer Atomic     |      Prefer composite  | ALL-
                       RL       L      RND  |  RL       L      RND   | RND
paper results:         743     746     745     747     724     730     726
v4 paper results:      748     751     738     750     730     723     739
v5-hack paper results: 761     758     747     758     741     733     753

Presumably, the larger (positive) differences compared to v4 are due to further
changes in Fast Downward since then (in particular, moving away from global
objects), which also led to improvements in many other tests of other code bases
that I ran since then.

Any further comments? Otherwise I'm ready to merge.

I left one more (small) comment. Looks good to merge. Many thanks for the patience!

I'm done with the changes. (We can rename the new file further after our offline
discussion.)

I left some comments on bitbucket and am done looking at the parts that affect
the "core" of merge-and-shrink. If you can update the pull request for the
requested changes, I'll then have a quick look on the actual implementation of
the scoring function. (I wouldn't run extensive experiments for these changes,
but perhaps a quick sanity test on your local machine.)

In preparation of the sprint, I updated the pull-request, tagged the latest
version and re-ran all experiments. The previous version v3 is now called
v5-clean and v4 is v5-hack. v5-hack contains, not surprisingly, a hack to
emulate the computation of the implementation of the miasm score used in the
ICAPS16 paper (see msg6400 below). v5-clean does the computation as it was
originally intended.

The full data can be found in the following tables, split according to
tie-breaking strategies and version tags:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v5-clean-abp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v5-clean-pba.html.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v5-hack-abp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v5-hack-pba.html.html

The comparison of hack vs clean:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v5-hack-vs-clean-abp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v5-hack-vs-clean-pba.html
(subset of the paper configs:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v5-hack-vs-clean-paper.html)

Summary: no qualitative changes compared to the previous comparisons posted in
this issue.

I also wanted to reproduce the coverage table of the paper, as in the previous
message (msg6442), but noticed that I need to re-run these configs with the old
grid nodes and 2 GiB of memory limit first.

In v4, (which does *not* include v3, the removal of the below discussed "bug"),
I do not copy distances objects any more when computing merge candidates, and I
also compute the product directly from the existing transition system(s) if
it/they did not need to be shrunk, saving more copies.

Compared to v2 (which was already a slight improvement over v1), this sped up
the computation (again), increasing coverage consistently between 1-4 across all
configurations:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v2-v4-compare-abp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v2-v4-compare-pba.html.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v2-v4-compare-paper.html.html

Absolute reports:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v4-abp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v4-pba.html.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v4-paper.html.html

                     Prefer Atomic     |      Prefer composite  | ALL-
                  RL       L      RND  |  RL       L      RND   | RND
paper results:    743     746     745     747     724     730     726
v4 paper results: 748     751     738     750     730     723     739

(Interestingly, the all-random configuration got much better, while the other
partially randomized order got worse. See msg5955 for my assumption on the
changed use of random generators.)

> Unless you want the same old review again, it should be a new entry. :-)
Done. 

> I'll try to get to it soon (perhaps out of order).
That would be great because it would ease (re-)running experiments for the
"state of the art in merge-and-shrink" for the journal paper (and thesis).

Unless you want the same old review again, it should be a new entry. :-) I'll
try to get to it soon (perhaps out of order).

It was already in the queue once; do we allow re-opening, and if so, would it
stay where it is, i.e. at the top? ;-)

Can you add it to the review queue? (I might do it out of order if it is quick,
but it's good to add it to the queue anyway.)

The last experiments are based on a partial integration of branch issue707, and
I don't think we changed anything else than documentation/cleaning-up in
issue707 afterwards. So yes, this issue should be ready to be reviewed and the
results are up to date.

Should this be reviewed now? After the merge of issue707, should we run new
experiments?

Issue707 has been merged, and now this pull-request is up-to-date again:
https://bitbucket.org/SilvanS/fd-dev/pull-requests/22/issue668/diff

I addressed the comments of the first review where possible, and left the
discussion of if, how and when to shrink the copied transition systems when
computing their product to a future issue (or to further research on this strategy).

(update summary)

No, you already once looked at the code and we discussed how to improve over the
"make copies of transition systems within the FTS"-business. Once issue707 is
integrated, the computation of this strategy will be very easy, because we can
apply shrink and prune transformations also without having the copied factors
within an FTS. So once you are happy with issue707, this one will merit another
hopefully quick review.

Very interesting! Is there something for me to do at the moment? This is set to
"reviewing", but I'm not sure what the status for me is at the moment.

I noticed "a bug" in the implementation of dyn-MIASM as we have been using it
since the ICAPS16 paper : the score (= ratio of alive states/total states) was
computed based on a different value for total states x than intended: x =
factor1.size * factor2.size for the unmodified factors factor1 and factor2,
rather than x = shrunk_factor1.size * shrunk_factor2.size. Recall that in the
current implementation, we shrink the temporarily copied factors using the same
strategy as the real merge strategy would use before merging them. I put bug in
quotation marks here because a) in the description of dyn-MIASM we never
mentioned that we perform shrinking before merging as usual when attempting to
compute all candidate merges, and b) you already wrote that you find it rather
unintuitive that we shrink these temporary copied factors at all.

Long story short, fixing this bug (v3) has quite an impact (comparison of v2
with v3):
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-compare-v2-v3-abp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-compare-v2-v3-pba.html
subset of the paper configs:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-compare-v2-v3-paper.html
Some of the configurations experience a huge increase in coverage, others a
non-negligible decrease. In particular, the better configurations now surpass
the "real MIASM" by quite a margin.

As you wrote in msg6218, I think we should first integrate the implementation
with the "bug" and then in a follow-up issue consider changing/improving the
strategy even further.

Update summary.

I already integrated branch issue707 (pruning as a separate step) to see how the
changes work for this issue. They work well and experiments look good (with the
same differences observed as in msg5955):

http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v2-abp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v2-pba.html.html

Subset of configurations reported in the ICAPS16 paper:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v2-paper.html.html

(I can't easily create comparison results for v1 without rerunning them due to
changes in lab, but coverage never decreases in v2 compared to v1 and sometimes
increases.)

As we also need to be able to prune a transition system independently of it
being part of an FTS, we should wait with continuing with this issue until
issue707 has been merged, where we make computation of distances and pruning
configurable, and also will make the prune transformation be part of the public
interface of FTS.

We settled for option 2) and will first change the design of the rest of the
code in issue722 to ease the integration of the new merge strategy in this issue.

Thanks! I'm done with my comments. There are three kinds of comments:

1) Small things that don't affect behaviour like documentation, typos etc.

2) The question how exactly we want to implement the "temporary merges".

3) The question which shrink strategy should be used within MIASM.

Dealing with 1) should not be too difficult. Before merging, I think we should
address 2) too; I think the current solution is a bit too hacky because it
allows leaving the FTS in an invalid state, which I think always increases the
"mental load" for understanding the code a lot.

Regarding 3), perhaps we need to discuss this conceptually and perhaps also run
some additional experiments. I think this is something that we could potentially
defer to a follow-up issue.

I also updated this pull-request.

Hi Silvan, it's FIFO time! This one comes next after issue667.

Can you bring the pull request up to date, i.e., make sure that it is based on
the most recent master version? If I look at it right now, I see some small
conflicts (e.g. in the CMake files).

I ran experiments, including full tie-breaking variants as described in the
ICAPS2016 paper.

http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v1-abp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v1-pba.html

abp: atomic before product (prefer atomic transition systems over products)
pba: product before atomic (prefer product transition systems over atomics)
rl/l/rnd: order of atomic transition systems (reverse level/level/random)
nto/otn/rnd: order product transition systems (new to old/old to new/random)

This table is just a subset of the above configurations, matching Table 3 of the
paper:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue668-v1-paper.html

There are quite some differences in the configurations involving randomness. I
suspect that this has to do with the change of how we use random number
generators (the old global one, or a local one, or a mixture). Another
difference to the paper version is that back then, when temporarily merging
entries of the factored transition system, we did not only copy the transition
systems, but also the merge-and-shrink representation. As this is not necessary,
we do not do it anymore.

Sure, I'll keep it in mind.

I made some preliminary comments on bitbucket, but I realized I cannot really
review this now or probably in the next days. Can you please insert it into the
(to be discussed) queue? Then I'll pop it from my inbox for now.

I started over after having merged issue670, and the new pull request, this time
containing only changes specific to this issue, can be found here:
https://bitbucket.org/SilvanS/fd-dev/pull-requests/22/issue668

> I like the idea of such a queue, do you have a good idea where it could live,
> so that you could easily administrate it and we could see the status?

I don't know. Maybe something to discuss for the next Fast Downward meeting?

naming it "verbose" to have the positive use case in the code. (My touchpad just
hit the send button...)

I like the idea of such a queue, do you have a good idea where it could live, so
that you could easily administrate it and we could see the status?

Regarding 1. + 2., I opened issue670 to introduce the option in a separate
issue, and I'm happy with n

> As for issue667, I'd like to queue this code review into your list,
> but I guess issue667 would be much easier to be integrated first.

Perhaps it would be a good idea to actually start such a review queue, not just
during the sprints? It would help me keeping track of things, and it might also
be useful for the others to see what is happening.

I had a quick look, but it's a bit much to review quickly in one chunk, and I
think the changes to the "infrastructure" are large enough that a review would
be good.

Two comments:

1. I think we could speed up the review process by separating the change with
the "silent" option (conceptually simple, but many lines and many files
affected) from the other changes related to copying stuff. What do you think? It
would be extra work for you, but it might get merged faster overall.

2. I wonder if we should call the option "verbose" rather than "silent" because
we always test for the negated form ("!silent"). I searched the code for
precedent on this, but I found no occurrences of either "silent" or "verbose".

For the temporary computation of the products corresponding to all merge
candidates, the new code requires quite some changes to the existing code:

- Because we want to apply shrinking before merging, we need to actually copy
the elements of the factored transition system (i.e. transition
system/distances/heuristic representation) before doing so, to not compromise
the rest of the factored transition system. This requires copy constructors in
several classes, and also to have the factored transition system qualified
non-const.
- Because merge-and-shrink usually prints logging messages when
shrinking/merging/pruning, we need to disable such logging whenever operating on
the copied objects, to avoid producing very large log files. This requires
passing around "silent" flags in several places.
- To be able to use the same shrinking settings for the new scoring function, it
needs to have the exact same shrinking related options as
MergeAndShrinkHeuristic itself. This means to have small duplication in the
command line syntax (and of course a slight memory overhead for storing a second
shrink strategy, but these objects should be very light weight).

All of these issues have been part of the strategy already when we described in
the paper, so there are no performance concerns, but code quality concerns.

As for issue667, I'd like to queue this code review into your list, but I guess
issue667 would be much easier to be integrated first.

https://bitbucket.org/SilvanS/fd-dev/pull-requests/20/issue668/diff

We would like to integrate the recent merge strategy "dynamic MIASM", which is a
dynamic, i.e. non-precomputed, variant of the original MIASM merge strategy,
described in the ICAPS 2016 paper An Analysis of Merge Strategies for
Merge-and-Shrink Heuristics.

Technically speaking, this means to "just" add a new merge scoring function
which prefers merges that maximize pruning opportunities through throwing away
unreachable and irrelevant states.