Abstract: 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 propose two such

bound-sensitive variants of existing classical planning heuristics, and show

experimentally that the resulting search is significantly more informed than

with comparable heuristics that do not consider bounds.