An Introduction to MultiAgent Systems, 2nd Edition

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