Patrick Doyle
Professional:  Publications

Annotated Worlds for Animate Characters

Intelligent characters are presently quite limited. How useful and how believable they are depends on the extent to which they are integrated into a specific environment for a particular set of tasks. This tight integration of character and context is an inadequate approach in the rapidly-expanding realm of large, diverse, structurally homogeneous but disparate virtual environments, of which the Web is only the most obvious example. By separating a character.s core features, which are invariable, from its knowledge of and abilities in any specific environment, and embedding this latter information in the environment itself, we can significantly improve the character.s believability, its utility, and its reusability across a variety of domains.

This thesis describes the requirements for an agent architecture that can interact with an annotated virtual environment, together with languages for representing information in and about these environments. An example applying this approach to intelligent characters is presented and used in two substantially different environments, the Web and a multi-user virtual world.

  Patrick Doyle

Ph.D. Thesis, Stanford University, May 2004.

(Single-sided PDF version)
(Double-sided PDF version)
Believability through Context: Using "Knowledge in the World" to Create Intelligent Characters

Intelligent characters are presently quite limited. How useful and how believable they are depends on the extent to which they are integrated into a specific environment for a particular set of tasks. This tight integration of character and context is an inadequate approach in the rapidly-expanding realm of large, diverse, structurally homogeneous but disparate virtual environments, of which the Web is only the most obvious example. By separating a character`s core features, which are invariable, from its knowledge of and abilities in any specific environment, and embedding this latter information as annotations in the environment itself, we can significantly improve the character`s believability, its utility, and its reusability across a variety of domains.

This paper describes an agent architecture that can interact with an annotated virtual environment, together with languages for representing information in and about these environments. An example applying this approach to intelligent characters is presented and used in a complex multi-user virtual world.

  Patrick Doyle

In Proceedings of the International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2002), Bologna, Italy, July 2002, pp. 342-349.

Adventure Games: A Challenge for Cognitive Robotics

This paper presents a set of challenges for cognitive robotics in the context of a text-based adventure game. Games in this class have many challenging properties for cognitive robotics, including incompletely specified goals, an environment revealed only through exploration, actions whose preconditions and effects are not known a priori, and the need of commonsense knowledge for determining what actions are likely to be available or effective. These qualities require an agent that is able to use commonsense knowledge, make assumptions about unavailable knowledge, revise its beliefs, and learn what actions are appropriate. At the same time, more traditional robotics problems arise, including sensing, object classification, focusing on relevant features on a situation, reasoning within context, and decision-making, all within a large state space. In this paper we introduce the game and its environment, elaborate upon the properties of both as they pertain to cognitive robotics, and argue that this is a highly advantageous venue for exploring cognitive robotics issues.
  Eyal Amir
and Patrick Doyle

In AAAI '02 Workshop on Cognitive Robotics.

(PDF version)
 
Design and Evaluation of Embodied Conversational Agents: A Proposed Taxonomy

This workshop call demonstrates that our field is eager to move beyond first-generation generalist projects, toward a more mature practice. To do so, we seek to set up a common set of expectations and criteria for how to judge our work. In this paper, we propose some subclasses of embodied conversational character research and design, with criteria for describing and evaluating research and design advances in each. We suggest that researchers in this field could benefit from carefully identifying their own areas of expertise and contribution, and then looking for ways to collaborate on standards and share advances within these sub-areas. Presenting results, then, would require making clear the sub-areas addressed by the particular project, with evaluations appropriate to those areas included. We believe this approach can help the research community to clarify contributions, and more easily build a common base of knowledge.
  Katherine Isbister
and Patrick Doyle

In AAMAS '02 Workshop on Embodied Conversational Agents.

(PostScript version)
 
Touring Machines: Guide Agents for Sharing Stories about Digital Places

Human understanding of the physical world frequently derives from the narratives we construct about it. Analagously, we can incorporate narratives in virtual spaces to give visitors a sense of place and purpose. In this paper we describe two projects using interactive characters as a medium for story building and storytelling within and about the digital places they inhabit.
  Katherine Isbister
and Patrick Doyle

In Working Notes of the 1999 AAAI Fall Symposium on Narrative Intelligence.

(PostScript version) (PDF version)
 
When is a Communicative Agent a Good Idea?

Research suggests humans treat computers in social ways. We understandably have an interest in building interfaces that use embodiment and natural language to conform to these social roles. However, we must be careful how and when we embed these agents so they actually improve on existing interfaces, rather than simply making them more social.
  Patrick Doyle

In Workshop on Communicative Agents of the Third International Conference on Autonomous Agents, Seattle WA, May 1999.

(PostScript version) (PDF version)
 
Virtual Intelligence from Artificial Reality: Building Stupid Agents in Smart Environments

As the nature of online gaming changes to accomodate vast, persistent virtual worlds, there is a growing need to populate them with inhabitants capable of dynamic, adaptable, fruitful interactions with players. In this paper we argue that by separately placing abstract compentencies in the agent and concrete domain knowledge in the environment, we can build simple intelligences that exhibit sophisticated behaviors.
  Patrick Doyle

