Online Agent Supervision in the Situation Calculus

Bita Banihashemi, Giuseppe De Giacomo, Yves LespéranceIJCAI 2016

Abstract

Traditional agent supervision frameworks often assume an "offline" setting where the agent possesses a static knowledge base. However, real-world autonomous systems operate in "online" environments, acquiring information through sensing and reacting to uncontrollable events in real-time. This paper extends the theory of agent supervision to these dynamic contexts, formalizing a maximally permissive supervisor that preserves agent autonomy while ensuring adherence to safety and operational specifications.

Introduction

In the field of autonomous systems, Agent Supervision is the process of enforcing "guardrails"—logical specifications that ensure an agent, such as a mobile robot or a business process, adheres to safety protocols, legal requirements, or business rules. While the existing De Giacomo, Lespérance, and Muscetolla (DLM) framework provides a robust foundation for offline supervision, it falters when applied to agents that must sense their environment during execution.

In an online scenario, an agent performs sensing actions (e.g., a drone checking weather conditions or a software agent querying a database) that update its knowledge base dynamically. Because the supervisor cannot pre-calculate every possible path without knowing the outcomes of these future observations, a new formal logic is required to handle dynamic knowledge updates and uncontrollable actions—actions the agent might take that the supervisor is powerless to prevent.

Methodology and Formal Framework

The research is grounded in the Situation Calculus, a logic-based language designed for representing changing worlds, and ConGolog, a high-level programming language for agents. To bridge the gap between static models and dynamic execution, the authors introduce several key technical contributions:

Online Transition Relations

Because an agent’s knowledge base evolves at every step, the authors define transitions meta-theoretically. In this view, the "truth" of a situation is not evaluated against a single static world model but against the agent's current epistemic state. This allows the framework to reason about what the agent knows at any given point in time.

The Online Maximally Permissive Supervisor (MPS)

The authors formalize the Maximally Permissive Supervisor (MPS), which acts as the least restrictive controller possible. The MPS only intervenes to block an action if that action—or a subsequent sequence of uncontrollable actions—could lead to a violation of the system's specifications. This ensures the agent retains maximum autonomy while remaining within safe bounds.

Supervision and Lookahead Operators

Two new constructs are introduced to manage the interaction between the agent and the supervisor:

  1. Supervision Operator ($\delta_1 \&^{onl}_{A_u} \delta_2$): A programming construct that synchronizes the agent's program ($\delta_1$) with the supervisor's specification ($\delta_2$), specifically accounting for the set of uncontrollable actions ($A_u$).
  2. Weak Online Lookahead Search ($\Sigma^{w}_{onl}$): This mechanism allows the agent to perform a limited search of future states to ensure that the chosen path is "non-blocking." It guarantees that the agent will not enter a state from which it cannot successfully terminate, given its current knowledge.

Key Insights

Knowledge as a Moving Target

A central insight of the paper is that in online execution, the supervisor must reason about the agent's epistemic state. An action might be safe in one possible model of the world but hazardous in another. The supervisor must therefore ensure safety across all models compatible with the agent's current knowledge, effectively managing uncertainty in real-time.

Proactive Management of Uncontrollability

The framework distinguishes between controllable and uncontrollable actions. A core requirement for the supervisor is to be proactive: it must block a controllable action if it could eventually lead to a state where an uncontrollable action (which the supervisor cannot stop) violates the specification.

Results and Theoretical Guarantees

The authors provide several rigorous proofs to validate the framework:

  • Existence and Uniqueness: They prove that for any online situation-determined agent and specification, a unique online MPS always exists.
  • Soundness and Completeness: The proposed supervision operator is shown to correctly implement the MPS, ensuring that only valid, specification-compliant runs are executed.
  • Guaranteed Completion: The weak lookahead search construct is proven to ensure "non-blockingness," meaning the agent is guaranteed to reach a successful termination state if one is epistemically accessible.

Limitations and Future Work

While the framework provides a robust theoretical foundation, the authors identify several areas for future research. Currently, the model does not fully account for adversarial nondeterminism, where an external actor might actively work to thwart the agent's goals. Additionally, the computational complexity of performing lookahead searches in infinite-state environments remains a challenge. Future work may explore "bounded" action theories to make the synthesis of these supervisors more efficient and potentially decidable for a broader range of temporal properties.

Summary updated

BibTeX
@inproceedings{banihashemi2016online,
  author = {Bita Banihashemi and Giuseppe De Giacomo and Yves Lespérance},
  title = {{Online Agent Supervision in the Situation Calculus}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure