An Introduction to MultiAgent Systems

The study of multi-agent systems (MAS) focuses on systems in which many intelligent agents interact with each other.  These agents are considered to be autonomous entities such as software programs or robots. Their interactions can either be cooperative (for example as in an ant colony) or selfish (as in a free market economy).  This book assumes only basic knowledge of algorithms and discrete maths, both of which are taught as standard in the first or second year of computer science degree programmes.  A basic knowledge of artificial intelligence would useful to help understand some of the issues, but is not essential. The book's main aims are:

• To introduce the student to the concept of agents and multi-agent systems, and the main applications for which they are appropriate
• To introduce the main issues surrounding the design of intelligent agents
• To introduce the main issues surrounding the design of a multi-agent society
• To introduce a number of typical applications for agent technology

After reading the book the student should understand:

• The notion of an agent, how agents are distinct from other software paradigms (e.g. objects) and the characteristics of applications that lend themselves to agent-oriented software
• The key issues associated with constructing agents capable of intelligent autonomous action and the main approaches taken to developing such agents
• The key issues in designing societies of agents that can effectively cooperate in order to solve problems, including an understanding of the key types of multi-agent interactions possible in such systems
• The main application areas of agent-based systems

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