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).
- 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