> Thanks. I merged and send out an email to downward-dev. Should I also send the
> email to the general list?

I would suggest so.

Thanks. I merged and send out an email to downward-dev. Should I also send the
email to the general list?

Just out of curiosity I also ran some new combinations (canonical heuristic with
GA-patterns, 0-1-PDB heuristics with hillclimbing and systematic patterns, and
PhO with patterns from combo and GA methods):

http://ai.cs.unibas.ch/_tmp_files/pommeren/issue585-v3-new-configs.html

I am fine with the changes (see one comment at bitbucket) and the results, so
please go ahead and merge.

If you an Silvan are happy with it, please merge.

cpdbs(): Mostly no change but pegsol tasks below 1 second stick out.
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue585_astar_cpdbs_base_v3_total_time.png

cpdb(systematic): Majority of runs is faster, the ones that are slower are below
10%.
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue585_astar_cpdbs_systematic_base_v3_total_time.png

single pdb: some larger deviations up to 13%. 
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue585_astar_pdb_base_v3_total_time.png

pho(systematic): Most runs are actually faster, a few are slower usually below 5%.
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue585_astar_pho_systematic_base_v3_total_time.png

0-1-PDBs: some larger deviations up to 13%.
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue585_astar_zopdbs_base_v3_total_time.png

Full report:
http://ai.cs.unibas.ch/_tmp_files/pommeren/issues585_v3_rest_compareconfigsreport.html

Forgot to link the full report:

http://ai.cs.unibas.ch/_tmp_files/pommeren/issue585-v3-compareconfig.html

The new experiment showed some difference in the number of expansions. This only
happens in a few tasks and could be caused by the hillclimbing timeout.

Here are some plots to see the time difference in more detail:

http://ai.cs.unibas.ch/_tmp_files/pommeren/issue585_ipdb_base_v3_total_time.png
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue585_gapdb_base_v3_total_time.png

The issues with iPDB and the PhO constraints turned out to be unrelated. We had
three unrelated issues:

1) A bug in the canonical heuristic lead to ignoring dominance pruning. After
fixing this, the performance of new and old version is now closer together.
There still is a ~1% negative trend which could be because we now use shared
pointers to access the PDBs in each evaluation. I think we can live with that.

2) Dominance pruning was always enabled in the old iPDB code which also meant it
was enabled for PhO constraints when they used this generation method. Dominance
pruning is not a sound pruning technique for those constraints, so the pruning
made the heuristic less informed. On the other hand it made it faster because
dominance pruning often removes a significant amount of PDBs. The net effect was
that PhO constraints without dominance pruning (the new code) solved 4 tasks
less. However, I still suggest we don't implement the option because the concept
of dominance is not useful for PhO.

3) We always ordered lists of patterns in the new code. In the old code, we did
this sometimes but not always. This is problematic for 0-1-PDBs because they
depend on the order. We decided to drop the invariant that list of patterns must
be ordered (each pattern still must be ordered).

Change 3) lead to some changes in the class PatternCollectionInformation, which
could influence all experiments. I'm re-running the configs for iPDB and
GA-PDBs. If they look ok and Silvan is happy with my changes, I'll also re-run
the other configs to be sure.

Experiments look ok for most configs with two exceptions:

There still seems to be a bug in the hill climbing generator which makes it
slower than the original implementation. This shows more in iPDB than in the PhO
constraints (maybe because the evaluation of PhO constraints takes longer and
offsets this a bit).

The genetic algorithm also seems to be slower and in this case the number of
expansions increases, so it seems the generator no longer generates the same
pattern collection.

http://ai.cs.unibas.ch/_tmp_files/pommeren/issue585-compareconfigs.html

After we find the bug, I think we only need to look at the configs
astar_gapdb_{base,v1}, astar_pho_hillclimbing_{base,v1}, and
astar_ipdb_{base,v1} (no need to look at astar_ipdb_alias which behaves like
astar_ipdb_v1 as expected). All other configs are close enough to merge them in
my opinion.

