version2: compute label ranks in MergeDFP on demand and cache them, rather than
precomputing for all transition systems.

version3: compute goal relevance of a transition system on demand in MergeDFP,
rather than storing this flag in transition systems.

version4: do not directly use g_rng in LabelReduction and ShrinkBucketBased, but use
a class variable that is a shared_ptr to either g_rng or to a new RNG object,
seeded via new options of these classes.

Resolved.

Fix summary.

Should the text for version4 in the summary begin with "do not"?
If yes, feel free to edit the summary and merge.

I'd like to merge this issue, to proceed with issue644. Do you have any objections?

In v4, the code was updated to the latest default branch and now label reduction
and shrink bucket based have their own RNG option.

Comparison against previous version, with the default seed (i.e., using the
global RNG):
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue645-v4-issue645-v3-issue645-v4-compare.html
(looks totally fine)

Running a few configurations with different random seeds, for testing:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue645-v4-random-seeds.html

For the rng issue, see issue648.

Note that I said to use the global *RNG* by default -- quite different from
using the global *seed*! The two main points:

1) The main point of random numbers is to be *random* by default. With the
solution where we use separate RNGs seeded from the same value, let's say for
example that "merge_and_shrink(merge_strategy=random_merge())" creates an M&S
heuristic with a random merge strategy. Let's say we want to use two of them in A*:

--heuristic h1=merge_and_shrink(merge_strategy=random_merge())
--heuristic h2=merge_and_shrink(merge_strategy=random_merge())
--search "astar(max([h1,h2]))"

This would generate two identical heuristics, so the max would do nothing (other
than waste time and memory). I think this is too dangerous and unintuitive to be
acceptable default behaviour. (Ditto for interleaved over epsilon-greedy
searches or other cases where you want to combine multiple random versions of
the same thing, which is a common pattern.)

2) Giving each user of randomness its own RNG object seeded appropriately would
be a decent solution if it was acceptable in terms of performance. But it is
not: Mersenne Twister RNG objects are huge (~20K bits), and we should not
multiply them unnecessarily. Also, we barely have enough entropy to seed a
single RNG, let alone a large number of them.


Regarding the question "Wouldn't it be better if every class that uses g_rng
(re)seeds the object with its own seed?" I would say no for several reasons (we
can discuss details on Monday), but also I don't think this would solve the
problem you want to address except in very limited circumstances (where no
control is passed to any other parts of the planner between reseeding and the
*last* call to the RNG in that piece of code). As long as they share an RNG,
they will interfere with each other.

More generally, reseeding is a code smell because it seriously compromises the
randomness properties and there are usually better solutions.

I see the point that being able to reproduce, e.g., the way that merging is
done, is very useful for debugging and experiments. But "--heuristic
h=merge_and_shrink(merge_strategy=random_merge(random_seed=2016))" would do
that, and it's even shorter (and more explicit) than our current way of
requiring a global random seed option for reproducibility.

Regarding msg5232: ok (but the experiments look like it does not really affect
the behavior).

> On the RNG issue: I think the clean approach is to

> 1. give all components using g_rng a random_seed parameter
> 2. have a default value ("-1" or whatever -- make sure the "allowed" seeds are
> non-negative) that means "use the global RNG"
> 3. use shared_ptrs to the RNG to implement this, the same way we share other
> kinds of shared objects between components

I see that 3 can be a problem, but I still feel uncomfortable with 2. Why should
the default be to use the global seed? I understand that this eases usage if you
want to change the global --random-seed option, but at the same time, I find it
dangerous that various components change their behavior at the same time when
using this option, and the problem I mentioned earlier (that reproducibility is
not possible whenever the usage count of g_rng changes) persists. Wouldn't it be
better if every class that uses g_rng (re)seeds the object with its own seed?
Maybe the option "-1" could mean to use the same default seed that g_rng uses
initially, but nevertheless re-seed g_rng in the using classes? This would
ensure reproducibility even in the light of change, but at the same time allow
the global --random-seed option affect *all* users of g_rng (because when the
users of g_rng still use "-1", they would adapt to the global random seed and
re-seed g_rgn). I'm not sure whether I could make clear the last idea, but I can
try to elaborate if not.

