«a dissertation submitted to the department of computer science and the committee on graduate studies of stanford university in partial fulfillment of ...»
ANNOTATED WORLDS FOR ANIMATE CHARACTERS
submitted to the department of computer science
and the committee on graduate studies
of stanford university
in partial fulfillment of the requirements
for the degree of
doctor of philosophy
Patrick Owen Doyle
c Copyright by Patrick Owen Doyle 2004
All Rights Reserved
I certify that I have read this dissertation and that, in
my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy.
Richard Fikes (Principal Adviser) I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy.
Barbara Hayes-Roth I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy.
Terry Winograd Approved for the University Committee on Graduate Studies.
iii iv Abstract Autonomous intelligent agents designed to appear as convincing “animate” characters are presently quite limited. How useful and how believable they are depends on the extent to which they are integrated into a speciﬁc 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 speciﬁc environment, and embedding this latter information in the environment itself, we can signiﬁcantly 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 animate characters is presented and used in two substantially diﬀerent environments, the Web and a multi-user virtual world.
v Author’s Note This thesis came about primarily because I was disheartened by the low level of interactivity and apparent intelligence (social, emotional, functional or otherwise) exhibited by the characters in every large multi-user environment I have encountered.
Large, lengthy, and expensive eﬀortsare being made to build massive virtual worlds where people can come together to learn, to socialize, and to play. They are often beautiful; they oﬀer many places to visit, many things to see and do, activities and challenges for the visitors. However, they are populated by a professional cast (so to speak) of characters only slightly more interactive than furniture, and I don’t mean particularly smart furniture.
The general trend in computer entertainment over the last several years has been to focus on improving the often spotty intelligence of the computer (as environment, as opponent, as assistant). This trend has not has signiﬁcant eﬀect in the massively multi-player worlds because of the very limited computational resources that can be devoted to any particular character and the diﬃculty of producing autonomous believable characters at all.
My belief is that embedding knowledge in the environment is the only way we are going to be able to take many characters with limited resources in large environments and get them to behave believably with respect to the world. This oﬀers the potential of much more believable characters, and much more capable characters as well. They shouldn’t just be shopkeepers and passers-by, milling around and making smalltalk.
They should be able to participate actively in the life of the world and the experiences of the visitors as friends, playmates, assistants, guides, leaders, opponents, and even just more colorful local color. Hopefully the ideas in this dissertation will help point
The production of a doctoral dissertation is a demanding, time-consuming, and draining process. I have always been keenly aware that it is also fundamentally a collaborative process: I have succeeded in large measure because of those who have supported and encouraged me on this path, emotionally, socially, and academically. These few brief remarks are an inadequate recompense for their eﬀorts, but luckily neither my expressions nor my feelings of gratitude are bounded by these pages.
First to thank is Barbara Hayes-Roth, my advisor for most of the years I spent at Stanford. She made me welcome here at the university and in her research group, and while freely sharing her considerable experience still actively encouraged me to ﬁnd my own path. Her casual conﬁdence in my abilities was and is something for which I am especially thankful.
To Richard Fikes, who has been my advisor these last many months, I owe many thanks. His willingness to take me on as a student, despite the very tenuous connection between his research and my own, was no less surprising than the enthusiasm he has displayed during our many productive and enjoyable conversations. The reﬁnements he has contributed to my work, to my thinking, and to its elaboration here, are numerable and wonderfully skilled. I was lucky to be his student, even if for only for a brief time.
Terry Winograd graciously agreed to be on my committee despite the considerable demands on his time. To him I owe my exposure to the wide-ranging and fascinating ﬁeld of human-computer interaction, which has had an enormous inﬂuence on this dissertation and on all my professional creations. The quality of his research and his teaching will always be ideals for me. I am grateful for his incisive comments on my viii research. He deserves thanks also for allowing me to join in on his research group’s weekly lunches, and also for introducing me, in passing, to the works of Jorge Luis Borges, from which I have derived much pleasure.
The delightful, discursive, and highly informative conversations I’ve had with Pat Langley qualify him for an unoﬃcial committee position at the very least. Pat’s good humor and terrible puns are matched by his vast knowledge of artiﬁcial intelligence and I have beneﬁted and suﬀered from them in turns.
Katherine Isbister has been my friend for several years, and I have had the good fortune to collaborate with her, both in research and in teaching. There is considerable value in knowing someone who has survived the Ph.D. process, done it recently enough that she still remembers what it felt like, and can oﬀer encouragement that it is actually possible to make it through. I think her students at RPI are going to be very lucky.
To Karl Pﬂeger I owe thanks for advice, guidance, feedback on my ideas and my writing, technical support, and years of TV nights with the gang at his house. All hail Joss Whedon!
Together with Karl, Eyal Amir, Urszula Chajewska, and Pedrito Maynard-Zhang were friends and comrades-in-arms in the Ph.D. process. Our TSG meetings provided critical analysis, practical advice, and much-needed support. They had as much faith in me as I did in them, to my perpetual amazement.
Thanks also go to Heidy Maldonado, who despite being several years younger than I has been at Stanford even longer than I have, though in that time she’s earned far more degrees. Heidy is one of the most well-connected researchers I know, and discussions with her about my work and how it relates to what others are doing have been frighteningly enlightening. Her enthusiasm has been simply frightening. To her I wish good luck as she completes her own Ph.D., which I suppose will be the ﬁrst of several.
Many others in the computer science department deserve mention. Along with the TSG members, Avi Pfeﬀer and Lise Getoor and I studied for the qualifying exam together. To them and that process I owe whatever breadth of knowledge in AI I possess today. Many others in the department combined friendship with ix scholarship and provided the social and intellectual atmosphere we all hoped for when we embarked on a university life: Lee Brownston (who also showed me where to ﬁnd the culture in the Bay Area), Francois Guimbretiere, Ruth Huard, Danny Huber, Jessica Jenkins, Uri Lerner (I bow to his superior knowledge of The Simpsons), Tamara Munzner (and her superior knowledge of science ﬁction, not to mention her legendary parties), Todd Neller, Aarati Parmar, Daniel Rousseau, Scott Sanner (sadly, an expert on Jimmy Buﬀett), and Diane Tang especially.
For almost the entire time I’ve been at Stanford, I have worked at Concentric Network Corporation (later XO Communications). The balance of research and realworld development I did there kept me, I hope, from growing stale in either. Of my friends at XO, special thanks to Rob Field for his good humor and endless frustrating Magic games, and to Jeﬀ Powell, who seemed almost as eager as I was to see me graduate.
I would like to thank Anson Lowe, Stanford professor and doctor, who in a literal sense kept me up and working during most of this process. How I got lucky enough to have a doctor who answers email, I don’t know.
Professors Kevin Compton and Bert Herzog at the University of Michigan both encouraged me to come to Stanford and see how another university does its teaching and learning. Each man had a profound inﬂuence on my early exposure to graduate school, Kevin as my research advisor and Bert as the ﬁrst professor for whom I was a teaching assistant. I am deeply grateful to them both.
My friends of many years, who knew me long before I came to Stanford and have endured nearly a decade of promises that I’m going to graduate “probably next year,” deserve thanks for their friendship and their faith. Especially to Scott Dexter, who got his Ph.D., a professorship and tenure all while I was still working on my thesis;
to Jeﬀ Woodside, who got his M.D., got married, had a child, and moved to Texas (a state he deeply loves); to Bonnie Wallace, who has a special ability to distance herself geographically while still staying a close friend; and most of all to David Schairer, true friend since childhood, I give aﬀectionate thanks.
My girlfriend Wendy has waited patiently for nearly two years for me to ﬁnish this document. She has given me support when I wanted it and has told me to buckle x down and get to work when I needed it. The sense of exhilaration at ﬁnishing the dissertation is tempered by the knowledge that I will ﬁnally have to take those swing dancing lessons.
Finally, to Mom and Dad, my sister Kate, and my brother Philip, my love and gratitude. With the help of all the people I’ve mentioned, and the many others that I haven’t, I ﬁnished this journey; but without your love and encouragement, I never would have been able to begin it.
xi Dear friends, reproach me not for what I do, Nor counsel me, nor pity me; nor say That I am wearing half my life away For bubble-work that only fools pursue.
And if my bubbles be too small for you, Blow bigger then your own: the games we play To ﬁll the frittered minutes of a day, Good glasses are to read the spirit through.
And whoso reads may get him some shrewd skill;
And some unproﬁtable scorn resign, To praise the very thing that he deplores;
So, friends (dear friends), remember, if you will, The shame I win for singing is all mine, The gold I miss for dreaming is all yours.
— Edwin Arlington Robinson, “Dear Friends”
6.1 Qualities of animate characters (reorganized).............. 107
8.1 Character goals referenced in aﬀective annotations........... 159
8.2 Notable annotations in puzzle description................ 168
8.3 Notable annotations in game description................ 184 B.1 Major elements in the art gallery vocabulary.............. 234
Introduction What we look for in a created character is not mere surprise but revelation. The unexpected behavior of a ﬁctional character must be surprising in the way that human beings are surprising; it must tell us something we recognize as being true to life.
The real world is ﬁlled with characters. The clerk at the bookstore, the professor in the lecture hall, the coworker in the oﬃce, all have their own appearances, personalities, and stories. Our imaginary worlds are also ﬁlled with characters, characters from Don Quixote and Sherlock Holmes to Homer Simpson and Daﬀy Duck, characters that are a purer distillation of the qualities that we hate, love, admire, disdain, embrace, reject, that fascinate us and that compel us. And yet we are always one step removed from them. We cheer for them, but cannot encourage; we sympathize with them, but cannot comfort; we love them but cannot tell them so. These characters interact with one another but they do not interact with us.
One of the great modern fantasies has been to imagine how to bring our characters to life in a more literal sense, and how to make it possible for us to interact with them.
The “holodeck” of Star Trek is a futuristic device that does just that — it transforms an ordinary room into a perfect replica of any imaginary environment, and populates it with intelligent, interactive characters. It enables the observer to become an active participant in the story.
2 CHAPTER 1. INTRODUCTIONObviously, we are not on the verge of installing home holodecks. We are seeing, however, ﬁrst approximations to such imaginary technology in the form of massive virtual worlds in which players can embody themselves, explore and live, and interact with others, whether they are players or characters controlled by the computer.
These worlds have beneﬁted from more than two decades of research on the creation of intelligent, interactive characters and on the construction of compelling virtual environments.