RESC: An Approach for Real-time, Dynamic Agent Tracking

1 Introduction

In a multi-agent environment, an automated agent of­ ten needs to interact intelligently with other agents to achieve its goals. Agent tracking - monitoring other agents' observable actions and inferring their unobserved actions, plans, goals and behaviors - is a key capability required to support such interaction.

1 We thank Rick Lewis and Yasuo Kuniyoshi for helpful feedback. This research was supported under subcontract to the University of Southern California Information Sciences Institute from the University of Michigan, as part of contract N00014-92-K-2015 from the Advanced Systems Technology Office (ASTO) of the Advanced Research Projects Agency (ARPA) and the Naval Research Laboratory (NRL).

This paper focuses on agent tracking in real-time, dynamic environments. Our approach is to first build agents that are (reasonably) successful in agent tracking in such environments, and then attempt to understand the underlying principles. Thus, the approach is one of first building an "interesting" system for a complex en­ vironment, and then understanding why it does or does not work (see [Hanks et al., 1993] for a related discus­ sion). ·In step with this approach, we are investigating agent tracking in the context of our on-going effort to build intelligent pilot a15ents for a real-world sy.ntheti.c air-combat environmentlTambe et al., 1995]. Thts envi­ ronment is based on a commercially developed simulator called ModSAF[Calder et al., 1993], which has already been used in an operational military exercise involving expert human pilots. For an illustrative example of agent tracking in this environment, consider the scenario in Figure 1. It involves two combating pilot agents- Lin the light-shaded aircraft and D in the dark-shaded one.

Initially, Land D's aircraft are 50 miles apart, so they can only see each other's actions on radar. For effective performance, they have to continually track these ac­ tions. Indeed, D is able to survive a missile attack by L in this scenario due to such tracking, despite the missile being invisible to D's radar. In particular, in Figure 1a, D observes L turning its aircraft to a collision-course heading (i.e., at this heading, L will collide with D at the point shown by x). Since this heading is often used to reach one's missile firing range, D infers the possibil­ ity that L is trying to reach this range to fire a missile. In Figure 1-b, D turns its aircraft 15° right. L reacts by turning 15° left, to maintain collision course. In Fig­ ure 1-c, L reaches its missile range, points its aircraft at D's aircraft and fires a radar-guided missile. While D cannot see the missile on its radar, it observes L's turn, and infers it to be part of L's missile firing behav­ ior. Subsequently, D observes L executing a 35° turn away from its aircraft (Figure 1-d). D infers this to be an fpole turn, typically executed after firing a missile to provide radar guidance to the missile, while slowing the closure between the two aircraft. While D still cannot observe the missile, it is now sufficiently convinced to attempt to evade the missile by turning 90° relative to the direction of L's aircraft (Figure 1-e). This beam turn causes D's aircraft to become invisible to L 's (doppler) radar. Deprived of radar guidance, L's missile is ren­ dered harmless.

Meanwhile, L tracks D's beam turn in Figure 1-e, and prepares counter-measures in anticipation of the likely loss of both its missile and radar contact.

Thus, the pilot agents need to continually track their opponents' actions, such as turns, and infer unobserved actions, high-level goals and behaviors, such as the fpole, beam or missile firing behaviors. This agent tracking ca­ pability is related to plan-recognition[Kautz and Allen, 1986; Azarewicz et al., 1986]. The key difference is that plan-recognition efforts typically focus on tracking a nar­ rower (plan-based) class of agent behaviors, as seen in static, single-agent domains. In particular, they assume that agents rigidly follow plans step-by-step. In contrast, agent tracking involves the novel challenge of tracking a broader mix of goal-driven and reactive behaviors. This capability is important for dynamic environments such as air-combat simulation where agents do not rigidly fol­ low plans - as just seen, pilot agents continually react to each other's maneuvers.

