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.
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$).
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