TUTORIALS ABSTRACTS
Planning in MAS
Cees Witteveen and Mathijs de Weerdt
To give an introduction into multi-agent planning we start with a brief overview of single agent AI planning techniques.
Then we present a survey on the most important and distinguishing aspect of multi-agent planning: the use of coordination techniques to manage dependencies between autonomous agents.
Finally, we present an overview of currently used multi-agent planning systems and techniques where various forms of coordination can be clearly distinguished.
Natural Language Generation for Embodied Agents
Emiel Krahmer and Paul PiwekEmbodied Agents (Virtual Characters, Humanoids, Animated Agents,...) have in the past 10 years become a new alternative paradigm in user interfaces for a wide variety of application domains including training, education, presentation, sales and entertainment. The appeal of embodied agents derives from the fact that they aim to communicate with human users in the mode of interaction which is arguably most natural for humans: face-to-face conversation.
In face-to-face conversation, we, humans, almost effortlessly produce complex messages simultaneously using various channels of communication: we speak, make gestures, change our posture, use facial expressions, etc. This tutorial is an introduction into research on algorithms, evaluation strategies and applications for embodied agents. We take a widely used reference architecture for text-based Natural Language Generation as our starting point and discuss a number of extensions and modifications for the generation of multimodal behaviours for Embodied Agents.
The tutorial is delivered as 8 chunks of half an hour each. General introductions to the main topics in the area of Natural Language Generation (NLG) for Embodied Agents are interleaved with presentations of cases in which particular generation tasks and approaches are explored further:
1. Introduction, 2. What is Natural Language Generation (NLG)?, 3. Case: Generation of Referring Expressions (GRE), 4. NLG for Embodied Agents: Architectures, 5. Case: GRE for Embodied Agents, 6. Realization: Audiovisual Speech and Gestures, 7. Case: NLG for Teams of Embodied Agents and 8. Evaluating Embodied Agents.
Game Theory
Marc Pauly and Paul HarrensteinMultiagent systems often consist of agents who want to obtain conflicting goals. When cooperation cannot be assumed, it becomes important to analyse the strategic properties of the interaction that takes place in a multiagent
system. Game Theory has developed a wealth of models for describing situations of strategic interaction. We will describe some of the game theoretic models relevant to the analysis of multiagent systems.The course is divided into 4 parts. In part 1, we will present the two basic models used in noncooperative game theory, strategic games and extensive games. In order to analyse how agents will actually interact in a given game-theoretic situation, we discuss a number of solution concepts that have been studied, in particular Nash equilibria and subgame-perfect equilibria. We also consider situations where agents have imperfect information about their environment.
Part 2 focuses on mechanism design. As a designer of a multiagent system, we want the system to exhibit certain desirable properties. In the case of strategic interaction, this usually means that self-interested agents should be induced to act in a way that leads to a socially desirable outcome, or the outcome intended by the designer.
In part 3 we discuss cooperative game theory where we assume that agents can make binding commitments. We illustrate how this assumption dramatically changes the game-theoretic models. As a particular example, we consider the bargaining problem and Nash's solution and characterisation result. More generally, we discuss coalition games with some associated solution concepts, also linking cooperative to noncooperative models of interaction.
In Part 4, finally, we turn to voting as a very general method of resolving conflicts of interest. After considering voting paradoxes and Arrow's celebrated (im)possibility theorem, we consider the problem of strategic manipulation. While strategic manipulation of voting outcomes is generally possible, it turns out that it is often computationally not feasible. In particular in the case of multiagent systems, these results concerning the complexity of manipulation play an important role in the development of systems that are safe.
Organization Oriented Programming in MAS
Olivier Boissier and Jaime Simao SichmanAbstract:
In the last years, social and organizational aspects of agency have become a major issue in MAS research. Recent applications of MAS on Web Services, Grid Computing and Ubiquitous Computing enforce the need of using these aspects in order to ensure some social order within these systems. However, there is still a lack of a comprehensive view of the diverse concepts, models and approaches related to agents? organizations. Moreover, most designers have doubts about how to put these concepts in practice, i.e., how to program them. This course aims at giving an answer to such questions and it is addressed to active practitioners, graduate and senior undergraduate students. We consider two main points of view along which organizations can be analyzed and used in MAS: an agent centered point of view (ACPV) and an organization centered point of view (OCPV). In ACPV, we discuss the fact that even in the absence of formal organizations, some notions like commitment and duties can be viewed as a kind of informal, bottom-up, emergent organization. On the other hand, when addressing OCPV, we discuss the literature about formal, top-down, pre-existent organizations, stressing the different aspects that may be considered in their classification. Next, we show how MAS organizations can be programmed either at the agent or at the system level. We discuss then how organizations can evolve during the MAS´s life cycle. Finally, we present some challenges for future research in this domain.
Methodologies for Agent-Oriented Software Engineering
Lin Padgham, Onn Shehory, Leon SterlingThis session will introduce students to the area of Agent Oriented Software Engineering (AOSE), and provide some experience in some of the available techniques. In building real multi-agent systems it is crucial that well developed design and development methodologies be applied. While much can be learned from OO (and other) SE methodologies, these are not in themselves suitable for use in developing agent systems.
The session will also explore in some detail the current integration of two AOSE methodologies: ROADMAP and Prometheus. ROADMAP has traditionally focussed on more abstract aspects of requirements gathering, as well as taking a broad view of what is required in an approach to AOSE. Prometheus has focussed more on a detailed methodology which is sufficient for guiding students or practitioners from application concept to a well designed and implemented agent system. These approaches are currently being integrated, and work is underway internationally to bring together things that are similar in different approaches, while more carefully delineating particular strengths and differences. Material on how to begin to evaluate different methodologies will also be covered, and some work will be presented in this area.
There will be opportunities for some practical work in order to better understand the approaches being presented.
Verification of Multiagent systems via model checking
Dr A Lomuscio and Prof W PenczekIntroduction:Much theoretical work in the area of Multi-Agent systems (MAS) has traditionally focused on logic-based specifications of MAS and their verification by theorem proving. More recently, model-checking has been put forward as an alternative method for automatic verification of MAS. Model checking is attractive as it is often computationally tractable, it allows a succinct description of the system to be checked by means of a programming-friendly language, and requires little or no specialistic knowledge from the user.
Description:The tutorial will last 4 hours and will cover part of the work the applicants have been directly involved in for the past 3 years, as well as a summary of other results available in the literature. The tutorial intends to provide both the theoretical background, as well as a hands-on introduction to two model checkers available in the area. The overall objective is to enable the student to achieve a basic understanding of the technology and to provide pointers to further results and open problems for further research.
Breakdown:
1 Hour and 20 minutes:
- Logic-based specifications of MAS.
- Interpreted systems.
- Temporal, Epistemic, Deontic Logics.
- Model checking basics.
- Survey of works in the area.
- Ordered-binary decision diagrams.
- Fix points.
- Model checking via OBDD for Interpreted Systems.
1 Hour and 20 minutes:
- SAT-based approaches.
- Bounded Model checking for temporal epistemic languages.
- Unbounded Model checking for temporal epistemic languages.
1 Hour and 20 minutes:
- Survey of tools available
- MCMAS - system description and examples.
- VERICS - system description and examples.
- Experiments in class.
Expected Learning Outcomes:
- asic understanding of temporal logic and its extensions to MAS.
- Basic understanding of BDD technology for model checking MAS logics.
- Basic understanding of SAT-based technology for model checking MAS logics
- Concrete programming experience and usage of the model checker
MCMAS.- Concrete programming experience and usage of the model checker
VERICS.Brief bios of the applicants:
Dr A Lomuscio is Senior Lecturer at UCL, Adastral Park, UK. He has worked
in the area of logic-based specifications for MAS since 1995. Since
2001 he has been involved in verification by model checking. He has
published about 50 research papers in the area. He has lectured at
EASSS a number of times, and has given a number of invited talks at
international conferences and workshops.
Further details at: www.cs.ucl.ac.uk/staff/A.Lomuscio/
Prof. Wojciech Penczek is the head of the Theory of Distributed
Systems group at ICS-PAS and the head of the Programming Methods group
of Podlasie Academy. He was awarded a habilitation in 1996 from
ICS-PAS. Since 2000 his research has been focused on verification
methods for (timed) distributed and multi-agent systems. He is the
author of more than 70 conference and journal articles in the area. He
has given a number of invited talks at international conferences and
workshops.Further details at: www.ipipan.waw.pl/~penczek/
Scaling-up learning agents to real-world problems
Daniel Kudenko and Matthew GroundsAdapting to unexpected or changing situations by learning from experience is a major goal in agent research. Reinforcement learning has proved to be highly popular for this purpose, since many agent domains are naturally formulated as reinforcement learning problems. However, reinforcement learning has mostly been demonstrated in toy domains, and generally performs poorly when applied to complex real-world tasks. The main difficulty has been scaling-up learning for problems with large (often continuous) state and action spaces. Standard algorithms quickly become infeasible as larger learning problems are considered. A wide variety of techniques have emerged in recent years which have allowed progressively more difficult problems to be solved by reinforcement learning.
In this tutorial we provide an introduction to reinforcement learning for researchers unfamiliar with machine learning techniques, and go on to present an overview of the state of the art in enabling agents to learn successfully in complex real-world domains.
The proposed tutorial goes beyond the standard "machine learning for agents" tutorials, in not only introducing basic techniques and leaving the student to grapple with application complexities, but rather show him practical and feasible ways to incorporate learning agents in his chosen application area.
Outline:
- Introduction to Reinforcement Learning
- Value Function Approximation
- Hierarchy and Abstraction
- Learning and Logic
BDI Agents in Service-oriented and Model-Driven System Design
Klaus FischerIntroduction:
Form the very beginning an important aspect of agent theories and technologies was to use such theories and technologies a software engineering approaches to system design. With the idea of wrapper agents agent technologies aimed at integration of legacy systems. The FIPA standards aim at interoperability among agents in a multiagent systems, however, with the just mentioned idea of integration of legacy systems can also contribute to interoperability of software systems in a broader sense. Especially in the area of business applications there are upcoming trends in software design, like for example Service-oriented Architectures (SoA), Model-driven Architectures (MDA) proposed by the Object Management Group (OMG), and Peer-to-Peer (P2P) Computing) which claim to support interoperability. An important questions to answer are, how agent technologies fit into this landscape and what the can contribute in contrast to the competing technologies.
Description:
The tutorial will last 4 hours and will discuss agents that are based on BDI models fit together with SoA, MDA, and P2P approaches to software design. It turns out that BDI models provide an interesting alternatives in describing workflow and interaction patterns in a service-oriented environment. When referring to BDI models the course will use the Jack Development Environment and will especially explain advantages of the team modeling layer that is available in Jack. The topics the tutorial deals with are:
- Service-oriented architectures (SoA)
- Model-driven architectures (MDA)
- Peer to peer computing
- Service Matchmaking
- Service Composition
- FIPA and its relation to SoA
- BDI theories and agents
- Jack Intelligent Agents(TM) development tool for BDI agents
Brief Bio of the lecturer:
Dr. Klaus Fischer is Research Fellow and head of the Multiagent Systems research group at the German Research Center for Artificial Intelligence (DFKI). He holds a PhD and a diploma in computer science form the Technische Universität München. He published more than 50 articles in scientific journals, conference and workshop proceedings, and books, and has given a number of tutorials and invited talks at international conferences and workshops.
Programming Languages for Multi-Agent Systems Part I
Mehdi Dastani, Rafael H. Bordini and Birna van RiemsdijkMulti-agent system is a very broad area, and has produced an impressive variety of techniques that can have an important impact on the development of intelligent distributed software systems. Multi-agent system software development will only be applied to large-scale real applications if the gap between multi-agent system specification and design on the one hand, and multi-agent system implementation on the other hand, is bridged. In order to achieve this objective, programming technologies must be developed so that the specifications and designs of multi-agent systems can be easily and directly implemented. Such technology should include agent-based programming languages as well as tools that support multi-agent programming in a way that is practical and effectively applicable in industry.
This tutorial is aimed at giving an overview of approaches that are now mature enough to be used in the development of (in some cases large-scale) multi-agent systems applications. Because of the variety of application areas for which multi-agent systems can be adequately used, it is unlikely that a single programming language will become the norm. Each multi-agent programming language provides particular features that usually have different importance for different application areas.
We will give a reasonably detailed account of two agent programming languages and their corresponding platforms. In particular, we give a detail presentation of 3APL and Jason programming languages and their corresponding platforms. We will discuss their syntax and operational semantics, and explain various programming features provided by the platforms. We also present the main features of two other multi-agent programming languages, in particular Jadex and JACK. Finally, we will also provide references to a number of agent programming languages that have appeared in the literature. In order to give the participants some practical experience with programming multi-agent
systems, we will organise a lab exercise where a simple multi-agent application should be implemented in either 3APL or Jason. The schedule for this tutorial consists of two 2-hour lectures and one 2-hour lab session.
Logics for MAS
Jan Broersen and John-Jules MeyerThe course contains two parts. The first part by Jan Broersen is an introduction to logics for AI, and treats the general question what logic is and what it is needed for in AI, the basics of modal logic, and applications to some reasoning domains. The second part by John-Jules Meyer is about logics for intelligent agents, and treats the BDI and KARO frameworks. These are modal logics tailored to the description of (the dynamics of) the mental attitudes of intelligent agents.
Computational Models for Argumentation in MAS
G.Simari and C.ChesñevarIn the last years, defeasible argumentation has proven to be a confluence point for many formalisms for commonsense reasoning. Research in Multiagent Systems (MAS) has highlighted the role of argumentation as a process which underlies different kinds of interaction among agents. In many settings, the exchange of illocutions between two agents can be conceptualized as the presentation of offers and counter-offers (equivalently, arguments and counter-arguments) in order to determine whether an original proposal is accepted or rejected. Such a dialogical setting has a natural analogy with computational models for defeasible argumentation.
The aim of this tutorial is to provide the participants with a good understanding of computational models for argumentation and their applicability to model various aspects of MAS. The tutorial will be structured in two parts. The first part will be devoted to present the fundamentals of defeasible argumentation. Practical aspects will be discussed in the context of a particular argument-based framework and its implementation. The second part will focus on how the above notions can be applied in the context of MAS, where argumentation as has been gaining increasing importance mainly as a vehicle for facilitating ``rational interaction". Particular emphasis on argument-based negotiation will be given. Most topics in the course will be covered on the basis of standard textbooks on MAS and technical surveys on defeasible argumentation, with references to recent journal articles. Participants are assumed to have a very basic knowledge of agent theory, predicate calculus, and non-monotonic reasoning.
Coordination & Development in Individual Modular Agents
Joanna BrysonThe agent community initially worked to fix AI by approaching it from the perspective of situated autonomous agents. The idea was to work not on single aspects of intelligence, but rather to bring together complete systems of interacting parts. Each part was kept as simple as possible because it could rely on the rest of the system, including the environment in which it was situated, to provide a robust, consistent (though dynamic) framework.
In the last decade though, much of the emphasis of the agent community has been on MAS and formal systems. The purpose of this tutorial will be:
- to review the history of modular single agents and describe the architectures that were developed to coordinate them.
- to introduce a methodology (Behavior Oriented Design) that facilitates the development of modular single agents.
- to introduce a coordination system (POSH action selection) and allow students to build their own agents.
We wil spend about one hour on history & architectures, including Brook's subsumption, PRS, Maes' ANA, Toby Tyrrell's PhD, Soar and ACT-R. The second hour will be a quick introduction to Behavior Oriented Design, and then we will spend an hour in the labs building humanoid agents in VR and / or artificial life.