Agent tracking and plan recognition are both part of a larger family of comprehension capabilities that enable an agent to parse a continuous stream of input from its environment, whether it be in the form of natural lan­ guage or speech or music or simulated radar input, as is the case here (e.g., see [Rich and Knight, 1990, chap­ ter 14]). Resolving ambiguities in the input stream is a key problem when parsing all of these different types of input. One example of the ambiguity faced in agent tracking can be seen in L's turn in Figure 1-c. From D's perspective, L could be turning to fire a missile. Alter­ natively, L could be beginning a 180° turn to run away from combat. Or L could simply be following its flight plan, particularly if it has a much shorter radar range, and thus is likely unaware of D. Despite such ambigui­ ties, D has to track L's actions with sufficient accuracy so as to respond appropriately. The novel challenge in this domain - at least with respect to previous work in plan recognition - is that the ambiguity resolution has to occur in real-time. As the world rapidly moves on, an agent cannot lag behind in tracking. Thus, if D is late or inaccurate in its tracking of L's missile firing maneuvers in Figure 1-c, it may not evade the missile in time.

This paper describes an approach called RESC (REal­ time Situated Commitments) for agent tracking that ad­ dresses the above challenges. RESC's situatedness rests on its constant attention to the current world situation, and its tracking of other agents' actions in the context of this situation. Despite its situatedness, RESC does make some commitments about the other agent's unobserv­ able actions, behaviors and goals, and attempts to use those in tracking the agent's future actions. In ambigu­ ous situations, these commitments could be inappropri­ ate and could lead to failures in tracking- in such cases, RESC modifies them on-line, without re-examining past world states. Together, RESC's situatedness, immediate commitments (despite the ambiguities), and its on-line modification of commitments provide RESC its real-time character.

In the following, we first describe the process that RESC employs for tracking other agent's flexible and reactive behaviors (Section 2). This process enables RESC to be situated in its present as it tracks an agent's actions. Subsequently, RESC's ambiguity res­ olution and real-time properties are described in Section 3. These descriptions are provided in concrete terms, using an implementation cif the pilot ae;ents in a system called TacAir-Soar[Tambe et al., 1995J, built using the Soar architecture[Newell, 1990; Rosenbloom et al., 1991]. We assume some familiarity with Soar's problem-solving model, which involves applying operators to states to reach a desired state.

2 Tracking Flexible Goal-driven and Reactive Behaviors

In an environment such as air-combat simulation, agents possess similar behavioral flexibility and reactivity. Thus, the (architectural) mechanisms that an agent em­ ploys in generating its own behaviors may be used for tracking others' flexible and reactive behaviors. Con­ sider, for instance, D's tracking of L's behaviors in Fig­ ure 1-c. D generates its own behavior using the operator hierarchy shown in Figure 2-a. (The solid lines indicate the actual hierarchy, and the dashed lines indicate unse­ lected options.) Here, at the top-level, D is executing its mission- to protect its home-base for a given time pe­ riod - via the execute-mission operator. Since the ter­ mination condition of this operator -completion of D's mission- is not yet achieved, a subgoal is generated. 2 D rejects options such as follow-flight-plan and run-away in this subgoal in favor of the intercept operator, so as to combat L. In service of intercept, D selects employ­ missile in the next subgoal. However, since D has not reached its missile firing range and position, it selects get-firing-position in the next subgoal. Skipping to the final subgoal, maintain-heading enables D to maintain its heading, as seen in Figure 1-c.

2 A Soar operator has termination conditions - if the op­ erator's application (or new sensor input) changes the state so as to satisfy the termination conditions, then that opera­ tor and all of its subgoals are terminated. If the termination conditions remain unsatisfied, a subgoal is created, within which new operators are applied.

The operators used for generating D's own actions, such as in Figure 2-a, will be denoted with the subscript D, e.g. , interceptD. Operatorn will denote an arbitrary operator of D . Staten will denote the global state shared by all of these operators. It maintains all of the dynamic sensor input regarding D's own aircraft, such as its head­ ing and altitude. It also maintains dynamic radar input regarding L's aircraft, such as heading, range, collision course and other geometric relationships. Additionally, it maintains iwn-sensor information, e.g., D's missile ca­ pabilities. Together, staten and the operatorn hierar­ chy constitute the introspectable aspect of D, and in this sense may be considered as D's model of its present self, referred to as modeln.

