Behavior Bounding: Toward Effective Comparisons of Agents & Humans

1 Introduction

Over the past twenty years, AI research has successfully demonstrated a number of techniques for constructing agents that exhibit intelligent behavior. Many applications have the additional requirement that the agent's behavior be consistent with that of a human expert. This is especially true for tasks in which the agent must simulate a human such as in train­ ing situations or in virtual social experiences such as on-line gaming.

For these tasks, the standard approach to developing ex­ pert level agents begins with knowledge acquisition. Unfor­ tunately, knowledge acquisition is usually imperfect. As are­ sult, significant resources must be spent on validation, which often requires both a knowledge engineer and domain expert to monitor the agent's behavior in a large number of test sce­ narios. In this paper, we present a method for automatically comparing two actors' behavior that could be used to over­ come this validation bottleneck.

The potential uses of automated behavior comparison ex­ tend well beyond knowledge-base validation. For example, a generalized approach for comparing two actors' behavior can be used to objectively score a Turing test. A perfect result would be indicated if no detectable differences between the human and its computer counterpart were identified. In addi­ tion, automated behavior comparison can serve as the core of an intelligent tutoring system, where the roles are reversed. A novice human's behavior is compared to a computer agent's behavior which serves as a gold standard and information about the student's errors is used to guide the lesson. In all of these applications, the basic process for comparing behavior is identical. The differences only stem from the source of be­ havior (e.g. human or machine, expert or novice) and how the results of the comparison are used (to identity programming errors, to score a test or to guide a lesson). For simplicity and cohesiveness, this paper will focus on using behavior compar­ isons to aid the knowledge-base validation problem, but the discussion and results can also be applied to the other tasks as well.

*This work was supported by the Office of Naval Research, con­ tract N61339-99-C-0104

2 Interactive Human-Level Agents

The need for behavior comparisons is particularly pro­ nounced when the agent must masquerade as its human coun­ terpart (the expert). These agents, which we term interac­ tive human-level agents, are distinguished by two properties. First, the agent's performance is judged based on its ability to behave as the human expert would behave. Secondly, like humans themselves, interactive human-level agents must in­ teract with an external environment in order to perform many of their tasks.

A good example of an interactive human-level agent is TacAir-Soar [Jones et a/., 1999]. TacAir-Soar flies virtual military planes as part of a simulated training exercise. Team­ mates may be other TacAir-Soar agents or human counter­ parts. Because the agents are intended to model expert level behavior, it is not acceptable just to achieve the final states (e.g. shooting down the enemy planes). Instead, th~ age~t must generate the same behavior as the expert. Meetmg th1s requirement is challenging because the expert may perform the task differently on different occasions.

In the remainder of this paper, we first begin by examin­ ing a simple method of comparing a computer agent's be­ havior to a human expert's behavior. Deficiencies with this method lead us to examine more sophisticated model-based approaches. In Section 4 we summarize desirable features of such an approach. Then, beginning in Section 5, we present our method of model-based behavior comparison.

3 Toward Automated Behavior Comparison

Before two actors' behavior can be compared, the behav­ ior must be represented in a form that can be processed by the comparison algorithm. We can do this most eas­ ily by storing individual instances of behavior, or behav­ ior traces. A behavior trace is a sequence of tuples B = ((s , G, a)o , (s , G, a)l , ... , (s, G, A)n) in which each tuple (s, G, a)i indicates the environmental state (s), the goals be­ ing pursued by the actor (G), and the action being performed (a). The state and action portion of the behavior trace can be captured by observing the actor perform the specified task. The actor's goals are necessary to disambiguate instances when different actions are performed in equivalent environ­ mental states. Depending on whether the actor is human or computer agent, the actor may need to record how their goals change during the task.

A simple approach to comparing the actor's behavior can be performed with the following steps:

Acquire a set of behavior traces from the human expert and the agent for the specified task. These sets, H and A, represent the human expert's and agent's behavior re­ spectively over a number of different trials.

Extract relevant features from the behavior traces. Some in­ formation gathered through observation may not be use­ ful to detect errors. In this step, the salient features from the sets H and A are used to create two new sets of se­ quences H* and A*.

