Venue: ICAPS 2023 Workshop HSDIP

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper presents triangle search. It maintains an open list for each
depth of the search tree and in each iteration expands a node from each
open list. A parameter called slope can be used to set the number of
depth levels that can be expanded in each iteration. The paper reports
experiments on four domains, comparing against ARA* and AEES. A
comparison against (mono?)bead search is also discussed.

The topic is clearly relevant to the workshop. The new algorithm seems
to be an interesting addition to the pool of anytime search algorithms.

While the paper is mostly well written, the description of triangle
search could be improved. For a paper that presents a new algorithm, I
found the text accompanying Algorithm 1 too unclear. The text should
guide the reader through the algorithm. What it does instead is to jump
back and forth between different parts of the algorithm, losing focus
of explaining the general idea and guiding through an execution of the
algorithm.

There is some confusion regarding slope: "for i = 0 to slope" means to
add *2* layers of open lists even when slope=1. I assume the range
should be exclusive, i.e., excluding the value slope itself? Or start
at i = 1 instead? The paper never discusses slope=0. The paper should
also explain the reasoning of the name slope, possibly better
explaining the right-hand-side of Figure 1.

I also think the pseudocode could be improved if the algorithm used a
variable depth which could be used to index openlists and to make it
easier to understand in which open list nodes are inserted. Also, this
would clarify the relation to the max-depth in each iteration, slope.

A greater problem is that the algorithm seems directly related to beam
search, and in particular monobeam and monobead search. However, the
latter two are not presented in enough detail for an non-expert to
fully understand them and in particular to judge the difference to
triangle search, making the further discussion difficult if not
impossible to understand. In particular, I never understood the
discussion of "slots" and how the width of the beam relates to
parameters (maybe slope?) of triangle search.

The presentation issue gets worse when the paper attempts, in textual
form, to describe a variant of triangle called stricttriangle and
compare this against monobead.

Finally, the amount of plots included in the paper feels overwhelming,
and their discussion is kept short and feels repetitive. Can we gain
more insights into why the algorithms behave like they do on different
benchmarks? I also wondered why the experiments didn't include a
comparison with monobead/monobeam, the closest related competitor, but
only discussed this in a separate short experiment in the end.

For a conference submission, I would require a reiteration of this
paper to address these issues, but for HSDIP this is fine.

review_title: Interesting new anytime search algorithm based on beam search, exhibiting good performance in some domains, bested by ARA* in others. Experimental-heavy paper with the need of improving the presentation of the algorithm.

final_score: rating: 6: Marginally above acceptance threshold
review_content: Short Summary: The paper introduces *Triangle Search*, an optimal anytime heuristic search algorithm inspired by bead search. In essence, the algorithm extends bead search with iterative widening and deepening. An exact bound on the number of additionally expanded nodes compared to bead search is established before a goal is discovered. In the experimental evaluation, triangle search is compared against Anytime Explicit Estimation Search, anytime repairing A* and bead search on four different planning domains, where triangle search performs best in three out of four domains.

The operation of triangle search is explained well and the algorithm performs convincingly in three out of the four tested domains against the other considered anytime algorithms. However, the algorithm and the connection to bead search (Theorem 1) are very simple, which trivializes the contribution by some degree. Nevertheless, given the relevance of anytime heuristic search to the workshop and the supportive experimental evaluation, I consider this paper acceptable. There are however a few things that I found missing.

Firstly, the *slope* of the algorithm can only increase the depth of the search compared to the width, which I find to be unnecesarily restrictive. Why not introduce two parameters $d$ and $w$ so that $d$ additional layers are expanded in each iteration, and $w$ expansions are made in each layer instead of one? Then $d=2$ and $w=1$ would correspond to a slope of $2$, and $d=1$ and $w=2$ would correspond to a slope of
$\frac{1}{2}$, prioritizing the width of the search over the depth. I could imagine this being useful in domains with a high branching factor, but short solutions. Secondly, could Theorem 1 be *easily* extended to also include the slope parameter? If yes, one should include a more general claim here, considering also that the claim is fairly simple. Lastly, the experiments only consider a non-default slope parameter of 500. The evaluation could be a little more fine-grained here, although this is not a big issue.

Regarding the slope parameter: Obviously, this parameter remains fixed throughout the algorithm. Have you thought about any ways to  perhaps dynamically adapt this parameter? I suppose this is also what is hinted at by "non-linearly shaped hypotenuse" shortly before the conclusion?

Concering clarity, the paper is overall very well-written and easy to digest. A very minor exception is in Theorem 1, where the sum formula $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$ was used. The formula itself is obviously well-known, but I think it would not hurt to instantiate it in an intermediate step before simplifying to document its usage and make things more clear. Also, $slope=1$ had me confused after I read the pseudocode, since it says $0..slope$ and I expected this to be an inclusive range. A slightly bigger annoyance are the legends within the plots, in which the algorithms keep changing in order, and which are hardly transparent enough to see for example the dot for triangle search in the plot in Figure 3, left column and center row. As far as I can see (and hopefully) the line styles are always the same within a figure anyway, so a single legend per figure should suffice. The x axis labels (always time) could also be omitted and just mentioned in the caption. 

Typos:
- "triangle" is written instead of "triangle search" several times (e.g., page 1 early in column 2)
- "optimally-efficient optimal" - Not really an error, but sounds really weird to me...
- page 2, col 2: "current incumbent" - "solution" is missing here
- page 5, col 2: "heavy cost 100 pancake"
- page 6, col 1: "of vacuum problem"


review_title: Fairly simple contribution but very relevant to HSDIP and with a supportive evaluation

Meta-review: We are happy to announce that the paper has been accepted for the workshop, congratulations.

Both reviewers expressed their support for this decision. Please make sure to incorporate the feedback mentioned by the reviewers and fix all typos for the the final version.
Decision: Accept