Modeln supports D's flexible/reactive behaviors via its embedding within Soar; and in particular, via two of Soar's architectural features : (i) a decision proce­ dure that supports flexibility by integrating all available knowledge about absolute or relative worth of candidate operators right before deciding to commit to a single op­ erator; (ii) termination conditions for operators that support reactivity by terminating operators in response to the given situation[Rosenbloom et al., 1991]. The point here is not that these specific architectural features are the only way to yield such behavior , but rather that there are such features, and that they can be reused in track­ ing other agents' behaviors. To illustrate this re-use, we assume for now that D and L possess an identical set of maneuvers. (Note that this sameness of maneuvers is not necessary; all that is required is for D to have an accurate model of its opponent's maneuvers .)

Thus, D uses a hierarchy such as the one in Figure 2b to track L's behaviors. Here, the hierarchy (the solid lines in Figure 2-b) represents D's model of L's current operators in the situation of Figure 1-c. These operators are denoted with the subscript DL. This operatorDL hierarchy, and the statenL that goes with it, constitute D's model of Lor modelnL· Within modelnL' execute­ missionDL denotes the operator that D uses to track L's mission execution. Since L's mission is not yet com­ plete, D applies the interceptDL operator in the subgoal to track L's intercept. The unselected alternatives here, e.g., run-awayDL> indicate the ambiguity in tracking L's actions (however, assume for now that this is accurately resolved). In the next subgoal, employ-missileDL is ap­ plied. Since L has reached its missile firing position, in the next two subgoals, final-missile-maneuvernL tracks L's final missile maneuver, and point-at-targetDL tracks L's turning to point at D . In the final subgoal , D ap­ plies the start-f3-maintain-turnDL operator to stateDL> which does not (can not) actually cause L turn. Instead, this operator predicts L's action and matches the pre­ diction against L's actual action. Thus, if L starts turn­ ing to point at D's aircraft, then there is a match with modeln:r., 's predictions - D believes L is turning to point at Its target, D, to fire a missile. When L's aircraft turns sufficiently to point straight at D 's aircraft (Figure 1-c) , the termination condition of the point-at-targetDL operator is satisfied, and it is terminated. A new oper­ ator, push-fire-buttonDL> is then applied in the subgoal of final-missile-maneuvernL · This operator predicts a missile firing, although the missile cannot actually be ob­ served. Statenr, maintains a representation of the mis­ sile, and marks It with a low likelihood. Following that, the fpole-rightDL operator predicts L's right turn for an fpole . When this prediction is matched with L's turn in Figure 1-d, the missile's likelihood is changed to high. D now attempts to evade the missile, with beam-rightn. (D currently chooses arbitrarily between the execution of operatorn and operator 0 ~, as it generates its own actions, while also tracking L s actions.)

The above agent tracking process is related to pre­ vious work on model tracing in intelligent tutoring sys­ tems(ITS) for tracking student actions[Anderson et a/. , 1990; Ward, 1991]. However, that work has primarily focused on static environments. A recently developed ITS, REACT[Hill and Johnson, 1994], extends model tracing to a more dynamic environment. REACT relies upon a plan-driven tracking strategy, and deals with the more dynamic aspects of the domain as special cases. It specifically abstracts away from tracking students' men­ tal states. In contrast, pilots appear to track their opponents' behaviors in more detail. Such tracking is sup­ ported here via a uniform apparatus for the generation of an agent's own flexible/reactive behaviors and tracking other agents' behaviors. In particular, operatoro and operatoroL are selected and terminated in the same flexible manner. Thus, as stateoL changes, which it does in reflecting the changing world situation, new operatorso~;, may get selected in response. This is key to RESC's situatedness - L's on-going actions are con­ tinually tracked in the context of the current stateoL· For further details on this tracking technique, please see[Tambe and Rosenbloom, 1995].

3 Real-time Ambiguity Resolution

Ambiguity manifests itself in two forms in the agent tracking process introduced in the previous section. One form involves the alternative operators available for tracking the other agent's actions, as seen in the dashed boxes in Figure 2-b. Given these alternatives, it is diffi­ cult to make accurate selections of operator 0 L, such that their predictions successfully match L's actions. Should an operatoroL selection be inaccurate, in typi­ cally results in a match failure (if not immediately, then in some further operatoroL application). Thus, in Fig­ ure 2-b, the operatoroL hierarchy predicts L will turn to point at D's aircraft. Suppose this prediction is in­ accurate, and L turns in the opposite direction. This difference in the anticipated and actual action leads to a match failure, indicating an inaccuracy in tracking. Sim­ ilar match failures can also occur if L fails to begin (or stop) turning or maintain heading as anticipated.

