Foundations of Rational Agency APPLIED LOGIC SERIES VOLUME14 Managing Editor Dov M. Gabbay, Department of Computer Science, King's College, London, U.K. Co-Editor Jon Barwise, Department of Philosophy, Indiana University, Bloomington, IN, U.S.A. Editorial Assistant Jane Spurr, Department ofC omputer Science, King's College, London, U.K. SCOPE OF THE SERIES Logic is applied in an increasingly wide variety of disciplines, from the traditional subjects of philosophy and mathematics to the more recent disciplines of cognitive science, computer science, artificial intelligence, and linguistics, leading to new vigor in this ancient subject. Kluwer, through its Applied Logic Series, seeks to provide a home for outstanding books and research monographs in applied logic, and in doing so demonstrates the underlying unity and applicability of logic. The titles published in this series are listed at the end oft his volume. Foundations of Rational Agency edited by MICHAEL WOOLDRIDGE Queen Mary and Westfield College, London, United Kingdom and ANANDRAO Mitchell Madison Group, Melbourne, Australia SPRINGER-SCIENCE+BUSINESS MEDIA, B.V. A C.I.P. Catalogue record for this book is available from the Library of Congress. ISBN 978-90-481-5177-6 ISBN 978-94-015-9204-8 (eBook) DOI 10.1007/978-94-015-9204-8 Logo design by L. Rivlin Printed on acid-free paper AII Rights Reserved © 1999 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1999 Softcover reprint ofthe hardcover Ist edition 1999 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner EDITORIAL PREFACE The Editors are very pleased to have the present collection on agents. Agent theory is an important field at the crossroads of philosophy, artificial intelligence, computer science, practical reasoning and logic. All of the above disciplies are trying to model and understand human agents, each for their own historical reasons, some dating back to Plato and Aristotle. This area is, therefore, a meeting ground for future cooperation between all these communities. In fact, the state of the research and application is such that cooperation is necessary, in my opinion, for the successful future development of each strand. Let us hope that the publication of this book, through the agency of our series, will serve to advance cooperation between all agent resarch communities. The Editors CONTENTS A. RAO AND M. WOOLDRIDGE Foundations of Rational Agency S. RUSSELL Rationality and Intelligence 11 A. SLOMAN What Sort of Architecture is Required for a Human-like Agent? 35 J. L. POLLOCK Planning Agents 53 P. J. GMYTRASIEWICZ Toward Rational Interactions in Multiagent Domains 81 M.P. SINGH Know-How 105 W. VANDER HOEK, B. VAN LINDER AND J-J.CH. MEYER An Integrated Modal Approach to Rational Agents 133 D.R. TRAUM Speech Acts for Dialogue Agents 169 A. HADDAD! Communication among Rational Agents 203 B. J. GROSZ AND S. KRAUS The Evolution of SharedPlans 227 S.R. THOMAS A Survey of Agent-Oriented Programming 263 Y. LESPERANCE, H. J. LEVESQUE, AND R. REITER A Situation Calculus Approach to Modeling and Programming Agents 275 A. RAO AND M. WOOLDRIDGE FOUNDATIONS OF RATIONAL AGENCY 1 AGENTS AND RATIONAL AGENTS The word agent is widely used in computer science these days. It can mean any thing from a few lines of code that gets executed automatically when a certain condition is satisfied (e.g., a daemon that gets scheduled by the Operating System every day at midnight), to a more sophisticated program that can reason about its own behaviour and achieve long-term goals (e.g., an autonomous intelligent vehi cle on Mars) [13]. In addition to the simplicity or sophistication of these software entities, agents are also characterised into different types based on their function ality. Interface agents, mobile agents, believable agents, reactive agents, learning agents, and emergent agents are just a few of these types. The level of autonomy (from being completely autonomous to being intelligent assistants to humans) and the level of their interaction with physical entities (from being totally in the soft ware environment-softbots -to being intimately connected with their physical environment - robots) are also used to characterise agents. The aim of this book is not to cover this entire spectrum of agents, but rather to examine one particular type of agents- the so called rational agents [19]. Rationality as a concept has been around for a long time even before the advent of computers. Rational agents are software entities that perceive their physical or software environment through appropriate sensors; have a model and can reason about the environment that they inhabit; and based on their own mental state take actions that change their environment. The key aspects of rationality include: • balancing reactive and pro-active behaviour; • balancing perception, deliberation, and action, especially when there are limited resources; • balancing self-interest and community-interest. It is these types of agents that will be of primary interest to us. Such rational agents have been investigated in a number of application domains, including intelligent information retrieval, modeling the tactics of groups of pilots in combat scenarios, aiding air-traffic controllers in the optimal sequencing and monitoring of aircraft, and diagnosis of faults in the Space Shuttle [13, 11]. Although, we will not be looking at these applications in detail, the foundations and theories discussed in this book form an integral part of developing such systems. M. Wooldridge and A. Roo (eds.), Foundations ofR ational Agency, 1-10. @ 1999 Kluwer Academic Publishers. 2 A. RAO AND M. WOOLDRIDGE 2 HISTORY Like most sub-fields of Artificial Intelligence (AI), the study of rational agents is a truly inter-disciplinary area. One can trace the roots of rational agents to philosophy, computer science, economics, sociology, and psychology. We explore some of these fields and their contributions to the understanding of rationality and the science of building rational agents below. 2.1 Practical Reasoning Practical reasoning is a branch of philosophy that deals with how a rational agent decides to act based on its internal mental state. Some of the major concerns of this branch of philosophy include: What are the primitive mental attitudes? How do these mental attitudes translate into actions by an agent? What are the processes involved in the cycle of perception-thinking-action? How do these attitudes and processes change under limited resources? Arguably, the work from this branch of philosophy that has most influenced the notion of building rational agents is the seminal work ofBratman [3]. In his 1987 book Intentions, Plans, and Practical Reason, he argues for the primacy of inten tions in human practical reasoning, and also argues convincingly that intentions are irreducible to other mental states - in particular, desires. He thereby lays the groundwork for the attitudes of beliefs, desires, and intentions, as three separate and irreducible mental states. Beliefs capture the informational state of an agent. Unlike desires and intentions, beliefs do not play any motivational role within an agent. Desires and intentions both play a motivational role and are referred to as pro-attitudes. However, while desires merely influence the actions of an agent, in tentions control the actions that are taken by an agent. Hence, desires are referred to as conduct-influencing pro-attitudes and intentions as conduct-controlling pro attitudes. Bratman's notion of intention is closely tied with the notion of plans. Inten tions are the building blocks of larger plans. Plans are used in two contexts - as abstract structures or recipes, and as mental states that are intertwined with one's beliefs and desires. It is in the latter sense that intentions are part of the adopted or committed plans of an agent. Bratman 's contribution to rational agency extends from the static analysis of these mental attitudes and their interrelationships to the processes of means-end-reasoning, deliberation, and reconsideration that continu ously shape and modify these attitudes [4 ]. While the three mental attitudes of beliefs, desires, and intentions may be a good starting point, and arguably necessary mental attitudes for the study of ratio nal agents, it is by no means a sufficient or complete analysis of mental attitudes of rational agents. A number of researchers have examined modeling other related attitudes, such as obligation, commitment, capability, wishes, wants, power, influ ence, and countless others [ 19]. Mental attitudes are not restricted only to single agents, but can also be ascribed to groups or "societies" of agents. Mutual belief, FOUNDATIONS OF RATIONAL AGENCY 3 common knowledge, joint intention, joint goal, and social commitment are just some of the multi-agent mental attitudes that have been studied (see e.g., [14]). Rational agents are not solitary entities living in an uninhabited static envi ronment; they are embedded in a continuously changing environment and have to constantly interact with other agents. Hence, communication with other agents and interaction with the environment are key concerns within this field. The theory of speech acts and its extensions, as well as philosophical theories of action, time, and change have greatly influenced the study of rational agents (see, e.g., [6]). 2.2 Philosophical Logic While philosophical theories are based on arguments, refutations, and informal claims, philosophical logic - a synthesis of philosophy and mathematical logic - takes these claims to the next level in formalizing the assumptions, intuitions, and claims as discussed in the philosophical theories. A variety of logics based on variants of classical mathematical logics and modal logics have been used as the basis of formalizing the mental attitudes of agents and their interaction with other agents and the environment. Modal and temporal logics [7] have been extensively used to capture the men tal attitudes discussed earlier and analyze their properties. The possible-worlds semantics of such logics provide an useful abstraction with which to analyze the behaviour of rational agents. Action and program logics [ 12] have been used to capture the connection between mental attitudes and action have also influenced the operational semantics of rational agents. 2.3 Decision Theory and Game Theory While philosophical logic is concerned with capturing the relationships between different attitudes, decision theory and game theory - branches of mathematics and economics-provide a quantitative account of rationality. While decision the ory considered individual decision-making under uncertainty and individual pref erence, game theory parameterised decision-making with respect to the decisions of other agents in the environment [ 1]. 2.4 Artificial Intelligence Philosophical logic and classical decision theory contribute a great deal to the un derstanding of the general principles of rational agency. However, they invari ably consider idealized conditions in which computational considerations are not an issue. Artificial Intelligence is, as much as anything, about building rational agents [ 18], and as such it is often the test bed for experimenting with new philo sophical, psychological, and sociological theories. Bratman 's philosophical theory of intentions and the role of plans in practical reasoning came at a time when AI researchers in planning were getting disillu- 4 A. RAO AND M. WOOLDRIDGE sioned with the state-of-the art classical planning techniques (see, e.g., [9]). Search based classical planning techniques, which worked in toy problems, did not scale well to real-world problems. In particular, the lack of explicit modeling of other agents and their actions, the failure to account for a continuously changing environ ment, and the limited resources available to real computational agents, were some of the more serious drawbacks. As a result, Bratman's theory of intentions, which explicitly addressed at least two of these three drawbacks, was embraced warmly by a group of planning researchers within AI. Planning that used pre-compiled plans or recipes rather than doing first-principles classical planning came to be known as reactive planning [10]. These developments led to one of the early implementations of rational agents -the Procedural Reasoning System (PRS) [10]. This system explicitly modeled the attitudes of beliefs, goals, and intentions. The system was programmed by specifying the plans that would achieve certain goals, under certain belief condi tions. The agent dynamically adopted these hierarchical plans based on its mental state (i.e., its current beliefs, goals, and intentions). Around the same time, a number of researchers in AI planning also started ad dressing the drawbacks of classical planning using decision theory. A number of decision-theoretic and utilitarian reasoning mechanisms were developed for plan ning with limited resources in uncertain environments [2]. Both these streams influenced the architectures that emerged for rational agents. The above architectures and techniques were also enhanced to account for com munication, coordination, synchronization, and joint decision-making with other rational agents. 2. 5 Software Engineering As ideas mature from philosophy to implemented systems it gains widespread cur rency amongst a larger group of practitioners requiring easy-to-use tools, efficient languages, and well-defined analysis and design methodologies. This is when the field makes a transition from AI to a software engineering discipline. Over the past couple of years the field of rational agents is slowly making this transition. This can be seen by the increasing emphasis on architectures, language constructs, reliability, and usability concerns within the rational agent community. 3 RATIONAL AGENTS: CURRENT RESEARCH PARADIGMS 3.1 Foundations Rationality and Intelligence by Stuart Russell sets the foundation for this collec tion by examining the very definition of rational agency. He proposes four formal definitions of rationality and discusses the merits of each definition. The last of these four formal definitions - bounded optimality - grounds the notion of ra-