TL;DR
This paper tackles the challenge of automatically verifying "agent abstractions" for classical planning problems. They propose a method to reduce this verification problem to model checking a logic called CTLK, enabling automated verification of whether a proposed abstraction is sound and complete for a given planning domain.
What Problem Does This Paper Address?
Classical AI planning often relies on abstraction to simplify complex problems and find solutions more efficiently. Agent abstraction, in particular, aims to provide high-level, explainable views of an agent's behavior. However, automatically verifying if a proposed abstraction (defined by a "refinement mapping") is correct has been a significant hurdle. This paper addresses the "existence problem" of agent abstraction: given a concrete planning problem and a proposed abstraction, does a valid abstract representation actually exist? This is crucial because creating abstract representations manually is easier than ensuring their correctness.
Methods
The authors introduce a framework for abstracting finite-state systems (Labelled Transition Systems - LTSs). They define "sound" and "complete" abstractions, which essentially guarantee that solutions found at the abstract level can be translated back to the concrete level, and vice-versa, under certain conditions. The core contribution is showing that verifying the existence of these propositional agent abstractions can be reduced to model checking a temporal logic called CTLK (Computation Tree Logic with Knowledge). They formalize this by constructing an "epistemic transition system" (ETS) from the concrete LTS and the refinement mapping, and then checking CTLK formulas on this ETS. They also define conditions for deterministic abstractions and relate them to the CTLK specifications.
Datasets
Not discussed in the paper. The paper uses standard classical planning domains like Blocksworld, Robot, and Childsnack for experimentation.
Key Insights and Ideas
- Abstraction Verification as Model Checking: The most significant insight is framing the abstract existence problem as a CTLK model checking problem. This leverages existing, powerful model checking tools for automated verification.
- Soundness and Completeness for LTSs: The paper provides formal definitions of sound and complete abstractions for LTSs, extending prior work on situation calculus models. This lays the theoretical groundwork for the verification approach.
- NDESCA+ and DeSCA+: The authors introduce strong versions of sound, complete, and deterministic abstractions (NDESCA+ and DeSCA+), which are crucial for their verification framework.
- Symbolic ETS Construction: The paper outlines a method to construct a symbolic epistemic transition system (ETS) from a planning domain and a refinement mapping, which is key to applying CTLK model checking.
Key Results
The paper demonstrates that the existence of propositional agent abstractions (NDESCA+ and DeSCA+) can be verified by checking specific CTLK formulas on an induced epistemic transition system. They implemented a prototype system called PAAChecker and tested it on standard planning domains. The experimental results show that their approach can solve medium-sized instances within reasonable time limits, though larger instances become computationally expensive.
Limitations and Future Work
The authors acknowledge that their current approach struggles with very large instances due to the computational complexity of CTLK model checking. Future work includes exploring more compact representations (like SAS+) and planning-goal-oriented abstraction to relax the requirement of complete abstraction. They also suggest exploring the synthesis of abstract planning domains and refinement mappings.
Summary updated