Automatic Verification for Soundness of Bounded QNP Abstractions for Generalized Planning

Zhenhe Cui, Weidu Kuang, Yongmei LiuIJCAI 2023 · DOI

TL;DR

This paper tackles the crucial problem of automatically verifying that "sound abstractions" for generalized planning (GP) problems are indeed sound. They achieve this by developing a proof-theoretic characterization of sound abstractions and a sufficient condition for their soundness, which can be checked using theorem provers. This work is important because it provides a formal framework to ensure that solutions derived from abstract planning problems will correctly solve the original, more complex problems.

What Problem Does This Paper Address?

Generalized Planning (GP) aims to find general solutions that work for a whole class of planning problems, not just a single instance. A key challenge in GP is guaranteeing that these general solutions are correct. One powerful technique to tackle GP is abstraction, where a complex problem is simplified into an abstract model (like Qualitative Numeric Planning or QNP). If the abstraction is "sound," then a correct solution in the abstract model can be translated back into a correct solution for the original problem. However, automatically verifying the soundness of these abstractions has been a significant hurdle. This paper addresses this by proposing a method to automatically verify if a given QNP abstraction is sound for a GP problem, specifically focusing on "bounded QNPs" where integer variables change by one.

Methods

The authors build upon existing work on abstraction in situation calculus and Golog. Their core contributions are:

  • Proof-Theoretic Characterization of Sound Abstractions: They first establish a formal, logical characterization of what it means for an abstraction to be sound. This provides a theoretical foundation for verification.
  • Sufficient Condition for Soundness: Based on this characterization, they derive a sufficient condition for soundness. This condition is more practical for automated verification because it's framed in a way that can be checked using theorem provers.
  • Handling Bounded QNPs: They specifically address "bounded QNP" abstractions, where integer variables are incremented or decremented by one. This is a common and practical type of abstraction.
  • Leveraging Regression and Theorem Proving: To check their sufficient condition, they employ techniques like "existential regression" and "universal regression" from situation calculus. They also develop methods to handle "counting" and "transitive closure" – common features in these abstractions that are challenging for standard theorem provers.
  • SMT Solver Integration: Their verification system uses the Z3 SMT solver to automate the checking of the derived conditions.

Datasets

The paper evaluates their system on several domains:

  • ClearA: A benchmark problem from [Bonet et al., 2019a].
  • Gripper, Logistics, OnAB, GetLast, FindA, Corner: These are additional domains used for evaluation. Some are from existing literature, while others were created by the authors. The paper notes that abstractions for ClearA and OnAB are from [Bonet et al., 2019a], and abstractions for other problems were provided by the authors.

Key Insights and Ideas

  • Soundness is Key for Correctness: The paper strongly emphasizes that the soundness of an abstraction is the critical link that guarantees the correctness of generalized plans derived from it.
  • Bridging Theory and Practice: The work successfully bridges theoretical definitions of sound abstractions with practical, automated verification using theorem provers.
  • Bounded QNPs are Tractable for Verification: By focusing on bounded QNPs and developing specific techniques for counting and transitive closure, they make the verification of this important class of abstractions feasible.
  • The Power of Regression: The paper highlights the utility of regression techniques (especially extended versions) in translating high-level planning concepts into verifiable conditions for low-level planning.

Key Results

The paper presents a system that can automatically verify the soundness of bounded QNP abstractions.

  • Successful Verification: Their implemented system was able to successfully verify the soundness of abstractions for all tested domains within seconds.
  • Experimental Validation: Table 1 shows that for various domains with different numbers of actions, functional fluents, and relational fluents, the system completed verification in a reasonable time (e.g., 4.1687 seconds for ClearA).

Limitations and Future Work

  • Sufficient, Not Necessary: The paper provides a sufficient condition for soundness. This means that if their condition holds, the abstraction is guaranteed to be sound. However, if the condition doesn't hold, it doesn't necessarily mean the abstraction is unsound; it just means their specific verification method couldn't prove it.
  • Deterministic Actions and No Iterations: The current work makes simplifying assumptions that HL actions are deterministic and their refinements do not involve iterations.
  • Future Work: The authors suggest several promising directions:
  • Automatic verification for trajectory constraints in non-deterministic abstractions.
  • Automatic learning of abstractions.
  • Abstraction revision based on verification results.

Summary updated

BibTeX
@inproceedings{cui2023automatic,
  author = {Zhenhe Cui and Weidu Kuang and Yongmei Liu},
  title = {{Automatic Verification for Soundness of Bounded QNP Abstractions for Generalized Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/351},
}

Loading related content...

Figure