Abstractions for Oversubscription Planning

In deterministic oversubscription planning, the objective is to achieve an as valuable as possible subset of goals within a fixed allowance of the total action cost. Although numer-ous applications in various fields share this objective, no sub-stantial algorithmic advances have been made beyond the very special settings of net-benefit optimization. Tracing the key sources of progress in classical planning, we iden-tify a severe lack of domain-independent approximations for oversubscription planning, and start with investigating the prospects of abstraction approximations for this problem. In particular, we define the notion of additive abstractions for oversubscription planning, study the complexity of deriv-ing effective abstractions from a rich space of hypotheses, and reveal some substantial, empirically relevant islands of tractability