All fine with me. :-)

Malte, we discussed the names today and ended up with the following typedefs:

class PatternDatabase;
using Pattern = std::vector<int>;
using PatternCollection = std::vector<Pattern>;
using PDBCollection = std::vector<std::shared_ptr<PatternDatabase>>;
using MaxAdditivePDBSubsets = std::vector<PDBCollection>;

class PatternCollectionInformation;

The class PatternCollectionInformation is new and contains everything we know
about a pattern collection (patterns, pdbs if we have them, maximal additive
subsets if we have them) and can compute missing information on demand. It
always contains at least a PatternCollection but may also contain a
PDBCollection and MaxAdditivePDBSubsets. It can share this information with
other classes by passing out shared pointers to these structures.

To avoid that Xs stands for vector<X> and vector<shared_ptr<X>>, we now use
Pattern/PatternCollection and PatternDatabase/PDBCollection. Its not a huge
difference to abbreviate PatternDatabase but we thought that it would at least
break the association a bit. We couldn't think of a good alternative to
"Collection". Do you have any better suggestions?

> It seems someone used a convention that includes the type name in each plugin
> for constraint generators. :-) 

Whoever that was, I'll happily refactor those as well :-)

I don't feel that strongly about this, but I have a slight preference for
shorter option strings.

> "users like that"

I meant "used", of course.

> using Patterns = std::vector<Pattern>;
> using PatternDatabases = std::vector<std::shared_ptr<PatternDatabase>>;

Isn't it a bit confusing that for X = Pattern, X + s means "vector of X", and
for X = PatternDatabase, X + s means "vector shared pointer to X"? If I just
read some code using

Patterns foo;
PatternDatabases bar;

this might trip me up somewhat.

> 4) Is "gapdb" also used like that in the literature?

Not sure what you mean with "users like that", but all current users most use
the "gapdb" syntax because it's the only way to access this functionality. I
know that Santiago Franco uses gapdb; don't know who else. We can of course
change command-line options. When non-esoteric options change in non-obvious
ways, perhaps we should send an email to the public Fast Downward list. This
could be part of a more general email explaining the overall change and the new
opportunities it affords. The list of old => new translations you give in your
comment might be useful for such an email.

> 5b) In this case, I would prefer to rename the classes, because
> "patterns=hillclimbing()" is much more explicit than "patterns=haslum()".

and shorter than the more correct
"patterns=haslum_botea_helmert_bonet_koenig()". ;-)

> 5d) I don't like to call generators "collection_X" because it makes the option
> strings longer and it does not carry much additional information. We also don't
> have this convention for other types, e.g., heuristics are not "heuristic_X".

It seems someone used a convention that includes the type name in each plugin
for constraint generators. :-) We also currently have a convention like this for
landmark graphs, merge strategies and shrink strategies. (I'm not arguing either
side here, just pointing out the status quo.)

1) I also thought of this alternative, but I thought that you might prefer
collection over appending an s. The potential problem we get when using
"Patterns" for vector<Pattern> is that we cannot use the plural any more if we
were to store a vector or set or anything containing Patterns, i.e.
vector<Patterns> patterns would look strange for me. When using collection, this
problem would not appear.

 What do you mean by "it makes sense to stick with one name"? If the majority
perfers to stick with PatternDatabase, I'm fine with that, but then I think that
it might be confusing to have other classes using PDBs as abbreviation, i.e.
CanonicalPDBs, CanonicalPDBsHeuristic, or IncrementalCanonical_PDBs, so we
should at least consider using PatternDatabase in these class names also. For
having shorter variables, I'm mostly fine with writing
"shared_ptr<PatternDatabase> pdb".

4) No, I think nobody ever used gapdb in any published work, at least that I
know of, so we can drop it.

5b) I already thought of it; maybe we could really rename it, if the others are
fine with that -- naming classes after people is a bit odd anyway. But maybe
this can happen at a later point in this issue?

5c) Good to know, and ok then for the shorter names.

5d) Ok.

