Merged. Of course we can reopen the discussion if you believe we should not have merged this.

(If this doesn't fix it, there is also issue1065 to consider.)

> - segfaults: there are more than 700 segfaults for the two "cpdbs-genetic"
> configurations. This needs further investigation.

On first glance, this looks like it could be issue785. I'll leave a message there.

I ran an experiment:

https://ai.dmi.unibas.ch/_experiments/ai/downward/issue1077/data/issue1077-exp1-eval/issue1077-exp1.html

This compares all pattern collection generation methods except "manual_patterns" (which needs per-task parameter settings) for both canonical heuristic and zero-one cost partitioning.

I included the default parameter settings for all methods but also tried to use ones that used similar settings to the other mathods, in particular including a 20M total abstract state configuration for all methods that can bound the total number of abstract states across the entire collection. It turned out these 20M configs were generally best. (FWIW, I think it would be good to add such an option to the methods that currently lack it, such as systematic PDBs and the genetic algorithm PDBs.)

Some interpretation of the results.

Error exits:

- The two "unsolvable" exit codes happen in Mystery, which is expected.
- exit code 30: this happens on one organic synthesis task and looks like a case where the translator runs out of memory and Python cannot shut down cleanly
- exit code -15: these are two ParcPrinter tasks where the output reaches the hard limit with some planner configuration. We should make these configurations less chatty, at least at default verbosity.
- segfaults: there are more than 700 segfaults for the two "cpdbs-genetic" configurations. This needs further investigation.
- sigkill: like exit code 30, this happens on some Organic Synthesis instances where other runs run out of memory

Coverage with canonical heuristic:

- genetic PDB is worst due to the many segfaults; I don't give its numbers in the next two points
- total coverage from worst to best when using the best setting for each pattern generation method: systematic (833), random (860), disjoint cegar (867), combo (871), multiple cegar (936), hillclimbing (943)
- total coverage from worst to best with default settings: systematic (833), combo (852), random (855), disjoint cegar (867), multiple cegar (924), hillclimbing (943)
- I found only one domain where a combo config is uniquely best among the cpdb configurations (tetris-opt14, with 13 solved vs. 11 for the best other cpdb configuration).

It looks to me like we should recommend "multiple_cegar" or "hillclimbing" as a replacement for "combo" when using cpdb.

Coverage with greedy zero-one cost partitioning:

- total coverage from worst to best when using the best setting for each pattern generation method: multiple cegar (839), genetic (840), random (849), hillclimbing (853), systematic (861), combo (875), disjoint cegar (899)
- total coverage from worst to best with default settings: systematic (832), multiple cegar (838), random (848), hillclimbing (853), combo (859), genetic (871), disjoint cegar (899)
- domains where a combo config is uniquely best amont the zopdb configs: freecell (21 vs. 20), pipesworld-notankage (23 vs. 21), pipesworld-tankage (18 vs. 16), scanalyzer-08 (14 vs. 12), scanalyzer-11 (11 vs. 9), snake (13 vs. 11), tetris-opt14 (13 vs. 9), woodworking-08 (14 vs. 13), woodworking-11 (9 vs. 8)

It's interesting to see how poor zopdb is overall, but perhaps not so surprising because it makes no attempts to optimize the order. It works best in combination with heuristics that are already designed to compute disjoint collections (as in the patterns are disjoint, not as in the patterns are additive). This also makes sense: once all variables have occurred once in a pattern, all subsequent patterns have action cost 0 and are essentially dead weight (unless they can prune some states; we can still get infinite heuristic values out of them).

I would recommend "disjoint cegar" as a replacement for "combo" when using zopdb, but also it would be nice to have a better cost partitioning method in the code. :-)

I wondered if this would be the first time we would ever run an experiment with "combo", but I grepped for "combo" in the old experiments directory, and it looks like we did use it exactly once, for issue585. This was the issue that introduced a common interface for pattern generation methods. We used one configuration with "combo" (--search 'astar(operatorcounting([pho_constraints(patterns=combo())]))'), presumably to have reasonable coverage of all existing pattern generators. This was not a PDB heuristic use, though, but an operator-counting constraints use.


Regarding replacements: I think the more natural replacement suggestions for combo would be other pattern collection generators, not individual pattern generators. For example, disjoint_cegar and multiple_cegar both include all goal variables.


For me the motivation to remove it is not based on performance but because it is something we should never have added in the first place. It is unprincipled and ad-hoc, not described in the literature, undocumented (we just give the automatically generated signature, no description of what it does), and as far as I know knowledge nobody including us has ever wanted to use it in an actual PDB heuristic experiment. None of these points is really related to performance; for all we know, it could perform very well. I can't find evidence we ever ran an experiment with it beyond the operator-counting example above, so perhaps it's the best planner configuration.

In my view running an experiment is not necessary, but perhaps I can use this as an opportunity to refamiliarize myself with how to run experiments on the grid. I'll do a basic comparison of our pattern collection methods with default parameters. I think this is interesting in any case.

