Reactive Policy Checking for Action Languages

Zeynep G. SaribaturIJCAI 2016

Introduction

As autonomous agents, such as search-and-rescue robots, become increasingly integrated into critical infrastructure, ensuring their reliability is paramount. These agents typically operate using reactive policies—sets of rules that dictate actions based on current perceptions (e.g., "move toward the farthest unvisited point until a target is located"). While these policies provide the flexibility needed for dynamic environments, verifying their correctness poses a significant challenge. This paper proposes a formal framework to mathematically prove that an agent’s decision-making logic will achieve its goals across all possible environmental configurations before deployment.

The Verification Challenge

The primary obstacle in agent verification is the state explosion problem, where the number of potential environmental states becomes too vast for traditional exhaustive checking. Furthermore, existing "action languages"—the formal tools used to model how actions change the state of the world—often lack the built-in structures necessary to represent the continuous loops of sensing, planning, and reacting that characterize autonomous behavior.

Methodology: Bridging Modeling and Formal Logic

The proposed research outlines a multi-pronged approach to bridge the gap between high-level agent modeling and rigorous formal verification:

  • Action Languages and ASP: The framework utilizes action language $\mathcal{C}$ to model dynamic systems as transition systems. These models are then translated into Answer Set Programming (ASP), a declarative logic programming paradigm, to make them computationally queryable.
  • Formal Semantics for Reactivity: The author defines new semantics that integrate target establishment and online planning directly into the transition system. This allows the model to simulate the agent's internal "thinking" process alongside its physical actions.
  • Model Checking via Branching-Time Logic: To verify safety and liveness properties (e.g., "Will the agent always find the person?"), the framework employs branching-time logics. This allows for the analysis of multiple possible future paths originating from a single state.

Scaling through Abstraction and Refinement

To handle the complexity of large-scale environments, the framework incorporates advanced verification strategies:

  • CounterExample-Guided Abstraction Refinement (CEGAR): This technique simplifies the model by removing irrelevant details. If a failure (counterexample) is found in the simplified model that would not occur in the actual environment, the system automatically refines the model to be more precise.
  • Compositional Reasoning: This involves decomposing large, complex systems into smaller sub-behaviors. By verifying these individual components separately, the overall computational burden is significantly reduced.

Key Insights and Theoretical Contributions

A central theme of this work is the distinction between verification and synthesis. Rather than focusing on the automated generation of a policy, this research provides the tools to check human-designed policies for potential failure points.

By leveraging declarative modeling, the system remains understandable and concise for human designers compared to low-level code. Furthermore, the framework is designed to handle "unknown environments," aiming to prove that a policy is effective regardless of the specific layout or size of the environment (parameterization). This includes integrating the agent's internal planning processes—often handled by external tools like HEX programs—into the verifiable model.

Current Progress and Future Directions

As a progress report on a doctoral thesis, the paper establishes several foundational results:

  1. Semantic Integration: Successfully described reactive policy semantics within high-level transition systems.
  2. Language Mapping: Established relationships between these semantics and existing logic programming frameworks.
  3. Abstraction Framework: Defined a pathway for using CEGAR to mitigate state explosion.

Future work will address the mathematical hurdle of undecidability—the fact that verifying policies for all possible environment sizes is often impossible. The author plans to investigate "cutoff sizes" and specific environmental constraints to overcome this. Additionally, the research will focus on developing a functional prototype and performing a formal complexity analysis to determine how well these methods scale in practice.

Summary updated

BibTeX
@inproceedings{saribatur2016reactive,
  author = {Zeynep G. Saribatur},
  title = {{Reactive Policy Checking for Action Languages}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure