Venue: ICAPS 2021 Workshop HSDIP

Reviews:

final_score: rating: Weak Accept
review_content: The authors introduce a MILP model for a restricted class of numeric planning, which primarily focuses on being able to reduce the number of required layers in the temporal encoding. They do this by shifting from a forall semantics on simultaneous actions to the exists semantics, and further introduce the element of branch-and-cut to remove cycles found in the causal support at each layer.

The work is relevant to HSDIP, and the model seems to be complete. However, in this format, it is extremely dense. There isn't a lot of space to fully expand on what the parts of the model mean, and it feels as though a journal submission might be the best format for the work.

Ultimately, the results are not that great for the elements introduced. There could be some deeper exploration as to where the problem lies (unsolvable iterations? final iteration?), but the evaluation is otherwise fairly complete and indicative of when this approach works. Seeing only 3 domains pose an issue for cycle removal is an interesting result, even if it leads to little improvement across the full benchmark set.

On the topic of benchmarks, it would be interesting to see if there is a synthetic domain that exemplifies the strength of what's being proposed. Over both the previous MILP model and (ideally) the heuristic-based approaches.

I'm leaning towards accepting, and below are some minor points to fix / questions for the authors.

- I understand that it complicates matters having the ADD and DEL sets overlap, but it's probably worth using the standard STRIPS state update: (s_p \ del(a)) U add(a)

- Table 2 is really nice to have! A general list of the differences between the approaches would be good too (rather than having to look up the subtle differences between equation #'s')

- For many of the domains, it seems as though both approaches achieve full coverage. Is there no way to sc

- You state"better admissible heuristics will improve the performance...by providing stronger lower bounds of the time horizon". What's the ceiling on this? I.e., if you had an oracle give you the /precise/ bound, how difficult would it be to solve that problem, compared to the other heuristic-based methods?

- The proposed encoding seems strikingly similar to exists-step plans ( https://link.springer.com/chapter/10.1007/978-3-540-76928-6_26 ). I realize that you are in the numeric setting, but I highly recommend including a comparison.
review_title: Thorough treatment; on point; a bit crammed

final_score: rating: Strong Accept
review_content: ### Summary

The paper extends a branch-and-cut procedure for MIP-based STRIPS planning to MIP-based numeric planning. The relaxing assumption in the MIP is that multiple actions can be executed in parallel in a single step. If a solution is found where the actions used in a step are not serializable, because they have a cyclic dependency, a constraint is added to break this cycle. This way, adding an exponential number of cycle-breaking constraints in the initial model can be avoided and a smaller time horizon is sufficient as actions can be executed in parallel. The experiments demonstrate that often cycles can be completely
avoided (by precomputing and removing cycles of length 2) and in the cases where there are cycles, only a few constraints have to be added. While the performance of the resulting method is not a huge advantage over the method without branch-and-cut, there are cases where a benefit is visible.

The theoretical contribution of the paper is interesting and I spotted no formal mistakes. I did not understand some parts (see below) but those where mostly based on previous work that was already reviewed, so I don't suspect an error here.

The paper is well written but very technical with a lot of content to go through and a lot of notation to keep in mind while reading. I don't have a good suggestion of how to improve this but anything you can do to simplify the paper would be appreciated.

In summary, this is a high-quality paper with an interesting theoretical contribution that should clearly be accepted at HSDIP.


### Technical Issues

For the MILP model for numeric planning, I wasn't able to see the correspondence between plans an MILP solutions. I can see that every plan can be transformed into a solution of the MILP but I'm less clear on whether any MILP solution can be transformed into a plan. The reason why I'm unsure is the lower and upper bounds for the numeric variable values. It seems as though the bounds could be weaker in later time steps and thus allow solutions that do not correspond to plans. This may be explained in the paper this is based on (I didn't look into it). I have the same doubts on the updated constraints that consider the effects of parallel actions.


### Experiments

I was somewhat surprised to see the benchmarks restricted to unit-cost domains as the theoretical part specifically mentions 0-cost actions and discusses how to deal with them.


### Minor comments

* In the definition of s[a]_p, the usual convention is to have add effects win over delete effects (add-after-delete semantics), so the order of set difference and union should be changed (adding parentheses would help as well). Of course it doesn't matter if add(a) and del(a) are disjoint but I'd still write the definition in this way to avoid confusion.
* Missing space in "planas" in the first paragraph of the background.
* The definition of "mutex(a)" is not sufficient to cover the conditions mentioned before equations (3)-(4). It doesn't consider numerical conditions and only considers applying b after a. In my opinion, the term "mutex" should not be used for such an asymmetric definition. I'd rather call such actions, the actions that a interferes with. Apart from the name, the sentence before (3) should be weakened (the constraint does not ensure the condition).
* The text mentions that constraints (12)-(16) enforce preconditions and effects. However, in all these constraints, variables y (talking about facts) occur with an index t+1 while the variables x (talking about actions) occur with an index t. The constraints thus all talk about applying an action at time t and the values of facts after applying the action. I see no way how a precondition of an action would propagate information to variables y with a lower index, i.e., how these constraints ensure that the precondition of a selected action are satisfied in the state where it is applied. This happens with a somewhat indirect interaction through constraint (19).
* In the first sentence of "Branch-and-Cut for STRIPS", I'd move the reference to van den Briel et al. after "a branch-and-cut framework for classical planning". In the current phrasing, it is easy to read the sentence in a way where the references are assigned to the wrong statements.
* When discussing constraint (27), a forward reference to the section "Big-M Values" would be helpful.
review_title: Review

Meta-review: The reviewers agreed that this submission fits well into the HSDIP program, so we are happy to accept it. The main point of criticism in both reviews was that the paper is very dense and we encourage the authors to follow suggestions in the reviews about improving this.
Decision: Accept