Oversubscription Planning: Complexity and Compilability

Meysam Aghighi, Peter JonssonAAAI 2014 · DOI

Introduction

In classical propositional planning, the objective is absolute: find a sequence of actions that achieves every specified goal. However, real-world scenarios, such as NASA space missions, often involve "oversubscription," where resources are limited and goals are numerous. In these cases, a planner must decide which subset of goals to prioritize to maximize "net benefit"—defined as the utility of goals reached minus the cost of actions taken. This paper investigates the computational complexity of oversubscription planning (OSP) and proposes a method to solve these optimization problems using standard classical planners.

Complexity Landscape

A central contribution of this work is a comprehensive mapping of the complexity landscape for OSP under various structural restrictions. By applying classic formalisms like SAS+ and restrictions such as Bylander’s pre/postcondition limits and the P (unary preconditions), U (unary postconditions), B (binary variables), and S (reversible actions) restrictions, the authors demonstrate a "complexity parity" between OSP and classical planning.

Figure 1: Complexity landscape of oversubscription planning under various structural restrictions.

As shown in Figure 1, OSP is generally no more computationally difficult than classical planning. In most cases where classical planning is NP-complete or PSPACE-complete, OSP falls into the same complexity class. However, the authors identify specific "borderline" cases where classical planning is tractable (in P), but oversubscription makes the problem NP-complete. This typically occurs when few preconditions exist but optimization is required.

The Compilation Approach

To leverage existing, highly-optimized classical planners, the authors develop a polynomial-time reduction that transforms a Net Benefit Planning (NBP) instance into a standard Plan Existence (PE) instance. The core of this "lean" compilation is the construction of a global counter within the planning state variables.

This counter tracks the net benefit as the plan progresses: decreasing when actions are taken (representing costs) and increasing when goals are achieved (representing utilities). By reframing optimization as reachability, finding an optimal plan becomes equivalent to finding any plan that reaches a state where the net benefit counter meets a specific target value. The number of variables added is logarithmic relative to the total utility, ensuring the state space remains manageable for modern planners.

Key Results

The paper provides definitive complexity results for OSP variants across dozens of restricted cases. Most are shown to be PSPACE-complete or NP-complete, mirroring the difficulty of their classical counterparts.

Figure 2: Complexity results for oversubscription planning under pre- and postcondition restrictions.

Table 1 (Figure 2) illustrates how complexity shifts based on the number of preconditions and postconditions. These formal proofs establish that even with very simple action structures, OSP remains computationally challenging. The authors also provide a formal blueprint for the NBP-to-PE compilation, proving that any NBP problem can be solved by a classical planner with only a moderate increase in the number of variables.

Conclusion

This research demonstrates that oversubscription planning is fundamentally similar in complexity to classical planning. The proposed compilation method offers a practical pathway to solving complex optimization problems using existing planning infrastructure. While the theoretical reduction is sound, future work will focus on empirical evaluation to see how off-the-shelf classical planners perform on these compiled "counter" problems in practice.

Summary updated

BibTeX
@inproceedings{aghighi2014oversubscription,
  author = {Meysam Aghighi and Peter Jonsson},
  title = {{Oversubscription Planning: Complexity and Compilability}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.9025},
}
Figure