A second form of ambiguity is seen in stateoL· StateoL needs to maintain the same types of informa­ tion as are in state 0 . Here, there is ambiguity related to both the dynamic sensor information and the static non­ sensor information. With respect to static information, there are ambiguities about L's radar and missile capa­ bilities. Even if these are resolved, there are ambiguities about dynamic information, such as whether L has de­ tected D on radar. For instance, in Figure 1-a, based on the static radar range information, D assumes it has arrived within L's radar range; but L may or may not have detected D, depending on its radar's orientation. Such ambiguities in stateoL are intimately connected to ambiguities in operatorDL> since the operatoroL hi­ erarchy is dependent on the current stateoL· Thus, if D assumes it is not detected on L's radar, then the interceptpL operator is ruled out, since there is nothing for L to mtercept. In contrast, if D assumes L has de­ tected it, then interceptDL is a likely possibility. A sub­ goal of interceptDL predicts L's turn to collision course, which is matched by L's turn in Figure 1-a- D now be­ lieves L has detected it, and L is going to collision course to intercept. Note that, if D believes that L has detected it, stateoL needs to maintain the various dynamic in­ puts that D believes L obtains from its radar regarding D's heading, range, geometric relationships etc. Fortu­ nately, many of these quantities are symmetric and can be reused from corresponding quantities in staten.

It is difficult to resolve the above ambiguities using methods that have been previously suggested in the model tracing literature. Ward[Ward, 1991] notes that previous model tracing systems have mostly relied on communication with the modeled agent to resolve am­ biguities. In air-combat simulation, such communica­ tion with enemy pilots is clearly ruled out. Ward's solu­ tion in the absence of such information is an exhaustive backtrack search of all of the different alternatives. In the example in 2-b, this involves an attempt to execute and match other operator hierarchies - generated by al­ ternatives such as run-awayDL or follow-flight-planDL - via a systematic backtrack search before committing to interceptDL· Unfortunately, this search-then-commit approach will very likely cause tracking to lag far be­ hind the rapidly changing world, precluding D from re­ sponding to L's maneuvers in real-time. Furthermore, given the volume of dynamic information on stateDL> the maintenance of multiple old copies of stateoL for backtracking could itself consume non-trivial amounts of space and time. Parallel real-time search of alterna­ tive modelsoL could eliminate the backtracking; how­ ever, we will focus on a sequential solution given the implementation technology available to us. Further­ more, parallelism may not be adequate when faced with the expected combinatorics in the number of alterna­ tives. Borrowing ambiguity resolution methods from the plan recognition literature would be yet another possibil­ ity; but the computational costs (intractability) of tech­ niques such as automated deduction[Kautz and Allen, 1986] are a significant concern.

So instead, we propose a new approach called RESC (REal-time Situated Commitments) that addresses the above concerns. As seen earlier, RESC's situatedness arises from its tracking of L's on-going actions and be­ haviors in the context of the current statel)L. RESC's commitment is to a single modelnL> with a single state:OL that records the on-going world situation in real-time and a single operatorDL hierarchy, that pro­ vides an on-going interpretation of an opponent's ac­ tions. Given the intense real-time pressure, RESC does not spend time trying to match alternatives; instead, it just commits to a single operatoroL hierarchy, and any facts inferred in stateDL due to this hierarchy. It then tries to use these commitments as context for tracking L's future actions. However, in some cases, the commit­ ments may get withdrawn given RESC's situatedness - as stateoL changes, it may satisfy the termination con­ ditions of an operatoroL and thus cause it, and all of its subgoals, to terminate.

When faced with ambiguity, it is possible that RESC commits to an inaccurate operatoroL and stateoL, leading to a match failure. RESC recovers from such failures by relying on a method called single-state back­ tracking, that undoes some of its commitments, result­ ing in the generation of new operatoroL hierarchies, in real-time. Of course, if RESC makes more intelligent commitments in the first place - by reducing the am­ biguity in the situation with which it is faced - there will be less of a need for undoing its commitments. Sub­ section 3.1 first describes strategies- some general and some domain specific - used for reducing ambiguities in both stateoL and operatoroL· Subsection 3.2 then

