Abstract
Verification of knowledge-based programs is a critical challenge for autonomous agents operating under uncertainty. This paper presents a formal framework using the epistemic Description Logic $\mathcal{ALCOK}$ to model agent knowledge and sensing. While verification is generally undecidable due to infinite state spaces, the authors identify a restricted fragment where non-deterministic choices are limited to known individuals, proving that verification in this context is decidable.
Introduction
In the field of Artificial Intelligence, designing agents that can operate effectively in "incomplete" environments is a fundamental goal. Such agents must not only act upon the world but also sense it to update their internal knowledge. Traditional action languages, such as those in the GOLOG family, provide powerful tools for defining complex behaviors. However, when these languages are based on expressive logics like First-Order Logic, the task of automatically verifying that a program will always achieve its goal becomes mathematically undecidable.
This paper addresses the challenge of creating a language that is expressive enough to handle an agent's knowledge and sensing capabilities while remaining constrained enough to allow for automated verification.
The $\mathcal{ALCOK}$ Logic and Action Formalism
The authors bridge the gap between Action Programming and Description Logics (DL) by employing $\mathcal{ALCOK}$, an epistemic Description Logic. The "K" operator in $\mathcal{ALCOK}$ allows programs to include conditions based on the agent's knowledge state (e.g., "If the agent knows a component is faulty").
The formalism defines actions with two types of effects:
- Physical effects: Changes to the state of the world.
- Sensing effects: Changes to the agent's knowledge base.
Furthermore, the framework incorporates a non-deterministic "pick" operator, enabling an agent to select an object for an action, such as picking a specific faulty gear to repair.
Knowledge Representation and Axioms
The agent's knowledge is structured into a TBox (terminological knowledge) and an ABox (assertional knowledge). The semantics of these components are adapted to the epistemic setting to ensure consistency across the agent's possible worlds.
Decidability through Abstraction
The primary source of undecidability in knowledge-based programs is the potential to quantify over an infinite domain ($\Delta$). If an agent can "pick" any anonymous object from this domain, the state space of its knowledge becomes impossible to explore exhaustively.
The authors propose a "restricted" fragment where the "pick" operator is limited to individuals the agent already knows about—specifically, those explicitly named in its ABox. They prove that under this restriction, the infinite state space can be collapsed into a finite "bisimilar" abstraction. This allows the application of standard model-checking techniques to verify program properties.
Key Results and Complexity
The paper provides a rigorous theoretical evaluation of the proposed framework:
- Undecidability: Theorem 8 proves that without restrictions on the "pick" operator, verifying programs with sensing is undecidable.
- Decidability: For the restricted fragment, verification is shown to be decidable.
- Complexity Bounds: The verification problem is shown to be in 2EXPSPACE (Theorem 12). While high, this establishes a theoretical upper bound. The projection problem—checking if a property holds after a specific sequence of actions—is EXPTIME-complete (Theorem 13).
Conclusion and Future Work
By restricting agents to act on known individuals, this research provides a clear path toward provably reliable autonomous systems. However, limitations remain. The current decidable fragment cannot handle "anonymous" individuals in the pick operator, such as when a robot knows a fault exists but has not yet identified the specific object. Future work will explore tighter complexity bounds and the practical integration of these theoretical results into existing Description Logic reasoning systems.
Summary updated