Teamwork in Multi-Agent Systems E-Book

Barbara Maria Dunin-Keplicz

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley Series in Agent Technology
• Sprache: Englisch

Seitenzahl: 462

Veröffentlichungsjahr: 2011

Beschreibung

What makes teamwork tick? Cooperation matters, in daily life and in complex applications. After all, many tasks need more than a single agent to be effectively performed. Therefore, teamwork rules! Teams are social groups of agents dedicated to the fulfilment of particular persistent tasks. In modern multiagent environments, heterogeneous teams often consist of autonomous software agents, various types of robots and human beings. Teamwork in Multi-agent Systems: A Formal Approach explains teamwork rules in terms of agents' attitudes and their complex interplay. It provides the first comprehensive logical theory, TeamLog, underpinning teamwork in dynamic environments. The authors justify design choices by showing TeamLog in action. The book guides the reader through a fascinating discussion of issues essential for teamwork to be successful: * What is teamwork, and how can a logical view of it help in designing teams of agents? * What is the role of agents' awareness in an uncertain, dynamic environment? * How does collective intention constitute a team? * How are plan-based collective commitments related to team action? * How can one tune collective commitment to the team's organizational structure and its communication abilities? * What are the methodological underpinnings for teamwork in a dynamic environment? * How does a team and its attitudes adjust to changing circumstances? * How do collective intentions and collective commitments arise through dialogue? * What is the computational complexity of TeamLog? * How can one make TeamLog efficient in applications? This book is an invaluable resource for researchers and graduate students in computer science and artificial intelligence as well as for developers of multi-agent systems. Students and researchers in organizational science, in particular those investigating teamwork, will also find this book insightful. Since the authors made an effort to introduce TeamLog as a conceptual model of teamwork, understanding most of the book requires solely a basic logical background.

Leseprobe

Contents

About the Authors

Foreword

Preface

1 Teamwork in Multi-Agent Environments

1.1 Autonomous Agents

1.2 Multi-Agent Environments as a Pinnacle of Interdisciplinarity

1.3 Why Teams of Agents?

1.4 The Many Flavors of Cooperation

1.5 Agents with Beliefs, Goals and Intentions

1.6 From Individuals to Groups

1.7 Group Attitudes

1.8 A Logical View on Teamwork: TEAMLOG

1.9 Teamwork in Times of Change

1.10 Our Agents are Planners

1.11 Temporal or Dynamic?

1.12 From Real-World Data to Teamwork

1.13 How Complex are Models of Teamwork?

2 Beliefs in Groups

2.1 Awareness is a Vital Ingredient of Teamwork

2.2 Perception and Beliefs

2.3 Language and Models for Beliefs

2.4 Axioms for Beliefs

2.5 Axioms for Knowledge

2.6 Relations between Knowledge and Belief

2.7 Levels of Agents’ Awareness

3 Collective Intentions

3.1 Intentions in Practical Reasoning

3.2 Language and Models for Goals and Intentions

3.3 Goals and Intentions of Individual Agents

3.4 Collective Intention Constitutes a Group

3.5 Definitions of Mutual and Collective Intentions

3.6 Collective Intention as an Infinitary Concept

3.7 Alternative Definitions

3.8 The Logic of Mutual Intention TEAMLOGmint is Complete

3.9 Related Approaches to Intentions in a Group

4 A Tuning Machine for Collective Commitments

4.1 Collective Commitment

4.2 The Language and Kripke Semantics

4.3 Building Collective Commitments

4.4 Tuning Collective Commitments

4.5 Different Notions of Collective Commitment

4.6 Topologies and Group Commitments

4.7 Summing up TEAMLOG: The Static Part of the Story

5 Reconfiguration in a Dynamic Environment

5.1 Dealing with Dynamics

5.2 The Four Stages of Teamwork

5.3 The Reconfiguration Method

5.4 Case Study of Teamwork: Theorem Proving

6 The Evolution of Commitments during Reconfiguration

6.1 A Formal View on Commitment Change

6.2 Individual Actions and Social Plan Expressions

6.3 Kripke Models

6.4 Dynamic Description of Teamwork

6.5 Evolution of Commitments During Reconfiguration

6.6 TEAMLOG Summary

7 A Case Study in Environmental Disaster Management

7.1 A Bridge from Theory to Practice

7.2 The Case Study: Ecological Disasters

