Computational Logic Foundations of KGP Agents

Antonis C. Kakas, Paolo Mancarella, Fariba Sadri, Kostas Stathis, Francesca Toni

Introduction

The KGP (Knowledge, Goals, and Plan) model, introduced in the Journal of Artificial Intelligence Research, provides a comprehensive formal framework for building autonomous agents. These agents are designed to be both logically sound and practically implementable, operating effectively in dynamic, open environments characterized by incomplete information.

The Specification-Implementation Gap

In Multi-Agent Systems (MAS), a persistent "specification-implementation gap" exists. While high-level models like BDI (Belief-Desire-Intention) offer elegant formal proofs, they are often difficult to translate into verifiable code. Conversely, practical architectures frequently lack a formal basis for analysis. The KGP model bridges this gap by integrating various forms of computational logic—abductive, constraint, and priority-based—to allow agents to interleave reasoning, sensing, and acting through a declarative "cycle theory."

The KGP Architecture

The KGP model represents an agent's internal state using a "forest" of trees where nodes represent goals and leaves represent actions. This architecture is powered by a synthesis of logic programming techniques:

  • Abductive Logic Programming (ALP): Facilitates planning and reactivity by allowing agents to hypothesize necessary actions or sub-goals.
  • Logic Programming with Priorities (LPP): Governs goal decision-making and the "cycle theory," enabling choices between conflicting behaviors based on context.
  • Constraint Logic Programming (CLP): Manages temporal reasoning to ensure plan consistency.
  • Event Calculus (EC): Provides the framework for reasoning about how actions change the world over time.
The hierarchical architecture of the KGP model, illustrating the relationship between state, reasoning, and cycle theory.

Key Insights: Declarative Control and Transitions

A core innovation of KGP is the Cycle Theory. Unlike traditional hard-coded "observe-think-act" loops, KGP's control logic is a declarative logic program. This allows for "context-sensitive" behavior; for instance, an agent can be configured to be more cautious or aggressive by simply adjusting priority rules.

The model defines eight specific transitions that act as state transformers, mapping one agent state to the next. These include Plan Introduction (PI), Action Execution (AE), Sensing Introduction (SI), and State Revision (SR). Selection operators determine which transitions are triggered based on the agent's current state and goals.

Mapping of selection operators to specific agent capabilities and transitions.

Evaluation and Results

The KGP model was implemented in the PROSOCS (Programming Societies of ComputeeS) platform and evaluated using the "San Vincenzo" scenario. This benchmark involves a personal digital assistant managing complex travel logistics, demonstrating the model's ability to handle interleaved reasoning, dynamic goal adjustment, and robustness in the face of incomplete information.

Conclusion and Future Directions

While the KGP model provides a robust logical foundation, several areas remain for future exploration. These include deep knowledge revision (learning), social reasoning (Theory of Mind), and the engineering challenges of true concurrency in reasoning capabilities. Despite these limitations, KGP stands as a significant step toward verifiable, proactive, and reactive autonomous agents.

Summary updated

Abstract

This paper presents the computational logic foundations of a model of agency called the KGP (Knowledge, Goals and Plan model. This model allows the specification of heterogeneous agents that can interact with each other, and can exhibit both proactive and reactive behaviour allowing them to function in dynamic environments by adjusting their goals and plans when changes happen in such environments. KGP provides a highly modular agent architecture that integrates a collection of reasoning and physical capabilities, synthesised within transitions that update the agents state in response to reasoning, sensing and acting. Transitions are orchestrated by cycle theories that specify the order in which transitions are executed while taking into account the dynamic context and agent preferences, as well as selection operators for providing inputs to transitions.
BibTeX
@article{kakas2008computational,
  author = {Antonis C. Kakas and Paolo Mancarella and Fariba Sadri and Kostas Stathis and Francesca Toni},
  title = {{Computational Logic Foundations of KGP Agents}},
  journal = {J. Artif. Intell. Res.},
  year = {2008},
  doi = {10.1613/jair.2596},
}
Figure