Strategic Directions in Artificial Intelligence
JON DOYLE
Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MA doyle@mit.edu; http://www.medg.lcs.mit.edu/doyle THOMAS DEAN ET AL.1
Brown University, Providence, RI tld@cs.brown.edu; http://www.cs.brown.edu/people/tld/home.html 1. WHAT IS ARTIFICIAL INTELLIGENCE? The field of artificial intelligence (AI) consists of long-standing intellectual and technological efforts addressing several interrelated scientific and practical aims: --constructing intelligent machines, whether or not these operate in the same way as people do; --formalizing knowledge and mechanizing reasoning, both commonsense and refined expertise, in all areas of human endeavor;
1 --using computational models to understand the psychology and behavior of people, animals, and artificial agents; and --making working with computers as easy and as helpful as working with skilled, cooperative, and possibly expert people. Even considering only the first two of these aims, AI has perhaps the broadest concerns of all areas of computing research, covering investigations ranging from the natural sciences to the social, from engineering to economics, physics to psychology. Its very nature forces AI to grapple with the complexity of the natural world as well as that of the artificial systems that form the subject matter of computing studies generally. Its main theoretical questions stand as peers of the deepest and most important questions in any scientific field, and its practical impact on living promises to equal that of any known technology. The aims of AI reflect ancient dreams of using minds and hands to create beings like ourselves. In centuries past, pursuit of these dreams gave rise to both mechanical automata and formal theories of reasoning, eventually yielding the spectacularly successful modern artificial computers that, in calculating and computing, replicate and surpass This report represents the efforts of the Strategic Directions in Computing Research AI Working Group--Ronald Brachman, Thomas Dean (CoChair), Johan de Kleer, Thomas Dietterich, Jon Doyle (Co-Chair), Cordell Green, Barbara Grosz, Ian Horswill, Leslie Pack Kaelbling, Daphne Koller, Joseph Marks, Fernando Pereira, Bart Selman, Yoav Shoham, Howard Shrobe, William Swartout, Michael Wellman, and Shlomo Zilberstein--formed as part of the ACM Workshop on Strategic Directions in Computing Research, held at the Massachusetts Institute of Technology Laboratory for Computer Science on June 14­15, 1996. Group members worked out the underlying ideas of this report at the meeting, aided by prior discussions and their individual position statements. Ron Brachman presented a talk on strategic directions in AI to the workshop as a whole. The general structure of this report derives from his talk, augmented through many contributions by the preceding. The editors, of course, bear the responsibility for any flaws. Permission to make digital / hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and / or a fee. © 1996 ACM 0360-0300/96/1200­0653 $03.50 ACM Computing Surveys, Vol. 28, No. 4, December 1996 654 · J. Doyle et al. tific discovery techniques and hypothesized neurophysiological mechanisms to procedures that extract a wide range of general trends, facts, and techniques from instruction, experience, and collected data; deliberation, planning, and acting concerns methods for making decisions, constructing plans or designs to achieve specified goals, and monitoring, interpreting, diagnosing, and correcting the performance of the plans and implementations of the designs; speech and language processing seeks to create systems capable of communicating in and translating among natural written and spoken languages; image understanding and synthesis develops algorithms for analyzing photographs, diagrams, and realtime video image streams, as well as techniques for the customized presentation of quantitative and structured information; manipulation and locomotion seeks to replicate and surpass the abilities of natural hands, arms, feet, and bodies; autonomous agents and robots integrates the other areas to create robust, active entities capable of independent, intelligent, real-time interactions with an environment over an extended period; multiagent systems identifies the knowledge, representations, and procedures needed by agents to work together or around each other; cognitive modeling focuses on contributing techniques and constructing integrated architectures that replicate structural or behavioral features of human cognition; and mathematical foundations takes the concepts and techniques of the other areas as subjects for formalization, distillation, analysis, and reconceptualization. abilities that people of earlier times regarded as intellectual activities on a par with writing letters and playing good chess. Using these computers over the past four decades, modern AI has built on the best thinking in a number of areas--especially computer systems, logic, the mathematical theory of computation, psychology, economics, control theory, and mathematical problem solving--to construct concrete realizations of devices that --solve intellectual problems both theoretical and practical, common and esoteric; --control robot motions through planning, sight, touch, and self-awareness; --interpret human language, both written and spoken; and --learn new skills and knowledge through instruction, from experience, and by analyzing other data. Some of these realizations have proven highly successful, others rudimentary and incomplete, but each captures recognizable and significant elements of human capabilities and provides a skeleton upon which future research may enlarge. One can divide present-day AI research into the following primary and (overlapping) areas.2 (1) knowledge representation and articulation seeks to discover expressive and efficient forms and methods for representing information about all aspects of the world and to use these methods to create and compile explicit, formal, multipurpose catalogs of substantive knowledge; (2) learning and adaptation extends statistical, analytical, and scien2 (3) (4) (5) (6) (7) (8) (9) The list of areas of AI and their descriptions draws some text from the corresponding list appearing in Weld et al. [1995]. The borrowed text is Copyright © 1995 American Association for Artificial Intelligence, and is reprinted with permission from AAAI. (10) ACM Computing Surveys, Vol. 28, No. 4, December 1996 Artificial Intelligence These areas form but one categorization of work in the field; other such lists have been suggested in the past, and categorizations will again change as problems are solved and new ones are identified. Consequently, no such list constitutes a definition of AI. For that matter, neither do other common misapprehensions, such as defining AI in terms of the activities of a particular group of people, or the use of a particular set of methods or programming languages, or as a label for computing research that does not come under some other heading. The first two of these mistake accident for essence, and the last incorrectly divides the computing field. AI is not a list of areas or a methodology, even less a group or a catch-all label, but consists of work on the enduring and intriguing aims of understanding intelligent beings and constructing intelligent systems.
2. PROBLEMS OF FORMULATION · 655 AI has won its successes only with great effort. In earlier times, researchers used informal means to specify the problems under investigation, and their work revealed the great difficulty of formulating these problems in precise terms. Solving these problems of formulation [Minsky 1962] required considerable experimentation with and exploration of alternative conceptualizations in order to find appropriate ways of making them amenable to technical investigation and solution. Although logic, game theory, and other disciplines contributed formal approaches to specifying these problems, their methods often missed the mark in essential ways, especially by begging AI's question through presuming too much reasoning power and coherence on the part of the agent. In coming to new formulations, AI has often advanced these other fields, providing the first precise means for addressing problems shared with them. Researchers in AI have traditionally met problems of formulation joyfully, courageously, and proudly, accepting the severe risks ensuing from such exploratory work in pursuit of the proportionately large gains that can result from finding successful formulations. The willingness to cultivate problems lacking ready formalizations has also engendered some disrespect for AI, as observers focus on the failures rather than on the successes. However, this adventurousness has proven highly fruitful, creating whole new subfields for formal investigation. Though some important problems still lack adequate formalizations, for many others AI has successfully provided formal foundations supporting rich areas of technical investigation. AI has undergone a sea-change in the general character of its research methodology since about 1980, partly through progress on its problems of formulation, and partly through increasing integration with related areas of computing research and other fields. Speculative exploratory work remains necessary in investigations of many difficult issues. In particular, the natural or useful scope of the formalized knowledge employed in an investigation does not always admit simple formally satisfying characterizations, so the field retains an element of conceptual exploration. The more typical research effort today, however, relies on formal, theoretically precise, and experimentally sophisticated methods for investigation and technical communication. Rigorous science, engineering, and mathematics now overshadow other work in much of the literature. Recent AI also replaces the focus of the early analytical studies on using isolated "toy" domains with a focus on using realistically broad and large-scale problem domains, and concentrates much more on integrating its ideas, systems, and techniques into standard computing theory and practice. These changes not only complement the increase in precision and formality, but demand additional rigor in order to enforce the conventions and coherence
ACM Computing Surveys, Vol. 28, No. 4, December 1996 656 · J. Doyle et al. One can appreciate the intellectual productivity of AI through the subjects it launched or has helped launch as independent areas of research, including artificial neural networks, automated deduction, constraint programming, heuristic search, integrated software development environments, logic programming, object-oriented programming, mechanized symbolic mathematical calculation, and program synthesis and verification methods. One should also note the major contributions AI has made to symbolic computing and functional programming. Both have been stimulated in fundamental ways through the sustained development and use of LISP and its relatives in AI research. AI has made important contributions to computational linguistics, to the area of epistemic logics (especially through nonmonotonic logics, theories of belief revision, and the computational applications now also heavily used in the theory of distributed systems), and to economics and operations research (where AI methods of heuristic search, especially stochastic heuristic search, have caused something of a revolution). AI has also served computing research as a prime exporter to other scientific fields of the notion of studying processes in their own right. AI models of process and information processing in language, reasoning, and representation have caused major shifts in linguistics, psychology, philosophy, and organization theory (e.g., with rule-based systems and artificial neural networks providing a "rehabilitation" of the impoverished and formerly stagnating behavioristic approach to psychology), and AI models now figure prominently in each of these fields. In addition to changing scientific fields, some AI methodologies (especially expert knowledge-based systems, artificial neural networks, and fuzzy systems) have changed the perspective of many engineers, who now go beyond the traditional concerns of algorithms and data to capture the knowledge or expertise underlying desired functionalities. The manifold practical applications of necessary in scaling up and integrating systems. Accompanying this change in the character of AI results and research, accepted methods of educating students in AI have changed to recognize many prerequisites sometimes overlooked in years past. To understand the literature and make good in their own work, modern AI students must learn the basics of a number of fields: logic, statistics, decision theory, stochastic processes, analysis of algorithms, complexity theory, concurrency, and computational geometry, to name but a few.
3. CONTRIBUTIONS Some highlights of the major contributions of AI to computing, and to science more generally, include artificial neural networks, automated deduction, autonomous and semi-autonomous mobile robots, computational qualitative reasoning (about physical systems), constraint programming, data-mining systems, decision-tree learning methods, description logics (structured declarative representations going beyond those structures common in traditional logic), design and configuration systems, evolutionary computation, expert or knowledge-based systems (based on corpora of explicit mainly declarative knowledge), fuzzy logic and control systems, graphical representations of uncertain information (Bayesian belief networks and others), heuristic search, logic and rule-based programming systems, mechanized symbolic mathematical calculation, natural language understanding and generation systems, nonmonotonic logics (a new category of logic formalizing assumption making), planning and scheduling systems, program synthesis and verification methods, real-time speakerindependent speech understanding, reason or truth maintenance systems (systematic recording and reuse of reasoning steps), robotic assembly systems, text processing and retrieval systems, and visual classification and registration systems.
ACM Computing Surveys, Vol. 28, No. 4, December 1996 Artificial Intelligence AI continue to expand every year. The following few examples give the flavor of current successes, but one may find many more in the proceedings of the annual AAAI conference on Innovative Applications of Artificial Intelligence, in recent issues of Communications of the ACM (e.g., the November 1995 and January, February, April, May, and August 1996 issues), and in other sources in the literature. Probabilistic diagnostic systems, based on graphical uncertainty representations, form a large class of successful applications, including the Intellipath pathology diagnosis system approved by the American Medical Association [Heckerman 1991], the VISTA monitoring and analysis system used by NASA for space shuttle mission control [Horvitz et al. 1992], and even the printer diagnosis and "wizard" subsystems of Microsoft software [Heckerman et al. 1995]. Artificial neural networks also appear in many successful systems, from automated Pap smear diagnosis to online handwriting recognition [Lyon and Yaeger 1996] and vehicle navigation [Jochem and Pomerleau 1996]. Fuzzy logic systems have been applied to many problems including camera and appliance control. Design and configuration systems form a large class in everyday use, with the largest, such as AT&T's PROSE and QUESTAR systems, processing orders worth billions of dollars [Wright et al. 1993]. Expert knowledge-based systems abound, with applications from credit authorization and detection of money laundering [Senator et al. 1995] to highly skilled simulations of helicopter pilots [Tambe et al. 1995] and great numbers of knowledgeable help-desk (customer service) systems. The automatically synthesized KTS (Kestrel Transportation Scheduler) software has proven startlingly efficient in large-scale scheduling applications [Smith et al. 1996], and knowledge-based planning and scheduling systems now yield dramatic improvements in manufacturing efficiency and productivity [Naj 1996]. Speech-understanding technology has begun to · 657 have commercial impact, from control aids for the manually impaired to the replacement of telephone operators. Machine-vision systems now find routine use in industrial inspection and assembly processes and play increasingly important roles in the analysis of medical imagery, from the analysis of radiographs to helping surgeons operate on the correct areas of the brain [Grimson et al. 1996]. Clinical trials now in progress seek to evaluate a wide range of computer-aided surgical procedures, including the use of surgical robotic devices in hip replacement surgery. Applications in automatic vehicle control have only reached the demonstration stage (CMU's RALPH vehicle drove across the continental United States with minimal human intervention [Jochem and Pomerleau 1996]), but promise more widespread applications in the near future. Machine-learning methods have successfully automated the analysis of astronomical data and found new classifications for astronomical objects [Goebel et al. 1989]. To these one must add the "impractical" but impressive success of game-playing systems, which through systematic exploitation of AI search techniques and special-purpose hardware now hold the position of the world's best checkers player [Schaeffer et al. 1992], have tied the world-champion backgammon player [Tesauro 1995], and seriously challenged the world chess champion [Kasparov 1996]. 4. DIRECTIONS Predicting the results of the next generation of fundamental research requires either bravery or foolishness. One need not hazard such risks, however, to identify the core challenges facing the next generation of AI systems, namely, exhibiting robust operation in hostile environments, broad and deep knowledge of large domains, the ability to interact naturally with people, and a degree of self-understanding and internal integrity.
ACM Computing Surveys, Vol. 28, No. 4, December 1996 658 · J. Doyle et al. tate their smooth interaction, maintain and improve its knowledge and skills, and dynamically regulate the use of its scarce resources. Building systems with these characteristics poses the same challenges that have driven AI research throughout its history, and each of the areas of technical investigation introduced earlier--knowledge representation and articulation, learning and adaptation, deliberation, planning and acting, speech and language processing, image understanding and synthesis, manipulation and locomotion, autonomous agents and robots, multiagent systems, cognitive modeling, and mathematical foundations--supports a vigorous research effort contributing to meeting these challenges. This brief survey cannot present a complete picture of all the important directions of research in each of these areas (see Weld et al. [1995] for a more generous, though still abbreviated, summary, the challenging problems listed by Selman et al. [1996], and the 1994 Turing Award lectures of Feigenbaum [1996] and Reddy [1996] for other perspectives). Instead, the following sections sketch some broad directions-- spanning many of the narrower areas of investigation--that characterize much of the work in the field today and, in all probability, for the next decade. These directions consist of pursuing systemic and intellectual integration, of which building robots (both physical and computational) and modeling rationality (mainly in the sense of economics and decision theory) form two broad special cases; supporting collaboration; enhancing communication; obtaining the broad reaches of knowledge needed for intelligent action; and deepening the mathematical foundations of the field. The robot direction also constitutes a technical area, but a broad one that touches on most of the other areas as well. The remaining directions each make essential use of several of the technical areas of investigation. --The world, although not necessarily malicious, provides a messy and hostile environment with a structure that cannot be completely anticipated. Whether a robot moving through the physical world, a "softbot" wandering through cyberspace, or an intelligent collaborative or analytical agent, the system confronts problems, opportunities, situations, and external (user or collaborator) demands that change over time. The system will surely fail in its purpose unless it can quickly learn from its experience and adapt to changes in its environment. --The system will require large amounts of knowledge reflecting a broad cross-section of the world. It must capture or embody this knowledge in a form suitable for use in many different tasks, for tailoring portions to achieve high performance on specific tasks, and for acquiring knowledge through its own problemsolving experience and through collaboration with people and other agents. Exploiting large bodies of poorly structured information, such as the World-Wide Web and older information systems, will demand efficiency and dexterity in handling extremely large amounts of complex information. --To interact with its human collaborators, the system must engage in extended dialogues that progressively clarify and enrich the depth of understanding. Doing this requires using natural languages and appropriate visual displays and tactile modalities to communicate, rather than simply exchange single correct sentences, as demanded by today's limited systems. Interacting with its artificial collaborators calls for similar economy and clarity and need not, but may, involve the same languages as used for communication with humans. --The system must also understand itself as well as its collaborators and the world around it, the better to integrate its diverse components, faciliACM Computing Surveys, Vol. 28, No. 4, December 1996 Artificial Intelligence
4.1 Pursuing Integration · 659 AI today vigorously pursues integration along several dimensions: integrating systems that support different capabilities, combining theories and methodologies that concern different facets of intelligence, coordinating subfields within AI, and reconciling, accommodating, and exploiting ideas from other disciplines. Making progress on hard problems requires analysis, and AI has made substantial progress by isolating and understanding many of the important subtasks and subsystems of intelligent behavior in terms of knowledge representation, learning, planning, vision, and like subjects. Much current research seeks to put the pieces back together by constructing integrated systems that incorporate major capabilities drawn from several or all of these areas. For example, natural language processing systems now incorporate learning techniques, recent planning systems incorporate methods for reasoning under uncertainty, and "active" vision systems combine planning control of robot motions with analysis of the resulting sensor data. Integration offers a special opportunity both to test the component theories and also to constrain further the requirements on them. Integration takes special prominence in work on building robots and supporting collaboration, detailed in the following, and in work on complete cognitive architectures, such as SOAR [Rosenbloom et al., 1993]. Apart from the engineering challenge of building complex hybrid systems capable of accomplishing a wide range and mixture of tasks, AI's scientific challenge consists of providing integrated computational theories that accommodate the wide range of intellectual capabilities attributed to humans and assumed necessary for nonhuman intelligences. Many efforts at theoretical integration occur among the subfields of AI. Common logical underpinnings help integrate theories of knowledge representation, planning, problem solving, reasoning, and some aspects of natural language processing, whereas economic concepts of rationality and the mathematics of Markov decision processes help unify recent theories of probabilistic planning, fault diagnosis and repair, reinforcement learning, robot control, and aspects of speech recognition and image processing. Of necessity, many of these efforts at theoretical integration cross disciplinary boundaries and lead to integration with other fields. AI has drawn on and contributed to logic, philosophy, psychology, and linguistics for some time. Integration with economics, decision theory, control theory, and operations research has served as a focus for more recent efforts, detailed in the section on rationality. The most novel case, but perhaps also of the greatest immediate practical importance, consists of integration with related areas of computing research and practice. Integration with these areas has progressed steadily, but slower than one might hope; the areas of tightest integration include theory, databases, and programming languages (especially for logic and object-oriented programming). No one in AI today views AI systems as standing alone; instead, most view AI techniques as supplying components of complex computer systems, components that provide key elements of the capabilities, flexibility, and cooperativeness of an overall system. To realize their benefits fully, AI techniques and the theories underlying them must be integrated much more completely into the warp and woof of computing theory and practice. Representative long-term goals for integration with related areas of computing research include: --dramatically change the nature of programming so that, for most tasks and applications, the programmer works with a collaborative, knowledge-based agent that provides direct and extensive support for specifying, designing, implementing, maintaining, and re-engineering reliable, roACM Computing Surveys, Vol. 28, No. 4, December 1996 660 · J. Doyle et al. ments include both physical environments and the "virtual" worlds of information systems. By focusing on everyday worlds of interest to people, such as office buildings or the Internet, researchers avoid the methodological hazards of designing and simulating toy worlds unwittingly tailored to the designs they were supposed to validate. They also avoid the opposite problem of focusing on problems so hard even humans cannot solve them. The term "robot" traditionally refers to automated agents acting in physical environments, with terms such as "softbot" and "software agent" introduced to refer to agents acting purely within information systems, but this distinction promises to fade in importance as physical agents enter into electronic communication with each other and with online information sources, and as informational agents exploit perceptual and motor mechanisms (such as interpretation of graphical images and synthesis of gestures and other animations). Accordingly, this report calls both types of agents robots, returning to the original sense of the word as an artificial worker in Karel Capek's 1921 play R.U.R. (Rossum's Universal Robots). Many of the major areas of AI and computing research play essential roles in work on robots, from planning, sensing, and learning to high-performance numerical computing and interacting with multiple databases across networks. Robots working in informational environments require little investment in additional expensive or unreliable robotic hardware, since existing computer systems and networks provide their sensors and effectors. Robots with physical abilities, in contrast, require mechanization of various physical sensory abilities, including vision, hearing, touch, taste, smell, thermoreceptivity, and mechanization of various physical motor abilities, including manipulation and locomotion. These areas comprise some of the major efforts of AI and bust, secure, efficient, and intelligible hardware and software systems; --remove artificial distinctions between knowledge bases and databases, which current systems treat separately (the knowledge bases in the running program, the comparatively large databases in specialized servers). Construct efficient, uniformly transparent mechanisms for representing large amounts of knowledge and data, for translating among these representations, and for applying knowledge-based inference, learning, and discovery mechanisms to information appearing in a variety of forms in extremely large-scale knowledge and data repositories; --better integrate reasoning systems with traditional programs, making it easy to mix computation and reasoning from knowledge to achieve desired results. Integrate the corresponding programming and specification tools as well, removing artificial distinctions between description logics and object-oriented systems and between logic programming, rule-based programming, and traditional programming systems; --lessen the tension between speed and quality of action by continuing adaptation and extension of knowledgebased reasoning and learning techniques to real-time operation and control of complex real-world systems that involve hard deadlines; and --make computers easier to use: more cooperative and customizable, with interfaces that employ natural languages and other modalities to communicate in familiar and convenient ways.
4.2 Building Robots (Physical and Computational) Building integrated agents that perceive and act in extant complex and dynamic environments requires integrating a wide range of subfields of AI and computing research. These environACM Computing Surveys, Vol. 28, No. 4, December 1996 Artificial Intelligence provide some of its most impressive successes. Recent work points toward new directions and applications in physical perception and motor abilities. Maturing work on vision as inverse graphics now finds applications in medicine and industry, and research on vision for autonomous robots now takes as its focus less well understood approaches employing more qualitative and "purposive" analyses that select which portions or aspects of images to look at based on what the robot is trying to do. Work on motor abilities now yields unexpected applications in rational drug design for traditional techniques such as configuration-space planning, whereas research on control of autonomous robots has shifted toward less detailed representations that make simpler demands on sensory and actuation systems. Other work actively seeks to transfer the new representation techniques to applications such as industrial cleaning and ordnance disposal. Scaling the operation of autonomous robots to more complicated tasks, and to natural environments in which the robots operate safely in the presence of humans, requires further integration of perception, action, and reasoning. Highlevel reasoning about what to do requires developing new perceptual systems that generate the kinds of data needed by the reasoning system, but the reasoning system in turn must make realistic demands on perception. The marriage of these abilities aims to produce robots that combine the high-level programmability of traditional AI systems with the fault tolerance of current autonomous robots. The area of computer vision exhibits increasing integration with other disciplines. The subfield of active vision, for example, seeks to radically simplify the process of information extraction by closely coupling it to the control of action for a particular task, thus exploiting the practical constraints imposed by the domain of operation. Other approaches exploit theoretical and techno- · 661 logical integration. For example, inverse optics--roughly, the use of images to build models like those used in computer-aided design systems--now draws on collaborations with computer graphics, medical image processing, computational geometry, and multimedia. Representative long-term goals in this direction include building robots that --combine planning, learning, vision, touch, speech, and other senses in performing everyday tasks, for example, housecleaning, cooking, shopping, answering the telephone, making appointments, and negotiating or bargaining with other agents (human or otherwise) for commodities and information; --adaptively monitor, select, tailor, and rewrite the contents of electronic information sources (TV, faxes, newswires, the World-Wide Web) to inform one of news and events in accord with one's changing personal interests, plans, and purposes; --record, monitor, and analyze one's medical history and condition over one's entire lifetime, helping to explain and maintain treatment plans, to detect physician mistakes, and to guide interactions with healthcare providers; --perform tasks people cannot or do not want to do, such as mining, firefighting, handling hazardous material, and planetary exploration; --operate within large-scale distributed systems to monitor and maintain the overall system operation, learning how to detect and defend against malicious external (criminal or terrorist) or internal (disgruntled or corrupt employee) attacks.
4.3 Modeling Rationality Formal and informal notions of rationality from psychology (reasoning and argument) and logic (semantic consistency, deductive closure) have served AI well from its earliest days. They supply concepts useful in mechanizing several
ACM Computing Surveys, Vol. 28, No. 4, December 1996 662 · J. Doyle et al. construct these functions at the outset. Moreover, economics formalized preference and probability information in terms of very abstract representations that, through a lack of much structure, supported only very inefficient algorithms for making rational choices. In contrast, the psychological problemsolving methodology quickly adopted in AI starts with an easily realizable notion of rationality that is much weaker than the standard economic notion (one sanctioned, moreover, by Herbert Simon, an heretical economist founder of AI). Rather than seeking to maximize the numerical utility or expected utility across all conceivable actions, problemsolving rationality simply seeks to find actions meeting less stringent aspirations, such as satisfying designated conditions ("goals") on the resulting states. Building on this approach, researchers now work towards ideal rationality through several means: by increasing the sophistication of reasoning about goals, by adopting explicit notions of utility, and by performing tractable optimizations that take into account the limited knowledge and abilities of the decision maker. As this approach to rationality suggests, recent work in AI has drawn on economic theory in many ways while remaining cognizant of its limitations. The first major exploitation came about through partially solving the problem of representing probabilistic information that stymied early attempts to use decision-theoretic ideas directly. The popular graphical formalisms, especially Bayesian networks and influence diagrams, now support great numbers of successful applications, from sophisticated medical reasoners to mundane printer-diagnostic subsystems of personal computer operating systems. Indeed, the decision-theoretic notions of preference, utility, and expected utility now play important roles in many areas of AI research, as they help to shape learning and adaptation, to guide the plans and actions of autonomous agents and robots, and to reconcile and inte- forms of reasoning, and provide the basis for major cognitive-modeling explorations of hypotheses about the psychology of human ratiocination and its integration with other mental faculties. These large-scale, detailed cognitive theories have already begun to change the face of psychological theory, while nonmonotonic, probabilistic, and new modal logics continue to expand conceptions of logical rationality. The main new direction here, however, seeks integration of rationality in the logical and psychological senses with the economic sense of rationality (maximum utility, optimal allocation of resources). Ratioality in the economic sense has made only sporadic appearances in AI until recently, even though it subsumes the logical sense from a formal point of view and provides explanations of important aspects of rationality in the psychological sense. Rationality in the economic sense offers many attractions as an organizing principle for both intelligent system construction and intellectual integration. It contributes to the system's coherence (in terms of explanation, justification, and verification), to its competence (offering performance advantages), and to its construction methodology (design and development advantages). Researchers in many areas of AI have recognized these advantages and begun work on exploiting rationality in the economic sense. In consequence, economic rationality promises to permeate much of AI; indeed, this work also promises to contribute to economics as well, as AI and economics work together on their shared problems. Early work in AI largely rejected formal economic models in favor of psychological ones because the standard economic theory focuses on an idealization in which rational agents suffer no limitations of memory or time in coming to decisions, and which, for these reasons and others, may not be realizable in the world. Economic approaches generally presupposed possession of utility and probability functions over all contingencies, which did not help in AI's need to
ACM Computing Surveys, Vol. 28, No. 4, December 1996 Artificial Intelligence grate AI planning methods with those of operations research. As interest in collaboration and multiagent systems has increased, many AI researchers have adopted the tools of game theory and the theory of social choice to analyze and design agent interaction protocols, to understand computational decisionmaking methods, and to analyze functional decompositions of mental organization. In the most explicit borrowing from economics, some work employs computational market price systems to allocate resources in a decentralized manner, and uses theoretical analyses of different economic systems to tailor multiagent organizations to achieve high efficiency in performing specific tasks. Just as AI has contributed to logic, the intellectual trade with economics flows both ways, though unequally at present. Bayesian networks and other AI methods have improved practice in statistics. The anticipated but as yet unrealized prize contribution, however, lies in using the precise detailed models of mental organization developed in AI in formulating a realistic and useful theory of the rationality of limited agents (such as people) and organizations composed of such agents, something that has evaded economics throughout its history. The AI theories relating goals and preferences provide one step in this direction, as they augment the traditional economic theories of preference with new qualitative languages for modeling the incomplete and conflicting desires of agents. Recent work on control of deliberation, balancing the costs of further deliberation against the expected benefits, also points in this direction. More immediately, AI and computing research might help economists get a handle on costs and value of information, computation, and communication, factors too often neglected in economics. Representative long-term goals in this direction include: · 663 --continued development of efficient representations and algorithms for rational decision and action that integrate, extend, and improve on current structured representations for probabilities, preferences, decisions, and (game-theoretic) games; --construction of effective computational techniques that allow trading amounts of computational commodities--such as time, memory, or information--for gains in the value of computed results. --understanding the relationship between the rationality of the design of a system (problem formulation, knowledge representation, computational resources) and the rationality of the resulting system; and --extending the application of theories of rationality to learning and adaptation, especially in situations where the learning process must both use and learn preference and utility information.
4.4 Supporting Collaboration Quite apart from the research collaborations within and without AI just described, the subject matter of collaboration and coordination of multiple agents (human or artificial) forms one of the main directions for AI research in coming years [Grosz 1996]. To prove useful as assistants, AI systems must interpret the words and deeds of people to model the desires, intentions, capabilities, and limitations of those people, and then use these models to choose the most appropriate or helpful actions of their own. Making these interpretations often means relying on statistical properties of past behavior, and choosing how to cooperate often means assessing or negotiating the preferences and tradeoffs held by the various participants. Studies of collaboration have a long history in sociology, economics, politics, linguistics, and philosophy. AI has studied collaboration issues in four primary contexts: understanding dialogue, conACM Computing Surveys, Vol. 28, No. 4, December 1996 664 · J. Doyle et al. and other desirable properties of group behavior. Research on collaborative systems draws together many of the research areas of AI, especially planning, multiagent learning, speech and language, and image understanding and presentation, and involves fundamental issues of modeling commitment, communication requirements, constraints and tradeoffs, negotiation methods, and methods for resolving conflicts among the intentions of collaborating agents. Collaborative systems also provide an interesting environment for attacking a core problem of knowledge representation, that of amassing enough knowledge about a broad domain, including many application tasks, to improve performance significantly. Situating people and artificial agents in a common environment with a shared domain model, even a rudimentary one, creates the opportunity for large numbers of collaborators to convey their knowledge to and share their discoveries with one another and with the artificial agents, and for each participant to learn from the collaborative experience. Representative long-term goals in this direction include: --construct DWIM (do what I mean) capabilities for household, educational, commercial, and industrial appliances, yielding machines that infer the desires and intentions of the users and cooperate with them in achieving their aims; --construct intelligence "amplifiers" or "prostheses" that act with a person to overcome limitations of knowledge, memory, or speed in achieving the person's aims; and --construct societies of human and artificial agents that collaborate in efficient ways to achieve complex ends.
4.5 Enhancing Communication structing intelligent assistants, supporting collaborative and group work, and designing "artificial societies." In the longest-studied of these contexts, understanding dialogue, the normal rules of conversational implicature presuppose cooperative intent on the part of the listener. Asking a computer "Can I see the accounts receivable summary?" should yield either presentation of the summary or an explanation of the reason for its unavailability, not a lessthan-helpful "yes" or "no." Aggravation with the stupidity of computers will never cease without such cooperative interpretation of requests and statements. In the more recent context of designing intelligent assistants, the assistant systems must seek to understand and support the aims of the user. These systems go beyond mere decision support by attempting to anticipate and satisfy the needs of the user whenever possible and appropriate. The ARPA/ Rome Laboratory Planning Initiative [Fowler et al. 1995] and NASA's VISTA ground-control support system [Horvitz et al. 1992] provide good examples of such assistants. In a broader context, AI research contributes to providing supportive environments for collaboration and groupcooperative work. As in understanding discourse and designing intelligent assistants, these supportive environments must model processes and plans, but they must also supply methods that reason from these models to coordinate projects, manage workflow constraints, filter and broker information, answer questions, notify participants as appropriate, translate "utterances" between different interface modalities, and generate summaries to quickly bring offline participants up to date. The newest context, designing artificial societies, introduces a design perspective into economics by seeking to tailor the preferences of agents, the protocols of interaction, and the environmental constraints so as to automatically yield collaboration, noninterference,
ACM Computing Surveys, Vol. 28, No. 4, December 1996 Efficient and natural communication holds the key to many of the promises of computers, given that relying on com- Artificial Intelligence mand languages, menus, textual display, and other traditional media stymies many potential applications.3 The activities these applications support normally rely on many different communication modalities, such as spoken utterances, written texts, and the gestures that accompany them, and effective participation in these activities requires the ability to understand and generate communications in these modalities. In addition, the ability to read would greatly simplify the task of imparting knowledge to artificial agents, considering the vast amount of human knowledge encoded in written form. AI has long addressed these issues, and has contributed to great progress in realizing linguistic and visual communication mechanisms involving multiple modalities, including natural language, gestures, and graphics. The most general form of these abilities, however, lies far beyond current scientific understanding and computing technology. Ambiguity, intent, and thinking while speaking form some of the main obstacles to achieving the desired communication. Human languages all use a small set of resources (such as words, structures, intonations, and gestures) to convey an exceedingly wide, rich, and varied set of meanings. Speakers often use the same word, structure, or gesture in many different ways, even in the same sentence or episode. Although people rarely notice such ambiguities, their identification and resolution challenge current speech- and language-processing systems. Intent, or the difference between what people say (or write) and what they actually mean, arises because people rely on their audience to infer many things left unsaid or unwritten from context and common knowledge. Furthermore, people often begin to
3 · 665 Much of the text in the section on enhancing communication was taken directly from sections of Weld et al. [1995], with some revisions. The borrowed text is Copyright © 1995 American Association for Artificial Intelligence, and is reprinted with permission from AAAI. speak or write before thinking through their ideas completely, using the formulation of utterances as a step in understanding their own partially formed ideas. Both practices result in partial and imperfect evidence for what people really mean to communicate. Recent developments include the use of statistical models, typically generated automatically, to predict with good accuracy simple grammatical features of utterances such as the part of speech of a word, as well as semantic properties such as the word sense most likely in a given context. These models thus reduce problems caused by ambiguities in the grammatical and semantic properties of words. In other work, idealized models of purposive communicative action support improved discourse modeling. Much of the success of current natural language processing technology stems from a long and tedious process of incremental improvement in existing approaches. Extracting the best possible performance from known techniques requires more work of this kind, but exploration of new and combined approaches supplies additional opportunities. For example, although statistical and machine-learning techniques in natural language processing offer broad (but shallow) coverage and robustness with respect to noise and errors, grammatical and logical techniques offer deeper a