Venue: ICAPS 2020 Workshop HSDIP

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The submission presents an extension of the subset-saturated cost partitioning framework for optimal classical planning. This extension considers transition- instead of operator- cost functions, very much in the same way as (Keller et al. 2016a) does for the standard saturated cost partitioning variant. The authors present an empirical evaluation of the technique that shows that while the obtained heuristics are more informed than their *operator* counterpart, overall the technique does not pay off.

The submission clearly fits the scope of the workshop, and while it reads a bit incremental, I think it can make up for an interesting presentation and discussion. I also think the background and definition sections are too lengthy, especially when compared to the experiments section, and taking into account that many definitions are straight-forward adaptations of their operator equivalents. I would suggest the authors could focus more on highlighting the differences with the latter. I definitely missed a bit more detail and analysis in the experiments section (which are by the way the benchmarks being used? ). Besides the overall conclusion on wheter the technique pays off overall or not, it would be great if the experiments could teach us something and illustrate in what kind of domains it works better/worse, and why that is the case.
review_title: Good paper, topic fits workshop, but experimental section could be improved

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper merges the existing approaches of subset-saturated cost partitioning
(where only a subset of all states keeps its heuristic value) with saturated
transition cost partitioning (where different transitions with the same
operator label can have different costs). The experimental evaluation shows
that while this approach generally results in better informed heuristics it
does not outperform existing approaches due to the significant computation
overhead caused by the exponential explosion from moving from operator to
transition cost functions.

The topic fits very well in this workshop and I find the approach and its
results interesting, however I would have wished for some more depth especially
in the experimental analysis. It highlights the tradeoff between expansions and
overall time between the best performing subset-saturated *operator* cost
partitioning and subset-saturated *transition* cost partitioning, but a more
general comparison of all tested configurations in terms of coverage is
missing. I would also be interested in how *subset*-saturated transition cost
partitioning compares to saturated transition cost partitioning, since both
share the problem of needing to represent large transition cost functions.

In the theoretical part I'm missing a coherent narrative; there are many
definitions, many of them are similar since they are generalizations of others,
but there is not really a thread tying them all together. I would significantly
shorten the background section (which is over 3 pages long) and focus more on
your generalized definitions, explaining the differences to existing definitions
without writing them down as well. For example, Definition 15 and 17 are very
similar, the major difference being that Definition 17 talks about transitions
rather than operators. I would only include Definition 17 and (shortly) discuss
that this Definition is similar to the one for subset-saturated *operator* cost
partitioning except for ..., and whether or not these changes introduce any
problems we need to be aware of (which I think is never the case?). Similarly,
many definitions in the background itself are redundant, for example Definition
10 (Transition Cost Partitioning) and 12 (Operator cost partitioning).

The description of the transition saturators on the other hand is somewhat
short, especially for the saturator you newly introduce. I would put more focus
on this saturator (since the others are fairly straightforward generalizations
of existing operator saturators) and explain in more detail how it works. For
example, I don't understand what you mean with setting the remaining smallest
cost of 0 to the abstract transition. Does that mean you set the cost to 0? Is
that safe (i.e. won't you introduce shortcuts this way)?

Overall I find the topic interesting but I do think the presentation of the
paper could be improved significantly, the description of the new transition
saturator needs to be improved, and the experimental evaluation should be more
extensively discussed, especially the comparison to saturated transition cost
partitioning.


Questions to the authors:
 1) Could you give a more in-depth explanation of the spd saturator?
 2) You say you always apply spd first. Does this mean that for example all_t
 is actually spd_t,all_t?
 3) Can you elaborate on the overall experimental results, specifically the
 comparison with saturated transition cost partitioning?
 

Minor comments
 - Cost Partitioning (and all its variations) -> cost partitioning
 - Classical Planning -> classical planning
 - Introduction: "Seipp and Helmert showed that ... (Seipp, Keller and
 Helmert)" Why do you cite two papers here? I don't understand if both papers
 showed the same thing (then why not cite both the same way?), or, if not, what
 the second citation is for.
 - Introduction: You say that unlike previous approaches your approach does not
 leave any costs unused. But you don't back that claim anywhere in the
 theoretical part.
 - Definition 2: "The length of \pi denoted by |\pi|, is n" -> \pi, denoted by
 (missing comma)
 - Definition 2: "\pi is called a goal path, if" --> goal path if (remove comma)
 - Planning tasks: "The set of operators induce a" ... --> induce*s* a
 - Planning tasks: "A finite set of operators (or actions) O where..." -> The
 main sentence is unfinished.
 - Abstractions: "every goal path in the abstract transition system corresponds
 to a goal path in the concrete transition system" -> this should be the other
 way around.
 - Abstractions: I don't understand the purpose of the last paragraph. You use
 A* with admissible heuristics within the abstraction? If not, why is this
 sentence there?
 - Definition 15 + 17: o/tcf_i = saturate_i(...), not saturate_{i-1}
 - The description of how the heuristic order is optimized is very unhelpful,
 it is not explained what h/stolen means and I don't understand how it can be
 optimized independent of the used transition saturator
 - Page 8: try to avoid a paragraph break after a single word
 - References: What is "2014. IPC-8 planner abstracts."? Is this used anywhere?
 - References: Keller et al. 2016a and Keller et al. 2016b are the same paper.
 - References: Kissmann and Edelkamp 2014: IPC in title not capitalized


review_title: Review

Decision: Accept