Abstract
This paper addresses a fundamental challenge in automated reasoning: proving that a dynamic system will eventually reach a goal state, regardless of its initial configuration or the number of objects involved. The authors introduce a novel framework for the automatic verification of "liveness" properties within the Situation Calculus. By combining SMT-based feature discovery with mathematical induction, the system can prove goal reachability even in systems with infinite state spaces.
Introduction
In the verification of dynamic systems, researchers distinguish between safety properties ("nothing bad will ever happen") and liveness properties ("something good will eventually happen"). While safety is often verifiable through standard model checking for finite systems, liveness is significantly more difficult to prove for generalized cases—such as proving a robot will reach its destination regardless of room size or the number of obstacles.
Proving these properties for any number of objects requires theorem proving rather than simple state-space exploration. Previous attempts in the Situation Calculus—a logic-based framework for representing change—were often restricted to specific formula types or fixed object counts. This research bridges that gap by automating inductive reasoning.
Methodology
The core contribution is a framework that automates the process of mathematical induction, mimicking human-like proof strategies through three main steps:
- Feature Discovery (
genFeatures): To perform induction, the system must identify a numerical "feature" that decreases as progress is made toward a goal. The authors use an SMT solver (Z3) to generate concrete "small models" of the problem and a classical planner (FF planner) to solve them. By observing which numerical counts consistently decrease during these solutions, the system identifies candidates for inductive proof. - Inductive Verification: Once a feature is identified, the system uses first-order theorem provers to verify the Basis Step (is the goal achieved when the feature is at its minimum?) and the Inductive Step (does an action always exist to reduce the feature value?).
- Regression: The system utilizes regression to transform complex goals into the necessary preconditions for the actions that achieve them, simplifying the inductive task.
Experimental Results
The implementation was evaluated across several classic AI planning benchmarks. In the Blocks World domain, the system successfully verified complex liveness properties, such as clearing a specific block or stacking one block on another, for an arbitrary number of blocks. As shown in the results table, verification times for these complex logical goals ranged from approximately 52 to 168 seconds.
In numerical and infinite-object domains, the system demonstrated even greater efficiency:
- Oil Lamp: Verified properties in an infinite row of lamps in approximately 4.23 seconds.
- Chop Tree & Pick Stone: Handled domains with unknown action counts or parity requirements (even/odd) in under 10 seconds.
- Corner: A grid-navigation task was verified in just 3.21 seconds.
Key Insights and Limitations
A major insight of this work is the use of small models as heuristics. By analyzing how a planner solves a simple 3-block problem, the system can "learn" the abstract feature required to prove the property for a 1,000-block problem. This simulates the human intuition of identifying a "distance" to a goal and ensuring every step reduces that distance.
However, the current system is limited to single induction. More complex problems requiring nested induction remain a subject for future work. Additionally, while the method is sound, it is incomplete; there may be cases where a proof exists but the system returns an "unknown" result due to the limitations of the current feature description language.
Summary updated