6) I'd prefer a lot indeed, but maybe the others have different opinions on this
subject? I mainly think that if you need to know the object's type when using it
anyway, then there is no point of typing auto instead of the class's name,
especially if it is a reference to a (smart) pointer.

7) I'm also not convinced of my suggestions, but PatternCollection seems to be
the wrong name for that class, which actually *contains* a "pattern collection"
(to be named Patterns?), among others. Let's think about other names: the class
contains the result of the generators, so maybe GeneratedPatterns or
GeneratedPatternDatabases could be an option. On the other hand, the class
contains both, Patterns and PatternDatabases.

I'm not sure if these were just renames and not rather extracted from different
files and distributed over new files:
- pattern_generation_combo
- pattern_generation_manual
- pattern_generation_single_greedy
- pattern_generation_single_manual
- pattern_generation_combo
- pdb_max_cliques

Thanks for the review Silvan. I didn't read all the comments on Bitbucket yet,
I'll first answer the more general questions.

1) I would prefer to stick with the non-abbreviated name PatternDatabase over
the abbreviation PDB. It makes sense to stick with one name even if it makes
names longer. We'll have slightly shorter names, if we use the plural form "Xs"
instead of "XCollection". What do you think about this suggestion:

using Pattern = std::vector<int>;
using Patterns = std::vector<Pattern>;
class PatternDatabase;
using PatternDatabases = std::vector<std::shared_ptr<PatternDatabase>>;
using MaxPatternDatabaseCliques = std::vector<PatternDatabases>;

2) That wasn't intentional, I'll change it. Thanks.

3) The type occurs in seven other classes, so I think it is important enough to
have a typedef there. We can discuss about the name, but I think it should
convey that these objects are more than just lists of lists of PDBs. They also
are maximal additive subsets of some larger set. We wouldn't use the type if
that condition were not true (just as we don't use the type Pattern for any
vector<int>).

4) Is "gapdb" also used like that in the literature? I left out some other
plugins as well, that can now be expressed in other ways. I prefer to have only
a few aliases, because they all have to be maintained. But I can add the one for
gapdb back in if you think we need it. Here is the the current way of calling
everything:
     pdb()    --> pdb() defaults to pdb(pattern=greedy())
     cpdbs()  --> cpdbs() defaults to cpdbs(patterns=combo())
     zopdbs() --> zopdbs() defaults to zopdbs(patterns=combo())
     ipdb()   --> ipdb() is an alias for cpdbs(patterns=hillclimbing(),
dominance_pruning=true) 
     gapdb()  --> can be expressed as zopdbs(patterns=genetic())
     cpdbs_systematic()           --> can be expressed as
cpdbs(patterns=systematic())
     pho_constraints_manual()     --> can be expressed as
pho_constraints(patterns=manual())
     pho_constraints_systematic() --> can be expressed as
pho_constraints(patterns=systematic())
     pho_constraints_ipdb()       --> can be expressed as
pho_constraints(patterns=hillclimbing())

5a) Both names seem very long to type in an option string. I would prefer
something shorter. If you specify a list of patterns manually, the parser will
complain an tell you to specify a generator instead. 

5b) In this case, I would prefer to rename the classes, because
"patterns=hillclimbing()" is much more explicit than "patterns=haslum()".

5c) The option parser can handle this. If we try to parse a single pattern,
we'll only look at plugins for single pattern generators. So I prefer to keep
the names simple.

5d) I don't like to call generators "collection_X" because it makes the option
strings longer and it does not carry much additional information. We also don't
have this convention for other types, e.g., heuristics are not "heuristic_X".

6) I like the use of auto in for loops (I think it makes the code more
readable), but I see your point and can change it if you prefer.

7) I agree that PatternCollection is not an ideal name, but I'm also not
convinced of PatternGeneratorInterface (sounds like its the interface that
PatternGenerators must implement), or ExtractFromPatternGenerator (the class can
also be created and used outside of the generators). Maybe we can come up with a
better name?


