Saturday, July 31, 2010

Simulate This?

Clouds in the Platte River Valley. That would be an interesting simulation study. Are the Rockies normally above the clouds? Is the ridge I live on higher as well? I hate to say this, but you don't have to simulate everything to get answers. Sometimes common sense works. Sometimes simple observation is adequate. In this case, I have seen this a few times after intense storms the previous night, but for the most part we do not live above the clouds, yet.

Tuesday, July 27, 2010

Deer Valley Ranch

Edit | Settings | Delete
I just returned from a week at Deer Valley Ranch, Colorado. While there I started my latest book, "Discrete Event Simulation with ExtendSim8". I am now sitting in my living room on the prairie of Colorado's eastern slopes of the Rocky Mountains. As I look out at my unobstructed view of Pike's Peak, I ask myself, "How could anyone ever simulate this?". I would never try. Nevertheless, I hope this new book will help with simulation of those things that we can simulate.

Discrete Event Simulation Using ExtendSim

I had a slight set-back on 29 June. I went to the emergency room with chest pains, and was admitted to treat my second pulmonary embolism (that's blood clots in the lungs). To make a long story short, I will be fine but will be on blood thinner forever.

I have been promising a book on Discrete Event Simulation with ExtendSim. I am waiting on the new version of ExtendSim to be released, but here is a start on chapter 1:

Simulation in general is to pretend that one deals with a real thing while really working with an imitation. In operations research the imitation is a computer model of the simulated reality. A flight simulator on a PC is also a computer model of some aspects of the flight: it shows on the screen the controls and what the "pilot" (the youngster who operates it) is supposed to see from the "cockpit" (his armchair).

What are a models and simulations?

Models
In order to understand what it means to model a phenomena or process, we must first understand the term “model” and understand its limitation. A model is a physical, mathematical, or otherwise logical representation of a system, entity, phenomenon, or process (DoDD5000.59). A model can also be thought of as an abstraction of the real world, or an approximation of it. If you think about the problem of modeling a human being, or just the mind of a human, you can immediately see the limitations of modeling. We will use the term “system” to encompass systems, entities, phenomenon, or process. Since a modeling is a representation, abstraction, or approximation of the “system” being modeled, we must understand that it is not an “exact” representation, i.e., we can’t model every aspect of the system. First, we don’t know everything we need to know in order to model the system. We may not be able to define a process of the system with mathematical precision, or with heuristic algorithms, and many of the processes may not appear logical. Second, even if we were to know everything about the system, we may not have enough computing power to model every process, at least for complex systems, e.g., a human being, the earth’s ecosystem, etc.

Yet with their limitations, models are a good way to gain understanding of how a system operates. George E.P. Box said, “All models are wrong; some models are useful.” They are wrong in that there is not a one-to-one mapping form the real system to the model; they are useful in that we can use them to understand the system, or at least certain aspects of the system. Even though we often use models to predict behavior, this is a dangerous process, and we must do it with caution.

There are many types of models that one can use when trying to represent a system. These can be divided into several classes, and for simplicity we will consider two classes: physical models and symbolic models (see Figure 1.1). Physical models include mock-up models (e.g., a vehicle mock-up), scale models (e.g., a 1:48 scale aircraft model), Iconic model, natural model, or a fashion model (which represent what we all want to look like).
Symbolic models include narrative models, graphical models, tabular models, software models, and mathematical models. These models are not necessarily mutually exclusive. For example a tabular model might contain data derived from a mathematical model, or a mathematical model may be embedded in software code.
Models can also be classified by contrast, e.g., a conceptual model (flowchart, picture, UML diagram) versus a computational model (spreadsheet, computer software) or static models that do not use time as a primary input, versus dynamic models based on time.

Simulations
A simulation is the execution of a model over time. Simulation involves designing a model of a system and carrying out experiments on it. The purpose of these "what if” experiments is to determine how the real system performs and to predict the effect of changes to the system as time progresses. For example, you use simulation to answer questions like:
  • Will this change to our process result in higher yields or quality?
  • How many people are required to maintain service at a specified level, for example, in a processing station?
  • Can we design this weapon system with fewer components and still maintain measures of performance, such as availability or lethality?
  • Does this force structure meet the capability requirement specified by the commander?
A formal definition of simulation is given by the Department of Defense Directive (DODD) 5000.59:

Definition 1: A method for implementing a model over time. Also, a technique for testing, analysis, or training in which real-world systems are used, or where real-world and conceptual systems are reproduced by a model.

Another definition is given by Winston & Albright, in Practical Management Science, 2001:

Definition 2: A simulation model is a computer model that imitates a real-life situation
  • It is like other mathematical models, but it explicitly incorporates uncertainty in one or more input quantities.
  • When we run a simulation, we allow these random quantities to take on various values, and we keep track of any resulting output quantities of interest.
  • In this way, we are able to see how the outputs vary as a function of the varying inputs.
Why use models
To fly a simulator is safer and cheaper than the real airplane. For precisely this reason, models are used in industry commerce and military: it is very costly, dangerous and often impossible to make experiments with real systems. Provided that models are adequate descriptions of reality (they are valid), experimenting with them can save money, suffering and even time.

When to use simulations
Simulations are appropriate with systems that change with time, such as a gas station where cars come and go (called dynamic systems) and involve randomness. Nobody can guess at exactly which time the next car should arrive at the station, so one can simulate the arrival or cars. Modeling complex dynamic systems theoretically requires too many simplifications and the emerging models may not be valid. Simulation does not require that many simplifying assumptions, making it a useful tool, even in absence of randomness.

How to simulate
Suppose we are interested in studying cars receiving service at a gas station. We may describe the behavior of this system graphically by plotting the number of cars in the station; the state of the system, either arriving, starting service, or completing service. Every time a car arrives the graph increases by one unit while a departing car causes the graph to drop one unit. This graph (called sample path), could be obtained from observation of a real station, but could also be artificially constructed. Such artificial construction and the analysis of the resulting sample path (or more sample paths in more complex cases) consist of the simulation.

Types of simulations:

Discrete Event Simulation
The above sample path consisted of only horizontal and vertical lines, as car arrivals and departures occurred at distinct points of time, what we refer to as events. Between two consecutive events, nothing happens - the graph is horizontal. When the number of events is finite, we call the simulation "discrete event."

Discrete Time Step Simulation
In discrete time step simulations, instead of looking at state changes that occur at discrete events, we choose a time step before starting a run an observe what happens as time progresses. Unlike discrete event simulation, it is possible to have no state change at one or more time steps. This form of simulation is often used to approximate continuous systems, since we would expect state changes at each time step.

Continuous Simulation
In some systems the state changes all the time, not just at the time of some discrete events. For example, the water level in a reservoir with given in and outflows may change all the time. In such cases "continuous simulation" is more appropriate, although discrete event simulation can serve as an approximation.

How is simulation performed?
Simulations may be performed manually. Most often, however, the system model is written either as a computer program (for an example click here) or as some kind of input into simulator software.

System terminology
• System: A facility or process either actual or planned, comprised of a collection of entities that act together toward the accomplishment of some logical goal.
  • State: A variable characterizing an attribute in the system such as level of stock in inventory or number of jobs waiting for processing.
  • Event: An occurrence at a point in time which may change the state of the system, such as arrival of a customer or start of work on a job.
  • Entity: An object that passes through the system, such as cars in an intersection or orders in a factory. Often an event (e.g., arrival) is associated with an entity (e.g., customer).
  • Queue: A queue is not only a physical queue of people, it can also be a task list, a buffer of finished goods waiting for transportation or any place where entities are waiting for something to happen for any reason.
  • Creating: Creating is causing an arrival of a new entity to the system at some point in time.
  • Scheduling: Scheduling is the act of assigning a new future event to an existing entity.
  • Random variable: A random variable is a quantity that is uncertain, such as interarrival time between two incoming flights or number of defective parts in a shipment.
  • Random variate: A random variate is an artificially generated random variable.
  • Distribution: A distribution is the mathematical law which governs the probabilistic features of a random variable.
A Simple Example
Consider building a simulation gas station with a single pump served by a single service man (see Figure 1.3). Assume that arrival of cars as well their service times are random. At first identify the:
  • states: number of cars waiting for service and number of cars served at any moment
  • events: arrival of cars, start of service, end of service
  • entities: these are the cars
  • queue: the queue of cars in front of the pump, waiting for service
  • random realizations: interarrival times, service times
  • distributions: we shall assume exponential distributions for both the interarrival time and service time.
Next, specify what to do at each event. The above example would look like this: At event of entity arrival: Create next arrival. If the server is free, send entity for start of service. Otherwise it joins the queue. At event of service start: Server becomes occupied. Schedule end of service for this entity. At event of service end: Server becomes free. If any entities waiting in queue: remove first entity from the queue; send it for start of service.

Some initiation is still required, for example, the creation of the first arrival. Lastly, the above is translated into code. This is easy with an appropriate library which has subroutines for creation, scheduling, proper timing of events, queue manipulations, random variate generation and statistics collection.

Besides the above, the program records the number of cars in the system before and after every change, together with the length of each event.

The Importance of Simulation
Simulation provides a method for checking your understanding of the world around you and helps you produce better results faster. It is an important tool that you can use to:
  • Predict the course and results of certain actions.
  • Understand why observed events occur.
  • Identify problem areas before implementation.
  • Explore the effects of modifications.
  • Confirm that all variables are known.
  • Evaluate ideas and identify inefficiencies.
  • Gain insight and stimulate creative thinking.
  • Communicate the integrity and feasibility of your plans.
However, to ensure that the simulations are useful, we must insure that we have implemented them correctly (verification), and that their results match what would happen with the real system (validation).

Verification and Validation
Verification is the process of determining that a model implementation and its associated data accurately represents the developer's conceptual description and specifications (DoDI 5000.61). There are a number of ways to achieve verification. Some methods are:

  • Debug the computer program in modules. Start with a simple model and move toward complexity as needed.
  • Use a “structured walk-through” or group involvement methodology in order to gain another simulator’s perspective to avoid not so obvious errors.
  • Perform hand calculation checks.
  • Use “Trace” to evaluate each possible program path as well as the contents of the events list, the state variables, statistical counters, and “extreme” conditions.
  • Initially run the model under simplified conditions or assumptions for which the model’s true conditions are known or can be easily computed for comparison.
  • Use graphics and animation to analyze the movement of entities thus lending credibility to the model.
Validation is the process of determining the degree to which a model and its associated data are an accurate representation of the real world from the perspective of the intended uses of the model (DoDI 5000.61). Models are built and exercised to evaluate a situation that is not predictable by other means. Thus, results are not known with certainty. And, often no comparative data is available. Consequently, validation may be difficult to prove. Following the following steps will help validation your simulation results:
  • Develop a model with a high face value. That is, a model which is approved by people who are knowledgeable about the system under study. Make use of existing information such as:
o Expert opinions
o Existing theory
o Observations of the system
o General knowledge
o Intuition
  • Test the assumptions of the model empirically. Make use of input distribution tests to determine proper goodness-of-fit. Use sensitivity analysis to determine how much the model will vary with a small change in an input parameter.
  • Determine how representative the simulation output data are. Test the output data from the simulation with real world output results.
Verification and validation is often an integrated process that occurs over the life cycle of the simulation.

Benefits of Simulation
Simulation allows managers and analysts to evaluate proposed systems without building them. In some cases it offers the only way to solve the problem. Once built a model can easily be run repeatedly and changed to examine alternatives. Generally, it is less costly than other methods, if sufficient data is available. Also, simulation gives insight into how randomness affects a system and can be used to verify analytical solutions. Finally, simulation models are generally easier to understand than many analytical approaches.

Limitations of Simulation
In spite of its benefits, simulation carries with it certain limitations. Simulation may require a significant amount of time and resources. Lack of precise answers due to sampling errors may occur with simulations. As already mentioned, computer simulations can be difficult to validate. Also, simulations may be difficult to interpret. A major limitation is that some things cannot be simulated, in that either the system is too complex to simulate, or there are too many unknowns. Finally, simulation requires special training and experience.

References
  • Theory of Modeling and Simulation (Second Edition), by Zeigler, Praehofer, & Kim. San Diego: Academic Press, 2000.
  • Handbook of Simulation, Jerry Banks, Ed. New York: John Wiley & Sons, 1998.
  • Simulation Modeling Design and Execution, by Paul A. Fishwick. Englewood Cliffs, NJ: Prentice Hall, 1995.
  • Applied Simulation Modeling, by Seila, Ceric, & Tadikamalla. Belmont, CA: Brooks/Cole, 2003.
  • Introduction to Simulation and Risk Analysis, by Evans & Olson. NJ: Prentice Hall, 2002.
  • Spreadsheet Modeling and Applications, by Albright & Winston. Belmont, CA: Brooks/Cole, 2005.
  • Simulation Modeling and Analysis (Third Edition), by Averill M. Law & W. David Kelton. New York: McGraw-Hill, 2000.

SIMNET


SIMNET was a wide area network with vehicle simulators and displays for real-time distributed combat simulation: tanks, helicopters and airplanes in a virtual battlefield. SIMNET was developed for and used by the United States military. SIMNET development began in the mid-1980s, was fielded starting in 1987, and was used for training until successor programs came online well into the 1990s.

At the time SIMNET was fielded in 1987, I was the commanding officer of K Troop, Second Armored Cavalry Regiment (2ACR) in Amberg, Germany, during the Cold War. My tank platoons were the first to train in SIMNET at Grafenwohr, Germany. Surprising me, the white cell (or controller) hardware consisted of Macintosh Plus computers (I bought my first Mac in 1986). Our SIMNET experience was followed by a successful tank platoon live fire exercise.

SIMNET was developed by three companies: Delta Graphics, Inc.; Perceptronics, Inc.; and Bolt, Beranek and Newman (BBN), Inc. There was no prime contractor on SIMNET; independent contracts were let directly to each of these three companies. BBN developed the vehicle simulation and network software, as well as other software such as artillery, resupply, and semi-automated forces often used for opposing forces. Delta Graphics, based in Bellevue, Washington, developed the graphics system and terrain databases. Delta Graphics was eventually bought by BBN. Perceptronics, based in Los Angeles, was responsible for the actual SIMNET simulators; the company's engineers, human factors personnel and manufacturing team designed, developed and built over 300 full-crew simulators, integrating the controls, sound systems and visual systems into the special simulator shells; they also installed the simulators in a number of facilities in the US and Germany, trained the operators and supported the system for several years.

The major software components of SIMNET have become almost standard fare among distributed simulators today:· The Network Interface allows the software to interoperate with other simulators on a computer network.· The Image Generator Software creates the beautiful full-color images that present the scenario to the training audience.· A Controls & Displays Interface covert digital information from the computers into information that can be displayed on instruments in the vehicle. They also transform trainee input into digital signals that can be processed by the simulation computers.· The Other-Vehicle State Table tracks the state data on the other vehicles in the scenario.· Own Vehicle Dynamics software is used to model the vehicle in which the trainee is sitting. This software generates vehicle movement, firing, and communication.· The Sound Generator recreates the deafening sounds of combat - the roar of tank engines, the clanking of tracks against the terrain, the firing of munitions, and the explosions of incoming rounds.

SIMNET, along with the tank crew trainer UCOFT simulator, helped make K Troop, 2ACR, one of the top two tank units in the United States Army Europe.

Foreword to Fundamentals of Combat Modeling

As an assistant professor of mathematics at the United States Military Academy at the turn of the century, I was teaching applied mathematics for systems engineering and systems engineering management majors. I really had thought a great deal about the complexities of combat modeling, other than the applications I had used in teaching calculus and differential equation and applied as an Army Operations Research Analyst. That changed in the summer of 2002 when I began writing a curriculum and teaching combat modeling at the Army's premier entry level Operations Research course, and started developing a set of course notes for combat modeling.

As I transitioned from the military and moved into chief scientist and engineer roles in the defense industry, I was continually challenges to expand my understanding of combat modeling, as I supported the Army’s Future Combat Systems program. I also continued to expand the course notes I had started in 2002. When I finally found a way to move to Colorado (God’s country), it was as a contractor supporting the Missile Defense Agency (MDA), providing technical direction for the Ballistic Missile Defense System (BMDS) Threat Modeling Center.

A little over 18 months ago I started out on the adventure of compiling my course notes into a published textbook. I was recovering from a pulmonary embolism and had a lot of time to reflect on issues in combat modeling. As I write this foreword, I am recovering from a second pulmonary embolism, and I have lots of time to reflect on the people who helped me arrive to this point in my life.

First and foremost, I could not have written this without my Lord and Savior Jesus Christ. I know that may sound corny to those untouched by His hand, but I literally would not be here without His miraculous intervention. When I was in the valley, he lifted my eyes to the hills. The most prominent person on the hills was my bride of 28 years. Laurie is my best friend, my biggest supporter, and my greatest critic. When I look back, I see that she was right behind me in those valleys, helping me along my way. Thanks!

Dr. Bob Simmonds hired me to be the director of the Operations Research and Systems Analysis Military Application Course (ORSA MAC) I, without having met me. He took a chance on me and my wild ideas about operations research and teaching. He is a dear friend and supporter to this day.

Kent White and Skip Songy were fellow Spartans (now Cobham Analytics), intelligent colleagues and endearing friends. They had faith in me when others did not understand me.

Dr. Mikel Petty is the Director of the Center of Modeling, Simulation and Analysis (CMSA) at the University of Alabama in Huntsville (UAH). He likewise took a chance on me and I was employed by him for a short time. He remains a colleague and supporter.

John Pace and Wayne Grissom are friends, colleagues, and mentors in the BMDS Threat Modeling Center. They have allowed me to bring my experience to bear and have supported my every breath.

Dr. Roger Smith is a colleague whom I greatly respect. Roger encouraged me to publish my writings.

Joe Kier is my best friend and mentor. Joe showed me what right looks like.

Mariah and Evie are two little joys in my life. Together with Laurie, they provide my inspiration.