Venue: ICAPS 2019 Workshop HSDIP

Reviews:

final_score: rating: 10: Top 5% of accepted papers, seminal paper
review_content: Brief summary of the paper:
This work discusses the transformation of planning tasks based on a finite domain representation (FDR) into tasks based on factored state transition systems (FTS). The transformation is based on the Merge&Shrink framework, which consists of various abstraction-based techniques commonly used to compute abstraction heuristics. The key idea of this work is to transform the original task via a sequence of task transformations and to provide a reconstruction procedure which allows to use a plan from the transformed task to compute a plan for the original task. The paper discusses how to perform search on these FTS-based tasks and also provides an adaptation of the FF heuristic. Additionally,  previous FDR task reformulations are put into context and it is formally shown that these are dominated by the FTS reformulations presented here. The paper concludes with a comprehensive empirical evaluation, which uncovers advantages and disadvantages of different types of task reformulations.

Brief summary of the review:
This paper was a pleasure to read. The quality of the work is very high and suitable to be presented at a top AI conference. It is written fluently, the formal presentation is concise and clear, and simple examples guide the reader through the definitions. Moreover, the framework generalizes multiple previously introduced planning task reformulations, and FTS-based planning tasks warrant a deeper look into heuristic search performed on such tasks, therefore this work fits perfectly into the scope of the workshop.

Detailed review:
The paper is very dense, yet it manages to cite relevant related work. One can note though, that while the introduction mentions that reformulations are a common tool to reduce the accidental complexity of a planning task, this is never discussed again later on. I wonder how the presented reformulation methods impact the accidental complexity.

The presentation of FDR/FDS representations, the M&S framework and the various transformations is concise, clear, formally correct, and easy to follow. The plan reconstruction is a bit harder to follow, although being familiar with cascading tables helps here. The example really helps to completely grasp the reconstruction process. What I find a bit odd is that the paper mentions that it avoids pruning-based reformulations because of the overhead, yet Proposition 1 includes pruning-based reformulations. Since the proof considers the previously shown plan reconstruction process I wonder if Proposition 1 really should include pruning (I do not necessarily think it is wrong, as I guess the overhead for pruning does not really affect the poly-time property). I would also have expected a part of the empirical evaluation to discuss this overhead, yet it is not mentioned anywhere. I think the paper would benefit from one or two more sentences in how much overhead one can expect when using pruning (maybe the overhead warrants the pruning power?).

The relation to other FDR reformulation methods is also clearly written and interesting to follow, although one could argue that 'dominating' is not necessarily the most fitting description for a method which can perform the same formulations (why not require the dominating method to provide additional reformulations, both, shrinking and label reduction, would still dominate in this case, no?).

The evaluation is also very comprehensive (it evaluates the different techniques over *all* planning tasks of the previous IPCs) and provides interesting insights. While it mostly covers the results over all domains, I think an analysis on the effect of the different transformations on particular domains could be interesting. While this is partially hinted to in the conclusion, the paper could benefit from a short discussion on which types of transformation might be particular useful (or harmful) in what type of domain.

Minor comments:

Plan reconstruction:
- 'On the final task, we can run any planning algorithm on /Pi_n [...] to find a plan [...] for /Pi_n'. Since the final task is /Pi_n this sentence mentions three times the same task.

Reconstruction of MLB Reformulations:
- /lambda(l) is not defined before or later on. (I suspect /lambda was renamed to f^L?)
- Example: 'keeping track of one of the factored state that corresponds' => one of the factored states

- /tau-label reconstrunction:
 - "to some in \Pi_i" => to some TS in \Pi_i
 - you use /alpha for the weak bisimulation of /Theta, but before /alpha was usually used as the abstraction function for states, and not transition systems. 

- Proof of Prop 2: why can computing the coarses weak bisimulation of a TS be done in poly time?
- Def. 4: I suggest to use two different naming/font schemes to differentiate between the reformulation methods of FTS and FDR tasks.
- Figure 2: The figure could explicitly say which plot refers to weak bisimulation shrinking.
- Discussion of Fig. 3:
 - 'This plots' => This plot
 - 'Tt is also remarkable the large amount of instances' => grammar
 - '(there is no expansions until last jump)': first I wanted to mention grammar, but then I remembered that this is one of the search properties for FD benchmarks. I suspect this confuses more people than it helps people familiar with FD benchmarks, so I would suggest to just remove this remark.
 



review_title: This paper was a pleasure to read

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper revisits the idea of applying a suite of automatic simplification techniques to a planning problem in advance of solving it, with the difference that simplifications are applied to the internal factored transition system representation instead of the original modelling formalism, such as STRIPS or FDR. This is claimed to have some advantage in that the representation allows for conditional effects and certain forms of disjunctions, which allows the result of certain additional simplifications to be expressed. On the downside, the authors need to recreate the planning machinery to operate on this representation, which at current is less efficient than the well-developed planner implementation in fast downward that operates on the FDR representation.

In Section "Reconstruction of MLB Reformulations", on page 4: At the beginning of the section, the label-abstracting function is falled f^L, but later in the section it seems to change name to \lambda. Is this a typo, or is \lambda a different function? If so, what is it?

Binary variables example later in the same section: The authors claim that "...applying bisimulation shrinking, the resulting TS has still only 2 states: one where both counters are set to 1 and another where at least one counter must still be set." I don't see how this can be a bisimulation. It would mean that (0,0) ~ (0,1) ~ (1,0), but applying the action that sets the first variable in (0,0) leads to (1,0) while applying it in state (0,1) leads to (1,1), which with bisimilarity should imply that (1,0) ~ (1,1), which contradicts the first condition of bisimilarity since (1,1) is a goal state and (1,0) is not.

Perhaps the authors meant applying *weak* bisimilarity? But in that case, which are the internal labels?

In Figure 2, what is the difference between the plots in the top row and the plots in the bottom row? The labels or caption does not say anything.

In the section on search space reduction, the authors mention a number of domains that are completely solved by simplification. This was also observed in the original paper. Does the generalization of the simplifications proposed here result in any new domain being fully solved, that was not with the previous versions of the same techniques, or any individual task within a not fully solved domain?

review_title: dense read - moderate novelty - weak accept

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).
Best regards
HSDIP organizers
confidence: 5: absolutely certain
Decision: Accept