One case where this can happen with the current code is if we do
bisimulation-based shrinking and group by h, and the number of different h
values is larger than the target size. In this case the initialization of the
bisimulation already creates too many abstract states.

For now, the assertion has been commented out, since it's not clear what the
best strategy is:
- shrink if we have too many different h values, making the shrink
non-h-preserving, or
- live with the fact that the target bound isn't respected in this case

ParcPrinter is a good domain to test this because it has such large action costs
and hence so many different h values.

Added Raz to the nosy list.

Raz: Moritz is currently refactoring the m&s code. If you're working on a bugfix
for this and/or the other bug we discussed, it may be hard to merge them with
his refactoring unless they are only small changes. (Just a warning so that
you're aware of each other's efforts.)

Makes sense. It also makes sense that this would show up primarily in
ParcPrinter, since this has solution costs in the range of millions while other
domains are almost always below 1000.

I think that the natural generalization of DFP to the case where there are M
distinct h values and N < M abstract states is to allocate N - 1 abstract states
to the lowest N - 1 h values and throw all the larger ones into a single
abstract state.

If it helps avoid code duplication (not sure if it does), the existing
bucket-based shrinking code could be used for that if we have one that considers
only the h value, not the f value. (I thought he had one like this, but now I
can't find it any more.)

The following will produce an assertion fail:
$ ./translate/translate.py ../benchmarks/parcprinter-08-strips/p27.pddl
$ ./preprocess/preprocess < output.sas
$ ./search/downward-1-debug --search
'astar(mas(max_states=200000,merge_strategy=5,shrink_strategy=SHRINK_DFP_ENABLE_GREEDY_BISIMULATION))'
< output
[...]
next variable: #64
shrink by 183334 nodes (from 200000 to 16666)
Size of collapsed groups =25524
Simplification was not f-preserving -- must recompute distances.
size of abstraction after shrink: 25524, Threshold: 16666
downward-1-debug: raz_abstraction.cc:1993: void Abstraction::shrink(int,
ShrinkStrategy, bool): Assertion `size() <= threshold || threshold == 1' failed.
Peak memory: 521876 KB
caught signal 6 -- exiting


When not running in debug mode, a segfault will occur.


The reason for this failure:
See the first lines of the method
compute_abstraction_dfp_action_cost_support(...) in raz_abstraction.cc. 
num_groups is at least as big as num_used_h. But num_used_h may be greater than
the target size already. So especially if max_states is small, this
implementation will fail on many tasks.