Venue: ICAPS 2019 Workshop HSDIP

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper presents an approach to solve oversubscription planning 
(OSP) tasks optimally by using a translation to classical planning 
with multiple cost functions. A new class of heuristics is introduced 
that makes explicit use of the cost bounds encoded during the 
transformation such that solving the tasks optimally with the standard 
A* + admissible heuristic approach also leads to an optimal solution 
of the OSP task. 

The main contribution of the paper is the introduction the new type of 
heuristic based on the already existing task transformation, and 
designing the necessary adaption for two concrete heuristics, namely 
hMax and Merge&Shrink heuristics.


Some comments:
In my opinion, the authors could do a better job introducing the task 
reformulation, since this is the basis for the rest of the paper. I 
found it somewhat hard to understand why bounds are implemented in 
this way.

The introduction of Merge&Shrink lacks formality, leading to the fact 
that Theorem 3, i.e., the claim that the introduced adaption of 
standard M&S heuristics is indeed an admissible heuristic that 
respects the bounds of the transformed task properly, cannot be 
verified. There are too many details missing.

The experimental evaluation is not very convincing. Although the 
search space size gets reduced significantly, coverage is 
significantly worse than for the baselines branch-and-bound, as well 
as blind search. There is only a single setting where the new M&S 
heuristic is better. Other than that, there is only a few domains 
where the new heuristics can solve more instances.

You state that M&S times out when constructing the heuristics in many 
cases. 1) Does this only happen in instances that are too large to be 
solved, anyway? 2) Given the large amount of existing M&S 
configurations, what is the bottleneck of trying out a different 
strategy? Are there any specifics that need to be adapted for each 
variant individually?


Minor:
- please remove the copyright statements from the first page
- "in which a set of hard goals" => "where a set of hard goals"
- "shown to *be* outperform"
- I found the usage of "v = v_g" of values as v_g a bit confusing, since
in the rest of the paper you use \vartheta. Also, later you use \theta
instead. Please make it consistent throughout the paper.
- in the definition of G' of Def1: it should probably be "v = v_g", not v_g
- Please consider reformulating the sentence ".. when the node n with
minimal f(n) value is a goal state".
- "if the cost of the new path is less" => lower
- M&s section: "s, s' *C_i*
- you never introduce the configuration shortcuts "ms^b", "max^b", and
so on.
- "80 instances *fewer* than" => less than
review_title: somewhat incremental; clarity could be improved; topic fits workshop

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes modifications to admissible heuristics to make them better informed in a multi-criteria setting where one cost function is the minimization objective and one or more secondary cost functions are constrained by bounds. The modified heuristics are applied to a reformulation of oversubscription planning.

Over all it is not a bad paper, but I think it misses some relevant connections. I also have some questions about the OSP formulation.

The special case of multi-criteria planning optimizing for one cost function while remaining within bounds for another has been studied in the context of stochastic problems. The ICAPS 2016 paper by Trevizan et al. introduced algorithms for the constrained SSP (CSSP) problem, which is a stochastic shortest path problem with exactly this kind of constraint/cost structure. More to the point, the ICAPS 2017 paper by Trevizan et al. introduced a form of projection/operator counting heuristics to SSPs, which they also extended to CSSPs. The extension follows essentially the same pattern as that used by the authors of this paper, in that the bounding constraint on each of the secondary costs is added to the heuristic formulation. Clearly this can be applied to non-stochastic problems as well, in which case it reduces to an operator counting heuristic for the bounded multi-criteria problem.

Another special case that has seen some attention is the bounded-cost planning problem. This is formulated the same way as the bounded MCF in this paper but without a primary cost function. In other words, the question is simply does there exist any plan within the secondary cost bound? Typically, this problem considers only a single bounding cost function. Some specialized search algorithms were introduced by Stern et al. (ICAPS 2011) and Thayer et al. (ICAPS 2012), but adaptation of some common planning heuristics to this setting were also proposed (Haslum ICAPS 2013; Dobson and Haslum HSDIP 2017). Again, the pattern of adaptation is similar, with the cost bound somehow imposed on the selection of actions in the abstract or relaxed plan.

The paper should at least discuss these closely related works. Even better would be a comparison between the proposed new heuristics and the previous ones in settings where they are comparable. For example, the bounded-cost problem can be formulated as an OSP, by simply making the goal soft, which has a solution with reward equal to the trivial upper bound (the sum of all subgoal utilities) if and only if the original bounded-cost problem is solvable.

The OSP formalism used in this paper, and presumably also in the paper by Katz et al. cited for the reformulation, assigns utilities only to individual facts, i.e., variable-value equalities. There is no explicit provision for assigning utilities to conjunctions (or disjunctions) of facts (for example, to say that the utility of have(bread) and have(butter) is more than the sum of the utilities of each of the two facts by themselves, or, for that matter, that the utility of have(train-ticket) and have(bus-ticket) is no more than the max of the utilities of each of these two facts individually). One can imagine
encodings that use an artificial, zero-cost action to set an auxiliary variable to true when a conjunction is achieved, but this raises some problems with the reformulation, in that undoing any part of the conjunction must also force a reset of the auxiliary variable. It is also not clear how this would work in situations where the utility of a conjunction is less than the sum of its parts. It would be good if the authors can comment in the paper on how limiting the restriction to single-fact utilities is.

The readability of Table 1 could be enhanced. For example, alternating rows with white and lightly shaded backgrounds would make it visually easier to follow a row. The plus/minus zero entries could be omitted (blank) to make it easier to identify where the differences are.

References:

Felipe Trevizan, Sylvie Thiébaux, Pedro Henrique Santana, Brian Charles Williams. Heuristic Search in Dual Space for Constrained Stochastic Shortest Path Problems. ICAPS 2016. http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13179

Felipe W. Trevizan, Sylvie Thiébaux, Patrik Haslum. Occupation Measure Heuristics for Probabilistic Planning. ICAPS 2017. https://aaai.org/ocs/index.php/ICAPS/ICAPS17/paper/view/15771

Jordan Tyler Thayer, Roni Stern, Ariel Felner, Wheeler Ruml. Faster Bounded-Cost Search Using Inadmissible Estimates. ICAPS 2012. http://www.aaai.org/ocs/index.php/ICAPS/ICAPS12/paper/view/4706

Roni Tzvi Stern, Rami Puzis, Ariel Felner. Potential Search: A Bounded-Cost Search Algorithm. ICAPS 2011. http://aaai.org/ocs/index.php/ICAPS/ICAPS11/paper/view/2687

Patrik Haslum. Heuristics for Bounded-Cost Search. ICAPS 2013. http://www.aaai.org/ocs/index.php/ICAPS/ICAPS13/paper/view/5993

Sean Dobson, Patrik Haslum. Cost-Length Tradeoff Heuristics for Bounded-Cost Search. HSDIP 2017. http://icaps17.icaps-conference.org/workshops/HSDIP/proceedings/dobson-haslum-icaps2017wshsdip.pdf

I think I have seen a paper titled something along the lines of "planning with conjunctive utilities" somewhere, but now I cannot find it or recall where, or who wrote it.

review_title: missing related work - weak accept

Meta-review: metareview: Dear Authors,
thank you very much for your submission. We are happy to inform you that
we have decided to accept it and we look forward to your talk in the workshop.
Please, go over the feedback in the reviews and correct or update your papers
in time for the camera ready date (May 24). In particular, please address the
comments raised by Reviewer1 regarding clarity and discussion of related work,
by making use of the additional space (9 pages) allowed by HSDIP.
Best regards
HSDIP organizers
confidence: 5: absolutely certain
Decision: Accept