In Working Notes of the 1999 AAAI Spring Symposium on Artificial Intelligence and Computer Games

(PostScript version) (PDF version)
 
Animate Characters

The world of everyday interactions is filled with characters, real or fictitious, and human knowledge of how to make these interactions satisfying and productive relies upon an understanding of character. As agents become more intelligent and more ubiquitous, we may naturally ask how we can endow them with life and personality to make them easier and more gratifying to use. This paper offers a broad definition of "animate character," and examines the technical and artistic issues involved both in the creation and the evaluation of such systems. We provide example interactions with several character types. The paper concludes with an annotated bibliographic survey of work done in this area.
  Barbara Hayes-Roth and
Patrick Doyle

Autonomous Agents and Multi-Agent Systems, Volume 1, Number 2, October 1998, pp. 195-230.

(No electronic version available)
 
Agents in Annotated Worlds

Virtual worlds offer great potential as environments for education, entertainment, and collaborative work. For agents to function effectively in heterogeneous virtual spaces, they must have the ability to acquire new behaviors and useful semantic information from those contexts. The human-computer interaction literature discusses how to construct spaces and objects that provide "knowledge in the world" that aids human beings to perform these tasks. In this paper, we describe comparable annotated environments containing explanations of the purpose and uses of spaces and activities that allow agents quickly to become intelligent actors in those spaces. Examples are provided from our application domain, believable agents acting as inhabitants and guides in a children's exploratory world.
  Patrick Doyle and
Barbara Hayes-Roth

Stanford Knowledge Systems Laboratory Report KSL-97-09, Stanford University, Stanford, CA, December 1997.

A revised version of this report appears in Proceedings of the Second International Conference on Autonomous Agents, Minneapolis MN, May 1998.

(PostScript version)
 
Annotating Virtual Worlds

Virtual worlds offer great potential as environments for education, entertainment, and collaborative work. To make full use of such worlds, they must support meaningful interaction with agents from heterogeneous sources. By annotating these environments with explanations of their purpose and descriptions of available actions, agents can quickly become intelligent actors in these spaces. In this paper we describe an effort to annotate a children's educational world to allow believable agents to function as guides, companions, and passers-by.
  Patrick Doyle and
Barbara Hayes-Roth

In Proceedings of the 1998 Virtual Worlds and Simulation Conference, The Society for Computer Simulation, San Diego, CA, January 1998.

(No electronic version available)
 
Tigrito: A Multi-Mode Interactive Improvisational Agent Annotating Virtual Worlds

This paper presents the implementation of Tigrito, an affective computer character. We outline how Tigrito can be used to study chidren's sense of engagement and relationship with virtual toys in different modes of interaction.
  Heidy Maldonado, Antoine Picard, Patrick Doyle and Barbara Hayes-Roth
Stanford Knowledge Systems Laboratory Report KSL-97-08, Stanford University, Stanford CA, December 1997.

Also appeared in Proceedings of the 1998 International Conference on Intelligent User Interfaces, ACM Press, New York, January 1998.

(PostScript version)
 
Guided Exploration of Virtual Worlds

As computers and computer networks become commonplace in the home and in our educational institutions, educators are searching for ways to make them effective tools for instruction. Virtual environments that support learning through exploration and experimentation hold the promise of being such a tool. In this paper, we introduce an intelligent computer agent whose purpose is to guide children in their discovery of such worlds, and by so doing, to increase both their enjoyment and the effectiveness of that discovery.

Our guide is modeled on Merlyn, the befuddled seer and tutor to young King Arthur in T. H. White's The Once and Future King. Merlyn is an autonomous agent that also has an integrated personality and emotional model, since he is intended to be a companion rather than a reference. We describe a particular kind of virtual world, the MUD (or Multi-User Dimension), that Merlyn is designed to interact with. We explain how he makes decisions in such a world, and how these places can be annotated with information to help him understand why they are there and how to use them. Merlyn can use these annotations to learn more about the world as the child travels, and this allows him to explain the world to the child, to suggest activities that may interest the child, and to participate with the child - in playing games, for example. We describe two prototype implementations of Merlyn, and describe future additions for a full-featured version. With Merlyn as a companion, a child can be guided into strategically-chosen learning activities while having a friendly, entertaining experience in the virtual environment.
  Patrick Doyle and
Barbara Hayes-Roth

Stanford Knowledge Systems Laboratory Report KSL-97-04, Stanford University, Stanford, CA, May 1997.

A revised version of this report is available in Network and Netplay: Virtual Groups on the Internet, ed. F. Sudweeks, M. McLaughlin, S. Rafaeli. New York: MIT Press, 1998.

(PostScript version)


The writer writes in order to teach himself, to understand himself, to satisfy himself; the publishing of his ideas, though it brings gratification, is a curious anticlimax.

-- Alfred Kazin
 
Gurevich Abstract State Machines and Schönhage Storage Modification Machines

