Abstract
This paper introduces a model-checking algorithm for Parameterised Resource-Bounded ATL (ParRB±ATL), a logic designed to determine the minimum resource requirements—such as energy, time, or capital—necessary for a coalition of agents to achieve a specific goal. While traditional resource-bounded logics focus on boolean verification (whether a goal is achievable within a fixed budget), ParRB±ATL enables parameter synthesis. We demonstrate that the model-checking problem for this logic is 2EXPTIME-complete and provide a direct inductive algorithm for computing the set of all satisfying resource assignments.
1. Introduction
In the study of multi-agent systems (MAS), Alternating-time Temporal Logic (ATL) has long served as a standard for reasoning about the strategic capabilities of coalitions. However, classical ATL ignores the physical or economic costs associated with actions. Extensions such as Resource-Bounded ATL (RB±ATL) introduced resource constraints, but these logics are limited to answering binary questions: can a group of agents succeed given a specific, pre-defined budget?
In real-world engineering and planning, the exact budget is often the unknown variable. Designers need to know the minimum resources required to guarantee success or the trade-offs between different resource types. This paper addresses this gap by introducing ParRB±ATL, which treats resource bounds as parameters to be synthesized rather than constants to be verified.
2. The Parameter Synthesis Problem
The core contribution of this work is the shift from verification to synthesis. Instead of returning a "Yes" or "No," the model-checking algorithm for ParRB±ATL returns a mathematical constraint representing the set of all resource assignments that make a goal achievable. This allows for the identification of the Pareto frontier—the set of non-dominated resource bounds where no single resource can be reduced without increasing another.
3. Methodology
The authors utilize several key formalisms and techniques to solve the model-checking problem:
3.1 Resource-Bounded Concurrent Game Structures (RB-CGS)
The underlying model is an RB-CGS, where transitions between states are determined by the simultaneous actions of all agents. Each transition is associated with a vector representing the cost (consumption) or gain (production) for various resource types. The inclusion of both production and consumption (the "±" in the logic's name) adds significant complexity, as it allows for the possibility of infinite resource cycles.
3.2 Witness Trees and Bounding
To represent successful strategies, the authors use witness trees. These are finite structures where nodes track the system state and the current resource balance. A critical challenge in resource logics with production is that the state space can theoretically become infinite. The authors provide a "maximal value" proof, demonstrating that if a successful strategy exists, there must be one where resource values remain within a specific exponential bound. This allows the search space to be effectively pruned.
3.3 The Inductive Algorithm
Unlike previous methodologies that relied on reductions to complex parity games on vector addition systems, this paper proposes a direct, inside-out inductive algorithm. It processes ParRB±ATL formulas by computing the satisfying resource assignments for sub-formulas and propagating these constraints upward through the formula's parse tree.
4. Complexity and Results
The paper establishes that the model-checking problem for ParRB±ATL is 2EXPTIME-complete.
- Lower Bound: The problem is at least 2EXPTIME-hard because it subsumes standard RB±ATL, which was previously proven to be in that complexity class.
- Upper Bound: The authors close the theoretical gap by showing that an alternating Turing machine can solve the problem in exponential space (AEXPSPACE), which is equivalent to 2EXPTIME.
While 2EXPTIME is a high theoretical complexity, the authors note that the exponential growth is primarily sensitive to the number of resource types and the magnitude of the costs. The algorithm remains polynomial relative to the number of states and transitions in the model, suggesting potential for practical application in systems with limited resource dimensions.
5. Discussion and Future Work
ParRB±ATL represents a significant step toward automated system design, particularly in its ability to handle both production and consumption of resources. However, some limitations remain. Currently, the logic treats nested strategies as independent; if a formula describes reaching a state to achieve a subsequent goal, the resource calculation for the second goal starts from a fresh budget.
Future research aims to extend this framework to Resource Agent Logic (RAL). RAL would allow for shared resource pools across nested strategies, enabling agents to reason about how much of a budget is "left over" from a previous task to be used for a future one. Additionally, while the theoretical framework is robust, the implementation of these algorithms into a software tool for empirical testing remains a priority for future development.
Summary updated