10.08.14 - 14.08.14, Seminar 14332

Formal Methods for Coordinating Multi-Agent Systems

The following text appeared on our web pages prior to the seminar, and was included as part of the invitation.

Motivation

Self-interest is a key characteristic of multi-agent systems. Agents pursue their individual objectives. These objectives – which may be consistent but can just as well be completely contradicting – often require cooperation between agents, and in particular, often cannot be solely ensured by individual agents. As a consequence, actions and behaviors need to be coordinated to satisfy the agents' objectives, but they also have to be controlled to meet the global system specification. Formal methods have been successfully applied to coordinate and control multi-agent systems. Among other things, an advantage of formal methods in comparison to non-formal ones is that they allow for rigorous system specification, verification and automation.

In particular, logic-based approaches have been used for the modeling of intelligent agents and for automatic reasoning: epistemic logics allow to talk about knowledge; temporal logics to reason about the evolution of system states; and strategic logics enable reasoning about abilities of agents and coalitions. What they all have in common is their descriptive flavor. Although cognitive models of agents, as well as agent communication languages, are heavily influenced by multi-agent logics, logic-based approaches are most often used directly to describe and to reason about the system from the outside, as opposed to actively change the state of the system or to reach agreements by agents inside the system.

Interaction between rational decision makers in general, and coordination problems in particular, has also been studied in game theory for decades. There are strong ties between these two fields; in particular, strategic logics and formal methods for multi-agent systems often make use of game theoretical concepts.

Agreement technologies are tailor-made for allowing agents to arrive at agreements. For example, norms and social laws can be used to coordinate the agents' behavior – often only with little interaction of agents with their peers. A key problem is the synthesis of appropriate norms and social laws. Their acceptance affects the behavior of the agents and depends on the way norm violations are detected and sanctioned. However, there are many more aspects that influence agents' behavior, including:

  • strategic power
  • argumentation abilities,
  • ressource limitations,
  • social dependencies, and
  • roles and institutions.

Due to the heterogeneity of multi-agent systems a single approach focussing on one of these issues is often not enough. This seminar aims at opening up new directions of research into the coordination and control of multi-agent systems, by bringing together researchers working in different areas.

Goals and research topics. Research topics that will be tackled at the seminar:

  • agreement technologies
  • formal verification and specification of multi-agent systems
  • multi-agent logics
  • game logics
  • models of coordination and control in multi-agent systems

In particular, the seminar will focus on possible intersections between these areas. Specific goals of the seminar include the following:

  • Identification of coordination and control problems in agreement technologies, game theory and multi-agent logic, and what they have in common.
  • Identification of implicit assumption made in strategic logics wrt. the inter-agent coordination.
  • Strengthening of the ties between logics, game theory and agreement technologies.
  • Computational methods for the coordination of multi-agent systems.
  • Development of benchmark coordination problems.