Compare each sequence a E A*, to the contents of H*. Compute the minimal number of edit operations (insert, delete, modify) that would be required to transform a into h, where his the sequence in H* that is most simi­ lar to a. Each edit operation indicates a potential error.

Report all deviations (after removing any redundancies) be­ tween the human's and agent's behavior. This report summarizes all potential errors.

This simple approach performs a more detailed analysis of behavior than simply checking that the agent and the expert reach the same final (goal) state. In this way, the agent's ex­ ternally observable behavior as well as some aspects of its internal reasoning process can be inspected to ensure that it is consistent with the human expert's. In addition, this method­ ology has the ability to identify a large number of possible errors because it has access to all the salient properties of the behavior trace.

However, this simple approach also suffers from a num­ ber of potentially serious flaws. First, the representation of the actors' behavior is a set of sequences extracted from the behavior traces. These sets grow as more observations are considered. Because interactive human-level agents can typ­ ically solve problems in a number of different ways, and be­ cause the environments they operate within are complex, it is likely that a very large number of observations will be re­ quired to adequately cover the actor's behavior. This problem is exacerbated by the fact that the sequential representation makes no assumption about how the actor's behavior might be constrained. Although this makes it possible to use this simple approach with any variety of behavior, it also makes it impossible to leverage regularities that might exist in large classes of goal directed tasks.

4 Model Based Approaches

To improve upon the simple approach for automated error de­ tection described in Section 3, we propose a model-based ap­ proach to comparing actors' behavior. Central to any such ap­ proach are the properties of the behavioral model. Our choice is guided by the following requirements:

Low Complexity Unless the new model is significantly less complex than the agent's knowledge base, understand­ ing the model and the behavior it represents is no eas­ ier than examining the knowledge base directly. For the model to be an asset, it must provide an adequately ac­ curate representation of behavior while remaining easy to understand.

Low Effort We have argued that one of the main uses of the behavior comparison is to reduce the cost of validating a human-level agent. In order to accomplish this goal, the human effort required to build the behavioral models must remain low.

Compatibility Behavior comparison has a number of poten­ tial applications, but most rely on being able to examine both human and software agent behavior. Thus the rep­ resentation must be limited to data that can be collected from either of these types of participants.

Efficiency Human-level agents operate in complex environ­ ments and may perform their tasks in a variety of differ­ ent ways. To address this problem, a model may be built using observations of expert behavior. In this case, it must be possible to generate the model efficiently, even if many observations are required.

Efficacy Meeting the preceding requirements will come at a cost. Most likely this will be a decreased ability to distinguish between some types of behavioral deviations (potential errors). A good representation will nonethe­ less be able to identify a wide range of behavioral devi­ ations that are likely to occur within the target environ­ ments and overlook meaningless differences.

Prior work in model-based diagnosis (e.g. [Lucas, 1998]) has examined how to detect errors given a model of correct behavior. In general, however, the models in these systems are relatively complicated and intended to identify problems with mechanical or solid state devices as opposed to software agents. However, one system, CLIPS-R [Murphy and Paz­ zani, 1994] was designed expressly for validating software agents.

In CLIPS-R, the behavior model consists of environmen­ tal constraints that must be met initially, as well as during and after task execution. In addition, the model can include a finite state machine which identifies acceptable sequences of actions pursued by the agent. Superficially, the require­ ments for the CLIPS-R approach seem relatively simple to meet. However, specifying this additional knowledge is a manual process that can significantly increase human effort and ironically can introduce a recursive validation problem for the constraints.

5 Behavior Bounding

As an improvement to CLIPS-R and to the simple method presented in Section 3, our approach to behavior ~ompari~on, called behavior bounding, automatically and efficiently builds concise models of both the human's and agent's behavior by examining behavior traces. The model of the expert's. behav­ ior is used to identifY boundaries on acceptable behaviOr, and potential errors are reported by comparing the model of agent behavior to these boundaries.

5.1 A Hierarchical Model

The advantages of behavior bounding all stem from its rep­ resentation of behavior. Behavior bounding is inspired by the hierarchical representations used in AND/OR trees, HTN planning [Erol et al., 1994] and GOMS mo.delin~ [John .and Kieras, 1996]to encode the variety of ways m which particu­ lar tasks can be accomplished.

The hierarchical behavior representation (HBR) used in our approach is illustrated in Figure 1A. Th~ hierarchy is an AND/OR tree with binary temporal constramts represent­ ing the relationships between the actor's goals and actions. In this representation, internal nodes correspond to goals and leaves correspond to primitive actions. A node's chil­ dren indicates the set of sub-goals or primitive actions that are relevant to accomplishing the specified goal. For ex­ ample, in Figure 1A, the sub-goals Destro~-Lea? and Destroy-Wingman are relevant for completmg their par­ ent goal, Engage- Enemy. The manner in which sub-goals should be used to achieve their parent goal is encoded by the parent's node-type constraint (AND vs OR) and the ordering constraints between sub-goals. In Figure 1A, AND and OR nodes are represented with ovals and rectangles respectively. Binary temporal constraints are represented with arrows be­ tween siblings. Thus, the hierarchy specifies that Engage­ Enemy may be correctly accomplished by first accomplish­ ing Destroy-Lead and then accomplishing Destroy­ Wingman.

This model of behavior is clearly less complex than the agent's underlying knowledge base. Indeed, it is likely to be less complex than the model used by CLIPS-R. Behav­ ior bounding abstracts away internal data-structures the agent may use in problem solving that cannot be represented by the constraints in the hierarchy. This means, that the HBR alone could not be used to perform some basic tasks such as depth first search. This begs the question, if the agent's behavior can be represented using such a simple structure, why was it not programmed in this representation to begin with? The hypothesis here is not that this representation is sufficient to completely capture the agent's behavior. Most human-level agents do rely on intermediate data-structures that are not available through the environment or through the structure of the goal hierarchy. However, our hypothesis is that the representation provided by behavior bounding is sufficient to identifY a large class of possible errors in ag~nt behavior wi~h­ out sacrificing efficiency. Moreover, we believe that be~avwr bounding can also help identifY potential problem spots m the agent's knowledge (e.g. a specific goal) even if an exact error cannot be identified.

In contrast to the behavior representations used for the simple comparison described in Section 3, the HBR makes two strong assumptions about the organization of the actors' knowledge and the effects this will have on their behavior. These assumptions increase the efficiency and efficacy of er­ ror detection for certain types of human-level agents.

The first assumption used by the behavior bounding ap­ proach is that the actor's goals are organized hierarchically, with more abstract goals placed toward the top of the tree. We also assume that at any point in the problem solving pro­ cess the actor pursues a set of goals belonging to different levels in the hierarchy. This set, referred to as the goal stack, corresponds to a path in the hierarchy beginning at the top node and descending to the most concrete sub-goal that IS currently being pursued by the actor. Figure 1 B illustra.tes .a possible goal stack maintained by the actor whose behaviOr IS represented in Figure 1A.

The second assumption leveraged by behavior bounding relates to the independence of goals. Temporal constraints can only be formed between sibling nodes, and AND/OR clas­ sification determines which of a node's children must be per­ formed for a particular task. This makes it is easy to con­ strain the way a particular goal is achieved, but difficult to represent constraints between arbitraryyarts of the hie~archy. Although this may cause problems with some agent Im~le­ mentations, this property has significant benefits. Most Im­ portantly, it decreases the number of observations that are re­ quired. Consider a task that requires completing two goals, each of which could be fulfilled in four distinct ways. A se­ quential representation that makes no assumptions about goal independence (such as the one described in Section 3) would require sixteen distinct observations to cover the acceptable behavior space where as behavior bounding would onl.y re­ quire four observations. This significant impact on efficiency is the direct result of leveraging the assumption about how goals are likely to add regular structure to an actor's behav­ Ior.

5.2 Identifying Errors

In general, we can view a behavior comp~ison method a~ an algorithm which divides the space of possible beh~vwrs I~ to two regions: behaviors that are likely to be consistent with the expert, and behaviors that are likely to be inconsi~tent with the expert. The simple comparison method descnbed in Section 3 does this by enumerating consistent behaviors.

In behavior bounding, however, the constrained hierarchical representation allows us to break the space of possible behav­ iors into more refined regions.

