Pull request: https://github.com/aibasel/downward/pull/50

Merged, thanks everyone.

Finally, v4 implements a change in the random pattern generation: instead of randomly selecting a neighbor and terminating if it cannot be included in the pattern due to the PDB size limit, the algorithm now iterates over all neighbors (in random order) and takes the first one which fits the size limit. If there is none, it terminates.

The result are not really good: https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue1008-v4-random-patterns-multiple-seeds-issue1008-v3-issue1008-v4-compare.html
Coverage decreases on average for the random patterns config (i.e., repeated computation of random patterns). In particular, search time score and expansion score decrease quite a lot. The computation time of the pattern generation fluctuates a lot (in both directions).

We decided to stick with v2.

I tagged v3 after addressing more changes requested during the code reviews. No surprising performance changes: https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue1008-v3-cegar-multiple-seeds-issue1008-v2-issue1008-v3-compare.html

In v2, we changed the implementation details of the "stagnation" option. In the original implementation (v1 here), time counting towards the stagnation limit (an absolute limit in seconds) was started only after finding a duplicate pattern. Florian pointed out that this is rather unintuitive, and in v2, stagnation time counts from the beginning on and is reset only when a new pattern in found.

Experiments for a fixed random seed:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue1008-v2-cegar-fixed-seed-issue1008-v1-issue1008-v2-compare.html
The first and third configs do not use stagnation limits and are not affected by this change, since randomization is not altered. Yet blacklisting seemst to be affected positively, also in the combination with stagnation. As we have seen in the past, this may be well attributed to noise (due to time limits in the algorithms).

I ran experiments averaging over 10 random seeds with the configs using stagnation limits:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue1008-v2-cegar-multiple-seeds-issue1008-v1-issue1008-v2-compare.html
There are no large differences.

This means we can freely decide if we prefer v2 over v1, i.e., if we think it makes more sense to start counting time towards stagnation from the start/the last newly generated pattern on.

The results for the random pattern generation algorithms can be found here:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue1008-v1-random-patterns-multiple-seeds-30m.html
the single config (called sRCG in the paper) solves 763,5 tasks, which is more than reported in the paper (758.8). So this looks good.

In the paper, we did not report results for mRCG (multiple random patterns) with the CPDB heuristic, so we can't compare the results for this config.

Since this issue also touched the multiple CEGAR PDB code (making the multiple part an abstract base class so that the multiple random pattern algorithm can use the same code), I ran experiments to ensure that nothing changes there, which is indeed the case: https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue1008-v1-cegar-fixed-seed-issue1008-base-issue1008-v1-compare.html
Note that slight variations in number of patterns/iterations and therefore possibly in number of expansions are due to the two time-related options we use in the multiple * algorithms, namely total time and stagnation time limit.

Experiments for the random pattern(s) configuration (to compare with the paper result) are on the way.

I added a link to the pull request in the summary. The next step is to discuss if and how we could restructure the RCG collection generation code to reuse code from the multiple CEGAR plugin.

We want to integrate the simple randomized baseline algorithms for pattern (collection) generation described in the ICAPS 2019 paper by Rovner et al.