Contract-based Design and Verification of Multi-Agent Systems with Quantitative Temporal Requirements

Rafael Dewes, Rayna DimitrovaAAAI 2025 · DOI

Introduction

Multi-agent systems (MAS), such as autonomous vehicle fleets or collaborative robotics, often operate in unpredictable environments where strict binary satisfaction of requirements is unrealistic. Traditional verification methods treat system specifications as either satisfied or violated. However, real-world scenarios demand a more nuanced "quantitative" approach—measuring how well a system performs. Furthermore, as the number of agents increases, monolithic verification suffers from state-space explosion, making it computationally intractable.

This paper introduces a framework for the design and verification of MAS with quantitative temporal requirements. By proposing Good-Enough Decomposition Contracts (GEDC), the authors enable modular verification that ensures optimal system performance even under environmental constraints.

Methodology

The core of the proposed framework is the Good-Enough Decomposition Contract (GEDC), which facilitates the breakdown of global goals into local agent tasks.

Quantitative Logic: LTL[$\mathcal{F}$]

The framework utilizes LTL[$\mathcal{F}$], a variant of Linear Temporal Logic where formulas evaluate to a satisfaction value in the interval $[0, 1]$. This allows for "best-effort" reasoning: if a 100% success rate is impossible due to environmental factors, the system aims for the highest achievable value.

Good-Enough Decomposition Contracts

A GEDC consists of two primary components:

  1. Allowed Decompositions Map (ADec): This defines how local satisfaction values from individual agents aggregate to meet the global system requirement, essentially distributing the workload of a global goal.
  2. Assume-Guarantee (AG) Contracts: These formalize expectations between agents. Each agent guarantees a certain level of performance provided its environment (including other agents) meets specific assumptions.

Verification via Automata

The authors employ an automata-theoretic approach for verification. Specifications and contracts are converted into Generalized Nondeterministic Büchi Automata (GNBA). This allows for algorithmic checking of whether an agent's implementation fulfills its contractual obligations relative to the global objective.

Experimental Evaluation

The framework was evaluated using six synthetic MAS benchmarks: delivery_vehicles, tasks_collab, tasks_scaled, robots_help_a3, robots_help_a5, and synchr_response. These benchmarks test various coordination challenges, such as shared resource access and time-sensitive responses.

The performance of the compositional approach (verifying agents individually via contracts) was compared against a monolithic approach (verifying the entire system as a single entity).

Table 1: Runtime comparison (in seconds) between compositional (Comp.), revision (Rev.), and monolithic (Mono.) verification approaches across various benchmarks. "TO" indicates a timeout after 30 minutes.

Key Results

The experimental results, summarized in the table above, highlight three major findings:

  1. Scalability: For complex benchmarks like delivery_vehicles and synchr_response, the monolithic approach timed out (TO) after 30 minutes. In contrast, the compositional approach successfully verified these systems in approximately 5 to 7 minutes.
  2. Efficiency in Revision: The "Rev." column shows the time required to re-verify the system after updating a single agent's specification. This modular update process is significantly faster—often by orders of magnitude—than re-verifying the entire system from scratch.
  3. Overhead Trade-offs: For very small systems (e.g., robots_help_a3), the monolithic approach can be slightly faster due to the lack of contract management overhead. However, the compositional approach is the only viable method as system complexity scales.

Conclusion and Future Work

The GEDC framework provides a robust method for designing MAS that are both scalable and resilient to environmental uncertainty. By shifting from binary to quantitative satisfaction, designers can ensure "good-enough" performance in complex scenarios.

Future research directions include the automated synthesis of local contracts from global specifications and extending the quantitative logic to model non-cooperative or competitive agent interactions.

Summary updated

BibTeX
@inproceedings{dewes2025contract,
  author = {Rafael Dewes and Rayna Dimitrova},
  title = {{Contract-based Design and Verification of Multi-Agent Systems with Quantitative Temporal Requirements}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i22.34480},
}
Figure