3.1 Reducing Ambiguities

There are two classes of strategies used in RESC to re­ solve ambiguities: active and passive. The active strate­ gies rely upon an agent's active participation in its en­ vironment to gather information to resolve ambiguities. In particular, an automated pilot, such as D, can act in its environment and force its opponent L to react and provide disambiguating information. Consider again the example in Figure 1-a. As discussed earlier, D faces am­ biguit~ in stateDL about whether L's radar has detected D. Thts gets resolved with L's turn to collision course. ynfortunately, if L just happens to be on collision course, 1t may not turn any further, and the ambiguity would be more difficult to resolve. In such cases, D can ran­ domly turn 15-20°, as shown in Figure 1-b, causing L to react if it wishes to maintain collision course. This provides D sufficient disambiguating information- L's radar has detected D. Unfortunately, D's actions in ser­ vice of active ambiguity resolution may interfere with its other goals, such as firing a missile at L. In general, such interference is difficult to resolve. Therefore, cur­ rently, active ambiguity resolution is based on a fixed set of known maneuvers (supplied by human experts).

In contrast, passive ambiguity resolution strategies rely on existing information to resolve ambiguities. One key piece of information is that in this hostile environ­ ment, an opponent is likely to engage in the most harm­ ful maneuver. This information is used in the form of a worst case strategy for disambiguation. Thus, given a choi~e, D always selects the worst-case operatorDL (from 1ts own perspective) while tracking L's actions. Fo~ instance, if there is ambiguity between run-awayDL or zntercep~DL> D will select interceptpL, which is more harmful. Stmilarly, D resolves ambigmty in the static in­ formation in stateDL via the worst-case strategy, e.g., it assumes that L's aircraft is carrying the most powerful missiles and radar that it can carry. Unfortunately, this worst-case strategy can lead to overly pessimistic behav­ ior. In the absolute worst-case, the only option for D is ~o run away. Therefore, D applies it selectively, typically m cases where it has to disambiguate rapidly, and yet no other means .are available. Thus, as seen above, D does not automatically assume detection by L's radar, even though that would be the worst-case assumption.

A second passive ambiguity resolution strategy is test incorporation[Bennett and Dietterich, 1986]. The key idea is to generate fewer incorrect alternatives in ambigu­ ous. situations. In particular, modelDL generates alter­ native operatorsDL that are tested by matching against L's actual actions. Observations regarding these actions can be used to avoid generating alternatives that are guaranteed to lead to match failures. For instance, in Figure. 1-d, fp?le-rightDL. and fp~le-lefiDL are two al­ ternatives avatlable to D m trackmg L's actions. If D already sees L turning to its right, then fpole-lefiDL can be eliminated, since it would be guaranteed to lead to a match failure. Test incorporation relies on such spatial relationships.

A third passive ambiguity resolution strategy is goal incorporation (e.g., see [Van Beek and Cohen, 1991]). The key idea here is to resolve ambiguities only to the ex­ tent necessitated by an agent's goals. For example, given the reality of the simulation environment, L's aircraft of­ ten unintentionally deviates from its intended heading. Given such deviations, L sometimes makes corrections to its headings. However, D does not really need to track and disambiguate these small deviations and cor­ rective actions. It therefore uses fuzz-box filters that dis­ regard specified deviations in L's actions. For instance for point-at-targetDL> which tracks L's pointing maneu~ ver (Figure 1-c), the fuzz-box filter disregards 5° of de­ viation in L's heading. Such filtering also helps to avoid tracking of detailed aspects of stateDL> and avoids am­ biguities there.

3.2 Single-State Backtracking in RESC

Based on the above disambiguation strategies, RESC commits to .a single stateD I,. and a single operatorDL hi­ erarchy, whtch track L's act10ns as described in Section 2. However, should this cause a match failure, single-state backtracking is used to undo some commitments. As its name suggests, this backtracking takes place within the context of a single stateDL· Starting from the bottom of the operatorDL hierarchy, operators are terminated one by one in an attempt to get alternatives to take their place. Some alternatives do get installed in the hierar­ ch.y, and possibly change stateDL> but lead to match fatlures. These are also replaced, until some alterna­ tive leads to an operatorDL hierarchy that culminates in match success. 3

