AAMAS 2010 Tutorial: Organised Adaptation in Multi-Agent Systems

 

 

Tutorial Description

Adaptation, for purposes of self-healing, self-management, or self-optimisation, taking advantage of new opportunities and responding to threats in the environment, is currently considered to be one of the most challenging properties of distributed, multi-agent systems (MAS) that operate in dynamic, unpredictable and potentially hostile environments. Engineering for adaptation is particularly complicated when the distributed system itself is composed of autonomous entities that, on one hand, may act collaboratively, either with benevolence or by obeying social rules, and, on the other, may behave selfishly, pursuing their own interests. Still, these entities have to coordinate themselves in order to adapt appropriately to the prevailing environmental conditions, and furthermore, to deliberate upon their own and the system's configuration, being transparent to their users yet consistent with any human requirements. The question, therefore, of “how to organise the envisaged adaptation for such autonomous entities in a systematic way” becomes of paramount importance.

A new specification or configuration of a MAS may unintentionally emerge from the local interactions of its members, or it may be the result of more organised activities. In this tutorial we intend to go beyond emergent behaviour seen, for example in swarm intelligence, i.e. the non-introspective application of hard-wired local computations, with respect to the environment and/or physical rules, which achieve unintended or unknown global outcomes. Instead, we are concerned with the introspective application of soft-wired local computations, with respect to the environment, physical rules and conventional rules (what some philosophers of language would call 'constitutive rules'), in order to achieve intended and coordinated global outcomes. This conscious, deliberate and targeted adaptation of a specification and/or configuration of a MAS is the focus of what we call organised adaptation.

Organised adaptation may take place at several different levels with different motivations. For example, the operating environment may need to be adjusted by controlled introduction or removal of new resources. Alternatively, changes in the environment may cause the existing members of the MAS to re-organise themselves, in an orderly manner, to optimise or preserve some specific system functionality. At another level of adaptation, existing members may leave the MAS, and new agents may be introduced; or institutionally empowered agents, such as the ‘board of directors’ of a virtual organisation, may decide to act on proposals for improving or innovating the services offered by the organisation. This might require that current members are allocated to different roles. Furthermore, the roles themselves may be the subject of adaptation, in which case the eligibility conditions for occupying a role, and/or the permissions, obligations, authorities, entitlements, responsibilities, institutional powers, and other normative positions that are associated with a role, are also subject to adaptation.

This tutorial will therefore focus on several dimensions of organised adaptation. We will present the parameters of organised adaptation, and critically review the state-of-the-art focusing on the fields of multi-agent systems, norm change, and autonomic computing and communications. Moreover, we will present the future challenges of organised adaptation. Participants will gain a deeper insight into and understanding of a range of issues in engineering adaptive systems, including design-time, and run-time specification of organised adaptation, run-time-control of organised adaptation, and systems architectures for and applications of organised adaptation.

Structure

This is a half-day tutorial structured into four 1 hour sessions. In overview, the four sessions will develop a thematic analysis of organised adaptation, from the state-of-the-art through to future challenges. The state-of-the-art will be reviewed along the following dimensions:

What is adapted? Several aspects of a MAS may be modified such as the system norms, the structure of a system, the assignment of roles to agents, the assignment of goals to a system, and the relationships (trading, and other) between the agents.

Why is adaptation performed? Environmental, social or other conditions may favour, or even require, organised adaptation. Consider, for instance, the case of a malfunction of a large number of sensors in a sensor network, or the case of manipulation of a voting procedure due to strategic voting, or when an organisation conducts its business in an inefficient manner. Organised adaptation may take place in order to better achieve the local, private goals of some agent - in this case an agent attempts to initiate the process of adaptation - or the global goals, if there are any - in this case designated agents, sometimes called 'institutional agents', initiate the process of adaptation. In any case, it cannot always be assumed that information about environmental, social or other conditions will be complete or reliable.

How is adaptation performed? It is often the case that the process of adaptation is specified at design-time, that is, it is specified before the system execution which component will be adapted at each state. In this case, adaptation is typically driven by designated agents. An alternative approach to adaptation is to decide at run-time which system component should be modified (if any). In this case adaptation may be driven by designated agents, or the system may allow for any member to participate in the decision-making over adaptation. For instance, the system members may negotiate over, vote for or against, or argue about a proposed modification.

Evaluation of Adaptation. Different types of metric are employed to evaluate the outcome of adaptation, either from a local, agent-specific perspective, or from a global perspective. Depending on the point of view, the outcome of adaptation may be positively or negatively evaluated - for example, changing the system norms in a particular way may be regarded beneficial for a particular agent, as opposed to other system members.

The 4 sessions of the tutorial are described below:

PART I. Introduction & Organised Adaptation in Multi-Agent Systems

  • Organised Adaptation vs Emergence
  • Examples of Organised Adaptation
  • What, Why, How to Adapt, and Evaluation of Adaptation: Requirements and Implications
  • Adaptive Multi-Agent Systems --- Significant Approaches
    • adapting system structure & behaviour
    • adapting decision-making frameworks
    • adapting the allocation of tasks and resources
    • programming organised adaptation
  • Organised Adaptation in Multi-Agent Systems: Open Issues

