A Decision Network Framework for the Behavioral Animation ...

1 Eurographics/ ACM SIGGRAPH Symposium on Computer Animation (2007)D. Metaxas and J. Popovic (Editors)A Decision Network Frameworkfor the Behavioral Animation of virtual HumansQinxin Yu1,3and Demetri Terzopoulos2,31 Artificialife Inc., Montreal, QC, Canada2 University of California, Los Angeles, CA, USA3 University of Toronto, Toronto, ON, CanadaAbstractWe introduce a Framework for advanced Behavioral Animation in virtual humans, which addresses the challeng-ing open problem of simulating social interactions between pedestrians in urban settings. Based on hierarchicaldecision networks, our novel Framework combines probability, Decision , and graph theories for complex behav-ior modeling and intelligent action selection subject to manifold internal and external factors in the presence ofuncertain knowledge. It yields autonomous characters that can make nontrivial interpretations and arrive at ra-tional decisions dependent on multiple considerations. We demonstrate our Framework in Behavioral animationscenarios involving interacting autonomous pedestrians, including an elaborate emergency response IntroductionCreating autonomous characters with humanlike behaviorsis a serious challenge.

2 Our goal is to develop advanced be-havioral systems for virtual humans. In particular, we ad-dress the level of Decision -making that enables the charactersto interact appropriately with their perceived environment,especially with other virtual humans. We focus on action se-lection; , on simulating how humans decide what to do atany given time. To this end, we introduce adecision networkframeworkfor specifying and activating human behaviorsthat is easy to define and modify, scalable, and ostensiblyemulates how people make and complexity are characteristics of humanbehavior that make it especially difficult to simulate. Uncer-tainty has largely been ignored in prior behavior models, par-ticularly uncertainty resulting from the natural limitations ofperception, especially perception of the intentions of otherpeople. Furthermore, no systematic approach has been pro-posed to deal with complexity. Our Decision Network frame-work addresses both issues. Decision networks are a general-ization of Bayesian networks [Pea88], also known as proba-bilistic graphical models, which combine probability theoryand graph theory to capture uncertain knowledge in a nat-ural and efficient manner.

3 An attractive feature of the deci-sion Network is that it is a powerful tool for modeling de-cision making under uncertainty. It provides an elegant andrigorous mathematical formalism for modeling complicatedrelationships among random variables and an intuitive visu-alization of these relationships as a graphical structure, thusfacilitating comprehension and debugging. Furthermore, themodularity of a Decision Network facilitates the intuitive re-duction of a complex behavior into manageable work should not be misconstrued as yet another ef-fort on so-called crowd simulation. Our objectives dif-fer. In particular, we arenotinterested in modeling multi-tudes of rather simple characters. Instead, we seek to de-velop complex autonomous individuals that, in addition tomotor and perceptual components, include broad behavioralrepertoires that are much more challenging to model. Ourself-animating pedestrians can independently assess the in-terrelationships among all the relevant factors to make ratio-nal decisions in the presence of uncertainty.

4 Hence, they aresuitable for animating the detailed Behavioral interactions ofsmall social Related WorkHuman modeling is a broad, multifaceted subject in com-puter graphics. The goal of our work is autonomous vir-tual humans that behave intelligently in complex, syntheticworlds [ST05]. To that end, we focus on human behav-ioral modeling. Since the introduction of Behavioral ani-mation by Reynolds [Rey87], researchers have pursued theethological approach to modeling animal behaviors, wherethe autonomous character takes actions based on its inter-c The Eurographics Association Yu & D. Terzopoulos / Decision Network Frameworknal state and its perceptual interpretation of external stimuli[TT94,BDI 02]. human behavior, by far the most complexof animal behaviors, is the subject of multiple disciplines, in-cluding ethology, psychology, sociology, and work addresses the human character s autonomy and in-teraction in its virtual environment, aside from natural verbalcommunication and dialog, nor do we consider the cognitivelevel of Decision making, which concerns what a characterknows, how that knowledge is acquired, and how it can beused to reason and plan actions [FTT99].

5 In the area of human Behavioral Animation , Musse andThalmann [MT97] simulated crowd behavior using a rule-based system. Badler et al. [BAZB02] proposed a Parame-terized Action Representation (PAR), which includes speci-fications for low-level Animation concepts, and descriptionsof primitive or complex actions, with action selection basedon the conditions specified in the PAR to our approach, Ball and Breese [BB00] encodedemotions and personality using Bayesian networks. Unlikeour work, however, their emphasis was on conversationalagents with speech recognition and generation. Kshirsagarand Thalmann [Ksh02] also used a Bayesian Network tomodel personality and mood in a chat application, as didEgges et al. [EZKT03] to model mood in their conversa-tional agent. The work closest to ours is that by Hy etal. [HABL04] who simulated simple behaviors for a first-person shooter game character by using a Bayesian networkto specify finite-state-machine-like behavior selection, andto learn by imitating a human player.

