Venue: ICAPS 2020 Workshop HSDIP

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 

Saturated cost partioning methods are one of the strongest heuristics for cost-optimal
planning in terms of coverage. However, they depend on an offline precomputation with a
fixed time limit, which is detrimental in terms of solving time, specially for easy
planning task. This paper addresses this limitation by considering approaches that compute
the saturated cost partitioning during the search.

The approach is simple but effective, showing that one can achieve the same performance in
terms of total coverage, and address the limitation in terms of total time.

My main criticism against the paper is that the analysis stops there, without analyzing
more deeply the differences between offline and online methods. I think the paper would
benefit from discussing some of the following points (by doing a long submission):


1) The state of the art in heuristics based on saturated cost-partitioning uses the PDB
selection based on the saturated cost partitioning itself:
Jendrik Seipp: Pattern Selection for Optimal Classical Planning with Saturated Cost Partitioning. IJCAI 2019: 5621-5627

Here, all the evaluation assumes a different set of abstractions. Arguably, this is
because making an online variant of the IJCAI'19 pattern selectioon is harder since one
should also add new abstractions to the collection in an online manner.

How far are the results of the proposed heuristics of IJCAI'19?  Is it possible to perform
the pattern selection in an online fasion too?

2) Comparing Algorithms 2 and 3, one can see that the offline and online methods are different in two aspects:
  (a) offline samples states using random walks, online uses states during the search 
  (b) offline considers an order useful if it obtains a better heuristic value on one out of 1000 sampled states; online requires the heuristic to improve on the "sampled" state

One could think of analyzing what's the impact of these changes. For example, one could
still use random walks to sample states in the online variant (instead of using the
current state). Even if it seems a bit counter-intuitive, it'd be interesting to see how
much this decreases performance, i.e., how much online benefits from using states from the
search rather than random walk sampling.

Also, one could analyze whether results could be better by using previously sampled states
to analyze if an order is useful, as the offline variant does.

Finally, it'd be interesting to see how the two variants differ in terms of selected
orders. Is one of the variants significantly selecting more orders at the end of the
search for a fixed time limit T? How many orders are typically selected (i.e. around what
order of magnitude)?

3) Related to the previous two points, one could also just use the offline method as it
was, just interleaving it with the search. It would be interesting to see if the online
method has any advantage over that one.

4) In the related work, it is mentioned that Eifler and Fickert used a different criteria
to decide when to refine the heuristic, based on the Bellmann equation. Have you
considered using their criteria to compare against interval and novelty?

5) Are states re-evaluated upon expansion? This could have a positive effect, since the
heuristic has possibly improved since the state was first evaluated. In this case, one
could actually store for each state which orders were evaluated, to avoid re-evaluating
the same order more than once.

Minor:

I'd suggest to remove the subsection header Time Limit in the Experiments.  It was a bit
strange to me to change subsection and still continue discussing the same table.

review_title: Good paper, but many open questions that could be addressed

final_score: rating: 7: Good paper, accept
review_content: Brief summary of the paper:

This short paper introduces and discusses a novel online approach for computing saturated cost partitioning (scp) heuristics. A key component of scp heuristics is the ordering on the heuristics that are used to modify (saturate) the cost function. Previous algorithms that compute saturated cost partitionings are either offline and compute heuristic orderings in a precomputation step to search; or online but compute only a single ordering for a given state. The paper proposes to combine both approaches and compute a diverse set of orderings online during search. An empirical evaluation shows that the proposed approach outperforms the other approaches.

Summary of the review:

The paper discusses saturated cost partitioning heuristics which are one of the most powerful tools to solve optimal classical planning problems, it therefore fits perfectly into the HSIP workshop. The paper is generally well-written, mostly easy to follow and the evaluation shows that the idea works well in practice. I therefore recommend acceptance. Nevertheless, I have a few critical comments on the accessibility of the work for readers not familiar with saturated cost partitioning.

Major comments:

- As someone who is familiar with the original work on saturated cost partitioning by Seipp and Helmert (2014) the paper was mostly easy to follow. I agree with referring readers to related work for concepts that go beyond the scope of the paper, yet I recommend to at least outline the general idea of the discussed topics, e.g.:

 - What is the underlying idea of the perim* saturator?
 - How is the subset of states chosen in line 4 of Algorithm 1?
 - What is the underlying idea of the greedy ordering method, what is 'stolen'?

- I think the paper could do a better job in emphasising the difference between the original online computation and the online diversification approach. It only became obvious to me that the original online approach does not consider different orderings once the 'Interval' paragraph pointed out the difference between the two approaches. This could be made more explicit by not only giving the comparison to offline diversification before the 'Time Limit' paragraph, but also discussing the difference to the online variant without diversification.

- In general, the paper uses the term 'diversification' a lot but, apart from mentioning it in the abstract, never makes it clear what 'diversification' means.

Minor comments:
 - In Algorithm 1 the (what I assume) sequence concatenation operator is not formally defined. As far as I am aware there is no canonical notation of sequence concatenation, so this should be made explicitly clear (especially because $\oplus$ is sometimes used for bitwise-xor in computer science).

 - The meaning of subtraction of two functions (cost - scf_h) is not explicitly defined

 - "Algorithm 2 shows the strongest offline SCP algorithm from the literature" - reference?

 - It is never said explicitly that novelty-1 and novelty-2 refers to novelty with k=1, resp. k=2.

 - The paper focuses only on A* search, but in principle the approach works for general best-first search algorithms. Obviously the use-case is clearly $A^\star$, but I don't see why some statements could not be written in a more general way. Readers might wonder whether the approach only works for $A^\star$ search.

Questions:
 -  You only evaluate greedy ordering of heuristics. Seipp, Keller, and Helmert (2020) also evaluate other ordering functions (random, h, stolen). Is there reason to assume their evaluation would have similar results in the online diversification scenario?


review_title: Official review

Decision: Accept