I hope that the experiments show that combo is dispensable (and I wouldn't be bothered if there is no individual configuration that is universally better); if they show that it is an important part of the pareto frontier, we would have a bit of a problem because the points listed above (ad-hoc, unprincipled) would remain. But let's wait for the data first.

From your description, it sounds like there is an advantage in "combo" over "cegar_pattern", because "combo" is guaranteed to cover all goal variables.

To answer you question, yes, I think if we remove a feature, we should tell people what else to use. But this could be just a note in the commit message that then is copied to the change log on the next release. And since we agree on the recommendation, I don't see a reason not to include it. But we don't have to back up the recommendation by numbers and I would be fine with just the mention in the commit message.

I still see reasons to run the experiment (but like I said, would be fine without it): mainly, saying "we removed feature X because Y always outperforms X" is a better argument than saying "we removed feature X because we think feature Y is better". The other reason is just basic scientific curiosity but of course this doesn't count for much if I'm not the one setting up the experiment.

Why do we need a recommendation what people can use instead if we don't know any users of "combo"? 

Let me get back to the discussion of what "combo" does vs what "cegar_pattern" does. The latter computes a single (as large as possible) pattern, while the former computes a collection with one large (greedy) pattern and using singleton pattens with missing goal variables. To me it rather sounds like cegar_pattern is a better version than greedy, and combo tries to fix greedy by adding missing goal variables. Florian, since you stated that what you liked about combo is that it computes a large pattern, is that really the advantage you see in combo?

If you really think that we "need" to recommend something over combo and that cegar_pattern is an adequate such thing, then I can setup an experiment. Otherwise, I would strongly prefer to simply remove combo.

Any volunteers to set up such an experiment?

I'll not fight to keep it. I have no problem with removing the feature if we have a good recommendation what people can use instead, and CEGAR patterns look good for this. Maybe we could run an experiment comparing the two generators, so we can back the recommendation up with some numbers.

I want to make another attempt to remove the combo generator. It is a really weird beast. I don't think anyone really knows why it's there, it doesn't seem to be referenced anywhere, and I'm not convinced that the proposed use cases aren't served better by alternatives.

Anyone want to fight to keep it? (We should wait at least until Florian is back from holiday, plus one week.)

I never used it and don't know any paper using/mentioning it.

> I see some point in having this generator: the other generators focus more on
> having several smaller patterns of roughly equal size, while this one tries to 
> get one PDB as large as possible.

Don't the CEGAR pattern generators already achieve this? The base CEGAR algorithm makes a pattern as large as possible, stopping only when the task is solved, proved unsolable, or a pattern size limit is reached.

I'm a bit worried about a "let's simplify the code" issue turning into "let's add another feature" unless someone is enthusiastic about the new feature.

Have we ever used the "combo" generator as a baseline to compare against, for example in the CEGAR paper? Or has it been mentioned/described in a paper?

If the answer is "no" and "no", I'd rather remove it (and explain in the change log which configurations we recommend as a replacement).

If the answer to either is "yes", mentioning such a paper in our documentation would be good (and provide some justification for the code being present).

The benefits of removing features are:
- reduced code maintenance (every time we need to touch all features or all pattern collection generations; this is what triggered Silvan stumbling over this)
- smaller planner executable and hence lower memory usage
- reduced compilation time
- reduced code complexity (doesn't matter so much if the code doesn't interact with other things, but it's still the case that having less code allows one to get a quicker overview of where things are in the PDB code)
- reduced complexity for users; documentation becomes smaller and it's easier to find a "good" pattern collection

I'll write separately about this specific case.

In the model where the single pattern is parametrized and the collection is always filled with atomic patterns, this filling up seems to be the main work done in the class, so maybe something like this?

extend_with_atomic(initial_pattern=greedy())
extend_with_unused_variables(...)
extend_with_singletons(...)

Ok, let's keep it simple. Can we also have a better name than combo?

That sounds useful. I lean towards sticking with one parameter for picking the single pattern. My reasoning against the second parameter is that the second part needs to know about the result of the first, so we cannot just use our existing collection generators. If we introduce a new type of feature for this second parameter, we'd have one class per fill-strategy plus one for the pattern collection. But these fill strategies are only useful for the combo collection.
Without them (making the fill strategy the responsibility of the collection generator), we'd just have one combo-collection per strategy.

It is the only generator that wraps another generator. That is not something bad per se, but I dislike that the used single pattern generator is hard-coded and not configurable. The resulting combo generator is very specific (and with a very unspecific name). 

If people want to keep it, I would rather suggest to have a general, configurable collection generator that uses a pattern generator to generate a single pattern (doesn't need to be large, could be configurable) and "fills" the remaining collection size limit with singleton patterns (also for that there could be different strategies).

I see some point in having this generator: the other generators focus more on having several smaller patterns of roughly equal size, while this one tries to get one PDB as large as possible. Depending on what the patterns are used for, I see both being an advantage. I also do not see what we gain by removing it.

I suggest to remove the combo pattern collection generator. If someone objects, please speak up within the next two days.