Oversubscription planning (OSP) is the problem of finding plans that maximize the utility value of their end state while staying within a specified cost bound. Recently, it has been shown that OSP problems can be reformulated as classical planning problems with multiple cost functions but no utilities.   Here we take advantage of this reformulation to show that OSP problems can be solved optimally using the A* search algorithm, in contrast to previous approaches that have used variations on branch-and-bound search. This allows many powerful techniques developed for classical planning to be applied to OSP problems. We also introduce novel bound-sensitive heuristics, which are able to reason about the primary cost of a solution while taking into account secondary cost functions and bounds, to provide superior guidance compared to heuristics that do not take these bounds into account. We implement two such bound-sensitive variants of existing classical planning heuristics, and show experimentally that the resulting search is significantly more informed than comparable heuristics that do not consider bounds. Oversubscription planning (OSP) problems are a family of deterministic planning problems. In contrast to classical planning, where a set of hard goals is specified and the planner searches for a minimal (or low) cost plan that reaches a state in which all of the goals are made true, oversubscription planning specifies a utility function that describes the benefit associated with achieving different possible states, and asks for a plan whose cost does not exceed a set bound and achieves as high a utility as possible BID5 .While domain-independent classical planning approaches have increasingly standardized around variations on A * search and heuristics that are automatically extracted from the problem description BID0 BID3 BID0 Edelkamp, 2001; BID2 Helmert and Domshlak, 2009] , OSP has generally been solved with branch-and-bound algorithms and heuristics that compute an admissible (in this context nonunder) estimate of the utility achievable from a state. In order to obtain these estimates, recent approaches often adapt classical planning techniques such as landmarks BID4 BID5 or abstractions BID4 , and enhance them with reasoning that is specific to the context of OSP, such as the knowledge that there always exists an optimal plan that ends with a utility-increasing action, or that the cost bound for the problem can be reduced under specific conditions to aid the search algorithm in detecting that improving over the currently achieved utility is impossible.In contrast to these approaches, our aim here is to show that general methods from classical planning, including A * search, can be used in the OSP setting nearly as is. This previously turned out to be the case for the related net-benefit planning problem, where classical planners solving a compilation were shown to outperform planners designed specifically for that task BID3 . Here, we use a similar, recently proposed compilation that converts OSP problems into classical planning problems with multiple cost functions but no utilities BID3 . In addition, we demonstrate that existing classical planning heuristics can be used to guide the search for optimal plans. While these heuristics are typically uninformative out-of-the-box, they require only minor modifications (and no specific reasoning about utilities) to render them sensitive to the secondary cost functions and bounds that are introduced by the compilation. Our experiments with A * and the newly introduced estimators that we refer to as bound-sensitive heuristics show that they lead to informed searches that are competitive with, and in some cases outperform, the state of the art for optimal OSP.One related area of research in the classical setting is that of bounded-cost planning, where the planner looks for any plan with (primary) cost below a given bound, similar to the treatment of the secondary cost in the OSP setting. Approaches proposed for this setting include dedicated search algorithms BID6 and heuristics that take into account accumulated cost and plan length at the current search node BID7 BID0 . These approaches work by preferentially expanding nodes in areas of the search space that are likely to have a solution under the cost bound. Optimal OSP, however, requires expanding all nodes that potentially lie on a path to state with maximal utility. Furthermore, it cannot be assumed that solutions necessarily achieve all soft goals. Heuristics that are able to take into account bounds on secondary cost functions have also been investigated in the stochastic shortest path setting, where they were used as additional constraints in an LP-based heuristic to consider limitations on fuel or time resources BID7 .We now briefly review the various flavors of planning that we consider in this work, and introduce the formalisms by which we describe them. We have shown that a previously introduced compilation to multiple cost function classical planning allows the A * algorithm to be used to solve oversubscription planning problems, and introduced a family of bound-sensitive heuristics that are much more informed than their classical counterparts in this setting. Our experiments show that this approach results in a state-of-the-art method for some bound settings and domains.One future research direction we would like to explore that builds on the methods introduced here is the use of non-admissible heuristics for satisficing OSP. The method by which bound-sensitive h max is obtained is fairly general and should be equally applicable for h add or general relaxed plan heuristics BID3 . A second direction is the use of these heuristics in other planning settings in which tradeoffs must be made between different cost functions, e.g. minimizing fuel use in the presence of bounds on time or vice versa in logistics problems.Finally, our methods may be applicable to numeric planning problems in which the variables describe resources that are strictly decreasing and can be expressed in terms of secondary cost functions and associated bounds. Boundsensitive heuristics could provide a principled way of reasoning about numeric variables in this context.
We show that oversubscription planning tasks can be solved using A* and introduce novel bound-sensitive heuristics for oversubscription planning tasks. Presents an approach to solve oversubscription planning (OSP) tasks optimally by using a translation to classical planning with multiple cost functions. The paper proposes modifications to admissible heuristics to make them better informed in a multi-criteria setting where.