7.3 Global Plans

7.4 Adjusting the TEAMLOG Definitions to the Case Study

7.5 Conclusion

8 Dialogue in Teamwork

8.1 Dialogue as a Synthesis of Three Formalisms

8.2 Dialogue Theory and Dialogue Types

8.3 Zooming in on Vital Aspects of Dialogue

8.4 Information Seeking During Potential Recognition

9 Complexity of TEAMLOG

9.1 Computational Complexity

9.2 Logical Background

9.3 Complexity of TEAMLOGind

9.4 Complexity of the System TEAMLOG

9.5 Discussion and Conclusions

A Appendix A

A.1 Axiom Systems

A.2 An Alternative Logical Framework for Dynamics of Teamwork: Computation Tree Logic

Bibliography

Index

This edition first published 2010 © 2010 John Wiley & Sons Ltd

Registered office

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book. This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold on the understanding that the publisher is not engaged in rendering professional services. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

Library of Congress Cataloging-in-Publication Data Dunin-Keplicz, Barbara.

Teamwork in multi-agent systems: a formal approach/Barbara Dunin-Keplicz, Rineke Verbrugge. p. cm.

Includes bibliographical references and index.

ISBN 978-0-470-69988-1 (cloth: alk. paper) 1. Intelligent agents (Computer software) 2. Formal methods (Computer science) 3. Artificial intelligence. I. Verbrugge, Rineke. II. Title.

QA76.76.I58D98 2010 006.3 - dc22

2010006086

To Maksymilian To Nicole

About the Authors

Barbara Dunin-Kęplicz

Barbara Dunin-Kęplicz is a Professor of computer science at the Institute of Informatics of Warsaw University and at the Institute of Computer Science of the Polish Academy of Sciences. She obtained her Ph.D. in 1990 on computational linguistics from the Jagiellonian University, and in 2004 she was awarded her habilitation on formal methods in multi-agent systems from the Polish Academy of Sciences.

She is a recognized expert in multi-agent systems. She was one of the pioneers of modeling BDI systems, recently introducing approximate reasoning to the agent-based approach.

Rineke Verbrugge

Rineke Verbrugge is a Professor of logic and cognition at the Institute of Artificial Intelligence of the University of Groningen.She obtained her Ph.D. in 1993 on the logical foundations of arithmetic from the University of Amsterdam, but shortly thereafter moved to the research area of multi-agent systems.

She is a recognized expert in multi-agent systems and one of the leading bridge builders between logic and cognitive science.

Foreword

The ability to cooperate with others is one of the defining characteristics of our species, although of course humans are by no means the only species capable of teamwork. Social insects, such as ants and termites, are perhaps the best-known teamworkers in the animal kingdom and there are many other examples. However, where the human race differs from all other known species is in their ability to apply their teamwork skills to a variety of different domains and to explicitly communicate and reason about teamwork. Human society only exists by virtue of our ability to work together in dynamic and flexible ways. Plus of course, human society exists and functions despite the fact that we all have our own goals, our own beliefs and our own abilities, and in complete contrast to social insects, we are free agents, given fundamental and important control over how we choose to live our lives.

This book investigates teamwork from the point of view of logic. The aim is to develop a formal logical theory that gives an insight into the processes underpinning collaborative effort. The approach is distinguished from related work in for example game theory by the fact that the focus is on the mental states of cooperation participants: their beliefs, desires, and intentions. To be able to express the theory in such terms requires in itself new logical languages, for characterizing the mental state of participants engaged in teamwork. As well as developing the basic model of teamwork, this book explores many surrounding issues, such as the essential link between cooperative action and dialogue.

Michael WooldridgeUniversity of Liverpool, UK

Preface

The journey of a thousand miles startsfrom beneath yourfeet.

Tao Te Ching (Lao-Tzu, Verse 64)

Teamwork Counts from Two

Barbara and Rineke met at the Vrije UniversiteitAmsterdam in the Winter of 1995. The cooperation started blooming as the spring started, mostly during long lasting research sessions in Amsterdam's famous cafe "De Jaren". Soon Rineke moved to Groningen. Then, on her autumn visits, Barbara survived two floods in Groningen, while Rineke was freezing on her winter trips to Warsaw. Over these years ("de jaren"…) they started to dream not only about some detachment from their everyday university environment, but especially about a more human-friendly climate when working together. In 2001 Barbara recalled that a place of their dreams exists in reality! Certosa di Pontignano, a meeting place of scholars, situated in the old Carthusian monastery near Siena, Italy, hosted them out of the courtesy of Cristiano Castelfranchi.

