In Search of Tractability for Partial Satisfaction Planning

Michael Katz, Vitaly MirkisIJCAI 2016

Abstract

Partial Satisfaction Planning (PSP) addresses scenarios where goals have associated values and actions incur costs, requiring agents to optimize their pursuit of objectives under resource constraints. This paper maps the computational boundaries of two primary PSP variants: net-benefit planning and oversubscription planning. By analyzing causal graph structures such as forks and inverted forks within the SAS+ formalism, the authors identify the boundaries of tractability. The results reveal that while net-benefit planning often mirrors the complexity of classical cost-optimal planning, oversubscription planning is fundamentally more difficult, frequently reducing to the NP-complete Knapsack problem even under minimal structural complexity.

Introduction

In classical AI planning, the objective is typically to reach a predefined goal state at minimal cost. However, real-world applications often involve multiple competing goals with varying importance. Partial Satisfaction Planning (PSP) formalizes this by assigning values to goals. There are two main formulations:

  1. Net-Benefit Planning: Maximizing the difference between total achieved goal value and total execution cost.
  2. Oversubscription Planning: Maximizing achieved goal value within a fixed cost budget.

Despite the development of numerous heuristics, the theoretical landscape of PSP tractability remained largely unmapped. This work seeks to identify "tractable fragments"—subclasses of problems solvable in polynomial time—based on the structural properties of the problem's causal graph.

Structural Analysis and Methodology

The authors utilize the SAS+ formalism to represent planning tasks and categorize them based on their causal graph structures. The causal graph illustrates dependencies between state variables. Key structures analyzed include forks, where a single root variable influences multiple leaf variables, and inverted forks, where multiple parent variables influence a single sink variable.

Causal graph structures analyzed for tractability, including forks (a), inverted forks (b), and more complex dependencies (c-e).

The research employs formal complexity analysis, using reductions from the 0-1 Knapsack Problem and Bounded Classical Planning to establish NP-completeness, while providing dynamic programming algorithms for tractable cases.

Key Insights: The Knapsack Connection and the Binary Boundary

A central finding is the inherent difficulty of oversubscription planning. Even when variables are entirely independent, the problem of selecting goals to fit a budget is weakly NP-complete, directly mapping to the Knapsack problem.

Furthermore, the "Fork" structure reveals a sharp complexity transition based on variable domain size. If the root variable is binary (two states), the problem remains tractable (pseudo-polynomial). However, if the root is ternary (three states), the problem becomes strongly NP-complete. This "binary boundary" highlights how sensitive planning complexity is to even minor increases in variable domain size.

A standard Fork structure (a) where a single root variable controls multiple leaf variables.

In contrast, net-benefit planning is generally more tractable. Many net-benefit problems can be reduced to cost-optimal classical planning, allowing them to leverage existing polynomial-time results for specific causal graph topologies.

Results and Conclusion

The study concludes that oversubscription planning is significantly more challenging than net-benefit planning. While specific tractable fragments exist—such as Forks with binary roots or Inverted Forks with constant-sized sink domains—most oversubscription scenarios are NP-hard.

These results provide a theoretical foundation for future research, suggesting that heuristic development should focus on these tractable fragments to improve general-purpose planners. Future work will explore more complex value functions beyond additive models to find further pockets of tractability in the planning landscape.

Summary updated

BibTeX
@inproceedings{katz2016search,
  author = {Michael Katz and Vitaly Mirkis},
  title = {{In Search of Tractability for Partial Satisfaction Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure