Venue: ICAPS 2020 Workshop HSDIP

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper describes and evaluates on a standard benchmark set neural-network
heuristic functions learned from samples obtain by backward search.

It is an interesting paper showing that even a very simple type of neural
networks can learn useful heuristic function if it is fed with a suitable data.
In this case the data was obtained by two variants of backward search and it
seems to me that the generation of (full) states in a backward search was the
main difficulty the authors had to deal with.

In my opinion, the paper probably warrants publication on the workshop, but I
I have some reservations about the paper:
1. Regarding the presentation: The authors use two variants of a problem
representation, STRIPS and FDR, which, sometimes, makes the presentation
confusing. For example in Section 4.2, the paragraph "Regression" starts with
saying that "modified SAS+ representation" used by Alcazar et al. (2013) is
used here and then follows a desription using a STRIPS action. First, this way
you introduce another formalism, because Alcazar et al. is using SAS+
formalism with preconditions, effects, and *prevail conditions* which is the
main difference to FDR. Second, if you choose to describe the conditions with
STRIPS actions, why do you need to talk about another formalism?

My suggestion would be to use only one formalism (in this case FDR would be
the better choice, because you use variable encoding for the neural network),
and reformulate the whole paper in this formalism (which is certainly
possible). It could help if you define a set of facts in FDR as a set of all
variable-value pairs, e.g., F = {(V,v) | V \in Vars, v \in Dom(V)}, and allow
interpretation of preconditions and effects as sets of facts.

2. Regarding the method: If I understood correctly, in the "regression"
variant, you treat the undefined variables as if none of the facts from the
corresponding variable is set, which seems to me incorrect (although it seems
that it works well in the experiments), because undefined variable means that
there can be any value of the variable (or one can use mutexes to infer which
of the facts can be in a reachable state). Can you explain why did you choose
to interpret it this way? It is not clear to me from the text.


Minor issues:
First page, last paragraph: missing parenthesis after "by Geissmann (2015",
and extra comma after h_{nn}.

Section 3, second paragraph "Ferber et" -> "Ferber et al."

Section 5, the item starting with "blocks: " -- invalid citation

It seems there is a missing space after every subscript all over the text
(like after h_nn, h_ff and so on).
review_title: Interesting paper, but needs some work on the presentation

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
== SUMMARY ==

The authors proposed a new method to learn heuristics for a single planning instance which builds upon LHCFP (Geissmann 2015) and other recent developments in learning and planning. Their network input is the state represented either in SAS or STRIPS encoding. Training states are generated by explicit backwards search or regression using Random Walks or a hill climbing approach. They train very small networks which quickly predict heuristic values. In general, they evaluate their method on the IPC tasks with a time limit of 30 minutes for training and search. Thus,  the training time has pay off already on the first search. They show that they produce results competitive to hFF and hLM.


== FEEDBACK ===

I think the authors propose interesting an promising modifications for LHCFP. Experimenting with explicit search from some goal state and regression and using hill climbing are interesting ideas. I was especially impressed how fast the small networks evaluate (and that they are quicker than hFF). At the moment they do not outperform hFF and hLM on all IPC domains, but they show already promising results on some domains. 

We already assumed that the Boolean representation performs better than a plain SAS representation, because the SAS representation somehow randomly groups facts into variables (depending on the mutex groups in a task, different assignments from facts to variables are possible) and the plain SAS representation implies a wrong numeric dependency between the facts of the same variable. It is good to see that someone evaluated this.

After reading the paper, an important question is for me, what is your forward heuristic? It sounds like some standard heuristic to guide your hill climbing, but you state you do not need standard heuristics. And if it is a standard heuristic, which one have you chosen? The choice of such a heuristic could have a huge impact on how far the hill-climbing gets away from the goal.

I want to point out that the inverse actions are a hack for your explicit search. A fact in the delete list of an action does not need to be present in the state on which the action is applied. A fact present in the add list of an action does not need to be missing the the starting state. The inverse action might still be a good hack, but I kindly ask you to add this information.

Figure 4 looks very nice, but cannot show what you want to show us. Especially, you state that it shows the high accuracy of SING for state with heuristic values smaller than 30. I cannot verify this, because the data points are over-painted by the data points of the other algorithms. After a few data points have been plotted on the same (or overlapping) locations, the color intensity does not change anymore and we cannot see if there are 5 or 100 data points with a deviation of 20. Furthermore, if we have multiple different algorithms (like here), the data points of the later plotted algorithms hide the data points of the earlier algorithms. Shifting the dots plotted for each algorithm by a small value, is not a solution. It does not solve the first problem, that we do not know how many data points are at a single location. 
A possible solution is to use boxplots. For every distance (or for binned distances) and every algorithm add a boxplot. Every algorithm gets boxplots in a different color (e.g. SING is blue) and the boxplots of the n-th algorithm is slightly shifted on the x axis by n * x, such that they can never hide each other.