PART II. Norm Change as Organised Adaptation

  • Types of Norm Change
  • Relations between Norms, Abilities and Preferences
  • Logics for Norm Change
    • Representation languages
    • Reasoning tasks
    • Routes to implementation
  • Significant Approaches
    • Dynamic argument systems
    • Autonomic institutions
    • Dynamic communication protocols
  • Norm Change as Organised Adaptation: Open Issues

PART III. Organised Adaptation in Autonomic Computing and Communications

  • Background and Drivers
  • The Self-* properties
    • Self-healing
    • Self-organisation
    • Self-management and –optimisation
  • Significant Approaches
    • A reference implementation
    • Co-operating autonomic managers
    • Biologically- and physically-inspired approaches
  • Organised Adaptation in Autonomic Computing: Open Issues

PART IV. Challenges of Organised Adaptation

  • Bringing it all together: Multi-Agent Systems, Norm Change, and Autonomic Computing
  • Organised Adaptation in Non-Cooperative Systems
  • Organised Adaptation in Large-Scale Systems
  • Design-time Specified Adaptation vs Run-time Specified Adaptation
  • Machine Learning for Organised Adaptation
  • Metrics for the Evaluation of Organised Adaptation

Intended Audience

The intended audience of the tutorial consists of academics and practitioners from the fields of multi-agent systems, autonomic computing, and norm change, as well as computer science students that have some familiarity with the multi-agent systems literature.

Computational systems such as formal organisations, electronic institutions and computational economies, often have to adapt in order to address, among others, environmental, social, and economic changes. It is evident, therefore, that researchers aiming to build such systems need to be aware of techniques for organised adaptation.

Presenters

Alexander Artikis is a Research Associate in the Institute of Informatics & Telecommunications at the National Centre for Scientific Research ''Demokritos'', in Athens, Greece. He holds a PhD from Imperial College London on the topic of norm-governed multi-agent systems. His research interests lie in the areas of distributed artificial intelligence, temporal representation and reasoning, AI & Law, and description logics. He has published papers in related journals, conferences and workshops, such as the Artificial Intelligence Journal, the ACM Transactions on Computational Logic, and the Logic Journal of the IGPL. Dr. Artikis has been teaching undergraduate courses on Logic, and Distributed Artificial Intelligence, in the University of Piraeus, Greece. He has served as a member of the program committees of several workshops and conferences, including AAMAS, and has co-organised in the last two years four international workshops, including two AAMAS workshops.

Simon Dobson is Professor of Computer Science in the School of Computer Science at the University of St Andrews. His research interests centre around the design, analysis and construction of highly adaptive, highly sensorised computing systems. He is a recognised expert in the fields of autonomic and pervasive computing, a reputation supported by over 100 internationally peer-reviewed publications and a leadership role in research grants worth over EUR30M. He has served, amongst other activities, as programme and general chair for the IEEE International Conference on Autonomic Computing; as an invited editor for Computer Networks; on the editorial board of the Journal of Network and Systems Management; and on the programme committees of a wide range of international workshops and conferences. He was a director and vice-president of the European Research Consortium for Informatics and Mathematics from 2006 — 2009, and has served on a number of national and EU committees and strategic initiatives. He was also the founder and CEO of a research-led start-up company. He holds a BSc and DPhil in computer science, is a Chartered Fellow of the British Computer Society, a Chartered Engineer and Senior Member of the IEEE.

Jeremy Pitt is a Reader in Intelligent Systems in the Electrical & Electronic Engineering Department of Imperial College London. He has been a researcher in Multi-Agent Systems for the the past 15 years, and has contributed to the ideas of agent societies, institutions, and organisations, and more recently has studied the logical and computational foundations of participative and adaptive behaviours in mechanism design (primarily voting) in multi-agent systems. He has published extensively in the field (over 100 papers, h-index 20), and was active in the standards body FIPA from 1997 until 2001. He is a Senior Program Committee member for AAMAS, and is a member of the Steering Committee for the Engineering Societies in the Agents World (ESAW) and Coordination, Organisations, Institutions and Norms (COIN) workshops. As well delivering full undergraduate lecture courses in Software Engineering, Human-Computer Interaction, and Artificial Intelligence, he has previously given Tutorials on Multi-Agent Systems at the ECMAST'97 and '98 conferences. He has been an accredited teacher of the University of London and Imperial College since 1996, is a Senior Member of the ACM, and is a member of the IET.

George Vouros holds a BSc in Mathematics, and a PhD in Artificial Intelligence all from the University of Athens, Greece. Currently he is a Professor in the University of the Aegean, Greece, and President of the Hellenic Society of Artificial Intelligence. He has done research in the areas of Expert Systems, Knowledge management, Collaborative Systems, Ontologies, and Agents and Multi-Agent Systems. His published scientific work includes book chapters, journal and national and international conference papers in the above mentioned themes. He has served as chair and member of organising committees of national and international workshops/conferences on related topics. Concerning adaptation in multi-agent systems he has co-chaired two workshops (CEAS@ECAI04 and OAMAS@AAMAS08) and he has served as co-editor in a related special issue published in IJCIS. He is member of the COIN steering committee and has served as member of program committee in AAMAS conferences, where he has published work concerning agent organisations and their adaptation.

Alexander Artikis