An Introduction to MultiAgent Systems

ISBN-13: 9780470519462 / Angielski / Miękka / 2009 / 488 str.

Michael J. Wooldridge

Opis

The eagerly anticipated updated resource on one of the most important areas of research and development: multi-agent systems

Multi-agent systems allow many intelligent agents to interact with each other, and this field of study has advanced at a rapid pace since the publication of the first edition of this book, which was nearly a decade ago. With this exciting new edition, the coverage of multi-agents is completely updated to include several areas that have come to prominence in the last several years, including auctions, computational social choice, and markov decision processes. In turn, a variety of topics that were initially considered critical have dwindled in importance, so the coverage of that subject matter is decreased with this new edition. The result of this redefined balance of coverage is a timely and essential resource on a popular topic. Introduces you to the concept of agents and multi-agent systems and the main applications for which they are appropriate Discusses the main issues surrounding the design of intelligent agents and a multi-agent society Delves into a number of typical applications for agent technology Addresses deductive reasoning agents, practical reasoning agents, reactive and hybrid agents, and more Reviews multi-agent decision making, communication and cooperation, and intelligent autonomous agents By the end of the book, you will have a firm grasp on how agents are distinct from other software paradigms and understand the characteristics of applications that lend themselves to agent-oriented software.

Recenzje

“Nevertheless, despite these minor issues, this book is highly recommended to all socio–economic agent–based modellers, beginners or otherwise. Wooldridge’s scope, rigor, and well–respected experience at the current coalface means there’s plenty in here of interest for old–timers, while beginners can skip some of the maths and more bleeding–edge theory and concentrate easily on the implementation without loosing much.”  (Appl. Spatial Analysis, 2011)

 

Spis treści

Preface xiii

Acknowledgements xxi

Part I Setting the Scene 1

1 Introduction 3

1.1 The Vision Thing 6

1.2 Some Views of the Field 9

1.2.1 Agents as a paradigm for software engineering 9

1.2.2 Agents as a tool for understanding human societies 12

1.3 Frequently Asked Questions (FAQ) 12

Part II Intelligent Autonomous Agents 19

2 Intelligent Agents 21

2.1 Intelligent Agents 26

2.2 Agents and Objects 28

2.3 Agents and Expert Systems 30

2.4 Agents as Intentional Systems 31

2.5 Abstract Architectures for Intelligent Agents 34

2.6 How to Tell an Agent What to Do 38

3 Deductive Reasoning Agents 49

3.1 Agents as Theorem Provers 50

3.2 Agent–Oriented Programming 55

3.3 Concurrent MetateM 56

4 Practical Reasoning Agents 65

4.1 Practical Reasoning = Deliberation +Means–Ends Reasoning 65

4.2 Means–Ends Reasoning 69

4.3 Implementing a Practical Reasoning Agent 75

4.4 The Procedural Reasoning System 79

5 Reactive and Hybrid Agents 85

5.1 Reactive Agents 85

5.1.1 The subsumption architecture 86

5.1.2 PENGI 90

5.1.3 Situated automata 90

5.1.4 The agent network architecture 91

5.1.5 The limitations of reactive agents 92

5.2 Hybrid Agents 92

5.2.1 Touring Machines 94

5.2.2 InteRRaP 96

5.2.3 3T 98

5.2.4 Stanley 99

Part III Communication and Cooperation 105

6 Understanding Each Other 107

6.1 Ontology Fundamentals 108

6.1.1 Ontology building blocks 108

6.1.2 Anontology of ontologies 110

6.2 Ontology Languages 113

6.2.1 XML–adhoc ontologies 113

6.2.2 OWL–The web ontology language 114

6.2.3 KIF–ontologies in first–order logic 120

6.3 RDF 121

6.4 Constructing an Ontology 124

6.5 Software Tools for Ontologies 127

7 Communicating 131

7.1 Speech Acts 132

7.1.1 Austin 132

7.1.2 Searle 133

7.1.3 The plan–based theory of speech acts 134

7.1.4 Speech acts as rational action 135

7.2 Agent Communication Languages 136

7.2.1 KQML 136

7.2.2 The FIPA agent communication language  140

7.2.3 JADE 146

8 Working Together 151

8.1 Cooperative Distributed Problem Solving 151

8.2 Task Sharing and Result Sharing 153

8.2.1 Task sharing in the Contract Net 156

8.3 Result Sharing 159

8.4 Combining Task and Result Sharing 159

8.5 Handling Inconsistency 161

8.6 Coordination 162

8.6.1 Coordination through partial global planning 163

8.6.2 Coordination through joint intentions 165

8.6.3 Coordination by mutual modelling 170

8.6.4 Coordination by norms and social laws 173

8.7 Multiagent Planning and Synchronization 177

9 Methodologies 183

9.1 When is an Agent–Based Solution Appropriate? 183

9.2 Agent–Oriented Analysis and Design 184

9.2.1 The AAII methodology 184

9.2.2 Gaia 186

9.2.3 Tropos 187

9.2.4 Prometheus 188

9.2.5 Agent UML 188

9.2.6 Agents in Z 189

9.3 Pitfalls of Agent Development 190

9.4 Mobile Agents 193

10 Applications 201

10.1 Agents for Workflow and Business Process Management 201

10.2 Agents for Distributed Sensing 203

10.3 Agents for Information Retrieval and Management 205

10.4 Agents for Electronic Commerce 211

10.5 Agents for Human–Computer Interfaces 213

10.6 Agents for Virtual Environments 214

10.7 Agents for Social Simulation 214

10.8 Agents for X  218

Part IV Multiagent Decision Making 221

11 Multiagent Interactions 223

11.1 Utilities and Preferences 223

