Issue668

Title Merge-and-Shrink: Integrate dynamic MIASM merge strategy
Priority feature Status reviewing
Superseder Nosy List malte, silvan
Assigned To silvan Keywords
Optional summary
- When merging, open follow-up issue to discuss if non-perfect shrinking of
merge candidates is reasonable, and if so, at which place. (Currently, we
imitate the behavior of the merge-and-shrink computation.) See also 3) in msg6218).

- Before merging: re-order some of the methods in the implementation file of FTS
 to match the order in the header file.

Created on 2016-09-02.10:46:17 by silvan, last changed by silvan.

Summary
- When merging, open follow-up issue to discuss if non-perfect shrinking of
merge candidates is reasonable, and if so, at which place. (Currently, we
imitate the behavior of the merge-and-shrink computation.) See also 3) in msg6218).

- Before merging: re-order some of the methods in the implementation file of FTS
 to match the order in the header file.
Messages
msg6442 (view) Author: silvan Date: 2017-07-12.11:56:08
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.)
msg6439 (view) Author: silvan Date: 2017-07-10.16:58:20
> 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).
msg6438 (view) Author: malte Date: 2017-07-10.16:53:13
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).
msg6434 (view) Author: silvan Date: 2017-07-09.20:29:48
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? ;-)
msg6433 (view) Author: malte Date: 2017-07-09.16:16:54
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.)
msg6432 (view) Author: silvan Date: 2017-07-09.16:12:21
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.
msg6431 (view) Author: malte Date: 2017-07-09.16:05:01
Should this be reviewed now? After the merge of issue707, should we run new
experiments?
msg6430 (view) Author: silvan Date: 2017-07-09.15:59:12
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).
msg6429 (view) Author: silvan Date: 2017-07-09.15:56:05
(update summary)
msg6407 (view) Author: silvan Date: 2017-07-04.23:30:35
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.
msg6404 (view) Author: malte Date: 2017-07-04.19:38:13
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.
msg6400 (view) Author: silvan Date: 2017-07-04.14:42:24
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.
msg6399 (view) Author: silvan Date: 2017-07-03.16:10:58
Update summary.
msg6398 (view) Author: silvan Date: 2017-07-03.16:09:54
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.)
msg6382 (view) Author: silvan Date: 2017-05-19.17:49:25
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.
msg6249 (view) Author: silvan Date: 2017-04-27.17:50:12
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.
msg6218 (view) Author: malte Date: 2017-04-25.15:50:16
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.
msg6212 (view) Author: silvan Date: 2017-04-25.11:19:08
I also updated this pull-request.
msg6210 (view) Author: malte Date: 2017-04-25.10:52:47
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).
msg5955 (view) Author: silvan Date: 2016-12-21.12:13:12
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.
msg5613 (view) Author: silvan Date: 2016-09-08.21:44:51
Sure, I'll keep it in mind.
msg5612 (view) Author: malte Date: 2016-09-08.18:45:10
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.
msg5611 (view) Author: silvan Date: 2016-09-08.17:14:28
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
msg5596 (view) Author: malte Date: 2016-09-04.19:18:47
> 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?
msg5595 (view) Author: silvan Date: 2016-09-04.17:52:14
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?
msg5594 (view) Author: silvan Date: 2016-09-04.17:51:00
Regarding 1. + 2., I opened issue670 to introduce the option in a separate
issue, and I'm happy with n
msg5590 (view) Author: malte Date: 2016-09-02.18:39:39
> 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.
msg5589 (view) Author: malte Date: 2016-09-02.18:37:45
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".
msg5588 (view) Author: silvan Date: 2016-09-02.15:43:41
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
msg5583 (view) Author: silvan Date: 2016-09-02.10:46:17
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.
History
Date User Action Args
2017-07-14 16:09:24silvansetsummary: - When merging, open follow-up issue to discuss if non-perfect shrinking of merge candidates is reasonable, and if so, at which place. (Currently, we imitate the behavior of the merge-and-shrink computation.) See also 3) in msg6218). -> - When merging, open follow-up issue to discuss if non-perfect shrinking of merge candidates is reasonable, and if so, at which place. (Currently, we imitate the behavior of the merge-and-shrink computation.) See also 3) in msg6218). - Before merging: re-order some of the methods in the implementation file of FTS to match the order in the header file.
2017-07-12 11:56:08silvansetmessages: + msg6442
2017-07-10 16:58:20silvansetmessages: + msg6439
2017-07-10 16:53:13maltesetmessages: + msg6438
2017-07-09 20:29:48silvansetmessages: + msg6434
2017-07-09 16:16:54maltesetmessages: + msg6433
2017-07-09 16:12:21silvansetmessages: + msg6432
2017-07-09 16:05:01maltesetmessages: + msg6431
2017-07-09 15:59:12silvansetmessages: + msg6430
2017-07-09 15:56:05silvansetmessages: + msg6429
summary: - When merging, open follow-up issue to discuss which shrink strategy should be used when shrinking the temporary copies of transition systems (see 3) in msg6218). -> - When merging, open follow-up issue to discuss if non-perfect shrinking of merge candidates is reasonable, and if so, at which place. (Currently, we imitate the behavior of the merge-and-shrink computation.) See also 3) in msg6218).
2017-07-04 23:30:35silvansetmessages: + msg6407
2017-07-04 19:38:13maltesetmessages: + msg6404
2017-07-04 14:42:25silvansetmessages: + msg6400
2017-07-03 16:10:58silvansetmessages: + msg6399
summary: - When merging, open follow-up issue to discuss which shrink strategy should be used when shrinking the temporary copies of transition systems (see 3) in msg6218).
2017-07-03 16:09:55silvansetmessages: + msg6398
2017-05-19 17:49:25silvansetmessages: + msg6382
2017-04-27 17:50:12silvansetmessages: + msg6249
2017-04-25 15:50:16maltesetmessages: + msg6218
2017-04-25 11:19:08silvansetstatus: chatting -> reviewing
messages: + msg6212
2017-04-25 10:52:47maltesetmessages: + msg6210
2016-12-21 12:13:13silvansetmessages: + msg5955
2016-09-08 21:44:51silvansetmessages: + msg5613
2016-09-08 18:45:10maltesetmessages: + msg5612
2016-09-08 17:14:28silvansetmessages: + msg5611
2016-09-04 19:18:47maltesetmessages: + msg5596
2016-09-04 17:52:14silvansetmessages: + msg5595
2016-09-04 17:51:00silvansetmessages: + msg5594
2016-09-02 18:39:39maltesetmessages: + msg5590
2016-09-02 18:37:45maltesetmessages: + msg5589
2016-09-02 15:43:41silvansetmessages: + msg5588
2016-09-02 10:46:17silvancreate