Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics

Christer Bäckström, Peter Jonsson, Sebastian OrdyniakJAIR 2021 · DOI

TL;DR

This paper investigates the theoretical limits of approximating optimal plans in AI planning systems, particularly focusing on "monotone" planning where actions only have positive effects. The authors establish tight bounds on how well these problems can be approximated, revealing surprising connections between planning complexity and parameters like the number of variables and action effects, which have implications for designing efficient heuristic functions.

What Problem Does This Paper Address?

In AI planning, the goal is to find a sequence of actions (a plan) to get from an initial state to a goal state. "Cost-optimal planning" aims to find the cheapest plan, where actions have associated costs. This is computationally hard. A common approach to tackle this is using "heuristic search," which relies on "heuristic functions" to estimate the cost to reach the goal. These heuristics often work by simplifying the planning problem, for example, by ignoring negative effects of actions (called "delete relaxation"). This paper delves into the theoretical limits of how well we can approximate the optimal plan cost in a simplified setting called "monotone planning" (where actions only have positive effects). Understanding these limits is crucial because it directly informs us about the potential performance of heuristic functions that are based on such relaxations. The core question is: how close can a polynomial-time algorithm get to the true optimal cost, and are there fundamental barriers to getting even closer?

Methods

The paper employs techniques from computational complexity theory, specifically focusing on approximation algorithms and parameterized complexity.

  • Approximation Algorithms: The authors analyze algorithms that aim to find a solution whose cost is within a guaranteed factor of the optimal cost. They establish both upper bounds (what's achievable) and lower bounds (what's provably impossible) for approximation ratios.
  • Parameterised Complexity: They investigate how the complexity of planning problems changes with respect to specific parameters, such as the number of variables or the number of actions affecting a variable. This allows for a more nuanced understanding of hardness beyond just input size.
  • Reductions: A key technique is using reductions from known hard problems (like SAT, Vertex Cover, and Directed Steiner Tree) to planning problems. If problem A can be reduced to problem B, then the hardness of A implies the hardness of B. This is used to prove NP-hardness results for approximation.
  • Specific Planning Formalisms: The analysis is conducted on various restricted versions of STRIPS planning (a common AI planning language), including monotone planning, planning with positive preconditions, and planning with unary actions.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and hardness results, using constructed instances derived from logical formulas and graph problems rather than empirical datasets.

Key Insights and Ideas

  • Monotone Planning is Still Hard to Approximate: Even in the simplified "monotone" setting (where actions only add positive effects), approximating the optimal plan cost is fundamentally difficult. The paper shows that for many variants, we can only get approximations within factors that grow with the problem size (like $|V|$ or $|V|^\epsilon$), and getting significantly better is NP-hard.
  • Heuristics are Fundamentally Limited: The approximability bounds directly translate to limitations on heuristic functions. If a planning problem is hard to approximate, it means any polynomial-time computable heuristic function will necessarily have instances where it significantly overestimates the true cost. This provides a theoretical basis for why some heuristics, even if admissible, might not perform optimally.
  • Parameter Matters: The paper highlights that the "hardness" of approximating planning problems depends heavily on the specific parameters considered. For instance, restricting actions to have at most one effect (unary actions) or bounding the number of actions that affect a variable can change the approximability landscape.
  • Surprising Connection to Effects: The paper notes that for certain problems, the approximability is more closely tied to the number and type of preconditions than the effects of actions, which might be counter-intuitive.
  • Bridging Theory and Practice: By analyzing these theoretical limits, the paper aims to provide a better understanding of why certain heuristics work well in practice and where their fundamental limitations lie.

Key Results

The paper presents a comprehensive set of non-approximability results (hardness results) and approximability results (upper bounds) for various classes of monotone planning problems. Some highlights include:

  • Cost-Optimal Planning (COP):
    • For instances with free preconditions and bounded action weights $\beta(|V|)$, it's NP-hard to approximate within $\beta(|V|)$ and polynomial-time approximable within $|V|\beta(|V|)$.
  • For instances with positive preconditions and at most one precondition, it's NP-hard to approximate within $g_c(|V|)$ for $c < 1/2$, where $g_c$ grows faster than polylogarithmic functions.
  • For instances with positive preconditions and at most one precondition, COP can be approximated within $|V|^\epsilon$ for any $\epsilon > 0$.
  • Length-Optimal Planning (LOP):
    • For instances with free preconditions, it's NP-hard to approximate within $|V|^{1-\epsilon}$ for any $\epsilon > 0$.
  • For instances with positive preconditions and at most one precondition, LOP can be approximated within $|V|$.
  • For instances with positive preconditions and at most one precondition, it's NP-hard to approximate within $\log^{2-\epsilon}|V|$ for any $\epsilon > 0$.
  • Parameterised Tractability: The paper shows that COP(*,1+) (cost-optimal planning with unary actions) is solvable in $2^{\chi(P)} \cdot \text{poly}(||P||)$ time, where $\chi(P)$ is a parameter related to the number of actions with overlapping effects. This suggests that parameter $\chi$ is more effective for fixed-parameter tractability than parameter $\delta$.

Limitations and Future Work

  • Theoretical Focus: The paper is heavily theoretical, focusing on worst-case complexity and approximation bounds. While it provides insights into heuristic design, it doesn't directly propose new heuristics or empirical evaluations.
  • Monotone Planning Assumption: Many results are specific to "monotone" planning (actions only have positive effects). Extending these findings to general planning with negative effects remains an open challenge.
  • Parameter Identification: The paper emphasizes the importance of identifying the "right" parameters for fixed-parameter tractability. While it explores $\delta$ and $\chi$, further research is needed to understand which parameters are most effective for various planning problems.
  • Connecting Theory and Practice: A key future direction is to bridge the gap between theoretical approximation bounds and the practical performance of heuristics. Understanding how theoretical limitations manifest in real-world planning scenarios is crucial.
  • Non-Admissible Heuristics: While the paper touches upon non-admissible heuristics, a more in-depth analysis of their approximability and how they differ from admissible ones could be beneficial.

Summary updated

BibTeX
@article{backstrom2021cost,
  author = {Christer Bäckström and Peter Jonsson and Sebastian Ordyniak},
  title = {{Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics}},
  journal = {J. Artif. Intell. Res.},
  year = {2021},
  doi = {10.1613/jair.1.12278},
}
Figure