Learning Policies for Embodied Virtual Agents through Demonstration

1 Introduction

An Embodied Virtual Agent, or EVA, is a software agent with a body represented through computer graphics [Badler et al., 1999; Dinerstein et al., 2006]. If given sufficient intelligence, these characters can animate themselves by choosing actions to perform (where each action is a motion). Applications of these agents include computer games, computer animation, virtual reality, training simulators, and so forth.

Despite the success of EVAs in certain domains, some important arguments have been brought against current techniques. In particular, programming the agent AI is difficult and time-consuming, and it is challenging to achieve naturallooking behavior. We address these issues by learning a policy for controlling the agent's behavior that is:

1. Scalable -The policy learning must scale to problems with continuous and high-dimensional state spaces.
2. Aesthetic - The virtual agent behavior must appear natural and visually pleasing.
3. Simple - The policy learning must be directable by a non-technical user.

Parris K. Egbert Dan Ventura

CS Department, Brigham Young University {egbert,ventura}@cs.byu.edu

Reinforcement learning (RL) is a powerful scheme and an obvious choice for policy learning. However, it does not meet our requirements-RL does not always scale well to continuous state spaces of high dimensionality (which are common for EVAs), and it is challenging to encode aesthetic goals into a reward structure. We take a different approach.

We present a technique for automatic learning of a policy by mimicking demonstrated human behavior. This technique not only provides a natural and simple method for the construction of a policy, but it also allows an animator (or other non-technical person) to be intimately involved in the construction of the policy. We learn a reactive policy rather than more advanced behavior because this learning is simple and nearly automatic, thereby allowing for AI creation by nontechnical users. This approach is empirically shown to be effective at quickly learning useful policies whose behavior appears natural in continuous state (and action) spaces of high dimensionality.

2 RelatedWork

Designing and developing embodied virtual agents is fundamentally a multi-disciplinary problem [Gratch et al., 2002; Cole et al., 2003]. Indeed the study of EVAs overlaps with several scientific fields, including artificial intelligence, computer graphics, computer-human interfaces, etc.

The computer graphics community has been interested in EVAs since Reynold's seminal work on flocking behavior [Reynolds, 1987]. One of the most well-known examples in film is the Lord of the Rings trilogy [Duncan, 2002], depicting epic-scale battle scenes of humanoids. Such large-scale animation would be implausible if the characters were animated manually. Several notable techniques for constructing EVAs have been developed (e.g., [Monzani et al., 2001]) but the explicit programming of agent AI remains a difficult task.

Game-oriented EVA research includes the development of action selection and learning architectures [Laird, 2001]. Computational models of emotion have also been proposed [Gratch and Marsella, 2005]. Recent work has examined rapid behavior adaption such that an EVA can better interact with a given human user [Dinerstein and Egbert, 2005; Dinerstein et al., 2005]. In other work, a scheme has been developed whereby a non-embodied agent in a text-based computer game learns through interaction with multiple users [Isbell et al., 2001].

As discussed in the introduction, designing and programming EVA AI is often challenging. Several authors have addressed this through reinforcement learning (a survey is given in [Dinerstein et al., 2006]). RL is a natural choice since it has long been used for agent policy learning. However, RL does not meet our requirements in this paper. For example, it is quite challenging to achieve natural-looking behavior since these aesthetic goals must be integrated into the fitness function. Also, many EVAs live in continuous virtual worlds and thus may require continuous state and/or action spaces, such as flocking EVAs [Reynolds, 1987]. Traditional RL is intractible for large or continuous state/action spaces, though recent research has begun to address this problem [Ng and Jordan, 2000; Wingate and Seppi, 2005]. Nevertheless, the learning is still computationally expensive and limited. Our technique learns stylized EVA behaviors quickly as empirically shown later.

The agents and robotics communities have long recognized the need for simplified programming of agent AI. There has been some interesting work performed in programming by demonstration, such as [Pomerleau, 1996; van Lent and Laird, 2001; Mataric, 2000; Kasper et al., 2001; Angros et al., 2002; Nicolescu, 2003], where an agent is instructed through demonstrations by a user. Our technique fits in this category but is specifically designed for EVAs trained by non-technical users. In contrast to these existing techniques, our approach does not require significant effort from a programmer and domain expert before demonstration can be performed. The existing technique that is most related to our work is "Learning to Fly" [Sammut et al., 1992]. However, our technique is unique in many aspects, in particular because it performs conflict elimination, can operate in continuous action spaces, and can be operated by non-technical users. There has been some previous work in conflict elimination through clustering [Friedrich et al., 1996], but that approach quantizes the training examples and culls many potentially useful cases.