Why is this process real-time? The main reason is that backtracking occurs without a re-examination of past se1_1sor input.or mental recreation of older statesDL· In particular, whtle backtrack search would normally in­ volve revisiting old statesDL and reconsidering the dif­ ferent operatorsDL possible in each of those states - creating an opening for combinatorics - RESC com­ pletely avoids such computation. Furthermore, although RESC does backtrack over the operator hierarchy, there are three factors that ameliorate the combinatorics there. First, given RESC's situatedness, backtracking remains tied to the present stateDL· Thus, while a match fail­ ur; is _recognized ~nd the backtrack process begun, L and D s aucraft contmue to move and turn, changing their speeds, headings, altitudes, and relative geometric rela­ ~ionshi~s (e.g., range, collision course, etc). StateDL 1s contmuously updated with this latest information. The backtracking process takes place in the context of this continuously changing state. Thus, only those al­ ternative operatorsDL that are relevant to the current ~tateDL get applied. Similarly, in some cases, changes m stateDL cause portions of the operatorDL hierarchy to terminate automatically during the backtrack process. In other words, RESC is continuously dragged forward as the world changes. Second, RESC does not oblige D to address the match failure before D can execute any of its own operatorsn . Thus D is free to act to the extent it can. Finally, indeed, if the world were to magically become static, RESC's strategy will result in a complex search, although still within the context of a single staten:(.. However, it is unclear if this is necessar­ ily problematic - a static world should possibly merit a more thorough search.

3 In a few cases, there are pending changes related to ambi­ guities in statenL, e.g., has L detected D? These are applied first, hoping they cause changes to operatornL and lead to success.

Let us consider some examples of single-state back­ tracking. As a simple example, suppose D has com­ mited to the modelnL in Figure 2-b. Initially, point-at­ targetDL has match success in that , as predicted, L in­ deed starts turning towards D(see Figure 3-a for an illus­ tration) . However, L !eally has decided to run away; so it continues turning 180° without stopping when point­ ing at D (Figure 3-b ). This leads to a match failure in the operatorn:J;. hierarchy. Single-state backtracking now ensues, termmating operators beginning from the bottom of the hierarchy. Finally, interceptDL is termi­ nated and replaced by run-awayDL· This predicts L to be turning towards its home-base, which successfully matches L's actions (Figure 3-c). Thus, D successfully applies run-awayDL> predicting and matching L's ac­ tions, without mentally recreating the statenL in which L may have initiated its run-away maneuver.

A slightly more complex example involves situations where L is engaging in a beam maneuver. Here, D ini­ tially matches fpole-rightnL' and even infers L's missile firing, as part ofstatenL· However, as L keeps turning, there is soon a match failure , causing D to backtrack until beam-rightnJ., successfully matches. There are two key points here. Fust, again D is successful in applying beam-rightDL> without mentally recreating the statenL in which L may have initiated its beam maneuver. Sec­ ond, D's earlier inference of L's missile firing is not re­ moved, even though it is based on a sequence of operators that eventually led to a match failure . This is because it is difficult for D to decide if L was initially maneuvering to fire a missile and then switched to beam, or if it was always engaged in beam. Not knowing any better, D does not eliminate the earlier inference from statenL· Fortunately, when aircraft turn goo to beam, they can. not provide radar guidance to their missiles. Therefore, with L's beam, D infers that the missile that it ear­ lier inferred on statenL has lost guidance and become harmless. The end result is identical to a case where D had successfully tracked L's beam maneuver, with­ out the failed intermediate inference of an fpole-rightnL maneuver.

We have so far found RESC's single-state backtrack­ ing to be successful in the air-combat simulation domain (see Section 4). Given the potential application of this approach for other areas of real-time comprehension, it is useful to analyze the reasons behind its success. To­ wards this end, consider first the following simplified and abstract characterization of a successful application of single-state backtracking: L initiates some maneuver {3 at time TO. However, at TO, D attempts to match it by applying an operator aDL to statef}L . (which denotes statenL at time TO) . At time TO+r, in statef:·{r D recognizes a match failure with anL· It backtracks and applies !3nL to statef:·{r . The key observation here is that despite the time delay T and the intervening ap­ plication of aDL> !3nL is successful in predicting and matching L's maneuvers, as though it were applied to statef)L. Based on this observation, in terms of opera­ tor preconditions and effects, we can infer at least three requirements that need to be met for single-state back­ tracking to work. In the following, we list these require­ ments, and illustrate how pilot agents currently adhere to them:

