Intelligent Agents VIII: 8th International Workshop, ATAL 2001 Seattle, WA, USA, August 1-3, 2001 Revised Papers (Lecture Notes in Computer Science, 2333)

This Volume Is The Eighth In The Intelligent Agents Series Associated With The Atal Workshops. These Workshops On “agent Theories, Architectures, And L- Guages” Have Established Themselves As A Tradition, And Play The Role Of Small But Internationally Well-known Conferences On The Subject, Where Besides Theory Per Se Also Integration Of Theory And Practice Is In Focus. Speci?cally, Atal - Dresses Issues Of Theories Of Agency, Software Architectures For Intelligent Agents, Methodologies And Programming Languages For Realizing Agents, And Software Tools For Applying And Evaluating Agent-based Systems. Atal 2001 Featured Two Special Tracks In Which Both The More Theoretical / Formal And The More Practical Aspects Were Present, Viz. “formal Theories Of Negotiation”, Organized By Frank Dignum, And “agents For Hand-held, Mobile, Or Embedded Devices”, Organized By Tim Finin. There Was Also An Extra Session On Robocup Rescue, Organized And Presented By Satoshi Tadokoro And Ranjit Nair. Atal 2001 Attracted 68 Papers From Over 20 Countries All Over The World, Of Which 30 Were Selected For Presentation At The Workshop And Publication In This Volume. We Invited Two Outstanding Speakers: Fausto Giunchiglia (trento, Italy) And Tom Dean (brown, Usa). Introduction / John-jules Ch. Meyer And Milind Tambe -- Knowledge Level Software Engineering / Fausto Giunchiglia, Anna Perini And Fabrizio Sannicolo -- Emotions And Personality In Agent Design And Modeling / Piotr J. Gmytrasiewicz And Christine L. Lisetti -- The [psi] Calculus: An Algebraic Agent Language / David Kinny -- Evolving Real-time Local Agent Control For Large-scale Multi-agent Systems / Thomas Wagner And Victor Lesser -- On The Epistemic Feasibility Of Plans In Multiagent Systems Specifications / Yves Lesperance -- On Multi-agent Systems Specification Via Deontic Logic / Alessio Lomuscio And Marek Sergot -- Agents And Roles: Refinement In Alternating-time Temporal Logic / Mark Ryan And Pierre-yves Schobbens. John-jules Ch. Meyer, Milind Tambe (eds.). Includes Bibliographical References And Index. Also Available Via The World Wide Web. Intelligent Agents VIII Preface Program committee Workshop Organization Table of Contents Introduction Agent Modelling Formal Speci.cation and Veri.cation of Agents Agent Architectures and Languages Agent Communication Collaborative Planning and Resource Allocation Trust and Safety Formal Theories of Negotiation Agents for Hand-Held, Mobile, or Embedded Devices Knowledge Level Software Engineering 1 Introduction 2 Early Requirements 3 Late Requirements 4 Architectural Design 5 The Last Two Phases: Detailed Design and Implementation 6 Conclusions References Emotions and Personality in Agent Design and Modeling 1 Introduction 2 Decision-Theoretic Preliminaries 3 Emotional States and Personality 3.1 Transformations of the Action Space A 3.2 Transformations of the Utility Functions U 3.3 Transformations of the Probabilities of States 4 Conclusions and Future Work References The Calculus: An Algebraic Agent Language 1 Introduction 2 The Psi Agent Model 2.1 External Interactions 2.2 Representation of Internal Components 2.3 Informal Semantics of Intentions 3 Operational Semantics of Psi Computation 3.1 Semantics of Intentions 3.2 Agent Computation 4 Conclusions and Acknowledgements References Evolving Real-Time Local Agent Control for Large-Scale Multi-agent Systems 1 Introduction 2 Quantifying and Comparing Motivations 3 Scheduling and Analysis 4 Demonstrating Control via MQs 5 Conclusion, Limitations and Future Work References On the Epistemic Feasibility of Plans in Multiagent Systems Specifications 1 Introduction 2 Overview of CASL 2.1 Modeling Domain Dynamics 2.2 Modeling Agent Behavior 3 Subjective Execution 4 Deliberative Execution 5 Conclusion References On Multi-agent Systems Specification via Deontic Logic 1 Introduction 2 Deontic Interpreted Systems 2.1 Syntax 2.2 Deontic Interpreted Systems 3 Axiomatisation of Deontic Interpreted Systems 3.1 Some Secondary Properties of Kripke Frames 4 Discussion 4.1 The Logic KD45_n^{i - j} 4.2 A Notion of `Global' Correctness 5 Further Work and Conclusions References Agents and Roles: Refinement in Alternating-Time Temporal Logic 1 Introduction 2 Refinement between Agents: Example 3 Alternating-Time Temporal Logic 3.1 ATL and ATL* 3.2 Alternating Transitions Systems 3.3 Semantics 4 Refinement of Agents 4.1 Some Properties of the Refinement Relation 4.2 Horizontal Composition of Refinements 5 Conclusions References The Computational Complexity of Agent Verification 1 Introduction 2 Agents, Environments, and Tasks 3 Agent Verification 4 Types of Tasks 4.1 Achievement and Maintenance Tasks 4.2 Boolean Task Specifications 5 Related Work 6 Conclusions References A Goal-Based Organizational Perspective on Multi-agent Architectures 1 Introduction 2 Organizational Styles 3 Multi-agent Patterns 4 An e-Business Example Conclusions References - A Dynamic Logic Programming Agent Architecture 1 Introduction 2 Dynamic Logic Programming 3 Overall Architecture 4 Common Knowledge Base 5 Sub-agents 6 Related Work 7 Conclusions References Running AgentSpeak(L) Agents on SIM_AGENT 1 Introduction 2 AgentSpeak(L) 2.1 Syntax 2.2 Informal Semantics 3 SIM_AGENT 3.1 Knowledge and Reasoning 3.2 Architecture of a SIM_AGENT Agent 3.3 Execution Cycle 4 SIM_Speak 4.1 Converting an AgentSpeak(L) Agent into a SIM_AGENT Agent 4.2 A SIM_Speak Interpretation Cycle: Running an AgentSpeak(L) Agent 5 Discussion 5.1 Current Implementation 5.2 Extensions to AgentSpeak(L) 5.3 Related Work 6 Conclusion References Ontological Overhearing 1 Introduction 2 The Overhearing Architecture: An Overview 3 Overhearer - Suggester Interaction Language 3.1 The Conceptual Language 3.2 The Performative Language 3.3 The Full Temporal Language PT_{ACC} 4 Answering Queries from the Suggester 5 From Theory to Practice 6 Experimental Results 7 Some Comparisons 8 Conclusions and Future Work References Agent Dialogues with Conflicting Preferences 1 Introduction 2 Arguing with Conflicting Preferences 3 A Dialogue System 3.1 A General Framework 3.2 The Set of Agents 3.3 Dialogue Acts and Protocol 3.4 Dialogue Strategy 3.5 Properties 4 An Example 5 Conclusion References An Abstract Machine for Classes of Communicating Agents Based on Deduction 1 Introduction 2 Abstract Functional Definitions 3 A Concrete Model of Non-deterministic Agents with Sensing 4 Non-deterministic Agents with Plans A Particular Case: Priority Processes 5 Communicating Agents Based on Deduction A Concrete Model and Its Implementation Example: Two-Agent Meeting Scheduling 6 Related Work 7 Conclusion and Future Work Acknowledgement References Appendix: Towards a Prolog Implementation A Formal Semantics for ProxyCommunicative Acts 1 Introduction 2 Background Concepts 2.1 REQUEST 2.2 INFORM 3 PROXYING 3.1 NOTATION 3.2 PROXY 3.3 PROXY-WEAK 4 Discussion Acknowledgements References Commitment Machines 1 Introduction 2 Technical Framework 3 Commitment Machines 4 Compiling Commitment Machines 4.1 Compilation Formalized 4.2 Completeness 5 Discussion References A Semantics Generating Bids for Group-Related Actions in the Context of Prior Commitments 1 Introduction 2 The Setup 2.1 The Opportunity 2.2 The Combinatorial-Auction-Based Group Decision-Making Mechanism 3 Simple Temporal Networks 4 Solving the Temporal-Constraint-Generation (TCG) Problem 4.1 The TCG Problem 4.2 An Algorithm for Solving the TCG Problem 4.3 Correctness of the TCG Algorithm 5 The Task-Integration-Scheduling (TIS) Algorithm 6 Conclusions References Dynamic Distributed Resource Allocation: A Distributed Constraint Satisfaction Approach 1 Introduction 2 Domains and Motivations 3 Formalization 4 Dynamic DCSP 5 Generalized Mapping 6 Experiments in a Real-World Domain 7 Summary and Related Work References Improving Optimality of n Agent Envy-Free Divisions 1 Introduction 2 Division of a Good 2.1 Desired Characteristics of Divisions 2.2 Envy-Free Divisions with Improved Efficiency 3 Optimality of n-Agent Envy-Free Divisions 3.1 Finding Pair-Wise Envy-Free Exchanges 3.2 Choosing Optimal Envy-Free Exchanges 4 Discussion References 1 Proof of Incremental Matching Algorithm 1.1 The Difference Component Representation 1.2 Graphs Differing by One Edge 1.3 The Algorithm Trustworthiness of Information Sources and Information Pedigrees 1 Introduction 2 Essential Constituent Beliefs for Trusting Information Sources 3 Trustworthiness and Degree of Beliefs 3.1 Degree of Trustworthiness 3.2 Degree of Deception and Degree of Sincerity 3.3 The Evaluation of Competency and Sincerity w.r.t. Topics 4 Evaluating Trust on Passing-On Information Using Information Pedigree 4.1 Representing Information Pedigrees 4.2 Information Pedigree Transformation Using Trust Evaluation 5 An Example in Resolving Conflicting Information 6 Discussions and Future Work References Revisiting Asimov's First Law: A Response to the Call to Arms 1 Introduction 2 Electric Elves 3 General Approach to AA in Teams 4 Avoiding Harm: Safety Constraints 4.1 Definition of Constraints 4.2 Value Iteration with Constraint Propagation 4.3 Correctness of Propagation Algorithm 5 Evaluation 6 Summary and Related Work References Formal Theories of Negotiation References A Stable and Feasible Payoff Division for Coalition Formation in a Class of Task Oriented Domains 1 Introduction 2 Framework Description 2.1 Task Oriented Domains 2.2 Assumptions and Definitions 3 Solving the Task Allocation Problem 4 Payoff Division According to the Core 5 Conclusions and Future Works References Antisocial Agents and Vickrey Auctions 1 Introduction 2 The Dominant Strategy 3 The Antisocial Attitude 4 Antisociality and Vickrey Auctions 5 Antisocial Bidding in Repeated Auctions 5.1 Revealing Private Values by Underbidding 5.2 Step by Step Approach 5.3 Leveled Commitment Contracting 6 Experimental Results 7 Conclusions References Formalizing a Language for Institutions and Norms 1 Introduction 2 A Model Institution 3 A Language for Institutions 3.1 Ontologic and Communicational Components: The Dialogic Framework 3.2 Social Components: Scenes and Performative Structure 3.3 Normative Rules and Institutions 4 Grounding the Language 4.1 Agent Communication 4.2 Agent Mobility 5 Related Work References Simple Negotiating Agents in Complex Games 1 Introduction 2 The Contracting Problem 3 The Negotiation Protocol 4 The Objective Functions 5 Local Agent Strategies 6 Coalition Strategies 7 Simulations: Procedures and Results 8 Conclusions and Future Work References Optimal Negotiation Strategies for Agents with Incomplete Information 1 Introduction 2 Related Work 3 The Negotiation Model 4 Optimal Negotiation Strategies 4.1 Negotiation Environments 4.2 Negotiation Strategies 4.3 Optimal Strategies in Particular Environments when $beta ^s=1$ 4.4 Optimal Strategies in Particular Environments when $beta ^s not =1$ 5 Negotiation Outcomes 5.1 Conditions for Convergence of Optimal Strategies 5.2 Payoffs to Agents 6 Conclusions References Implicit Negotiation in Repeated Games 1 Introduction 2 Bimatrix Games 3 Q-learning 4 Leader Strategies 4.1 Bully 4.2 Godfather 5 Experiments 5.1 Deadlock: An Obvious Choice 5.2 Assurance: Suboptimal Preference 5.3 Prisoner's Dilemma: Incentive to Defect 5.4 Chicken: Incentive to Exploit 6 Related Work 7 Conclusions References Dialogues for Negotiation: Agent Varieties and Dialogue Sequences 1 Introduction 2 Preliminaries 3 Dialogues 4 Properties of Agent Programs 5 Agent Varieties: Concrete Examples of Agent Programs 6 Dialogue Sequences 7 Using Dialogue Sequences for Resource Reallocation 8 Conclusions References Agents for Hand-Held, Mobile, or Embedded Devices KSACI: A Handheld Device Infrastructure for Agents Communication 1 Introduction 2 Requirements 2.1 Programming Language 2.2 Agent Communication Language 2.3 Communication Infrastructure 3 Java 2 Platform, Micro Edition (J2ME) 4 KSACI 4.1 SACI 4.2 SACI Extended Architecture 4.3 Transport Protocols 4.4 Agent Communication Language 5 Related Works 6 Conclusions References LEAP: A FIPA Platform for Handheld and Mobile Devices 1 Introduction 2 Objectives of the LEAP Project 3 Architectural View of the LEAP Platform 3.1 Deployment Issues 3.2 Communication Issues 4 Conclusions and Future Work Acknowledgement References FIPA-OS Agent Platform for Small-Footprint Devices 1 Introduction 2 Problems in Running Java Agent Platform on Small-Footprint Devices 2.1 Limitations of Small-Footprint Devices 2.2 Java on Small-Footprint Devices 2.3 FIPA-OS in Small-Footprint Devices 3 Test Environment 3.1 Target Devices 3.2 Modifications to FIPA-OS 4 Performance of FIPA-OS on the Small-Footprint Devices 4.1 CaffeineMark Tests 4.2 Platform Startup Time 4.3 Agent Communication 4.4 Agent Startup Task Breakdown 4.5 XML Parsing 5 Discussion 6 Conclusion and Future Work References Author Index "This book is the eighth in the successful line of Intelligent Agents books published in LNAI. It is based on the Eighth International Workshop on Agent Theories, Architectures, and Languages, ATAL 2001, held in Seattle, WA, USA, in August 2001. The 31 revised full papers presented together with an overall introduction and two special session overviews were carefully reviewed and selected during two rounds of improvement from 68 submissions. The papers are organized in topical sections on agent modeling; formal specification and verification of agents; agent architectures and languages; agent communication; collaborative planning and resource allocation; trust and safety, formal theories of negotiation; and agents for hand-held, mobile, or embedded devices"--Publisher description