Schematic Invariants by Reduction to Ground Invariants

Jussi RintanenAAAI 2017 · DOI

Abstract Automated planning relies heavily on state-space invariants for pruning search trees and generating efficient heuristics. However, a significant trade-off exists between simple "ground" representations, which suffer from combinatorial explosion, and "schematic" representations, which are mathematically complex and often computationally expensive. This paper introduces a hybrid "limited grounding" technique. By proving that invariants discovered on a small, representative subset of objects hold universally, the author enables the use of efficient ground algorithms on large-scale problems. Experimental results on International Planning Competition (IPC) benchmarks demonstrate dramatic reductions in action counts and runtime, particularly in temporal planning where hour-long computations are reduced to seconds.

Introduction: The Grounding Wall

In AI planning, invariants are properties of a state space that remain true across all reachable states (e.g., a specific resource cannot be in two locations simultaneously). Traditionally, researchers have faced a binary choice for invariant synthesis:

  1. Ground Algorithms: These instantiate every possible action. While easy to implement, they fail as the number of objects grows due to the combinatorial explosion of actions.
  2. Schematic Algorithms: These work with action templates. While they scale better with object counts, they are mathematically complex, difficult to implement correctly, and can be slow when many different action templates exist.

This paper addresses the "grounding wall" by proposing a method to achieve the implementation simplicity of ground algorithms without the associated scalability issues.

Methodology: Limited Grounding

The core innovation is Limited Grounding. Instead of grounding the entire problem, the algorithm performs invariant synthesis on a "miniature" version of the domain using a calculated, representative subset of objects.

Theoretical Guarantees

The paper provides a formal lower bound ($L_t^N$) for the number of objects required to ensure that any discovered invariant is sound for the full problem. This bound is determined by the number of parameters in the action schemas and the size of the invariants being sought. The heavy lifting is provided by Theorems 3 and 5, which prove that if a schematic invariant holds for this small subset, it is guaranteed to be a valid invariant for the original, much larger problem.

Synthesis Process

The algorithm employs a fixpoint iteration. It begins with a set of candidate invariants (facts true in the initial state) and iteratively "weakens" or removes them if a ground action in the limited domain can be shown to falsify them. This method is also extended to temporal planning, where the complexity is significantly higher because the algorithm must check if sets of concurrent actions can collectively violate an invariant.

Experimental Evaluation

The approach was evaluated using standard benchmarks from the International Planning Competitions (2008, 2011, and 2014), including domains such as driverlog, satellite, and parking.

Table 1: Comparison of the number of actions in the limited grounding ($|A_{lim}|$) versus the maximum number of actions in the full problem ($max |A|$) across various IPC domains.

As shown in Table 1, the reduction in the number of ground actions is massive. In the satellite domain, for instance, the number of actions was reduced from over 33,000 to just 64. Because the number of objects needed depends on the complexity of the action definitions rather than the total problem size, the technique remains efficient even as problem instances scale.

Key Results and Performance

The reduction in action count translates directly into dramatic speedups. In temporal planning instances that previously required over four hours of computation, the limited grounding algorithm identified the same invariants in mere seconds.

Figure 1: Runtime in seconds plotted against the number of actions, illustrating the performance gains achieved through action reduction.

The efficiency is consistent across benchmarks: with 50 actions, computation typically takes less than 3 seconds; even at 250 actions, it remains under 10 seconds. Furthermore, the limited grounding approach identified the exact same invariants as the much slower full-grounding methods in almost all test cases.

Conclusion

By leveraging structural symmetry, the limited grounding technique collapses the complexity of invariant synthesis. While some limitations remain regarding domains with highly specific initial state data or varying action durations, the method provides a robust framework for scaling temporal planning. Future work may extend this technique to support numeric invariants and more complex temporal abstractions.

Summary updated

BibTeX
@inproceedings{rintanen2017schematic,
  author = {Jussi Rintanen},
  title = {{Schematic Invariants by Reduction to Ground Invariants}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11030},
}
Figure