If you want to look at the files that I renamed, I can prepare another pull
request against a dummy branch where I just copy the files. Can you tell me
which files you mean?

I am done with commenting at bibucket. For some of the files, mainly those new
ones where I expected that most of the code was copied with only minor changes
from existing one, but where there is no proper diff, I didn't carefully read
all lines of code.

Coming back to the names discussion, I'd suggest the following names:
- rename class PatternDatabase to class PDB
- call std::vector<Pattern> PatternCollection instead of Patterns
- call std::vector<PDBCollection> MaxCliquesPDBCollection instead of PDBCliques
- rename class PatternCollection (interface between factories and users) to
PatternGeneratorInterface, or ExtractFromPatternGenerator or anything along
those lines

Hmm, but we also call the classes "pattern_generation" and not
"pattern_generation_collection", so in this case we should probably leave manual
and haslum as they are, and just change greedy and (single) manual to
single_greedy and single_manual.

Addition to 5): maybe all collection generators should also have "collection" in
their plugin name, i.e. "collection_manual" etc.

I'll start with some general comments in the tracker before annotating the
"diff" at bitbucket, because this diff introduces so many new files that it
seems wrong to comment on some general things in a specific file. Furthermore,
these are mostly issues with names, and we probably want to discuss these here
anyway.

I think that the general setup of classes and responsibilities is very good!
However, for now, the code (diff) is very hard to read due to unclear names of
typedefs, classes and variables:

1) using Patterns = std::vector<Pattern>;  
   using PDBCollection = std::vector<std::shared_ptr<PatternDatabase>>;
I find it very confusing that a vector of Pattern is Patterns, but that a vector
of PDBs is PDBCollection. I think Patterns should be called PatternCollection (I
know that this conflicts the new bridge class between factories and users, but
this had the TODO: change name? anyways.) While at this, maybe we can get rid of
the difference of the class name PatternDatabase to its abbreviated name PDB.
Being strict, vector<shared_ptr<PatternDatabase>> should be
PatternDatabaseCollection, or PatternDatabase should be PDB.

2) Variable names. I assume that you did not rename many variables for a smaller
diff; but something like "std::unique_ptr<IncrementalCanonicalPDBs>
current_heuristic;" (in PatternGenerationHaslum) or
"std::shared_ptr<PDBCollection> pdbs;" (in PatternCollection) is hard to keep in
mind when looking at the implementation files. And in the long run, these should
be renamed anyway, so I suggest to do this already now. With so many similar
names (Pattern, PatternDatabase which we usually denote pdb, collections etc),
we should name variables always exactly like their class name/typedef, to avoid
confusion. I hope that I'll comment on all/most of such variable missnamings at
bitbucket next.

3) using PDBCliques = std::vector<PDBCollection>;
While I understand that we use a vector of PDBCollection as cliques for the
canonical heuristic, the typedef itself seems a bit odd: in many other places,
we would call vector<something> "somethings". Maybe this type is too specific to
be in a general file called types.h?

4) There still is a plugin "ipdb", which is good, given that this name is used
in the literature, but there is no more "gapdb" plugin, which should probably
just be a shorthand for zopdbs(patterns=genetic).

5) Option names: 
- patterns could be called pattern_generation_method or pattern_generator, to
make it more precise. "patterns" lets me think of specifying a list of patterns
manually.
- genetic and hillclimbing: if we like to have the convention that a
pattern_generation_x class provides the plugin x, then genetic should be
edelkamp and hillclimbing should be haslum.
- manual/greedy: for the single pattern variants, these should be called
single_manual/single_greedy, also to avoid name conflicts with the other
"manual" method (I don't know if the option parser is able to deduce the correct
class automatically, but I would expect that it is not?)

