Abstract
This paper presents a formal logic based on Propositional Dynamic Logic (PDL) for the verification of agent programs written in SimpleAPL, a fragment of the 3APL cognitive agent programming language. By extending PDL with belief and goal operators and providing a systematic translation of agent programs into logical expressions, the authors establish a sound and complete framework for automated theorem proving. The utility of this logic is demonstrated through a vacuum cleaner agent case study, proving essential safety and liveness properties.
1. Introduction
As autonomous agents grow in complexity, ensuring their behavior aligns with intended rational principles becomes a critical challenge. Developers require formal tools to verify that an agent's architecture is sound and that its specific programs will actually achieve their goals. Historically, a "gap" has existed between high-level cognitive constructs—such as beliefs and goals—and the low-level execution of code. While languages like 3APL allow programming with these constructs, verification often relies on laborious manual proofs. This research bridges that gap by providing a formal logic grounded in the agent's actual computation, enabling automated verification.
2. The SimpleAPL Language
The authors focus on SimpleAPL, a streamlined fragment of the 3APL language designed for cognitive agents. A SimpleAPL agent is defined by its beliefs and goals (represented as sets of literals), basic actions (belief updates and tests), and plans.
Plans in SimpleAPL are constructed using sequences, conditional choices (if), and iterations (while). Additionally, Planning Goal (PG) rules trigger specific plans based on the agent's current goals and beliefs. The formal grammar for these components is detailed in Figure 1.
3. Logical Framework and Methods
The core contribution is an extension of Propositional Dynamic Logic (PDL). While standard PDL reasons about program execution, this variant incorporates:
- Belief ($B$) and Goal ($G$) Operators: These allow for reasoning about the agent's internal cognitive state.
- Operational Semantics: Formal transition systems define state transitions under two execution strategies: non-interleaved (sequential plan execution) and interleaved (concurrent plan execution).
- Translation Rules: A systematic method converts SimpleAPL programs into PDL expressions ($\xi$ for non-interleaved and $\xi^i$ for interleaved strategies).
- Axiomatization: A set of logical axioms (e.g., $B\neg p \to \neg Gp$, stating an agent does not pursue a goal it believes is already achieved) is proven to be sound and complete.
4. Case Study: The Vacuum Cleaner Agent
To evaluate the logic, the authors employ a Vacuum Cleaner Agent case study. This scenario involves an agent navigating rooms, monitoring battery levels, and cleaning floors. This concrete example demonstrates how the logic can verify liveness properties—such as ensuring the agent will eventually clean all rooms—and "blind commitment" properties, where an agent persists in its goal until it is achieved or believed to be achieved.
5. Key Insights and Results
The research yields several significant findings:
- PDL Suitability: PDL's "programs-as-modalities" approach is naturally suited for mapping agent plans to logical expressions.
- Formalizing Rationality: The logic successfully encodes principles of rational agency through specific axioms.
- Strategy-Dependent Translation: The logical translation must account for the execution strategy (interleaved vs. non-interleaved) to remain faithful to the agent's behavior.
- Soundness and Completeness: The authors prove that their axiom system ($Ax_C$) perfectly matches the intended transition system models ($M_C$).
- Automation: By framing verification within a sound and complete PDL variant, the work enables the use of existing automated theorem provers like MSPASS or PDL-TABLEAU.
6. Conclusion and Future Work
While SimpleAPL provides a robust foundation, it remains a simplified fragment lacking first-order logic, explicit goal-dropping rules, and complex plan revision. Furthermore, the current model assumes a static, predictable environment. Future research aims to extend the logic to the full 3APL language and incorporate non-deterministic environments where external changes can occur independently of the agent's actions.
Summary updated