Verifying that Agents Implement a Communication Language

Michael J. WooldridgeAAAI 1999 · OpenReview

Abstract

In recent years, a number of attempts have been made to develop standardized agent communication languages. A key issue in such languages is that of conformance testing. That is, given a program which claims to semantically conform to some agent communication standard, how can we determine whether or not it does indeed conform to it? In this article, we present an expressive agent communication language, and give a semantics for this language in such a way that verifying semantic conformance becomes a realistic possibility. The techniques we develop draw upon those used to give a semantics to reactive systems in theoretical computer science. To illustrate the approach, we give an example of a simple agent system, and show that it does indeed respect the semantics.

Introduction

In the late 1990s, the multi-agent systems community faced a significant challenge: interoperability. For agents developed by different organizations to collaborate effectively, they required standardized Agent Communication Languages (ACLs) such as KQML or FIPA. However, these languages were typically defined using "mentalistic" semantics. For instance, an agent was expected to send an "inform" message only if it truly "believed" the content of that message.

This created a "semantic gap" for engineers. How can one mathematically prove that a program written in Java or C++ "believes" a specific proposition? Without a method to verify that a program's execution aligns with the language's formal semantics, standardization remains unenforceable. This research addresses the "conformance testing" problem by transforming semantic verification into a formal program verification task.

Methodology: QUETL and Grounded Semantics

The proposed framework relies on Quantified Epistemic Temporal Logic (QUETL). This logic integrates three critical components:

  1. Temporal Logic: To reason about the progression of events over time (e.g., "eventually" or "until").
  2. Epistemic Logic: To reason about "knowledge." In this framework, knowledge is grounded in the agent's local state—its variables and program counter—rather than abstract mental states.
  3. First-Order Logic: To manage complex predicates and objects.

By modeling agents as concurrent processes (represented as labeled multi-graphs), the author defines the semantics of communication in terms of verifiable program states. Knowledge is defined through state indistinguishability: an agent "knows" a property if that property holds in every possible global state that is identical to the agent's current local state.

The Communication Language $L_C$

The framework defines a core communication language, $L_C$, consisting of four primary performatives. These performatives are mapped directly to QUETL formulas, allowing for rigorous checking of an agent's "sincerity" and "commitment."

Table of performatives in the communication language L_C, including inform, ask-whether, commit, and refrain.

For example, an agent is considered conformant in sending an inform message if its internal state at the time of sending mathematically implies the truth of the message's content.

Verification Example

To demonstrate the feasibility of this approach, the paper provides a manual proof for a small agent program. This 7-line example illustrates how temporal reasoning and epistemic rules (e.g., "if a variable $x=n$, then the agent knows $x=n$") can be used to verify conformance.

A simple 7-line agent program used to demonstrate the formal verification of communication semantics.

In this example, the program's behavior is translated into a QUETL formula. By showing that this formula logically implies the axioms of the communication language, the author proves the agent is conformant regarding the inform and refrain performatives.

Conclusion and Future Work

This research demonstrates that semantic conformance testing is a realistic possibility using tools from theoretical computer science. By grounding "mental" states in bit-level program analysis, the framework bridges the gap between abstract ACL specifications and concrete software implementation.

However, challenges remain regarding scalability. While the proof for a 7-line program is successful, verifying real-world systems with thousands of lines of code would require significant advances in automated theorem proving. Additionally, the current model assumes synchronous communication, which may need to be adapted for the asynchronous nature of modern distributed systems. Future work will focus on automating these checks and expanding the language to include more complex performatives.

Summary updated

Abstract

Verifying that Agents Implement a Communication Language Michael Wooldridge, Queen Mary & Westfield College In recent years, a number of attempts have been made to develop standardized agent communication languages. A key issue in such languages is that of conformance testing. That is, given a program which claims to semantically conform to some agent communication standard, how can we determine whether or not it does indeed conform to it? In this article, we present an expressive agent communication language, and give a semantics for this language in such a way that verifying semantic conformance becomes a realistic possibility. The techniques we develop draw upon those used to give a semantics to reactive systems in theoretical computer science. To illustrate the approach, we give an example of a simple agent system, and show that it does indeed respect the semantics. This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.
BibTeX
@inproceedings{wooldridge1999verifying,
  author = {Michael J. Wooldridge},
  title = {{Verifying that Agents Implement a Communication Language}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
  url = {https://openreview.net/forum?id=HkZ4Y1bdbS},
}
Figure