Contribution: We present a novel scheme for programming EVA behavior through demonstration. While many of the components of our scheme are pre-existing, our overall system and application are unique. Moreover, some notable and critical components of our scheme are novel. Specific contributions made in this paper include:

• The application of agent programming-by-demonstration concepts to policy learning for humanoid EVAs.
• An intuitive interface for non-technical users to quickly create stylized and natural-looking EVA behavior.
• A novel conflict elimination method (previous techniques in agents/robotics have usually ignored or blended conflicts).

3 EVA Programming by Demonstration

Learning an EVA policy through demonstration involves the following steps (see Figure 1):

1. Train:

(a) Observe and record state-action pairs.

• (b) Eliminate conflicts.
• (c) Generalize state-action pairs into a policy μ.
• Autonomous behavior:
• (a) Use μ to compute decisions for the agent, once per fixed time step Δt.

This is a process of learning to approximate intelligent decision making from human example. We formulate decision making as a policy:

where s ∈ Rn is a compact representation of the current state of the character and its world, and a ∈ Rm is the action chosen to perform. Each component of s is a salient feature defining some important aspect of the current state. If the character has a finite repertoire of possible actions, then a is quantized.

A state-action pair is denoted 〈s,a〉. The demonstrator's behavior is sampled at a fixed time step Δt, which is equal to the rate at which the character will choose actions when it is autonomous. Thus the observed behavior is a set of discrete cases, B= {〈s,a〉1, . . . , 〈s,a〉q}. Each pair represents one case of the target behavior. There is no ordering of the pairs in the set. We construct μ by generalizing these cases. Specifically, to ensure that the character's behavior is smooth and aesthetically pleasing, we construct μ by interpolating the actions associated with these cases. Because s ∈ Rn and a ∈ Rm , we can theoretically use any continuous real-vectorvalued interpolation scheme. In our implementation, we either use ε-regression SVM or continuous k-nearest neighbor, as detailed later. If the action set is symbolic, we use voting k-nearest neighbor.

For generalization of cases to succeed, it is critical that the state and action spaces be organized by the programmer such that similar states usually map to similar actions. In other words, ‖si -s j‖ < α ⇒ ‖ai -a j‖ < β , where α and β are small scalar thresholds and ‖ · ‖ is the Euclidean metric. Certainly, this constraint need not always hold, but the smoother the mapping, the more accurate the learned policy μ will be.

3.1 Training

In training mode, both the demonstrator and programmer need to be involved. First, the programmer integrates our technique into an existing (but thus far "brainless") character.

This integration involves designing the state and action spaces such that μ will be learnable. Once integration is complete, the demonstrator is free to create policies for the character at will. In fact, the creation of multiple policies for one agent may be interesting to achieve different stylized behaviors, etc.

Demonstration proceeds as follows. The character and its virtual world are visualized in real-time, and the demonstrator has interactive control over the actions of the character. Note that the continuous, real-time presentation of state information to the demonstrator is critical to making the character training process as natural as possible, as this is analogous to how humans naturally perceive the real world. As the simulation-visualization of the character and its world proceeds in real-time, the demonstrator supplies the character with the actions it is to perform. This information is saved in the form of state-action pairs. Once enough state-action examples have been collected, all conflicting examples are automatically eliminated, as described below. We now have a discrete but representative sampling of the entire policy function μ. Moreover, because the demonstrator has had control of the character, she has forced it into regions of the state space of interest - therefore the density of the sampling corresponds to the importance of each region of the state space.

Elimination of conflicting examples is important because human behavior is not always deterministic, and therefore some examples will likely conflict. This is an important issue, because the machine learning schemes we utilize will "average" conflicting examples. This can result in unrealistic or unintelligent-looking behavior. Note that conflict resolution might also be possible by augmenting the state with context (e.g. the last n actions performed). However, this increase in the state-space dimensionality will only make the learning μ more challenging and require additional training examples. Thus we have designed our technique to directly eliminate conflicts.

Conflicting examples are formally defined as:

where ν and υ are scalar thresholds. To eliminate conflicts, we cannot arbitrarily delete cases involved in a conflict - this can lead to high frequencies in the policy. Our goal is to remove those examples that represent high frequencies.

Pseudo-code for our conflict elimination technique is given in Figure 2. To complement this pseudo-code, we now describe our technique. In brief, each state-action pair is tested in turn to determine whether it is an outlier. First, the l neighbors (according to state) of the current example are found and their median action avm is computed, using the following vector-median method [Koschan and Abidi, 2001]:

In other words, avm is equal to the action of the neighbor that is the closest to all other actions of the neighbors according to the Euclidean metric. Finally, if ‖avm - a′‖ > η, then the case is an outlier and is marked for deletion. Marked cases are retained for testing the other cases, and then are all deleted as a batch at the conclusion of the conflict elimination algorithm.