1. The preconditions of f3nL are satisfied in statef:(;r in much the same way as in statef)L: For pilot agents, operator preconditions are expressed so they do not test specific positions of aircraft, but rather abstracted features of statenL - similar to the fuzz-boxes in Section 3.1 - that are unlikely to change in r . That is, abstracted features tested by preconditions change at a rate smaller than 1/r.
2. The effects of !3nL when applied to statef:(;r are equivalent to the effects of !3nL when applied to statef)L: This is achieved by expressing operator effects relative to some feature of staten:(. that is unlikely to have changed in the intervenmg time period r. For instance, the effect of run-awayDL predicts L is headed towards its home base - the location of this base is unlikely to change within r. Similarly, the effects of operators such as beam­ rightnL are expressed in relative terms as L turning to achieve goo angle-off, which is an angle formed by L's heading relative to the straight line joining D and L (while this line does change its position in r , given the range between D and L the change is small, and gets absorbed by the fuzz-boxes) . If the effects were expressed instead as turning goo from L's current heading, they would have provided very different results at TO and TO+r, defeating single­ state backtracking. Overall, the above seems possi­ ble because operators in this environment typically strive to achieve positions relative to slowly chang­ ing reference points, such as turning to a particular heading relative to an opponent's aircraft, or rela­ tive to a waypoint such as the home-base.
3. The effects of anL as applied to statef)L are elim­ inated at some time TO+ r before they cause incon­ sistencies in D 's response: As seen in an example above, even though L's missile firing was inferred, and this inference was not "cleaned up" upon recog­ nition of a match failure, L's future maneuver auto­ matically nullifies the effect of that inference. For­ tunately, typical operatornL applications do not

commit to such inferences on stateDL· For those that do commit, these commitments get removed by future maneuvers or become irrelevant.

In some cases, L quickly terminates its maneuver {3 within time period r, and initiates a new one r at time TO+r. Here, given RESC's situatedness, at time TO+r, D completely skips tracking f3oL· and tracks rDL in­ stead. Fortunately, since D's imtlal attempt is to apply worst-case operatorsD_L, there is at least the assurance that what is skipped lf3DL) is not among the worst of the possibilities.

4 Implementation and Evaluation

To understand the effectiveness of the RESC approach, we have implemented it as part of an experimental vari­ ant of TacAir-Soar[Tambe et a/., 1995]. The current TacAir-Soar system contains about 2000 rules, and au­ tomated pilots based on it have participated in combat exercises with expert human pilots. Our experimental version - created to investigate the RESC approach - contains about 950 of these rules. Proven techniques from this experimental version, called TacAir-SoarRESC are transferred back into the original TacAir-Soar.

There are at least two aspects to understanding the effectiveness of TacAir-SoarRESC. The first aspect is whether the current approach enables D, the TacAir­ SoarRESC pilot agent, to track its opponents' actions accurately in real-time. We conducted two sets of exper­ iments to address this issue. The first set involved run­ ning Soar-vs-Soar air-combat simulation scenarios (as outlined by the human experts). The results from these experiments are presented in Table 1.

The first column lists the scenario number. The sec­ ond column lists the number of opponents that D faces in each scenario - this varies from one to four in these scenarios. The third column indicates the total num­ ber of D's operator executions in each scenario. This includes operators for D's own actions, as well as for tracking opponent actions. The total number provides some indication of the comparative complexity of the different scenarios. Note that these operators are not all applied in a sequence at regular intervals; D often waits in between applications as it tries to get into different positions. Indeed, despite the differences in the num­ ber of operators, the total time per scenario is about the same, approx 5 minutes. The fourth column shows the percentage of operator executions involved in agent tracking. This percentage clearly depends on the num­ ber of maneuvers that the opponents execute, and the number of opponents. The key point here is that agent tracking is a non-trivial task for D . Furthermore, higher percentages of operator executions may be dedicated to agent tracking with increased numbers of opponents.

