Venue: ICAPS 2023 Workshop HSDIP

Reviews:

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: ### Summary
The paper studies a new problem denoted by any-start-time safe interval
path planning (@SIPP). It complements other research areas in temporal
planning in that it is the first offline planning approach to problems
where the start-time of executing a plan is unknown. The problem is
outlined very clearly and the text is easy to follow. An example is
introduced early and repeatedly used to guide the reader through the
discussion of different theoretical aspects. I really liked reading this
paper and think the authors did a great job in clearly outlining the
problem and their approach to solving it.

An experimental evaluation considers standard pathfinding problems
extended with moving objects to model the changing environment required
for an interesting analysis of @SIPP problems. Certain paths are
sometimes blocked by these moving objects and therefore some actions are
not always applicable. The agent searching for a shortest plan can
instead wait at any position to consider the option of taking that path
once it becomes unblocked again. The overhead of @SIPP algorithms
compared to regular SIPP seems bearable. Furthermore, planning ahead of
knowing the start time is reasonable in scenarios where time is the
critical part of the cost function.

### Minor Comments
- Oftentimes spaces are missing before citations.
- Introduction: "ie." --> "i.e."
- Some parts of "Earliest ATFs for Paths" only became clear once I read
  the example, but I cannot really point out what information I was
  missing.
- "Searching with ATFs", definition of $f$ in parentheses: "($f(n) =
  \alpha(n) + \Delta(n) + h$" --> "($f(n) = \alpha(n) + \Delta(n) +
  h(n)$)"
- I don't understand the following sentence: "We measured the overhead
  of each instance as one hundred times the increase in runtime of ASIPP
  divided by the runtime of SIPP."
- "How long are SIPP plans valid?": something is off with "(confidence
  intervals are all are ..."
- "How long are SIPP plans valid?": "make a @SIPP approach attractive."
  --> "make an @SIPP approach attractive."
- Conclusion: "This work strengths ..." --> "This work strengthens ..."

review_title: Very clear description and discussion of a previously unstudied problem.

final_score: rating: 7: Good paper, accept
review_content: Paper summary: This paper generalizes Safe Interval Path Planning (SIPP) to any-start-time SIPP, enabling planning before a specific start time for the is known. To this end, it is demonstrated how the piecewise linear arrival time function (ATF) of a search path can be constructed inductively during search, and how the final ATF of the task can be constructed from the goal-reaching path ATFs using a data structure that supports efficient lookup of the corresponding path for any given input start time, once it is known.

I acknowledge the relevance of this paper for the workshop. Although this is definitely not my field of research, I would say that the paper makes a significant contribution. The central parts of the paper are fairly comprehensible, containing many examples and explanations that help following along with the developments made. The only exception for me was in Eq. 5, where I did not understand why the minimum of $\alpha_e$ and $\beta_e$ is used. For edge ATFs it seems redundant since here $\alpha_e < \beta_e$? One should mention this to avoid confusion. The construction of the earliest ATFs of edges, the inductive construction of the earliest ATFs for paths and the multi-path earliest ATFs are quite intuitive and correct to the best of my knowledge. Regarding the usage of ATFs during search, the provided example leaves little room for any misunderstandings, and up until this point, the paper is nicely written.

The search algorithms were a little less accessible to me. Namely, I am a bit unsure whether I fully understood how RSIPP operates in the any-start-time setting. In my understanding, RSIPP performs online planning by repeatedly computing a path from the current time point until the time spent while doing so did not already invalidate said path. However, that seems to be entirely different from the proposed any-start-time planning setting, but you also acknowledge that it does not "truly solve @SIPP", so perhaps I did understand it correctly.
ASIPP seems like a simple yet useful extension of the SIPP algorithm.

The experimental evaluation of the algorithms is okay. The ASIPP extension is shown to have only little overhead over SIPP, which is totally fine considering that ASIPP provides information that SIPP does not. I was a bit confused by the scatter plots in Figure 3, I do not really see a reason as to why the axes should be different. Also, what parameter is even changed between these three plots? If I had to guess, the plots show N=256, 1024, 2048 from left to right. The presentation should definitely be improved here. Nevertheless, what I get from this is that as the number of obstacles increases, the @SIPP becomes more suitable compared to replanning, which would take very long to find a path, or not find a path at all. Regarding PEAT vs RSIPP, 40x the runtime of SIP seems to be a lot considering that the algorithms are very similar. It is unfortunate that the evaluation is not more detailed at this point. It is suggested that the time loss does not come from the ATF data structure, which only leaves the larger search space of @SIPP as the reason for this big increase. It would be interesting to see how the number of expanded configurations and the overall pre-computation time for @SIPP scales with the number of obstacles. All in all, the evaluation could be clearer and more detailed in some aspects. On a side note, it is mentioned that tied f values are broken by *higher* g value. Why are higher g values preferred and not lower ones? Would that not correspond to longer durations?

Needless to say, the paper is slightly overlength. Although the provided examples are nice, it is possible to reduce space here without compromising on their usefulness.

Miscellanous Comments:
- I find it odd to have contiguous line numbers across seperate algorithms
- I also find it odd for the scatter plots in Figure 3 to have different axes lengths. Is there a reason for this?
- There is a broken citation: Halp*re*n (1974) should be Halp*er*n (1974)
- Abstract: "... we introduce algorithms to plan using it." - I found this sentence very hard to parse.

Typos:
- Missing spaces between a word and a following parenthesis (occurs multiple times)
- Page 2: "represent an interval in time"
- Page 3: "three times and a duration" - "time points" would make this more parsable
- Page 4: "equivelent"

review_title: Mostly easy to follow, but experimental evaluation could be more detailed

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

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