An Operational Semantics for a Fragment of PRS

Lavindra de Silva, Felipe Meneguzzi, Brian LoganIJCAI 2018 · DOI

TL;DR

This paper introduces a formal operational semantics for a significant fragment of the Procedural Reasoning System (PRS), a foundational BDI agent architecture. By providing this formalization, the authors enable rigorous analysis of PRS's expressive power and pave the way for more robust verification and understanding of complex agent behaviors.

What Problem Does This Paper Address?

The Procedural Reasoning System (PRS) has been a cornerstone of agent programming for decades, heavily influencing subsequent BDI (Belief-Desire-Intention) agent architectures. Despite its widespread use and influence, PRS has historically lacked a formal operational semantics. This absence makes it challenging to precisely determine its expressive capabilities compared to other agent programming languages and to formally verify the correctness of PRS programs. The authors aim to bridge this gap by providing a formal semantics for a key subset of PRS, focusing on its unique graph-based plan representation and its handling of maintenance goals.

Methods

The authors develop a formal operational semantics for a fragment of PRS. Their approach involves:

  • Formalizing PRS Syntax: Representing PRS plans as directed bipartite graphs, providing a precise structural definition.
  • Defining an Operational Semantics: Establishing a set of derivation rules that govern the transitions between agent configurations. These rules cover actions, belief updates, goal and plan adoption, and crucially, the execution of graph-based plans, including the adoption, suspension, resumption, and abortion of nested maintenance goals.
  • Proving Key Properties: Demonstrating that the developed semantics is sound and that the PRS fragment is strictly more expressive than typical plan constructs found in other BDI languages. They also analyze the behavior of wait and preserve programs, which are key to PRS's expressiveness.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Formalizing the "Folk Belief": The paper provides a formal basis for the intuition that PRS's plan graphs are more expressive than those in many other BDI languages. This is a significant step towards understanding the theoretical underpinnings of PRS.
  • Handling Nested Programs: The semantics explicitly addresses the complex interactions that arise from nested wait and preserve programs, which are crucial for robust agent reasoning in dynamic environments.
  • Graph-Based Plans as a Core Feature: The formalization highlights how the graph structure of PRS plans allows for more flexible and expressive representations of procedural knowledge compared to simpler sequential or parallel compositions.
  • Expressivity Gap: The paper demonstrates that PRS plan-libraries, even when restricted to features also present in other languages like CAN, are strictly more expressive, suggesting that the graph-based representation itself is a key enabler of this power.

Key Results

  • A formal operational semantics for a significant fragment of PRS is presented, covering graph-based plans and maintenance goals.
  • Key properties of the semantics are proven, including soundness and the fact that the PRS fragment is strictly more expressive than typical plan constructs in other BDI languages.
  • The paper provides a formal framework for understanding the behavior of PRS's wait and preserve programs, including their adoption, suspension, and resumption.
  • The authors show that PRS plan-libraries cannot be directly translated into equivalent CAN plan-libraries, indicating a fundamental difference in expressive power.

Limitations and Future Work

  • Fragment of PRS: The paper focuses on a fragment of PRS, omitting features like meta-level reasoning, true concurrency, and semaphores.
  • Future Work: The authors suggest several avenues for future research:
  • Investigating whether arbitrary PRS plan-rules can be simulated by sets of CAN or AgentSpeak plan-rules.
  • Extending the semantics to include more PRS features, such as meta-level reasoning and overlapping plan steps.
  • Further exploring the expressivity comparison with other agent programming languages.

Summary updated

BibTeX
@inproceedings{silva2018operational,
  author = {Lavindra de Silva and Felipe Meneguzzi and Brian Logan},
  title = {{An Operational Semantics for a Fragment of PRS}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/27},
}
Figure