For each recorded pair 〈s,a〉′ ... Find l closest neighbors of 〈s,a〉′ Compute median action avm of l neighbors using Eq. 3 if (‖avm - a ′‖>η) Mark 〈s,a〉′

Delete all marked pairs

Figure 2: Conflict elimination algorithm.

In our experiments, we have found that it works well to use l = 5. We use a threshold η of about 10% of the possible range of component values in a.

3.2 Autonomous Behavior

Once an adequate set of state-action pairs has been collected, we must construct the continuous policy, μ : s → a. We do this through one of two popular machine learning techniques: ε-regression SVM [Haykin, 1999] or k-nearest neighbor [Mitchell, 1997] (or through a classification scheme if the actions are symbolic). We have chosen these two techniques because they are powerful and well-established, yet have contrasting strengths and weaknesses in our application.

The primary strength of continuous k-nearest neighbor (knn) is that there are strong guarantees about its accuracy, as it merely interpolates local cases (e.g., it can robustly handle non-smooth mappings, and the outputs will be within the convex hull of the k local cases). Therefore we use k-nn whenever the demonstrated policy is rough. However, k-nn does have a large memory footprint (∼1 MB per policy), and more state-action cases are required than with SVM due to weaker generalization.

The support vector machine (SVM) is an interesting alternative to k-nn. It is a compact and global technique. As a result, it performs powerful generalization, but can struggle with highly non-smooth mappings. We have found SVM to be useful when μ is somewhat smooth, especially when it is C 0 or C 1 continuous. We use the popular ε-regression scheme with a Gaussian kernel to perform function approximation.

4 Experimental Results

These experiments were designed to cover, in a general fashion, most of the major distinguishing aspects of popular uses of embodied virtual agents. Between our favorable experimental results, and the results from the agents/robotics literature on programming-by-demonstration (see the related work section), we have some empirical evidence that our scheme is a viable tool for creating some popular types of EVA policies.

The results we achieved in our experiments are summarized in Table 1. Comparisons against reinforcement learning, A*, and PEGASUS are summarized in Table 2 and discussed in more detail later (while we do not take an RL approach in our technique, we believe it is valuable to compare against RL since it such a popular approach). The results of an informal user case study are reported in Table 3. Videos of the animation results are available from:

4.1 Spaceship Pilot

In our first experiment, the virtual agent is a spaceship pilot (see Figure 3). The pilot's task is to maneuver the spaceship through random asteroid fields, flying from one end of the field to the other as quickly as possible with no collisions. The animation runs at 15 frames per second, with an action computed for each frame. The virtual pilot controls the orientation of the spaceship.

μ is formulated as follows. The inputs are the spaceship's current orientation (θ,φ), and the separation vector between the spaceship and the two nearest asteroids (ps - pa1 and ps -pa2). Thus the complete state vector is s = 〈θ,φ,Δx1,Δy1,Δz1,Δx2,Δy2,Δz2〉. There are two outputs, which determined the change in the spaceship's orientation: a = 〈Δθ , Δφ 〉.

We achieved good results in this experiment, as shown in Table 1 and in the accompanying video. The SVM and k-nn policies worked well for all random asteroid fields we tried, and the animation was natural-looking, intelligent, and aesthetically pleasing (verified in an informal user case study).

To gain a point of reference and to illuminate the interesting computational properties of our technique, we analyzed learning the policy through reinforcement learning (Table 2). This analysis helps validate why a non-RL approach is important in fulfilling our goals. It is straightforward to formulate our case study as an MDP. The state and action spaces have already been defined. We have a complete model of the deterministic environment (needed for animation), the initial state is a position on one side of the asteroid field, and the reward structure is positive for safely crossing the field and negative for crashing. However, even using state-of-the-art table-based techniques for solving large MDP's [Wingate and Seppi, 2005], it is currently implausible to performRL with a continuous state space of dimensionality greater than 6 (this size even requires a supercomputer). Our MDP state space dimensionality is 9. Even gross discretization is intractable: e.g., for 10 divisions per axis, 10 9 states. The best result reported in [Wingate and Seppi, 2005] is a 4-dimensional state space discretized into approximately 10 7.85 states. We also experimented with learning a policy through functionapproximation-based RL using a multi-layer neural net, but this failed (the learned policies were very poor). This type of learning is typically considered most stable when employing a linear function approximator, but this can limit the learning [Tesauro, 1995; Sutton and Barto, 1998]. Thus, for our application, demonstration-based learning is appealing since it is effective in high-dimensional, continuous state and action spaces.