We begin by noting that the constrained hierarchical rep­ resentation allows us impose order on the space of possi­ ble behaviors. In particular, we can define an ordering from specific to general over the behavior hierarchies, by starting with a maximally constrained hierarchy (at the top) and it­ eratively removing constraints until none remain. Construct­ ing a representation of an expert's behavior (Section 6) per­ forms this same generalization, but most often stops before all constraints have been removed. Figure 2, in which each node represents a behavior hierarchy, illustrates this ordering. Once we have created a representation for the expert's behav­ ior, we can identify the node it occupies in this ordered space (call this node A in Figure 2). This node (the upper boundary node) allows us to easily determine if the agent's behavior is likely to be correct. Because correct behavior must be con­ sistent with expert behavior, an agent whose behavior repre­ sentation is a specialization of the expert's (i.e. lies above A in the generalization lattice) exhibits behavior that is is likely to be correct.

The node that represents the completely unconstrained goal hierarchy is at the bottom of Figure 2 (labeled B) and provides a lower boundary. It contains the most basic specification for what may constitute acceptable agent behavior and as a result could be used to identify behavior representations that are known to be incorrect. Such representations would have a goal decomposition structure that was inconsistent with (i.e. contained different parent/child relationships than) this lower boundary (nodes in the right side of Figure 2).