On the goal relevance issue, if there is something nonobvious going on here (it
sounds like it), then we should comment the semantics we use clearly in the
code, and I suggest we should discuss this further in our next meeting.

On the RNG issue: I think the clean approach is to

1. give all components using g_rng a random_seed parameter
2. have a default value ("-1" or whatever -- make sure the "allowed" seeds are
non-negative) that means "use the global RNG"
3. use shared_ptrs to the RNG to implement this, the same way we share other
kinds of shared objects between components

The basic functionality should be implemented once, similar to the way we
implement common options elsewhere. Of course, there is no need to implement
step 1. for all components using the RNG simultaneously.

In particular, this would not (significantly) complicate the implementations of
the users, and we would not unnecessarily use multiple RNGs when we don't want
to. (RNG objects using the Mersenne Twister are rather large.)

Coming back to msg5228 below, I tested changed the goal relevance computation to
be done on demand by MergeDFP. This is implemented in v3, and it does not hurt
performance:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue645-v3-issue645-v2-issue645-v3-compare.html

In version 2, label ranks are computed on demand in MergeDFP, rather than
computing all label ranks always, independently of whether they are needed or
not. We lose 2 instances due to a slight memory increase in, but these are
borderline instances anyway.
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue645-v2-issue645-v1-issue645-v2-compare.html

Also attaching a memory plot for the configuration in question.

Another question that just came up is the following: I wanted to get rid of the
notion of "goal relevance", stored in transition systems, and let MergeDFP
compute this dynamically ("is there a non-goal state?"). The point is that the
two definitions are not equal when pruning is involved: a transition system may
contain a goal variable and still consist only of goal states, because all
non-goal states have been pruned (irrelevant/unreachable). For example, in
parcprinter-opt11-strips:p02.pddl, we have the following goal variables: 17, 18,
19, 20, 21, 25, 26, 27, 28, 29, 30, 31 (there are 32 variables). After computing
all atomic transition systems (including pruning), only 20, 21, 28, 29, 30, and
31 are goal relevant in the sense that they contain a non-goal state. 

Considering that this is somewhat a conceptual change, should we still go for
it? (I'll run experiments in the meanwhile, so we have some data to look at.)

I didn't consider this indeed. Hmm... I wanted to change this because when
integrating MIASM with factored symmetries, I had the problem that even when no
symmetries were found, MIASM behave differently than the "real MIASM", and this
was because of MIASM's sampling phase, where it constructs and uses its own
merge and shrink strategies, but with the same global rng.

Generally, I don't like the idea of a global rng variable, because that means
that the outcome depends on the number of times the global variable is used at
other places of the program. On the other hand, specifying a --random-seed
option for label reduction and shrink_fh (and for MergeDFP in the future, when
we integrate the new strategy) doesn't seem to be that great either, but I think
I would still prefer the second over the first alternative (we can have default
values for random-seeds, so the option is really optional). Is that okay with you?

One problem: if we document something as random, then the user would expect to
be able to affect it with the --random-seed option (or whatever it is called).
Is this the case here? If yes, should we add a random seed option for M&S (or
some of the involved components)?

Besides many smallish changes, I replaced the use of g_rng by a local
instantiation of a random number generator for reproducible behavior, regardless
of how often g_rng is used at other places. This affects LabelReduction and
ShrinkBucketBased. For the latter, I tricked the local rng instantiation by
using it as many times as LabelReduction (which uses it before) would have used
it. At a later time point, this should be changed, but then performance of
shrink_fh would need to be re-evaluated. 

This is version1:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue645-v1-issue645-base-issue645-v1-compare.html

Performance did not change, as expected.

This is part of meta issue567.

As soon as I get working on this issue, I'll post more precise changes, if
anything worth mentioning comes up.