Cost-Optimal and Net-Benefit Planning - A Parameterised Complexity View

Meysam Aghighi, Christer BäckströmIJCAI 2015

Summary

This research reveals that the choice of action costs—whether they are positive integers, zero-valued, or rational numbers—fundamentally alters the computational complexity of automated planning. While classical theory categorizes these problems as equally hard (PSPACE-complete), parameterised analysis explains why planners struggle with zero-cost or rational scenarios: these variations make finding optimal plans significantly more difficult.

The Problem: Bridging Theory and Practice

In automated planning, the goal is to find a sequence of actions that reaches a target state at minimum cost. Historically, researchers assumed the specific numeric type of costs (integers vs. fractions) or the inclusion of zero-cost actions did not significantly impact complexity. However, practitioners often observe a "performance gap" where planners fail when costs vary wildly or include zeros.

This paper uses parameterised complexity to bridge this gap. By fixing the maximum allowed cost ($k$) as a parameter, the authors investigate whether the underlying mathematical difficulty changes when switching from positive integers to non-negative integers or rational numbers.

Methodology

The authors utilize the SAS+ planning framework and parameterised complexity theory to analyze how complexity grows relative to the cost limit $k$. Key techniques include:

  • FPT Reductions: Transforming problems while maintaining manageable parameter growth.
  • Action Chaining: A construction that replaces high-cost actions with chains of unit-cost actions, proving that cost-optimal planning with positive integers is no harder than finding the shortest plan.
  • Hardness Proofs: Using reductions from problems like Minimum Set Cover and Independent Set to demonstrate that certain planning variants are "para-NP-hard," meaning they remain NP-hard even for small values of $k$.

Key Insights

  • The "Zero-Cost" Trap: Allowing zero-cost actions makes the problem para-NP-hard. Zero-cost actions allow for infinitely long plans within a finite cost budget, breaking the relationship between the cost limit $k$ and search depth.
  • Rationals vs. Scaled Integers: Rational costs cannot simply be scaled to integers in a parameterised context. The required multiplier depends on the entire problem instance rather than just the parameter $k$, violating the requirements for efficient (FPT) algorithms.
  • Net-Benefit Complexity: In Net-Benefit Planning (NBP), where the goal is to maximize (Utility - Cost), the problem is inherently harder because the net benefit parameter does not naturally bound plan length, even with positive costs.

Key Results and Subclass Analysis

The paper provides a detailed map of complexity across various structural subclasses defined by the "PUBS" restrictions (Post-unique, Unary, Binary, Single-valued).

Complexity landscapes for COP with positive integers (left) vs. non-negative integers and rationals (right).
  • Cost-Optimal Planning (COP) with Positive Integers: Found to be $W[2]$-complete, indicating it shares the same fundamental complexity as finding the shortest plan.
  • COP with Non-negative Integers or Positive Rationals: These are para-NP-hard, suggesting they are likely intractable even for small cost limits.
  • Net-Benefit Planning (NBP): Even with simple positive integer costs, NBP remains para-NP-hard.

Limitations and Future Work

While many cases have been categorized, some membership results remain open, such as the exact complexity class for COP with non-negative integers beyond its para-NP-hardness. Future research may explore different parameters, such as combining the cost limit $k$ with plan length limits or causal graph restrictions, to identify new islands of tractability. These findings could also inform the design of heuristics that specifically penalize zero-cost actions to avoid identified complexity traps.

Summary updated

BibTeX
@inproceedings{aghighi2015cost,
  author = {Meysam Aghighi and Christer Bäckström},
  title = {{Cost-Optimal and Net-Benefit Planning - A Parameterised Complexity View}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure