Learning And Abstraction In Simulation

ABSTRACT

Complex simulation programs typically require large amounts of computation to produce highly detailed output difficult for users to understand . Building abstracted simulation systems that simplify both computation and output can make simulation both more economical and more intelligi­ ble . We describe an approach to abstracted simula­ tion that uses a scenario network to represent typ­ ical sequences of events in the simulat~on domain. Abstract simulation output is generated by proba­ bilistically determined event-to-event transitions within the network. A learning process determines probabilities and builds up more abstract "chunked" events based on the actual frequency of event sequences in runs of the detailed simulator. The approach is generalizable across domains, and ful­ fills many of the goals of abstracted simulation: reducing computation, saving resources, filtering information and providing aggregated, intelligible output .

I !N"TRODUCTION

Artificial Intelligence techniques developed over the last decade have enabled us to create complex simulations in many domains. Such simulations typically include many rules that govern interactions between system entities and engage in intensive computation in order to gen­ erate their output. The complexity of these simu­ lations can pose problems, however, in situations where the user is time-limited, or cannot afford the necessary computation, or is interested only in rough results. Furthermore, the output of such simulations, which often consists of an agonizingly detailed trace of system events, can be difficult to understand at a global or intuitive level . These two considerations, economy of resources (time, cycles) and intelligibility, argue for the development of abstracted simulation systems, simu­ lations of reduced complexity that ignore certain interactions or collapse over some dimensions relevant in the detailed simulation . Abstracting a detailed simulation can simplify both computation and output, providing a general picture of simula­ tion events with a minimum expenditure of resources .

Our interest in abstracted simulation was stimulated by our work on the ROSS simulation environment and our implementation of strategic air warfare simulator [5]. The detailed simulator includes objects such as bombers, fighters, radars, targets and command centers. These objects interact according to heuristic rules to produce

events such as radar detections, bombings, fighter

LEARNING AND ABSTRACTION IN SH!ULATION

Sarah E. Goldin and Philip Klahr

The Rand Corporation

Santa Monica, California 90406

assignments, dogfights, and so on. Although ROSS has a graphics output capability that improves intelligibility, its main output is a lengthy event history . Furthermore, its speed decreases as increasing numbers of objects are included in the simulation. Hence, we have turned to abstracted simulation as a means of fulfilling several goals : 1) Filtering and aggregating output to improve inte 11 igibi 1 i ty; 2) Allowing "quick and dirty" approximate simulations to save resources; 3) Allowing the user to choose a level of detail appropriate to his or her needs . In addition, we have found that· abstracted s.imulation provides an arena for exploring a number of interesting AI issues involving learning and knowledge representa­ tion .

II A SCENARIO-BASED SCHEME -roR-ABSTRACTED-sfHULA~

Many alternative approaches to abstracted simulation are possible: 1) abstraction over time , e . g. by coalescing micro-events into more aggre­ gated macro-events; 2) abstraction over instances, e . g. by replacing individual objects with generic class objects; 3) abstraction over space, e.g . by combining spatial areas or schematizing spatially defined entities (such as radar ranges or routes); 4) abstraction over procedures, e.g . by simplifying computations or caching average results as a sub­ stitute for computation [6] . In this research, we have focused on alternatives (1) and (2) . The abstracted simulation model (ASH) generates event output by following a probabilistically- determined path through a scenario network that represents prototypic event sequences within the domain. The event network represents multiple levels of tem­ poral aggregation; through interaction with the detailed simulation model (DSM), it builds abstract events by chunking together lower level events that tend to form recurring sequences in runs of the DSM . The user ca.n then choose a level of abstrac­ tion and run the abstracted simulator as an independent system.

The abstracted simulation process includes two phases, the learning phase, in whi ch the ASH uses DSM output to generate an initial scenario network and build up new macroevents , and the event generation phase, in which probabilistic event-to­ event transitions are used to produce an event trace similar to the DSM output . Each of these phases is desc ribed in more deta i l be low .

III LEARNING ~!:f.ASE

Building up an abstracted simulation model beg ins with user specification of elementary simu­ l ation events . The set of elementary events de rives from the output events produced by the detail ed simulation model. In the ROSS air battle simul ator, we used the event messages sent to the event reporting module to extract an elementary event set, e.g. "Radar4 detects bomber3", "Fighter9 detects bomberS" . During the learning phase, these elementary events are connected by links indicating t emporal succession to create elementary event net­ works.

Once the elementary events have been speci­ fied, they must be grouped according to the roles i nvo lved in each event. The actors in an event desc ription determine its roles . For instance, the r o l es associated with "Radar4 detects bomber3" are RADAR and BO~BER. Typically, the event trace of a detailed simulation will indicate clusters of roles that interact (participate in common events) during some portion of the simulation history . For exam­ p le, bombers interact with radars, with fighters and with targets, radars interact 1dth command­ centers and with bombers, and so on . We refer to these role clusters as interaction sets. At the conclusion of the learning phase, the AS~ scenario ne twork will include a subnetwork corresponding to each interaction set, comprised of events that

share the same roles.

In the learning phase, the elementary event set i s modified in response to input from the DSH. Links between elementary events are created when thos e events occur in succession in the DSH input. Probabilities for each event-to-event transition a re built up by monitoring the frequency of DSM events . Each event in the network keeps track of how often instances of that event occur in DSH runs; each event-to-event link keeps track of how of t en the two events it connects occur in succes­ sion . The ratio of link frequency to first-event frequency defines the conditional probability of trans i ting to the second event from the first.

~hen several events occur together with sufficient frequency, the ASH chunks them to create an abstract event that represents that event sequence as a single entity (Fig . 1) . This chunk­ ing depends on the fact that each link can also be viewed as a higher order event (namely, "event 1. then event 2"). Abstract events are created by linking together two pre-existing links. This_pro­ cess of aggregation can extend upw·ard, gen~rat1ng more and more general descriptions of doma1n

events .

Each interaction set is considered separately during the learning process . Links are created and incremented within each interaction set subnetwork, but not between subnetworks . However, the ASM monitors for the first event occurrence relevant to each subnetwork. When a first occurrence is detected, the ASH attaches a con­ straint action to the preceding event, indicating that the preceding event activates the new subnet­ work . In the air battle domain (and, we suspect, in other domains as well), interaction sets operate in cascade. Bomber/radar interactions trigger radar/command-center interactions, which trigger command-center/fighter interactions , and so on. The constraint actions associated with a triggering event represent these inter-subnet dependencies.

Figure 2 shows a portion of the subnetwork structure build by the current version of the ASH, including event transitions, abstract events, and constraint actions . The set of subnetworks created during the learning phase provide the basis for event generation .

IV E\'ENT �E~ERATIO~ PHASE

In the event-generation phase, the ASH acts like a Markov model, moving from event~state to event-stat~ based on the tr~nsition probabilities built up during learning . Event generation begins with the activation of the first subnetwork and the start i ng of a simulation clock . Activating a sub­ network involves setting its current state to a predefined start state and scheduling its first transition. Each subnetwork makes a transition every x clock ticks, where x is a subnet-specific parameter. The transition procedure probabilisti­ cally selects the next event state from the candi­ date set specified by the network. Sometimes, no linked event will be chosen, and the subnet will remain in the same event-state until the n€'Xt move. As each subnet transits to a new event-state, it can output the name of that event, thus producing an event history similar to that of the DSM.

The different subnetworks usually generate events independently. However, contingenci es between subnets require the execution of con­ straint acts associated with triggering events . For example, the event "Radar reports detection to command-center", a part of Sl'BNET2, should not be generated until after the SUBNETl event "Radar detects bomber" . During the learning phase, the constraint action (ACTIVATE SUBNET2) will be asso­ c iated with the "detection" event . If the subnet transits to that event, its constraint actions will be executed, allowing the "report" event to be gen­ erated by transitions in SUBNET2.

The event-generation phase of ASM allows the user to select several output modes. In the sampling mode, the user selects one or two roles to follow through the network. Only events involving the sampled roles are reported . Thus, this mode fulfills an information filtering function. Alter­ natively, the user may select the statistics mode, specifying statistics of interest (e.g. number of bombs dropped) and the number of each role should be considered. The AS~I treats the probabilities associated with inter-event transitions as propor­ tional factors, multiplying probabilities through the network until the event relevant to the statis­