6) Usage of "auto": I am not sure if we converged towards a convention here, but
I think auto is mainly useful to avoid typing type::iterator or if there is a
deep nesting of vectors or other containers. I find it less useful or even
disturbing in regular for loops. Example:
    for (const auto &clique : *cliques) {
        for (const auto &pdb : clique) {
            Pattern pattern = pdb->get_pattern();
could be written as
    for (const PDBCollection &clique : *cliques) {
        for (shared_ptr<PatternDatabase> pdb : clique) {
            Pattern pattern = pdb->get_pattern();
This also makes the usage of "->" with pdb more plausible. With auto, you still
need to know the type of pdb to know that you should use "->", and then I think
typing the type out isn't really any extra work. (Sorry for posting code in
here, but I think that this is a rather general question, with several
occurrences in the pdbs code.)

I'll comment on more details at bitbucket next.

Adding myself here. Interestingly, even without being asked, I just got curious
about the state of this issue, because resolving it may help me a lot working
pattern collections and symmetries (where we do not necessarily need canonical
pdbs heuristics). I'll have a look at the pull request.

I am happy to have a brief look at this at some point, but the bulk of the
review should ideally be done by someone who can find time for this sooner than
me. Perhaps you can ask Silvan, who wrote most of the PDB code?

I started working on this and prepared a pull request on bitbucket:

https://bitbucket.org/flogo/downward-issues/pull-requests/6

The code introduces a lot of new classes but this helps to make the individual
classes less complex. Since it introduces a lot of changes in the PDB code, I
would like to merge this before there are too many conflicts, but I think if no
one currently plans to work on PDBs it can wait until after our next sprint.

I also reclassified this as a feature, because it would allow new combinations
(e.g., PhO constraints with GA patterns). 

Jendrik, I added you to the nosy list, because we already discussed the design
of some parts. If you're not interested, feel free to unsubscribe, of course.

One option is to have virtual methods in the pattern generation methods (which I
assume we will implement as a kind of factory object) like
"get_optional_additivity_information()" (name only meant as an illustration)
that can return additional relevant information like this if it is available, or
a special value to indicate that the heuristic needs to compute the information
itself if it needs it.

Not the most sophisticated interface, but let's not complicate things too much
at this stage.

> Do we intend to keep this arrangement?
I planned to do so, yes. Mainly because I can't think of a good alternative to
this incremental creation of the Canonical PDB. As you suggested, I also thought
about factoring out some part of the logic but none of my ideas helped with the
main problem.

> introducing an intermediate class which is not quite the heuristic but
> contains the main logic
Sounds good.

> If PatternGenerationHaslum will keep containing a CanonicalPDBsHeuristic or
> something similar, then it would be wasteful to compute all the information
> about addivitity during pattern selection, discard it, then recompute it when
> constructing the final heuristics object. Is that the issue?
Yes, exactly.

Let me ask some questions to make sure we are on the same page.
PatternGenerationHaslum currently owns a CanonicalPDBsHeuristic because the
pattern generation procedure is a form of boot-strapping, where the previous
iteration of the canonical heuristic informs the development of the next
iteration. Do we intend to keep this arrangement?

The arrangement still makes sense to me. We might want to make small changes
there to avoid the problems we get with statistics, evaluation contexts etc.
when using full-blown heuristic objects internally, e.g. by introducing an
intermediate class which is not quite the heuristic but contains the main logic
the heuristic uses (similarly to how we now introduce "FactoredTransitionSystem"
as an intermediary between MergeAndShrinkHeuristic and TransitionSystem). But
that's more of a detail.

If PatternGenerationHaslum will keep containing a CanonicalPDBsHeuristic or
something similar, then it would be wasteful to compute all the information
about addivitity during pattern selection, discard it, then recompute it when
constructing the final heuristics object. Is that the issue?

I had a look at the code today. It seems the main question is how to handle the
additional information computed by the canonical heuristic during the iPDB
hillclimbing. The field size can be easily recomputed once we get the PDBs, but
max_cliques and are_additive are also needed during the construction. If the
pattern generation method only outputs PDBs, then this effort has to be duplicated.

We want to refactor the pattern generation methods so the discovered patterns
can be used in different scenarios. For example, we want to use patterns
discovered by iPDB in posthoc optimization constraints.