We also tested a non-standard form of RL designed specifically for continuous state spaces: PEGASUS [Ng and Jordan, 2000; Ng et al., 2004]. In PEGASUS, a neural network learns a policy through hill climbing. Specifically, a small set of finite-horizon scenarios is used to evaluate a policy and determine the fitness landscape. Unlike traditional RL, PEGASUS succeeded in learning an effective policy in our case study (see Table 1). Interestingly, the performance of the policies learned through our scheme and PEGASUS are similar. However, PEGASUS learning was far slower than our technique (hours versus minutes). Moreover, we found it extremely difficult and technical to tune the PEGASUS reward structure for aesthetics. Thus, while PEGASUS is a powerful and useful technique, it does not fulfill the requirement given in the introduction of providing non-technical users with an intuitive and robust interface for programming EVA AI. As a result, RL does not appear to be a good fit for our application.

We also analyzed explicit action selection through A* (Table 2). A* has empirically proven successful, but requires significantly more CPU than our policies to make decisions, sometimes produces behavior that does not appear natural, and requires the programmer to develop an admissible heuristic.

4.2 Crowd of Human Characters

In our next experiment we created policies to control groups of human characters (see Figure 4). The characters milled about, then a boulder fell from the sky and they ran away. The policies controlled the decision making of the characters (i.e., "turn left," "walk forward," etc), while the nuts-andbolts animation was carried out by a traditional skeletal motion system. Thus the policy only specified a small set of discrete actions (the real-valued policy output was quantized to be discrete). We created several crowd animations. In each animation, all characters used the same policy, showing the variety of behavior that can be achieved. Note that each policy we constructed only required a few minutes to capture all necessary state-action examples, and only a few thousand examples were required for use online.

To train agents to interact in a crowd we performed several brief demonstration iterations, randomly placing some static characters in a scene. The human trainer then guided the learning agent through the scene. Thus the agent learned how to behave in response to other agents around it in arbitrary positions.

We created two policies. The first was used before the boulder impact, and the second afterwards. In the first policy (pre-boulder), the environment was discretized into a 2D grid. s was formulated as the current orientation of the character, and the separation between it and the next three closest characters. Decision making was computed at a rate Δt of about twice per second. After the boulder hit the ground, we switched to another policy (with continuous state/action spaces) which simply directed the characters to run straight away from the boulder. This modularity made the policy learning easier.

5 Discussion

Our technique has a number of strong points. As has been shown empirically, policies can be learned rapidly. The aesthetic value of these policies was verified through informal user case studies (Table 3). Also, its use is natural and straightforward, it is applicable to non-technical users, and there is empirical evidence that it is a viable tool for current uses of EVAs (e.g., computer games and animation). In addition, our approach has a nearly fixed online execution time, which is a useful feature for interactive agents.

Improvements to our approach that are the subject of ongoing research include the following. First, note that a demonstrator's choice of actions may not make the character traverse all regions of the state space, leaving gaps in μ. This problem can be automatically solved, during training, by periodically forcing the character into these unvisited regions of the state space. Another important issue is perceptual aliasing, which can result in unanticipated character behavior. However, perceptual aliasing can be minimized through effective design of the compact state space.

We have opted for learning standard policies (no task structure or rules, e.g. [Nicolescu, 2003]) because it allows for the most work to be done through programming-bydemonstration versus explicit programming. However, the scalability of policies is limited. Our technique could be augmented with a task learning method from the literature and thereby gain additional scalability and planning behavior, but at the cost of greater programmer involvement. A good example is our crowd case study. Pre/post conditions (e.g. [van Lent and Laird, 2001]) for the discrete contexts could be learned, determining when to switch between policies.

Because our current technique learns deterministic policies, there are some interesting behaviors that it cannot learn. For example, complex goal-directed behaviors that must be broken down into sub-tasks. Moreover, our technique is limited to policies that are smooth state-action mappings.

Conflict elimination is important because demonstrator behavior may be non-deterministic, and conflicts may arise due to varying delays in demonstrator response time. These conflicts can result in unintended behavior or temporal aliasing (dithering) in the behavior. Our conflict elimination technique safely removes high frequencies in the state-action pairs, helping make μ a smooth and representative mapping. Also, unlike elimination through clustering [Friedrich et al., 1996], our method does not quantize or eliminate examples. As an alternative to eliminating conflicts, one may consider allowing disjunctive action rules or incorporating probabilistic actions, perhaps weighted by how often each conflicting action is seen during the demonstration period.

Policies can be incrementally constructed or adapted by adding new state-action pairs. If desired, older examples can be deleted, or conflict elimination can be run to cull less applicable examples.