From my background the paper is easy to comprehend, but contains too many writing errors. Typos in general, typos in references, many inline citations contain typos (e.g. 'Geissmann (2015', missing '.', missing year, missing 'et al.'). Furthermore, the paper does not use the AAAI20 style (see section titles and citation style).


Overall I think the paper makes an interesting contribution, with promising results and I would like to accept it and to discuss it during the workshop. Sadly the submitted paper is very poorly written. Especially the inline citations contain a lot of errors. It is so poorly written (see == Typos and Style and Citations (!) ==) that I cannot convince myself to accept it.





== QUESTION ==
- page 3: You state that SING expands the goal to state by randomly assigning values to the unassigned variables. The Fast Downward translator might have detected many mutex groups and used only a subset of them as SAS+ variables (because they overlap). The unused mutex groups are still available in Fast Downward. Does your goal extension also takes those into consideration?
- page 4/8: You state that you do not need a standard heuristic for training data generation. But you use a forward heuristic in the data generation. What is this heuristic?
- page 7: What do you mean by "with less training samples of 100k"?
- page 7, table 3: Some IPC benchmarks have multiple different versions (e.g. transport exists for optimal and satisficing planning and for different years). Which versions have you used for those benchmarks with multiple versions?



== MINOR ISSUES ==
- figure 1-3: In the plots you use "lmc"/"SING" instead of "hLM"/"hNN". Please make this consistent.
- figure 1-3: 
	- The left column is not aligned with the right column
	- The title is redundant and too long. For the left column use just "expansions" and for the right one "search time". The domains are known from the caption of the figure, the heuristics are known from the labels of the axis.
	- Remove the "(solved .../wins...)" from the labels of the axis. This makes labels unnecessary complicated. Why can we remove "solved"? We see how many data points are on the unsolved lines of the plots. Why can we removed the "wins"? The wins just counts who is faster, but we see this already in the plot. Furthermore, the plot shows whether the wins are by a small or large fraction.
	- The caption states that we compare "run-time", the subplot title says "search time". Chose one and be consistent.


== Typos and Style and Citations (!) ==

- frequently: every 'hff', 'hlm' occurrence is missing a white space afterwards. I guess you use a command like \hff. Then you have to write \hff{} otherwise, the blank after the command is swallowed.
- frequently: missing '.' after 'et al'
- frequently: missing year after inline citation.
- page 1: "a instance-specific" -> "an instance-specific"
- page 1: "by Geissmann (2015" -> "by Geissmann (2015)"
	(I use the following command for inline citations: \newcommand{\inlinecite}[1]{\citeauthor{#1} \shortcite{#1}})
- page 2: "share a single share space" -> "share a single state space"
- page 2: "with hff and hlm". hff and hlm are not defined. Please define them the first time you use them. State their full name and citation. You use them frequently, but just define them at the end.
- page 2: "Applying a in s, s transitions to [...]" -> "After applying [...]"
- page 2: "a 5-tuple, $\PI = \langle V, O, I, G, \rangle". Either you are missing your fifth item (after the "G,") or it is a 4-tuple.
- page 2: "Ferber et investigated" -> "Ferber, Helmert, and Hoffmann (2020) ..." or "Ferber et al. (2020) ...". Use command for inline citation let it automatically use the right format.
- page 2: "using a heuristic as h ff" -> "using a heuristic as h_{ff}"
- page 2: "Arfaee et al and" -> "Arfaee et al. (YEAR)"
- page 2: "and Lelis evaluated" -> "Lelis et al. (YEAR)"
- page 3: "Although regression is useful perform backward search, [...]" -> This sentence is strange. Please reformulate.
- page 3: "Fast-Downward" -> "Fast Downward" (it is two words without a hyphen)
- page 4: "We identify var.-value pairs" -> "We identify variable-value pairs" 
- page 5: "[Hoffmann, ]" -> defect citation. Missing year (same in the reference at the end)
- page 6: "from IPC" -> "from the IPC."
- page 6, table 2: The table is fine. I think it might look better, if you use instead of vertical (|) bars a little bit of space to separate the blocks (add an additional 'p{Xcm}' column), use '\cmidrule{x-y} to add horizontal lines spanning the different blocks (i.e. one line spanning hnn -> hlm for coverage, one for median # expansions, ...).
- page 7: "Ferber et al compute" -> "Ferber et al. (2020)"
- page 7: "investigated by Ferber et al (2020)" -> "Ferber et al. (2020)"
- page 7, Table 3: Use either "hlm" or "lmc". Make this consistent.
- page 7: "Shen et al (2020)" -> "Shen et al. (2020)"
- page 8: "[Fern, Yoon, and Givan, 2004]]" -> "[Fern, Yoon, and Givan, 2004]"
- page 9: "functions inclassical planning" -> "functions in classical planning"
- page 9: "[Hoffmann, ]" -> ?
- page 9: "Ff domain collection" -> "FF domain collection"

review_title: Interesting approach, but carelessly written

Decision: Accept