Venue: ICAPS 2019 Workshop HSDIP

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The presented paper introduces an extension to existing pattern 
generation algorithms for PDB heuristics. The work is fairly 
incremental, mostly turning screws in a large space of existing 
methods and combining them in new ways. Also, it does not become very 
clear what the concrete contribution of this paper is. How does it 
differ from existing methods, such as those presented in "On Creating 
Complementary Pattern Databases" by Franco et al. (2017)? I guess a 
separate related work section could help a lot in clarifying the 
difference to existing methods and the contribution of this work.

The way the paper is currently written, by interleaving background on
existing methods (which btw. makes more than half of the paper), with
remarks about which ingredients of these methods are used in the 
presented approach with or without modifications, makes it hard to
follow. More generally, the write-up is not very good and could be
significantly improved. 

Also, at least in the presentation, the suggested changes are not very 
systematic, there is no consistent thread. Rather, I have the 
impression that various existing methods are combined to somehow 
achieve higher total coverage.

Still, the experimental evaluation is not very convincing. When 
choosing the right benchmark set (IPC'18), the new method slightly 
outperforms the shown existing methods (including Complementary2). 
When adding the IPC'11+14 benchmarks, Complementary2 is slightly 
ahead. What happens when using all IPC benchmarks ('98-18)?

Nevertheless, I think the topic of the paper is interesting for the
HSDIP audience and the presented ideas might foster interesting
discussions, since automatic pattern generation for PDB heuristics
seems to be a hot topic these day.

If the paper gets accepted, I urge the authors to work on the write-up
and introduce a separate related work section.



Minor comments:
- abstract: "...which*,* if expressed symbolically*,*..."
- next sentence: "in the automatic* generation"
- please remove the copyright statements from the first page.
- Def.1: s_o*and*s_*
- Def.1: the sets {\cal A} and {\cal A}^+ are not defined
- figure 1 floats into the margin
- "Franco et al... shows that ... (Franco etal)." remove one of the 
cites.
- end of paragraph below Def.4: "symbolic symbolic"
- "contribute to more that on*ce*"
- "the correlation between the cross product [..] is rather weak."
I agree that it is weaker than for explicit representations, but still
"rather weak" is not a good description.
- the cite of FD "[Helmert, 2006]" has a different format than the 
other cites
- the style of writing is sometimes very informal, e.g.
"Baeckstroem prefers the SAS+ formalism", or "in the most prestigious
and attended [..] track"
- for consistency, please put the caption of table 2 below the table
- the bibliography does not seem to be in AAAI style
- the references Edelkamp 2002a and b refer to the same paper, same
for Holte and Hernadvoelgyi.
- there is a typo in the reference to Preditis 1993 *heuristics*
review_title: Interesting topic, but presentation is poor. Incremental work where exact contribution is not very clear.

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper certainly addresses an interesting research question and I think trying to understand what made the Complementary planners work well in IPC 2018 is a worthwhile endeavor. Unfortunately, I don't think the paper in its current form takes us closer to this goal. The paper presents two algorithms but many details are left out. This makes it impossible to understand how the algorithms work and how they differ from previous work. Furthermore, the experiment section is missing many essential comparisons, making it impossible to judge how the algorithms compare to previous work.

Introduction:
* Each concrete plan has an abstract counterpart in an induced abstraction of the same length, not "a shorter one".
* The meaning of a pattern in the sliding-tile puzzle depends on the representation. It can be a set of tiles or a set of positions.

Background:
* No need to introduce STRIPS, PDDL and PSVN. It doesn't seem you're using these later in the paper.
* Definition 1: there's no definition for \phi, \mathcal{A}, and the concept of plans.
* "The set of reachable states is generated on-the-fly" -> it is defined declaratively
* You describe "spurious states" in the background section, but never evaluate their impact or describe how you deal with them.
* I think "unreachable states" would be a better name than "spurious states" if that is indeed what you mean.

Pattern Databases:
* The codomain of heuristics should include \infty.
* "the sum of heuristic values obtained via projection to a disjoint variable set is admissible"
  -> This is only true if no two operators affect the same variable.
* "The projection of state variables induces a projection of operators and requires 0/1 cost partitioning"
  -> No, any cost partitioning algorithm can be used. Or you can maximize over the estimates instead of summing them.
* Definition 5: "maximize the average heuristic [value]"
  -> why not the heuristic value of the initial state or a set of samples? I think this needs some motivation.

Pattern Selection and Cost Partitioning:
* "SCP relies on only using those costs which each heuristic uses to create an abstract plan."
  -> This sounds misleading: SCP preserves *all* heuristic estimates under the given cost function.
* "[SCP] is time consuming compared to other cost partitioning methods (Pommerening, Helmert, and Bonet 2017)"
  -> the reference does not mention SCP. Seipp, Keller, Helmert (ICAPS 2017) state
  "[SCP] can be computed at negligible overhead during the construction of the heuristic"

Greedy Selection:
* The way I understand it, Gamer uses *steepest-ascent* hill climbing and Gamer-style uses *simple* hill climbing. If that's the case, I think using these terms might clarify the presentation.

BP-PDB:
* "Even though reducing the number of PDBs used to group all possible variables does not guarantee a better PDB, by having a smaller PDB collections, it is less likely to miss interactions between variables due to them being placed on different PDBs."
  -> This suggests trying to base the pattern generation on the variable interactions and not on their domain sizes as bin packing does.
* "the method will start generating pattern collections stochastically"
  -> How?
* "We then decide whether to add a pattern collection to the list of selected patterns if it is estimated that adding such PDB will speed up search."
  -> How?
* "To evaluate the fitness function"
  -> Which fitness function?

GreedyPDB:
* The limits of 50s and 75s for bin packing seem very large, given that most tasks have less than 1000 variables and the greedy bin packing algorithms FFI and FFD should run very fast.
* The first sentence of the last paragraph in this section appears twice in the paper.
* I guess some variable names are wrong in Algorithm 1?: SelPDBs vs. P_sel and SizeLim vs. Size
* Why do you iteratively increase the size limit in the PACKER function? I thought either the variables fit or they don't.
* How does Generate_P work?
* How exactly does GreedyPDB differ from Complementary 1 and 2?

Experiments:
* Figure 2 should probably use a histogram or similar instead of a line plot.
* Which time and memory limits do you use?
* Tables 1 and 2 are superfluous since they are subsumed in Table 3.
* I don't think there's an advantage in knowing the coverage score of an oracle planner.
* What is "advanced" bin packing?
* The paper states that GreedyPDB is a "new state-of-the-art in cost-optimal planning". However, Table 3 shows that Complementary 2 solves more tasks than GreedyPDB in 14 domains, while the opposite is true in only 6 domains.
* How do the parameters of GreedyPDB influence the resulting heuristic?
* I think the experiments focus too much on comparing whole planners and too little on comparing pattern selection algorithms.
* Keeping all other parts of the planner the same, the paper should compare different approaches for selecting patterns. Table 3 goes into the right direction by evaluating the three Greedy PDB variants, but this comparison only includes new pattern selection algorithms. The comparison should also include the following pattern selection algorithms:
  * the algorithms used in BP-PDB and Complementary 1 and 2
  * the Gamer pattern selection (without it, we cannot judge whether "Gamer-style" has any merit)
  * the hill climbing pattern generator (Haslum et al., AAAI 2007)
  * the systematic pattern generation methods of patterns up to size 2 and 3 (Pommerening et al., IJCAI 2013), which have been shown to yield very strong heuristics.

References:
* Some of the references for Stefan Edelkamp are missing a venue.

Style:
* Horizontal and vertical lines in tables only help if not all cells are fully surrounded by lines. One line below the header should be sufficient.
* Your inline citation macro seems to put extra whitespace between the authors and the year.
* No need to abbreviate domain names in Table 3, there's enough space.
* The paper has numerous typos. I recommend having it proof-read.

Reproducibility:
* BP-PDB only has a very high-level description and the pseudo-code for GreedyPDB is also missing some crucial details (e.g., EM algorithm). The paper does not promise to make any code or results available. Therefore, it won't be possible to replicate the results or build on them in future work.

review_title: The paper evaluates two methods for generating patterns for symbolic pattern databases but omits many crucial details and comparisons.

Meta-review: metareview: Dear Authors,
thank you very much for your submission. We are happy to inform you that
we have decided to accept it and we look forward to your talk in the workshop.
Please, go over the feedback in the reviews and correct or update your papers
in time for the camera ready date (May 24). In particular, please address the
comments raised by both reviewers regarding clarity, discussion of related work,
and additional experimental results, by making use of the additional space (9 pages) 
allowed by HSDIP.
Best regards
HSDIP organizers
confidence: 5: absolutely certain
Decision: Accept