Using the upper and lower boundaries described above we can classify any representation of agent behavior as: likely­ correct (a specialization of the expert's behavior representa­ tion); likely-incorrect (a specialization of the expert's goal decomposition structure); and known-incorrect (inconsistent with the expert's goal decomposition structure).

Clearly, the hierarchical representation used by our ap­ proach describes behavior at a much higher level of abstrac­ tion than a typical knowledge base and in so doing, it presents a much more concise illustration of potential behavior than, for example, a set of individual rules. As a result, it meets our first requirement (low complexity). In addition, this represen­ tation can be generated automatically by examining behavior traces of an actor's performance on a task thus meeting the second requirement (low human effort). And because the be­ havior traces can be captured from either human or agent be­ havior with only minor support from the human participant, this model meets the third requirement. In the following sec­ tions, we will examine the remaining requirements in detail.

6 Learnability

In this section, we examine two aspects of behavior bound­ ing's hierarchical representation: the effort required to cre­ ate and maintain it, and its ability to represent behavior effi­ ciently. Both of these requirements are addressed by the over­ alllearnability of the representation. That is, if the representa­ tion can be learned from observations (as we have suggested), then it requires human effort only to initiate the learning pro­ cess. If the learning procedure is efficient, and the data struc­ ture's growth is limited, we can further say that the hierarchy represents behavior efficiently.

The learning procedure for constructing the HBR extracts goal stacks and actions from a behavior trace, forming a hi­ erarchical structure such as the one illustrated in the previ­ ous section. After processing the first behavior trace, the hierarchy contains the maximum number of constraints (i.e. AND/OR constraints on the goals and binary temporal con­ straints between siblings) that are consistent with the behavior in the trace. So, if each goal in the hierarchy is pursued only once while performing the task, all internal node-types are AND (maximally constrained) and all sibling internal nodes are totally ordered (again, maximally constrained). 1 Upon examining subsequent behavior traces, the hierarchy is gen­ eralized in such a way that it remains maximally constrained with respect to all of the behavior traces it has processed.

Due to page limitations, we cannot present the learning al­ gorithm in detail, however it should be clear that the hierarchy can be built as described above with complexity O(LINI 2 ), where INI is the size of the goal hierarchy and Lis the length of the behavior trace. In most cases, it is reasonable to as­ sume that one property of expert quality behavior is comple­ tion of the task within a number of steps proportional to IN I· When this assumption holds, we can say that this algorithm is bounded by O(INI 3 ) in time and space, with respect to the size of the input (i.e. the length of the behavior trace). Be­ cause this complexity is a low order polynomial of INI, the hierarchy is efficient when encoding an instance of behavior.

We can also classify the sample complexity of our hier­ archical representation. We can think of our representation as an ordered tuple P = (p1, P2, ... , PiN I) where each Pi is itself a tuple containing the type of the node i (either AND or OR), as well as a list L = (h, l 2 , ··. , ltNI) such that la = 1 iff gi is ordered before la Note that since ordering constraints only occur between siblings, the length of the Jist L would only need to be length INI in the degenerate case. The size of this hypothesis space is bounded by 21NI+INI 2 · Using Haussler's equation [Haussler, 1988], the number of training examples m required to learn the appropriate behav­ ior representation is bounded by:

1 The leaves, representing primitive actions, will only be totally ordered if each action was used only a single time to achieve its parent goal.

This indicates that the required sample size is polynomial with respect to the number of goals in the hierarchy (\N\). This, together with the fact that the time required to incorpo­ rate a new behavior trace into the learned HBR is also polyno­ mial in \N\, shows that our representation is PAC-Learnable. This means that the HBR efficiently represents aggregate be­ havior as well an individual instance of behavior, thus meet­ ing our fourth requirement.

7 Efficacy

The efficacy of behavior bounding is addressed by two com­ ponents. First, how good is the unconstrained hierarchical representation (the lower boundary) at identifying behavior that is known to be incorrect. Second, how well does the expert's representation (the upper boundary) serve to distin­ guish between potentially correct and incorrect behavior.

At first glance, it is not obvious how much behavior can be filtered by the lower boundary. However, its effectiveness as a filter is quite surprising. Consider an unconstrained behavior representation with branching factor b and depth d. Without loss of generality, assume that the nodes are uniquely labeled. For simplicity, also assume that at any level in this hierar­ chy, the actor completes its current goal before starting the next goal. Then, we could define an actor's behavior as a sequence of symbols chosen from the lowest level of the un­ constrained hierarchy. For behavior sequences of length b d, in which no symbol is repeated, there are b! 8 \s = L;~~ bi possible sequences that are consistent with the goal decom­ position of the unconstrained hierarchy. In contrast, there are bd! sequences in which the symbols may be placed without necessarily conforming to the unconstrained hierarchy. For a hierarchical structure of depth 4 and branching factor 2, only 1 in approximately 6.4 · 10 8 of the possible sequences oflength 16 are consistent with the goal decomposition spec­ ified by the unconstrained hierarchy. This illustrates the po­ tential power of the lower behavior boundary to discriminate between behavior that is potentially correct and the large col­ lection of behavior that is inconsistent with the expert's goal decomposition structure, and thus known to be incorrect.

To examine how well the expert's representation distin­ guishes between correct and incorrect behavior we would ide­ ally examine a large set of hand-programmed agents before they have been validated. Unfortunately, this is not feasi­ ble. Instead, we make random modifications to an agent's knowledge base. These modifications introduce unbiased be­ havioral flaws in the agent program, and experiments are per­ formed to determine how well each type of error is identified. Because the modifications are made randomly, the errors that are examined will not be biased by our expectations about how easily they will be to identified.

Our experiments are performed on a series of agents within a simulated object-retrieval environment. The object-retrieval task requires both planning and reactive reasoning. Initially, when given the task, the agent must plan a route through known territory to a building thought to contain the desired artifact. Because the agent has no prior knowledge of the building's layout, it must explore the facility until the object is found, and then find its way back out. The task is complete once the agent leaves the building with the object. A behavior comparison metric's performance is judged based its ability to correctly identify errors in agent behavior, to identify all errors that have occurred, and to produce minimal amounts of spurious information in the report.

7.1 Methodology

We implemented the algorithm described in Section 6, along with two version of the simple approach de­ scribed in Section 3 to serve as benchmarks. The first benchmark, the action sequence, extracts the se­ quence A = (ao, at, . .. , an) from the behavior trace B = ((s, G, a)0 , (s, G, ah, . . . , (s, G, a)n) while the sec­ ond benchmark extracts the sequence of goals G (Go,Gt, .. . ,gn) from B . Remember that the benchmarks are not particularly efficient representations; they can grow exponentially and have an exponential sample complexity. However, they do make interesting benchmarks of efficacy.

We initially constructed an agent that solves the problem in a very rigid manner. That is, across different attempts, the agent will complete the task using identical behavior so long as it is provided identical initial states and so long as the environment responds identically to its behavior. Given this agent, we performed modifications on its knowledge-base by randomly removing rules that determine preferences between competing goals and actions. The results of these modifica­ tions are agents that complete the task successfully in the tra­ ditional sense (i.e. they reach the same end state), but have increased flexibility in terms of the sequence of goals and actions they use to achieve that final state. In addition, the behavior exhibited by these modified agent's cannot be clas­ sified as incorrect by the lower behavior boundary node. As a result, these tests directly examine the abilities of the upper boundary node to distinguish between correct and incorrect behavior.

Each family of experiments begins by selecting two agents, e and n, such that n is a modified (more flexible) version of e. We designate e as the expert, and n as the novice. Because n is more flexible than e, it will behave in certain ways that are not consistent with expert behavior-these are errors.

After the expert and novice have been selected, they are individually incorporated into a simulation so their behavior can be observed. We then gather between 10 and 15 behavior traces of the actors performing their task, ensuring that no two behavior traces are identical. These traces form the sets BTE and BTN for the expert and novice respectively. Finally, each behavior trace in BTN is examined manually to determine what errors it contains.

The captured behavior traces are then split into a number of subsets: ni C BTN and ei C BTE. A single experi­ ment consists of examining each comparison method's per­ formance on a pair of these subsets (ni and ej)· A family of experiments contains the experiments that compare all n i to all ej for a particular novice/expert pair. Thus comparing four expert/novice pairs results in four experiment families although the total number of individual experiments may be much larger. By constructing experiment families in the way, we are able to examine the impact of different observational data more easily.

7.2 Results

For each experiment, we begin with a record (summarized by our manual examination of the agent's behavior traces) of what behavior errors were committed by the agent; these are true errors. This record identifies both low-level true er­ rors such as omissions, commissions, and intrusions, as well as higher-level true errors such as misplacement, or repetition which are the result of multiple low-level errors. We then col­ lect a summary from each comparison method about how the agent's behavior differed from the expert's behavior. Based on this, we record the number of true errors that occurred but were not identified by the summary (false negatives). Then, for each behavioral deviation in the summary we manually determine whether it indicates a new true error in the agent's behavior. If so, this -deviation is meaningful and thus a useful part of the report, otherwise it is spurious.

To judge the performance of a comparison method, we first determine how many errors it fails to identity (false nega­ tives). From this standpoint, all comparison methods per­ formed relatively similarly. Across all experiment families the range on false negatives is between zero and 1.75 for all comparison metrics. However, in each experiment fam­ ily behavior bounding does perform slightly better than the rest, maintaining the lowest average score, and achieving zero false negatives in five experiment families.

The other performance criteria we are interested in is how much of the comparison method's summary is useful. Be­ cause the summary is likely to be analyzed by a human, spu­ rious errors are undesirable because they require human effort to examine and follow-up before they can be dismissed. If a summary is largely spurious errors, it is unlikely that any­ one would actually care to read it. On the other hand, if the summary provides a large amount of good information, an occasional spurious error is likely to be acceptable.

This can be expressed as a ratio of how many true errors can be identified by the deviations listed in the summary to the total number of deviations listed in the summary. We call this value the report density of the summary. Thus, a compar­ ison method that reports no meaningful deviations, and only spurious information will have a report density of zero. Note that it is possible for the report density to be higher than one . When a deviation in the summary correctly identifies a high­ level error (such as the agent performing action a before bin contrast to the expert who performs b before a) we consider the summary as also identifying all the low-level errors that form this high-level error (e.g. two commissions in which a replaces b and vice-versa). This means that from the point of view of report density, it is better to identify high-leveler­ rors than low level errors. Because we should favor concise summaries, this is exactly what we want. Figure 3 illustrates the average report density of each comparison method's sum­ mary over all experiment families. Overall, behavior bound­ ing outperforms the other metrics by achieving an report den­ sity of one or higher in six of the seven experiment families.

7.3 Conclusions

Our behavior bounding method uses an abstract model of be­ havior to identify potentially problematic differences between two actors. This in tum leads to a semi-automated method that can be used to validate complex, human-level behavior. Moreover, behavior bounding offers significant advantages over prior validation approaches and traditional manual tech­ niques: it can be easily be used to validate an agent when human performance is the specification for acceptability; it requires only minimal human effort to initiate and perform the behavior comparisons, and behavior bounding is effective at identifying errors, even when compared to methods that are not constrained by efficiency requirements.