Indeed, everything helped them there. A typical Tuscan landscape, commonly considered by visitors as a paradise, the simple, ancient but lively architecture, the amazing beauty of nature, and not to forget: people! Andrea Machetti, Marzia Mazzeschi and their colleagues turned their working visits into fruitful and wonderful experiences. As Barbara and Rineke see it now, the book wouldn't have become real, if Pontignano hadn't been there for them. If one could thank this wonderful place, then they would.

Teamwork Rules

What is contemporary computer science about? Distributed, interactive, autonomous systems are surely in the mainstream, and so are planning and reasoning. These tasks are complex by their very nature, so it is not surprising that in multi-agent environments their complexity tends to explode. Moreover, communication patterns appear to be complex as well. That is where logical modeling is of great help. In this book logic helps us to build minimal, but still workable formal models of teamwork in multi-agent systems. It also lends support when trying to clarify the nature of the phenomena involved, based on the principles of teamwork and other forms of working together, as discovered in the social sciences, management science and psychology. The resulting model TEAMLoo is designed to be lively: to grow or to shrink, but especially to adjust to circumstances when needed. In this logical context, the book is not intended to guide the reader through all possible teamwork-related subjects and the vast multi-disciplinary literature on the subject. It rather presents our personal view on the merits and pitfalls of teamwork in multi-agent settings.

As prerequisites, this book assumes some initial literacy in computer science that students would gain in the first years of a computer science, cognitive science or artificial intelligence curriculum. An introductory course on propositional logic suffices to get a sense of most of the formulas. Some knowledge of modal logic would be helpful to understand the more technical parts, but this is not essential for following the main conceptual line.

As computational agents are the main citizens of this book, we usually refer to a single agent by way of 'it'. If in some example it is clear, on the other hand, that a human agent is meant, we use the conventional reference 'he/she'.

Teamwork Support Matters

First of all, we are grateful to our colleagues who joined our team in cooperative research, leading to articles which later influenced some parts of this book. In particular, we would like to thank Frank Dignum for inspiring collaboration on dialogue - we remember in particular a scientifically fruitful family skiing-and-science trip to Zawoja, Poland. We would also like to thank Alina Strachocka, whose Master's research project under Barbara's wings extended our view on dialogues during collaborative planning. Michal Slizak, one of Barbara's Ph.D. students, wrote a paper with us on an environmental disaster case study. Finally, Marcin Dziubinski's Ph.D. research under Barbara's supervision led to a number of papers on complexity of teamwork logics.

Discussions with colleagues have found various ways to influence our work. Sometimes a clever member of the audience would point out a counter-example to an early version of our theory. Other times, our interlocutors inspired us with their ideas about dialogue or teamwork. In particular, we would like to thank Alexandru Baltag, Cristiano Castelfranchi, Keith Clark, Rosaria Conte, Frank Dignum, Marcin Dziubinski, Rino Falcone, Wiebe van der Hoek, Erik Krabbe, Theo Kuipers, Emiliano Lorini, Mike Luck, and Andrzej Szalas. Still, there have been many others, unnamed here, to whom we are also indebted.

We gratefully received specially designed illustrations of possible worlds models, team structures and the overarching architecture behind TEAMLoo from Kim Does, Harmen Wassenaar, Alina Strachocka and Andrzej Szalas. In addition, Kim, Michal and Alina also offered a great support by bringing numerous technical tasks to a successful end.

A number of colleagues have generously read and commented various portions of this book. First and foremost, we are very grateful to Andrzej Szalas, who read and suggested improvements on every single chapter! We thank Alina Strachocka, Marcin Dziubiriski, Elske van der Vaart, Michal Slizak and Liliana Pechal for their useful comments on parts of the book. Our students in Groningen and Warsaw, on whom we tried out material in our courses on multi-agent systems, also provided us with inspiring feedback. We would like to thank all of them for their useful suggestions. Any remaining errors are, of course, our own responsibility. Special mention among the students is deserved for

Filip Grzadkowski, Michal Modzelewski, and Joanna Zych who inspired some examples of organizational structures in Chapter 4. Violeta Koseska deserves the credit for urging us to write a book together.