tic is reached.

All discussion so far has focused at the elementary event level. However, the same pro­ cedures apply to generating events at higher levels of abstraction, since the structure of event objects and links is the uniform . In general, the higher the level of abstraction chosen, the fewer the events in the network, and the faster the ASM runs .

V EVALUATION A~~ CONCLUSIONS

A. Implementation Status

Both the detailed and the abstracted simu­ lation models are implemented in the ROSS language [7] , an object-oriented, message-passing language based on Kahn's DIRECTOR [4]. The learning mode has been implemented, using elementary events from a first generation detailed air battle model. The event-generation mode is in the process of imple­ mentation . ~leanwhi le, a second generation DS~1 is being created . Its more complex event structure will better test the power of the abstracted simu­ lation approach described here .

B. Limitations of the ASM Approach

Although the current approach seems promis· ing, it does have some limitations. First, no methods currently exist to guide the selection of elementary event messages for the original DSM . We have not defined "event" in any formal way, but have relied on intuition to structure the simula­ tion output into useful and manageable units. Further experience with this approach may enable us to translate these intuitions into formal pro­ cedures for event specification. Second, ASM learning capabilities are limited to chunking together existing event concepts; it cannot dis­ cover new concepts. However, much of human learn­ ing consists of similar chunking processes [3]. Third, the ASM is not as flexibly parameterized as would be desirable . The dPtailed model allows the user to changP both ohject parameters and rules of behavior [5] . The ASM trades flexibility and modi­ fiability for int e lligibility and speed .

C. Advantages of -~-~ ~S~1 Approach

The ASM approach offers many advantages . It can be genPralized to simulation in practially any domain. Any detailed simulation model can provide a set of elementary events on which the abstracted simulation can be based. Furthermore, this approach does fulfill many of the goals of abstracted simulation . It reduces computation, saves resources, allows information filtering, and generates aggregated, intelligible output . Finally, this prototype-based scheme in many ways it parallels the workings of human learning and memory. Based on world experience, humans build up prototypic event sequences that represent likely occurrences, i.e., scripts or schemata [8] . These event sequence representations can be considered at multiple levels of aggregation, e.g . scenes, episodes, etc. [1} When asked to predict the events that will occur in a specific situation, humans will retrieve typical events in the order they are likely to occur [2} . The ASM is not intended as a serious model of human memory and mental simulation. However, it may have heuristic value in investigating these areas, as well as practical value in improving simulation effective­

ness .

REFERE~CES

• jl J Abbott, V. and Black, J . 8. "Th~ Represent at ion of Scripts in Memory" , Yale l lniversity Cog­ ni tive Scienc.P Technical Report #5, 1980 .
• \2] Goldin, S .E. "Script.s and ~tental Simulation". Paper in preparation .
• 131 Haves-Roth, 8 . "Evolution of Cognitive Struc­ tu~es and Processes . " Psvchological Rev i e~A, 19 i'7. ~. :!60-278.
• j4J Kahn, K.M. "Director Guide'', AI Memo 4828, ~tassachusetts Institute of Technology AI Laboratory. Cambridg·. l1A, 1979.
• )5 ) Klahr, P. and Faught. o . S. "Knowledge-based Simulation . " lnProcPt:>dings, First Annual 1\ational Conference~ ~rtifici~ Intelligence, stanford Lnl\'ersity , 1980.
• )6 ) Lenat , D., Hayes-Roth, f . and 1\lahr, P. "Cogni­ tive Economy in Artificial Intelligence Systems." ln ProccedLngs lJCAI-2)', 531-536 .
• f7J ~lcArthur, D. and SO\o'lZral, H. "An Object· oriented Language for Constructing Simulations." ln Proceedi~ }JCAI·!J. .
• {8) Schank, R. and Abelson , R. Scripts, Plans,
• Gogls !!:!.~ Understan~. La\o:rence Erlbaum Associates, 1977 .