11.2 Setting the Scene 226

11.3 Solution Concepts and Solution Properties 229

11.3.1 Dominant strategies 230

11.3.2 Nash equilibria 230

11.3.3 Pareto efficiency 233

11.3.4 Maximizing social welfare 235

11.4 Competitive and Zero–Sum Interactions 235

11.5 The Prisoner’s Dilemma 236

11.5.1 The shadow of the future 240

11.5.2 Program equilibria 243

11.6 Other Symmetric 2 ×2Interactions 245

11.7 Representing Multiagent Scenarios 248

11.8 Dependence Relations in Multiagent Systems 249

12 Making Group Decisions 253

12.1 Social Welfare Functions and Social Choice Functions 253

12.2 Voting Procedures 255

12.2.1 Plurality 255

12.2.2 Sequential majority elections 257

12.2.3 The Borda count 260

12.2.4 The Slater ranking 260

12.3 Desirable Properties for Voting Procedures 261

12.3.1 Arrow’s theorem 263

12.4 Strategic Manipulation 264

13 Forming Coalitions 269

13.1 Cooperative Games 270

13.1.1 The core 272

13.1.2 The Shapley value 274

13.2 Computational and Representational Issues 277

13.3 Modular Representations 278

13.3.1 Induced subgraphs 278

13.3.2 Marginal contribution nets 280

13.4 Representations for Simple Games 281

13.4.1 Weighted voting games 282

13.4.2 Network flow games 285

13.5 Coalitional Games with Goals 287

13.6 Coalition Structure Formation 288

14 Allocating Scarce Resources 293

14.1 Classifying Auctions 294

14.2 Auctions for Single Items 295

14.2.1 English auctions 295

14.2.2 Dutch auctions 296

14.2.3 First–price sealed–bid auctions 296

14.2.4 Vickrey auctions 296

14.2.5 Expected revenue 297

14.2.6 Lies and collusion 298

14.2.7 Counter speculation 299

14.3 Combinatorial Auctions 299

14.3.1 Bidding languages 302

14.3.2 Winner determination 306

14.3.3 The VCG mechanism 308

14.4 Auctions in Practice 310

14.4.1 Online auctions 310

14.4.2 Adwords auctions 311

14.4.3 The trading agent competition 312

15 Bargaining 315

15.1 Negotiation Parameters 315

15.2 Bargaining for Resource Division 317

15.2.1 Patient players 317

15.2.2 Impatient players 320

15.2.3 Negotiation decision functions 321

15.2.4 Applications of alternating offers 323

15.3 Bargaining for Task Allocation 323

15.3.1 Themonotonic concession protocol 326

15.3.2 The Zeuthen strategy 327

15.3.3 Deception 329

15.4 Bargaining for Resource Allocation 330

16 Arguing 337

16.1 Types of Argument 338

16.2 Abstract Argumentation 338

16.2.1 Preferred extensions 339

16.2.2 Credulous and skeptical acceptance 341

16.2.3 Preferences in abstract argument systems 343

16.2.4 Values in abstract argument systems 344

16.3 Deductive Argumentation Systems 345

16.4 Dialogue Systems 348

16.5 Implemented Argumentation Systems 350

17 Logical Foundations 355

17.1 Logics for Knowledge and Belief  355

17.1.1 Possible–worlds semantics for modal logics 357

17.1.2 Normal modal logics 358

17.1.3 Normal modal logics as epistemic logics 361

17.1.4 Logical omniscience 363

17.1.5 Axioms for knowledge and belief 364

17.1.6 Multiagent epistemic logics 365

17.1.7 Common and distributed knowledge 367

17.2 Logics for Mental States 369

17.2.1 Cohen and Levesque’s intention logic 369

17.2.2 Modelling speech acts 371

17.3 Logics for Cooperation 373

17.3.1 Incomplete information 375

17.3.2 Cooperation logics for social choice 376

17.4 Putting Logic to Work 376

17.4.1 Logic in specification 377

17.4.2 Logic in implementation 378

17.4.3 Logic in verification 381

Part V Coda 391

A A History Lesson 393

B Afterword 405

Glossary of Key Terms 407

References 425

Index 453

O autorze

Michael Wooldridge is a Professor of Computer Science at the University of Liverpool, UK. He obtained his PhD in 1992 for work in the theory of multiagent systems and has, since then, been active in multiagent systems research.

Blurb

"A thoroughly revised and updated book, written by one of the leading researchers in the field. This excellent book provides a wonderful introduction and a comprehensive exposition of the increasingly important field of multi–agent systems."
—Professor Nick Jennings FREng
Intelligence, Agents, Multimedia Group, Electronics and Computer Science, University of Southampton

Multiagent systems are a new paradigm for understanding and building distributed systems, where it is assumed that the computational components are autonomous: able to control their own behaviour in the furtherance of their own goals. The first edition of An Introduction to Multiagent Systems was the first contemporary textbook in the area, and became the standard undergraduate reference work for the field. This second edition has been extended with substantial new material on recent developments in the field, and has been revised and updated throughout. It provides a comprehensive, coherent, and readable introduction to the theory and practice of multiagent systems, while presenting a wealth of discussion topics and pointers into more advanced issues for those wanting to dig deeper.

Key new features include:

• dedicated new chapters on ontologies, voting, auctions, bargaining, coalition formation, and argumentation, reflecting recent research directions and new results;
• "mind maps" to illustrate key concepts and ideas – an essential study and revision aid;
• 590 literature references, revised, updated, and extended to reflect the state of the art in agent research and development.

Designed and written specifically for computing undergraduates, the book comes with a rich repository of online teaching materials, including a complete set of lecture slides.