Value Driven Landmarks for Oversubscription Planning

Abstract

Oversubscription planning is the problem of choosing an action sequence which reaches a state with a high utility, given a budget for total action cost. Most previous work on oversubscription planning was restricted to only non-negative utility functions and 0-binary utility functions. While this restriction allows using techniques similar to partial satisfaction planning, it limits the expressivity of the formalism. In this paper, we address oversubscription planning with general additive utility functions over a finite-domain representation. We introduce the notions of net utility of an action, and of a gross positive action. Using these notions, we prove several properties about the structure of an optimal plan, which are then compiled into a classical planning problem. The landmarks of this classical planning problem are value driven landmarks of the original oversubscription problem, that is, they must occur in any action sequence which improves utility. An empirical evaluation demonstrates that these landmarks are more informative than previous state-of-the-art methods for landmark discovery for oversubscription planning, and lead to better planning performance.