The fifth column shows the percentage of agent track­ ing operators involved in match failures (counting oper­ ators at the bottom of the hierarchy that encountered the failure, but not their parents) . The main point here is that the overall percentage of these operator is low; at most 17% of the agent tracking operators are involved in match failures .

In all of these cases, D is successful in tracking op­ ponents in real-time so as to react appropriately. Even in cases where D encounters match failures, it is able to backtrack to track the on-going activities in real-time and respond appropriately. However, as the number of opponents increases, D does face resource contention problems. With four opponents, it is unable to track the actions of all of the agents in time, and gets shot down (hence fewer operators). This resource contention issue is under active investigation[Tambe, 1995].

Our second set of experiments involved Soar-vs­ ModSAF simulated air-combat scenarios. ModSAF­ based[Calder et a/., 1993] pilot agents are controlled by finite state machines combined with arbitrary pieces of code, and do not exhibit high behavioral flexibility. While D was in general successful in agent tracking in these experiments - it did recognize the maneuvers in real-time and respond to them - one interesting issue did come up. In particular, in one of the scenarios here, there was a substantial mismatch in D's worst assump­ tions regarding its opponent's missile capabilities and the actual capabilities - leading to tracking failures. Deal­ ing with model mismatch is also an issue for future work.

The second aspect to understanding the effectiveness of TacAir-SoarRESC is some quantitative estimate of the impact of agent tracking on improving D's overall perfor­ mance. In general, this is a difficult issue to address (see for instance the debate in [Hanks eta/., 1993]). Nonethe­ less, we can at least list some of the types of benefits that D accrues from this capability. First, agent track­ ing is crucial for D's survival. Indeed, it is based on agent tracking that D can recognize an opponent's mis­ sile firing behavior and evade it. Second, agent tracking improves D's overall understanding of .a situation, so it can act/react more intelligently. For instance, if an op­ ponent is understood to be running away, D can chase it down, which would be inappropriate if the opponent is not really running away. Similarly, if D is about to fire a missile, and it recognizes that the opponent is also about to do the same, then it can be more tolerant of small errors in its own missile firing position so that it can fire first. Finally, agent tracking helps D in pro­ viding a better explanation of its behaviors to human experts. (Such an explanation capability is currently being developed[Johnson, 1994]) . If human experts see D as performing its task with an inaccurate understand­ ing of opponents' actions, they will not have sufficient confidence to actually use it in training.

5 Lessons Learned

This paper presented an approach called RESC, for agent tracking in real-time dynamic environments. Our investigation was based on a real-world synthetic envi­ ronment that has already been used in a large-scale op­ erational military exercise[Tambe et al. , 1995]. Lessons learned from this investigation - as embodied in RESC - are as follows:

• To track other agents ' flexible and reactive behav­ iors: Reuse the architectural mechanisms that sup­ port an agent 's own flexible/reactive behaviors in service of tracking others' behaviors.
• To address ambiguities in real-time: Quickly com­ mit to a single interpretation, and use single-state backtracking to recover from erroneous commit­ ments.
• To address real-time issues in general: Keep track­ ing firmly tied to the now, i.e., to the present state.

One key issue for future work is investigating the gen­ erality of these lessons by applying RESC to other com­ petitive and collaborative multi-agent domains. One candidate that has been suggested is a real-time multi­ robot domain where robots track other robots or humans to collaborate in a task by observation (rather than by communication)[Kuniyoshi et al., 1994]. Beyond agent tracking, there is some indication that RESC could apply in other real-time comprehension tasks. For instance, a RESC-type strategy has been previously used in a real­ time language comprehension system[Lewis, 1993]. This system also commits to a single interpretation of an in­ put sentence despite ambiguity, and attempts to repair the interpretation in real-time when faced with parsing difficulties. We hope that investigating these broader applications will lead to an improved understanding of agent tracking and comprehension.