We demonstrate that Schönhage storage modification machines are equivalent, in a strong sense, to unary abstract state machines. We also show that if one extends the Schönhage model with a pairing function and removes the unary restriction, then equivalence between the two machine models survives.
  Scott Dexter, Patrick Doyle and Yuri Gurevich

In Journal of Universal Computer Science, Volume 3, Number 4, April 1997.

An earlier version is available as Computer Science and Engineering Technical Report CSE-TR-326-97, University of Michigan, Ann Arbor, 1997.

(Journal Article) (Technical Report)
 
An Intelligent Guide for Virtual Environments

In T. H. White's famous retelling of the Arthurian legend, the aged wizard Merlyn is tutor to the young boy Wart, who will grow up to be King Arthur. Through his magic, Merlyn changes Wart into different creatures and transports him to alien environments so he can learn about worlds other than his own. In this paper, we introduce Merlyn as an autonomous intelligent agent, whose purpose is to be a guide and companion to children in their explorations of virtual worlds. Merlyn has an integrated personality and variable moods, so he will be a companion rather than a tool for the child's use. We discuss how Merlyn operates in 'annotated environments,' where the perceived world is reflected in data structures directly accessible to a broad variety of agents. Merlyn becomes more knowledgeable about such worlds as he travels with the child, and he can use these annotations to guide his choice of interactions -- in playing games, for example. Annotations also allow Merlyn to 'endow' the child with environment-specific capabilities to guide the child's experiential learning. Merlyn is also capable of monitoring the child's interests and abilities, and tailoring his personality and actions to them. With Merlyn as a companion, a child can be guided into strategically-chosen learning activities while having a friendly, entertaining experience in the virtual environment.
  Patrick Doyle and
Barbara Hayes-Roth

Stanford Knowledge Systems Laboratory Report KSL-96-20, Stanford University, Stanford CA, July 1996.

A poster abstract for this paper appears in Proceedings of the First International Conference on Autonomous Agents, ACM Press, New York, February 1997.

A revised version of this report appears in Animated Interface Agents: Making Them Intelligent, Proceedings of the IJCAI-97 Workshop.

(PostScript version)
 
Computer-Aided Exploration of Virtual Environments

We introduce an intelligent "guide" that assists users in learning about and exploring in virtual environments, particularly MUDs. The guide itself acts independently of the user, while the user controls his or her own avatar. In addition to accepting options offered by the guide, our system allows the user to direct the avatar by explicit MUD commands as well as via abstract instructions and constraints. The guide, in addition to scanning the MUD environment for actions and knowledge to present to the user, can communicate with the user, suggest activities, and record user preferences to tailor its behavior across multiple sessions.
  Patrick Doyle and
Barbara Hayes-Roth

In Entertainment in AI/A-Life: Papers from the 1996 AAAI Workshop, AAAI Technical Report WS-96-03, AAAI Press, Menlo Park, CA, August 1996.

(PostScript version)


Presentations

Web-Surfing Characters: Intelligent Interfaces for Believable Agents

Virtual worlds offer great potential as environments for education, entertainment, and collaborative work. The effective use and growth of such places in many cases depends upon their ability to support the activities of intelligent agents as well as human beings. To permit agents from heterogeneous sources to act in context-sensitive ways without requiring humanlike reasoning abilities, we propose to build annotated environments in which explanations of purpose, meaning and action permit agents quickly to become intelligent actors in those spaces.

In this talk, we present a summary of our work on building believable, or lifelike, characters that inhabit educational worlds. We will discuss the problems of building such characters, the kinds and structure of annotations needed to make them useful, and describe prototypes we have done both in MUD environments and on the Web.
  Patrick Doyle

Knowledge Systems Laboratory Seminar Series

Stanford University, November 1998


Lecturer, n. One with his hand in your pocket, his tongue in your ear, and his faith in your patience.

-- Ambrose Bierce, The Devil's Dictionary
 
Merlyn and the Foret Sauvage

(No abstract available.)
  Patrick Doyle

Center for the Study of Language and Information

Stanford University, November 1997
 
Agents in Annotated Worlds

Virtual worlds offer great potential as environments for education, entertainment, and collaborative work. The effective use and growth of such places in many cases depends upon their ability to support the activities of intelligent agents as well as human beings. To permit agents from heterogeneous sources to act in context-sensitive ways without requiring humanlike reasoning abilities, we propose to build annotated environments in which explanations of purpose, meaning and action permit agents quickly to become intelligent actors in those spaces.

In this talk, we present our work on building believable, or lifelike, characters that act as guides, companions, and inhabitants of a virtual educational world for young children. We will discuss issues in the construction of such characters, the kinds of annotations they require to support their activites, and describe some of the preliminary results from our current world.
  Patrick Doyle

Knowledge Systems Laboratory Seminar Series

Stanford University, November 1997
 
Agents in Annotated Worlds

(No abstract available.)
  Patrick Doyle

Combined Conference on MUDs in Education

Jackson Hole, WY, January 1997