PDBs Go Numeric: Pattern-Database Heuristics for Simple Numeric Planning

Daniel Gnad, Lee-or Alon, Eyal Weiss, Alexander ShleyfmanAAAI 2025 · DOI

TL;DR

This paper tackles the challenge of applying Pattern Database (PDB) heuristics, highly successful in classical AI planning, to problems involving numeric variables. The authors introduce novel methods to handle the infinite state spaces that arise with numeric variables, demonstrating that these numeric PDBs can significantly improve planning efficiency.

What Problem Does This Paper Address?

Classical AI planning problems often involve discrete states and actions. Pattern Database (PDB) heuristics are a powerful technique for these problems, estimating the cost to reach a goal by focusing on a subset of state variables (the "pattern"). However, extending AI planning to handle numeric variables (like quantities, resources, or continuous values) introduces significant complexity. A key challenge is that numeric variables can lead to an infinite number of possible states, making traditional PDB construction methods, which rely on exploring finite state spaces, infeasible. This paper aims to bridge this gap by adapting PDB heuristics for "Simple Numeric Planning" (SNP), where numeric variables are modified by constant quantities and goals/preconditions are linear inequalities.

Methods

The core of this work lies in adapting PDB heuristics to the unbounded nature of numeric state spaces. The authors propose several strategies:

  • Bounding Numeric Transition Systems: To make PDBs tractable, they introduce methods to limit the infinite state space. This includes:
  • Restricting Numeric Fluents: Limiting the range of values considered for numeric variables.
  • Structure-Specific Constraints: Defining rules to constrain numeric variable values during state transitions.
  • Abstraction Techniques: Representing the numeric state space at a higher level of granularity.
  • Handling Infinite LTSs: They adapt the concept of LTS homomorphisms to create abstractions of infinite transition systems, ensuring that the resulting heuristic remains admissible.
  • Pattern Generation for Numeric Variables: They extend existing pattern generation techniques (like iPDB and systematic pattern generation) to numeric domains. This involves approximating reachable value ranges for numeric variables and guiding the process to avoid overly large abstract state spaces.
  • Algorithm for Partial Generation: A specific algorithm is presented to generate a heuristic for a finite subset of an infinite LTS, ensuring it's informative for states reachable from the initial state.

Datasets

The paper evaluates their approach on:

  • The simple numeric benchmark set from IPC'23.
  • Existing benchmarks from the literature (Scala et al., Shleyfman et al.).
  • Two newly introduced benchmark sets: forestfire and minecraft (with "advanced" instances for specific tasks like pogo-stick and sword manipulation).

Key Insights and Ideas

  • Numeric Variables Dramatically Increase Search Space: The most striking insight is the sheer scale of the problem when numeric variables are ignored. Figure 1 shows that considering numeric variables can reduce the search space by up to six orders of magnitude compared to treating them as discrete or ignoring them entirely.
  • PDBs are Viable for Numeric Planning: Despite the theoretical challenges, the paper demonstrates that PDB heuristics can be effectively adapted and provide significant guidance for numeric planning problems.
  • Orthogonality is Tricky with Numeric Variables: The paper highlights that the concept of "orthogonal projections" (crucial for additive PDB heuristics in classical planning) becomes problematic when numeric variables are involved, especially if they are part of both patterns and affected by actions.
  • Approximation is Key: Due to the infinite nature of numeric state spaces, exact computation is often impossible. The authors leverage approximations for value ranges and heuristic bounds, which prove effective in practice.

Key Results

  • Significant Reduction in Search Space: Numeric PDBs (specifically, the iPDB variant) drastically reduce the number of state expansions required for optimal planning, often by several orders of magnitude compared to finite-domain PDBs or blind search.
  • Competitive Performance: While not always outperforming the absolute state-of-the-art (like LM-cut or OPC) in terms of total coverage on all benchmarks, numeric iPDB shows strong performance and competitiveness, especially in domains where numeric variables are critical.
  • Complementarity with Other Heuristics: Numeric PDBs demonstrate complementarity with other heuristics like LM-cut, suggesting that combining them could lead to even better performance.
  • Runtime Benefits: After an initial heuristic computation phase, numeric PDBs can lead to faster overall planning times compared to blind search.

Limitations and Future Work

  • Coverage Gaps: The authors acknowledge that their evaluated numeric PDB variants do not always achieve the same coverage as the strongest existing heuristics (OPC, LMc) on all benchmarks, particularly in domains like "farmland" and "sailing."
  • Approximation Accuracy: The approximation of reachable value ranges for numeric variables, while effective, is not a sound bound and could potentially impact heuristic accuracy in some cases.
  • Future Directions:
    • Investigating ways to combine multiple abstraction heuristics more efficiently, possibly through cost partitioning.
  • Applying PDBs and merge-and-shrink heuristics to detect unsolvability in numeric planning.
  • Exploring the combination of numeric PDBs with strong numeric heuristics like LM-cut.
  • Developing methods to compute lower bounds for unexpanded abstract states using other heuristics.

Summary updated

BibTeX
@inproceedings{gnad2025pdbs,
  author = {Daniel Gnad and Lee-or Alon and Eyal Weiss and Alexander Shleyfman},
  title = {{PDBs Go Numeric: Pattern-Database Heuristics for Simple Numeric Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i25.34851},
}
Figure