Search

We revisit decidability results for resource-bounded logics and use decision problems on vector addition systems with states (VASS) in order to establish complexity characterisations of (decidable) model checking problems. We show that the model checking problem for the logic RB+-ATL is 2EXPTIME-complete by using recent results on alternating VASS (and in EXPTIME when the number of resources is bounded). Moreover, we establish that the model checking problem for RBTL is EXPSPACE-complete. The problem is decidable and of the same complexity for RBTL*, proving a new decidability result as a by-product of the approach. When the number of resources is bounded, the problem is in PSPACE. We also establish that the model checking problem for RB+-ATL*, the extension of RB+-ATL with arbitrary path formulae, is decidable by a reduction to parity games for single-sided VASS (a variant of alternating VASS). Furthermore, we are able to synthesise values for resource parameters. Hence, the paper establishes formal correspondences between model checking problems for resource bounded logics advocated in the AI literature and decision problems on alternating VASS, paving the way for more applications and cross-fertilizations.

This paper focuses on computational mechanisms that control the behavior of autonomous systems at runtime without necessarily restricting their autonomy. We build on existing approaches from runtime verification, control automata, and norm-based systems, and define norm-based controllers that enforce norms by modifying system behavior at runtime to make it norm compliant. For many applications, an autonomous system should comply with a set of norms. We extend our approach to a distributed setting, where a set of norm-based controllers jointly modify the runtime behavior of an autonomous system. The norms that a set of norm-based controllers jointly enforce are investigated and characterized in terms of the norms that are enforced by individual norm-based controllers. We show that a set of norm-based controllers is able to modify the runtime behavior of an autonomous system to make it compliant with all norms that the individual norm-based controllers aim at enforcing.

The model-checking problem for Resource Agent Logic is known to be undecidable. We review existing (un)decidability results and identify a significant fragment of the logic for which model checking is decidable. We discuss aspects which makes model checking decidable and prove undecidability of two open fragments over a class of models in which agents always have a choice of doing nothing.

Norms have been widely proposed as a means of coordinating and controlling the behaviour of agents in a multi-agent system. A key challenge in normative MAS is norm enforcement: how and when to restrict the agents’ behaviour in order to obtain a desirable outcome? Even if a norm can be enforced theoretically, it may not be enforceable in a grounded, practical setting. In this paper we study the problem of practical norm enforcement. The key notion is that of a guard. Guards are functions which restrict the possible actions after a history of events. We propose a formal, computational model of norms, guards and norm enforcement, based on linear-time temporal logic with past operators. We show that not all norms can be enforced by such guard functions, even in the presence of unlimited computational power to reason about future events. We analyse which norms can be enforced by guards if only a fixed lookahead is available. We investigate decision problems for this question with respect to specific classes of norms, related to safety and liveness properties.

Runtime verification concerns checking whether a system execution satisfies a given property. In this paper we propose a model for collaborative runtime verification where a network of local monitors collaborates in order to verify properties of the system. A local monitor has only a local view on the execution of the system; thus, it can verify a specific system property with respect to its local view. However, the local monitor can also receive inputs from other local monitors about the evaluation of the properties that they are trying to verify. This information can be combined to allow the verification of more complex properties. A network built from such collaborating local monitors is called a collaborative monitor.

A framework for boolean-valued judgment aggregation is described. The simple (im)possibility results in this paper highlight the role of the set of truth values and its algebraic structure. In particular, it is shown that central properties of aggregation rules can be formulated as homomorphy or order-preservation conditions on the mapping between the power-set algebra over the set of individuals and the algebra of truth values. This is further evidence that the problems in aggregation theory are driven by information loss, which in our framework is given by a coarsening of the algebra of truth values.

This report documents the programme and outcomes of the Dagstuhl Serminar 14332 "Formal Methods for Coordinating Multi-Agent Systems", that took place from 10 to 14 August, 2014. This seminar brought together researchers from the following subfields of multi-agent systems: logic, game theory, and agreement technologies. It is set up at the intersection of these active fields of research and aimed at fostering collaborations between them. A key objective of the seminar has been to shed light on formal methods for coordinating multi-agent systems, in particular, how to combine research and tools from the different areas to obtain new techniques for coordinating the behavior of agents. The coordination problem is a key problem in multi-agent systems: how can we coordinate the individual behaviour of the agents such that the global behaviour of the system as a whole satisfies our needs? Dagstuhl was an excellent venue to bring together leading researchers from logics, game theory, and agreement technologies to learn about their research activities, to discuss as well as to work on timely problems, and to establish new collaborations between researchers. The outcome of the working groups and discussions provides promising avenues and open questions for future research in the field.

This book constitutes the proceedings of the 13th German Conference on Multiagent System Technologies, MATES 2015, held in Cottbus, Germany, in September 2015. The 11 full papers papers presented together with 2 short papers, 1 invited paper and 4 extended abstracts of doctoral papers in this volume were carefully reviewed and selected from 27 submissions. The papers are organized in topical sections on MAS engineering, modeling, and simulation; smart things working together; and innovative and emerging applications of MAS.

This book constitutes the proceedings of the 12th European Conference on Multi-Agent Systems, EUMAS 2014, held in Prague, Czech Republic, in December 2014. The 21 full papers and 8 short papers presented in this volume were carefully reviewed and selected from 79 submissions. They are organized in topical sections named: agent-based models, trust and reputation; coordination, coalitions and teamwork; logic and formal approaches; theories in practice and real-world problems; decision making, conflicts and agreements.

We propose a logical framework combining a game-theoretic study of abilities of agents to achieve quantitative objectives in multi-player games by optimizing payoffs or preferences on outcomes with a logical analysis of the abilities of players for achieving qualitative objectives of players, i.e., reaching or maintaining game states with desired properties. We enrich concurrent game models with payoffs for the normal form games associated with the states of the model and propose a quantitative extension of the logic ATL* enabling the combination of quantitative and qualitative reasoning.