From September 2006 through January 2007, Barbara and Rineke worked as Fellows at the Netherlands Institute of Advanced Studies in the Humanities and Social Sciences (NIAS) in Wassenaar. This joint book on teamwork was to be one of the -many!- deliverables of the theme group on Games, Action and Social Software, but as is often the case with such projects, the real work of writing and rewriting takes flight afterwards. We would like to thank group co-leader Jan van Eijck for his support. Furthermore, we are grateful to the NIAS staff, in particular to NIAS rector Wim Blockmans and to NIAS head of research planning and support Jos Hooghuis, for their open-mindedness in welcoming our rather unusual project team at NIAS, and for making us feel genuinely at home.

We also highly appreciate the work of our editors at Wiley, Birgit Gruber and Sarah Tilley, for supporting us in the writing process. During the final production process, the book became a real geographically distributed team effort at Wiley, and we would like to thank Anna Smart, Alistair Smith, Shruti Duarah, Jasmine Chang, and David Ando for their contributions.

A number of grants have helped us to work on this book. Both of us would like to acknowledge a NIAS Fellowship. In addition, Barbara would like to acknowlegde the support of the Polish KBN grant7T11C 006 20, the Polish MNiSW grant N N206 399334, and the EC grant ALFEBIITE++ (A Logical Framework for Ethical Behaviour between Infohabitants in the Information Trading Economy of the Information Ecosystem, IST- 1999-1029). Moreover, Rineke would like to acknowledge the Netherlands Organisation for Scientific Research for three grants, namely NWO ASI 051-04-120 (Cognition Programme Advanced Studies Grant), NWO 400-05-710 (Replacement Grant), and NWO 016-094-603 (Vici Grant).

Finally, we would like to express our immense gratitude to our partners for their steadfast support. Also, we thank them for bearing large part of the sacrifice that goes with such a huge project as writing a book, including having to do without us for long stretches of time.

Barbara Dunin-Kę[email protected]

Rineke [email protected]

1

Teamwork in Multi-Agent Environments

The Master doesn’t talk, he acts.When his work is done,the people say, ‘Amazing: we did it, all by ourselves!’

Tao Te Ching (Lao-Tzu, Verse 17)

1.1 Autonomous Agents

What is an autonomous agent? Many different definitions have been making the rounds, and the understanding of agency has changed over the years. Finally, the following definition from Jennings et al. (1998) has become commonly accepted:

An agent is a computer system, situated in some environment, that is capable of flexible autonomous action in order to meet its design objectives.

The environment in which agents operate and interact is usually dynamic and unpredictable.

Multi-agent systems (MASs) are computational systems in which a collection of loosely-coupled autonomous agents interact in order to solve a given problem. As this problem is usually beyond the agents’ individual capabilities, agents exploit their ability to communicate, cooperate, coordinate and negotiate with one another. Apparently, these complex social interactions depend on the circumstances and may vary from altruistic cooperation through to open conflict. Therefore, in multi-agent systems one of the central issues is the study of how groups work, and how the technology enhancing complex interactions can be implemented. A paradigmatic example of joint activity is teamwork, in which a group of autonomous agents choose to work together, both in advancement of their own individual goals as well as for the good of the system as a whole. In the first phase of designing multi-agent systems in the 1980s and 1990s, the emphasis was put on cooperating teams of software agents. Nowadays there is a growing need for teams consisting of computational agents working hand in hand with humans in multi-agent environments. Rescue teams are a good example of combined teams consisting of robots, software agents and people (Sycara and Lewis, 2004).

1.2 Multi-Agent Environments as a Pinnacle of Interdisciplinarity

Variety is the core of multi-agent systems. This simple statement expresses the many dimensions immanent in agency. Apparently, the driving force underlying multi-agent systems is to relax the constraints of the previous generation of complex (distributed) intelligent systems in the field of knowledge-based engineering, which started from expert systems, through various types of knowledge-based systems, up to blackboard systems (Engelmore and Morgan, 1988; Gonzalez and Dankel, 1993; Stefik, 1995). Flexibility is essential for ensuring goal-directed behavior in a dynamic and unpredictable environment. Complex and adaptive patterns of interaction in multi-agent systems, together with agents' autonomy and the social structure of cooperative groups, determine the novelty and strength of the agent-based approach.