Simulation for ARPI and the Air Campaign Simulator
Contents
1. Set ES to nil and set E to head of PEL Check for Interaction Real ze E Illustrate E optional Unless ES Nil Pop ES Do Every Event Stuff Check Wakeup Time Functions Write out E optional Change Activity Figure 1 Pseudo code for the Mess engine the simulation so that it s easy to arrange for some thing to be executed continuously during the sim ulation For example data collection code is often executed this way The wakeup time step awak ens event streams that have been put to sleep for some reason For example the fire simulation ES is asleep when no fire is burning The write out step saves every event to a file so that a simulation can be analyzed or replayed if desired Finally the pro tocol includes steps to check for interactions and change activities these are discussed in the next section Activities and Interactions 6i Events are point like in that they happen at a momentin time For example a customer arrivesin a queuing simulation or a tile disappears in TILE WORLD However many kinds of simulations in volve things that happen over an interval of time these are called activities in MESS For example a train travelling from one station to another would be represented as an activity Activities are repre sented as a pair of point like events representing the beginning and ending of the activity MEss is designed not only to support activities but also interactions2. The Air Campaign Simulator The Air Campaign Simulator ACS is being de veloped at UMass as a testbed for work in the ARPA Rome Lab Planning Initiative Currently ACS implements the Korea Scenario developed by Doug Holmes at ISX We will briefly describe the key features of ACS Campaign level Simulation Activities in ACS are large scale abstract aggre gated and at the strategic campaign level For example actions in ACS include Observe Sup ply Show Force Blockade and the like Actions commit resources but again these are aggregated forces not individual airplanes with tail numbers Outcomes of actions are similarly general for ex ample an attack on a supply route may disrupt supply We do not fly specific aircraft against par ticular targets on the supply route we do not model the engagements of these aircraft and their targets we do not perform simulated BDA At the cam paign level it suffices to direct a wing against a supply route and assess the change in status of the supply route Campaign level Ontology Doug Holmes ontology of campaign level actions is fully implemented in ACS One can simulate cam paigns manually by selecting actions from this on tology and placing them on the timeline or get ting closer to the aims of ACS various ARPI plan ners can select and have ACS simulate campaign actions We have augmented Holmes ontology with various objects locations types of terrain and weat
3. is Timed Common Lisp TCL which has all the functionality of ordinary Common Lisp but each function advances the clock predictably and appro priately Most simulators including our PHOENIX system use elapsed CPU time to assess how long an agent has been thinking This approach is intu itive and straightforward to implement but it has drawbacks It is platform dependent so a simula tion will run differently on a different CPU oper ating system Lisp implementation or even a dif ferent release of the Lisp compiler In fact a simu lation will behave differently from run to run even if none of these factors change due simply to vari ability in CPU time Indeed this variability can be quite striking Anderson 1995 For replicable experiments for explicit reasoning about time for deliberation scheduling and other applications it is very valuable to have a database of timings for Common Lisp functions and for user defined func tions This TCL provides One can use Mess without TCL but for real time applications one should use TCL The overhead is minimal Ander son 1995 Instrumentation and Data Analysis MEss is completely inte grated with the cLIP CLASP an instrumentation and analysis package developed at UMass With CLIP one attaches alligator clips to pieces of code for example messages sent by agents envi ronment events or various activities These alli gator clips collect state information perio
4. might be needed for the realiza tions at the start and finish of the activity It also yields a single object for specializing the interaction function The engine takes care of informing the object that its role as the beginning of the activity is over and it now represents the end of the activity this is the purpose of the change activity step in the pseudo code in figure 1 Planners An on line or real time planning agent is integrated into a MEss based simulation as just another event stream The agent discovers the state of the simu lation by producing sensory events and it acts by producing effector events Thus from the view point of the MEss engine a thinking agent appears to be the same as any event stream obeying the same peek and pop protocol Some planners can certainly be implemented us ing the pre defined function event streams but be cause the function is executed from scratch each time there is no continuous stream of thought Therefore most agents will want to use the pre defined class of thinking event streams These event streams run the planner as a co routine switching control back to the MEss engine whenever the plan ner produces an event since an event signifies inter action with the simulation and so the simulation must be brought up to date The MEss engine lets the agent ES have its turn when it needs to get the next event from that ES and the ES runs until it computes an eve
5. the event occurs and how it modifies the representation of the world The how code is the realization method of the event and executing that code is called realizing the event The hierarchy of event classes can be used to group kinds of events such as all the move ment events or all the fire events so that they can be controlled and modified as a group Mess is a process oriented simulator Bratley Fox amp Schrage 1983 p 13 which means that each event is produced by a process and that process determines subsequent events For example things like fire weather and particularly an agent s think ing might each be separate processes in the simu lation The representations of processes are called event streams Event streams are also defined using CLos so that users can add other kinds of event streams if they need a particular way of producing events MEss has a central engine which interleaves the streams of events that represent different real world processes The MEss engine is so called be cause it controls all the events and event streams and it invokes the realization of events Discrete event simulators go from state to state in discrete steps which we call advancing the simulation Fig ure 1 presents pseudo code for the algorithm to ad vance the simulation Each time the simulation is advanced exactly one event is realized The event to be realized is whichever is nearest in the future In a queuin
6. Simulation for ARPI and the Air Campaign Simulator Paul Cohen Scott Anderson David Westbrook Experimental Knowledge Systems Laboratory Computer Science Department LGRC University of Massachusetts Amherst MA 01003 4610 cohen anderson westy cs umass edu Abstract We describe a simulation substrate for building real time simulators in a Common Lisp environ ment and a simulation of Air Campaign Planning implemented in the substrate The substrate is designed for experimental work Trials are repeat able and randomness is carefully controlled all as pects of the simulation are instrumented and inte grated with the UMass CLIP CLASP instrumen tation and analysis package The ACS simulator is for testing campaign level planners and simula tors The Need for Simulation As planners become more sophisticated they will solve increasingly large planning problems involv ing for example the movement and actions of thousands of vehicles over many hours and under changing conditions It is extremely difficult to in spect such elaborate plans and determine for ex ample their probability of success the extent to which their goals will be satisfied and so forth Nevertheless such evaluation is critical to a sci entific understanding of how and how well a so phisticated planner works Simulation provides a solution plans are run many times in the space of conditions that they were meant to handle and various dependent varia
7. arches dependency space in a best first manner guided by a user supplied evaluation function The sec ond version employs a statistical measure of depen dency strength and uses bounds that we derive for the value of that measure to prune huge portions of the search space When the algorithm termi nates it returns a list of the k strongest dependen cies that is equivalent to the list that would be re turned by an algorithm that exhaustively searched the space of all possible dependencies The third version is incremental it does not require an ini tial batch of data from the streams as the first two versions do but instead incrementally refines hy potheses about where strong dependencies exist as new data is acquired from the streams The fourth version is a distributed algorithm that runs on net works of machines All versions of the algorithm employ domain independent heuristics to make the search efficient and can be augmented with domain specific heuristics to maximize performance on spe cific problems We have successfully applied MSDD to classifica tion problems and to learning rules in a shipping network that relate current states to future patholo gies In the latter we demonstrated that MSDD can automatically acquire rules that allow an agent to manage the network as effectively as when the agent uses hand coded domain knowledge We are cur rently applying MSDD to the problem of predicting faults in computer networks
8. between activities and other events including other activities Suppose a bull dozer or other vehicle is traveling from A to B while another is traveling on an intersecting course from C to D In many simulators this collision would never be noticed but Mess keeps track of all current activities and checks for interactions Activities are essentially a kind of event that hap pens twice Whenever an activity starts it is placed on a list by the MEss engine and it is removed when the activity ends Each event that happens while the activity is on the list has the opportunity to interact with the activity This opportunity is implemented via the interaction function The in teraction function is a two argument CLOS generic function extended by the user since the seman tics of the interaction between the activity and the event is necessarily domain dependent The interaction can affect either the activity or the event or both A rain activity might cancel a scheduled fire ignition event which is why the MEss engine checks for interactions before realiz ing the event An event representing the firing of a surface to air missile might terminate a fighter plane s flight activity The movement activities of two vehicles might result in a collision with both activities affected by the interaction Activities are represented as a single object a sub class of an event This representation allows an easy sharing of information that
9. bles are measured and sta tistically analyzed Furthermore simulators enable the planner to be on line it can be an agent in an ongoing environment monitoring the progress of the plan and making additions or corrections as necessary An on line planner can even scrap a fail ing plan or sub plan and replan Howe 1993 If the thinking time of the planner is limited so that there is time pressure on its thinking the on line planning becomes real time planning A number of simulation environments already exist to support research in on line and real time planning Hanks Pollack amp Cohen 1993 Some of these simulators are quite domain specific such as our own PHOENIX testbed Cohen et al 1989 which simulates forest fires in Yellowstone National Park Other examples are TRUCKWORLD Hanks Nguyen amp Thomas 1992 and Trains Martin amp Mitchell 1994 where trucks or trains move cargo in a graph of depots cities and towns Other testbeds are much more domain independent such as the Mick testbed Durfee amp Montgomery 1990 in which agents move in a generic gridworld These testbeds all have to solve the fundamen tal issues of simulation such as managing events from many sources and getting them to occur in the correct order They have to deal with the in terface between planners and the environment and often that interface is not well defined Because of the many design decisions these testbeds are of ten not as eas
10. dically or in response to specified events and dump the data to CLASP for analysis The CLASP package incorpo rates dozens of statistical techniques its design em phasized exploratory data analysis over strict hy pothesis testing After all most experiments with complex systems are intended to find out how the systems work the factors that affect performance singly and in combination which often involves searching for hidden structure in run time data In fact we have developed a mixed initiative planning assistant for exploratory data analysis described in a companion paper in this volume One general and apparently very powerful sta tistical method is called multi stream dependency detection or MSDD Consider the streams of data flowing from a robot s sensors a command and con trol network the monitors in an intensive care unit or periodic measurements of various indicators of the health of the economy There is clearly util ity in determining how current and past values in those streams are related to future values We for mulate the problem of finding structure in multi ple streams of categorical data as search over the space of dependencies unexpectedly frequent or in frequent co occurrences between complex patterns of values that can appear in the streams MSDD per forms an efficient systematic search over the space of all possible dependencies There are currently four versions of MSDD The first version se
11. g simulation if we have a customer arrival scheduled for time 18 and a de parture scheduled for time 13 the departure must obviously come before the arrival The simulation literature has several terms for the data structure holding these events we call it the pending event list or PEL When an event is scheduled it is in serted into the PEL in the correct place when the simulation is advanced the first event in the PEL is realized and removed from the list In MEss there can be two kinds of object in the PEL an event or an event stream ES If we think of an event as a sheet of paper an ES is like a pad of paper it has a bunch of sheets only one of which shows at a time The PEL in Mess contains either individual events or event streams In practice in the simulators implemented using MEss most of the objects in the PEL are event streams Let s look briefly at the pseudo code to see how MEss works A more detailed description is avail able in Anderson 1995 The primary objective of the engine is to realize events which we see in the center of the algorithm If the first thing in the PEL is an ES the engine must make the ES produce an event to realize which is done by the peek operation Later the event is removed from the ES by the pop operation After the event is realized the event is illustrated The purpose of realization is to change the state of the simulation while the purpose of illustration is
12. her and status variables Chains The concept of center of gravity is very important to campaign planners and we implement it in ACS with structures called chains A chain is a causal association between objects for example an anti aircraft battery is downstream on a command and control chain from the unit that controls it We have chains for command and control logistics personnel geography and other centers of gravity Visualization ACS has various interfaces to show the campaign at a glance Chains figure prominently because they identify leverage points in the campaign Computing Outcomes The outcomes of actions such as Attack Patrol Blockade and so on are computed by rules that take into account the readiness and morale of the units involved the weather and other factors Cur rently outcomes are crude only four status vari ables are allowed operational degraded disrupted and non operational Implementation ACS is implemented in Mess the simulation sub strate described earlier Currently it does not ex ploit much of the functionality of Mess for ex ample actions are implemented as events instead of activities and ACS isn t a real time simula tor These choices enabled us to produce a first draft of ACS very rapidly it is available from co hen cs umass edu Acknowledgments This work is supported by ARPA Rome Labora tory under contract F30602 95 1 0021 The US Government i
13. ily shared as their authors intended Our Mess substrate Anderson 1995 captures the best of the common domain independent aspects of these simulators and improves the representa tion of thinking agents and the measurement of time One builds a simulation environment in MEss by defining the events that happen thereby chang ing the state of the world and defining the event streams that produce those events The Mess sub strate takes care of synchronizing all the events so that the simulation unfolds in the correct way with processes interacting as they should Our goals in designing MEss were a domain independence b planner independence meaning that we pose little constraint on the kind of planner that can be integrated with Mess c extensibility by the user d portability to any Common Lisp platform and most importantly e a flexible platform independent definition of planning duration so that real time simulations will have those properties Mess Design MEss makes no commitment to a domain but in stead supplies the materials to build simulators in any domain namely events and event streams For example the ignition of a firecell is an event in PHOENIX the appearance of a tile is a TILE WORLD event Joslin Nunes amp Pollack 1993 Pollack amp Ringuette 1990 and a train travers ing a route is an event in TRAINS Events are de fined in Mess using CLOS where the user supplies code that determines when
14. nd the design of agent architectures AI Magazine 13 4 17 42 Howe A E 1993 Accepting the Inevitable The Role of Failure Recovery in the Design of Planners Ph D Dissertation University of Mas sachusetts at Amherst Also available as Com puter Science Department Technical Report 93 40 Joslin D Nunes A and Pollack M E 1993 TileWorld user s manual Technical Report 93 12 Department of Computer Science University of Pittsburgh Contact tileworld requestOcs pitt edu Martin N G and Mitchell G J 1994 A transportation domain simulation for debugging plans Obtained from the author martin cs rochester edu Pollack M E and Ringuette M 1990 In troducing the Tileworld Experimentally evalu ating agent architectures In Proceedings of the Eighth National Conference on Artificial Intelli gence 183 189 American Association for Artifi cial Intelligence
15. nt where upon it returns control to the engine To be pre cise an agent event stream gets its turn when it is popped and when it computes an event the event becomes the pending event in the event stream The timestamp on the pending event determines when the event is realized and when the ES runs again How is the timestamp on the pending event cal culated Note that this is not a question we have considered before We assumed that the event streams compute the timestamp in domain specific ways involving for example models of how fast ve hicles move or fire spreads With a thinking ES we want the timestamp on the event to be determined by the amount of computation that has occurred during this turn That is the computation of the timestamp on the next event in the agent is a side effect of its getting a turn to think the agent thinks until it gives an event to the substrate for realiza tion and the amount of thinking determines the timestamp of the event Thinking time only matters for real time agents A planner that is merely on line may think for as long as it wants It must therefore determine in some other way when it will get another chance to think It may for example simply get to run every five simulated minutes While the MEss substrate can easily accommodate on line agents it is partic ularly designed for real time agents Timed Common Lisp for Real Time Agents One valuable component of the Mess simulator
16. s authorized to reproduce and dis tribute reprints for governmental purposes notwith standing any copyright notation hereon The views and conclusions contained herein are those of the authors and should not be interpreted as necessar ily representing the official policies or endorsements either expressed or implied of the Advanced Re search Projects Agency Rome Laboratory or the US Government References Anderson S D 1995 A Simulation Substrate for Real Time Planning Ph D Dissertation Univer sity of Massachusetts at Amherst Also available as Computer Science Department Technical Re port 95 80 Bratley P Fox B L and Schrage L E 1983 A Guide to Simulation Springer Verlag Cohen P R Greenberg M L Hart D M and Howe A E 1989 Trial by fire Understanding the design requirements for agents in complex en vironments AI Magazine 10 3 32 48 Durfee E H and Montgomery T A 1990 MICE A flexible testbed for intelligent coordi nation experiments In Erman L ed Intelli gent Real Time Problem Solving Workshop Re port Palo Alto CA Cimflex Teknowledge Corp Hanks S Nguyen D and Thomas C 1992 The new Truckworld manual Technical report De partment of Computer Science and Engineering University of Washington Forthcoming Contact truckworld request cs washington edu Hanks S Pollack M E and Cohen P R 1993 Benchmarks testbeds controlled experi mentation a
17. to modify the graphical user interface GUI if any This separa tion of realization from illustration aids in running batch simulations because all the GUI code can be ignored The separation also helps keep testbeds portable since GUI code is a common source of portability troubles The highlighted operations peek interaction realize illustrate and pop are all CLos meth ods that can be specialized by the user Indeed the realize and illustrate methods which operate on events must be specialized since their default be havior is to do nothing The peek and pop methods operate on event streams as mentioned above sev eral general event stream classes are implemented in Mess already The user can arrange for partic ular events to happen during a simulation by us ing the list event stream The function ES classes run a function supplied by the user to generate an event either during the peek or pop operation We ve found it straightforward to implement many kinds of processes using just these event streams but the protocol is designed for extensibility by the implementer of a simulation Several minor steps in the pseudo code deserve mention The every event step executes all the code in a list supplied by the user at the start of Algorithm to Advance the simulation increment event counter advance time by head of PEL If head of PELis an event stream Set ES to head of PEL Peek ES Set E to event in ES else
Download Pdf Manuals
Related Search