6 Unlike us, they did notsimulate human prior Animation work and existing computergame titles have used finite state machines, fuzzy logic, neu-ral nets, scripting, smart environments, and Bayesian net-works, to our knowledge, ours is the first effort in computergraphics to develop and demonstrate a unified frameworkfor Behavioral Animation based ondecision networks. Thedecision Network (or influence diagram ), which was intro-duced by Howard and Matheson [HM81] in the area of deci-sion analysis, combines probability theory and utility theoryto provide a simple visual representation of a Decision prob-lem. Decision networks extend Bayesian networks by addingactions and with other common Decision -making mech-anisms such as fuzzy logic [Zad88] and neural net-works [Bis95], or rule-based architectures [LNR87], deci-sion networks offer the advantage of providing an intuitiveyet rigorous way to identify and display the essential el-ements of the problem, including objectives, uncertainties,interpretations, and decisions, and how they influence eachother, as well as the clear attribution of outcomes to the in-puts that generated them.

7 We assert that Decision networksare significantly better able to simulate social interactionsamong autonomous 1:Autonomous virtual Pedestrian virtual human ModelTo evaluate our Framework , we have implemented a vir-tual human model based on the software that was describedin [ST05], including the environment model of the originalPennsylvania Train Station in New York City. the architecture of our virtual pedestrian. Like realpedestrians, the synthetic humans sense their virtual envi-ronment, interpret the sensory stimuli, make decisions basedon their perceptual interpretations, and act in accordancewith their decisions. The important contribution of our hu-man model is the behavior submodel, in which we exploitdecision networks to simulate complex interactions betweenmultiple pedestrians and to model the effect of different per-sonalities on their character acts autonomously within the virtual en-vironment. To understand the structure of our system, letus consider an arbitrary character, say Jane.

8 At any giventime, Jane s intention generator assesses her current inten-tion based on internal attributes and memory. Jane observesher surroundings to determine what objects are within her180-degree field of view. The perceptual data Jane can gatherby querying the environment model includes the position,speed, and orientation of objects in the environment, includ-ing other characters as well as their gaze s attention mechanism guides her gaze depending onwhich objects are of interest given her current intention, orif an object attracts attention by making a sudden move-ment [EY97]. When Jane attends to a character she recog-nizes, or to a character with which she may be interested ininteracting, or when there is a potential collision with somecharacter, she draws inferences about the character using theinterpreter in her perception system and decides how to inter-act with them. This Decision making process is accomplishedwithin our novel Behavioral particular, Jane is equipped with the new behavioralmodels that we develop in the next section.

9 She also pos-sesses a set of behavior routines that enable her to carry outprimitive actions, such as walking to certain locations. Oncean action selection Decision is made, the relevant behaviorroutines are invoked to carry out the necessary actions. Atc The Eurographics Association Yu & D. Terzopoulos / Decision Network Frameworka lower level, her motor system is responsible for carry-ing out the actual primitive movements such as walking andrunning. Her geometric body model and its primitive move-ments are provided by Boston Dynamics Inc. s DI-Guy must remember the sequence of tasks she wants toperform. For this purpose, we implement a stack based mem-ory in her behavior system, as was done in [ST05], en-abling her to maintain persistence in her behaviors, whilealso adapting to the changing environment by storing newinterim goals that attract her have designed behavior routines to couple the deci-sions made at the Behavioral level to the low-level DI-Guymotor system.

10 Unfortunately, DI-Guy characters suffer lim-itations not just in their appearance but also in their motorskills, which restricts the possible motions that may be usedin actions triggered by our Decision Network Framework . Forone character to interpret the behavior of another, it mustmake observations. Currently there are only a limited set ofcues upon which our virtual humans can base their observa-tions, since their facial expressions and gestures are highlyconstrained. The available cues include change in direction,change in speed, gaze direction [Pet05], and body orienta-tion. Change in speed is an especially unreliable visual cueas DI-Guy characters cannot change their speed Behavioral Modeling Using Decision NetworksOur new Behavioral modeling approach employs decisionnetworks as its core methodology. We have applied our de-cision Network Framework to the design of interaction mod-els between virtual humans, guided by our commonsenseknowledge of how real humans behave in similar circum-stances.