Verifying Existence of Resource-Bounded Coalition Uniform Strategies

Natasha Alechina, Mehdi Dastani, Brian LoganIJCAI 2016 · OpenReview

Abstract

In multi-agent systems (MAS), agents must often achieve goals while managing finite resources and navigating incomplete environmental information. This paper introduces RB±ATSEL, a novel logic that integrates resource-bounded reasoning with a syntactic approach to agent knowledge. Unlike many epistemic logics with perfect recall that suffer from undecidability, RB±ATSEL focuses on coalition-uniform strategies. The authors demonstrate that the model-checking problem for this logic is decidable and provide a concrete labeling algorithm to verify strategies under strict budget constraints.

Introduction

Verifying the behavior of autonomous agents in complex environments—such as robotic disaster response teams or automated security systems—requires accounting for two critical factors: resource constraints and imperfect information. Agents consume energy or currency to perform physical actions (moving) and epistemic actions (sensing). While frameworks like Alternating-time Temporal Logic (ATL) have been extended to handle these factors individually (e.g., RB±ATL or Epistemic ATL), combining them often leads to undecidability, particularly when agents have perfect recall of their observations.

This research addresses this gap by proposing a "sweet spot" in logic design. By employing a syntactic representation of knowledge and focusing on coalition-level uniform strategies, the authors maintain decidability while providing sufficient expressivity for real-world scenarios.

The RB±ATSEL Framework

The core of the proposed approach is the Resource-Bounded Alternating Time Syntactic Epistemic Logic (RB±ATSEL). It introduces several key methodological innovations:

Syntactic Knowledge

Traditional epistemic logics use indistinguishability relations, which can lead to "logical omniscience"—the unrealistic assumption that agents know all logical consequences of their information. RB±ATSEL instead represents knowledge as a finite set of formulas. This syntactic approach is computationally efficient and better reflects the limited reasoning capabilities of real-world agents.

Coalition-Uniform Strategies

The logic centers on strategies where a coalition of agents acts based on their distributed knowledge. A strategy is "uniform" if the coalition chooses the same action in any two situations that appear identical based on their collective information. This focus on group-level knowledge is a key factor in achieving decidability.

The Model-Checking Algorithm

The primary contribution of the paper is a terminating model-checking algorithm. The algorithm operates by labeling states in a model where specific logical formulas hold true.

The main labeling algorithm for RB±ATSEL.

As shown in the figure above, the RB±ATSEL-LABEL function iterates through the subformulas of a goal formula $\phi_0$. It handles standard propositional logic, knowledge operators ($K_a$), and temporal operators like "next" ($\bigcirc$), "until" ($\mathcal{U}$), and "always" ($\square$).

For complex temporal properties, the algorithm performs a depth-first search on a state-resource tree. A significant challenge in resource-bounded logic is handling infinite paths. The algorithm identifies "unproductive loops" (where resources are stagnant or decreasing) and "productive loops" (where agents can potentially generate resources, potentially leading to an infinite supply, denoted as $\infty$).

Algorithm for verifying the 'always' temporal operator under resource constraints.

The BOX function (Algorithm 3) specifically handles the $\langle\langle A^b \rangle\rangle \square\phi$ operator, verifying if a coalition $A$ has a strategy to ensure $\phi$ always holds within resource bound $b$. It recursively explores the state space, checking for resource exhaustion and identifying cycles to ensure termination.

Case Study: Museum Monitoring

The authors evaluate RB±ATSEL using a "Museum Monitoring" scenario. In this model, two guard agents must monitor a visitor. They must balance actions like "observing" (to detect if the visitor is too close to an exhibit), "warning," and "recharging." The logic allows for the verification of complex conditional strategies, such as: "If the visitor approaches the artwork, the guards will collectively know it in the next state and possess sufficient energy to issue a warning."

Conclusion and Future Work

The paper successfully proves the decidability of the model-checking problem for RB±ATSEL. By treating learning as a resource-consuming action and focusing on coalition-uniform strategies, the authors provide a formal pathway for verifying MAS in resource-constrained environments.

While the algorithm is guaranteed to terminate, its computational complexity remains a subject for future study. Future research may also explore relaxing the assumption of free, instantaneous communication within coalitions or extending the framework to handle probabilistic outcomes.

Summary updated

Abstract

We consider the problem of whether a coalition of agents has a knowledge-based strategy to ensure some outcome under a resource bound. We extend previous work on verification of multi-agent systems where actions of agents produce and consume resources, by adding epistemic pre- and postconditions to actions. This allows us to model scenarios where agents perform both actions which change the world, and actions which change their knowledge about the world, such as observation and communication. To avoid logical omniscience and obtain a compact model of the system, our model of agents' knowledge is syntactic. We define a class of coalition-uniform strategies with respect to any (decidable) notion of coalition knowledge. We show that the model-checking problem for the resulting logic is decidable for any notion of coalition-uniform strategies in these classes.
BibTeX
@inproceedings{alechina2016verifying,
  author = {Natasha Alechina and Mehdi Dastani and Brian Logan},
  title = {{Verifying Existence of Resource-Bounded Coalition Uniform Strategies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=B1VHl7fdWH},
}
Figure