Areas of Research in Modeling and Simulation
Bernard Zeigler, University of Arizona
The text discusses research areas in three categories: (1) modeling theory, (2) modeling methodology, and (3) tools and environments. This appendix provides examples of research in each of these categories. The items shown are illustrative only, the point being to demonstrate something of the diversity of issues needing research.
Simulation-based Design Research
Manufacturing control is traditionally approached with analytic/Markov methods for the creation of analytic models. However, using discrete event models to represent the machines, material handling, and input devices frees the modeler for experimentation with new and unique control methods. Users can make decisions by observing simulations using realistic “scenarios” of the manufacturing process and examine the implications of change (Zeigler, 1990; Cho and Zeigler, 1997). Because of the modularity of the approach, a wide variety of on-line control elements —including not only classic control mechanisms, but also neural networks, fuzzy logic, or expert systems—can be installed for performance analysis.
While model-based control is intuitive and can represent some of the deep knowledge employed of a human expert charged with directing a process, the approach of applying discrete event simulation and the requisite large-scale computing for automation is still in its infancy. Further research is needed to bring it to the point where it can support manufacturing styles such as flexible or agile
paradigms. DOD has many manufacturing processes and similar processes, such as logistics repair, that could significantly benefit from agile or flexible design based on discrete event simulation.
Dynamic Structure Modeling and Simulation
In many important physical and military systems, the system “structure” changes in the course of time. For example, biological systems such as growing plants, and social systems such as self-organizing organizations (one model for highly dispersed ground forces in the future), change structures over time. So also does a military organization that suffers attrition and reorganizes with a new command structure or a military organization that reorganizes and replans because of events making the original concept of operations obsolete.
Although significant research has been done on such simulations, current simulation languages do not support them. To represent such changes, they must be recast into parameter changes, and this leads to convoluted code that is difficult to verify and inefficient to run. Augmenting or replacing current simulation languages to support dynamic structure modeling would greatly increase the power of simulations to study complex structurally variable systems to gain true insight and predictability. This technology has been the subject of numerous investigations, but only recently has a first theoretical framework even been proposed and implemented. Thus, research that can contribute to a coherent usable methodology is at an early phase. 1
Inductive modeling attempts to infer a system's internal structure from data representing its behavior. Given that data collected from all kinds of systems are abundant, realizing a comprehensive inductive modeling methodology will be of significant importance to the M&S community at large. Within the military domain, it may be possible to generate rich databases from exercises and training activities mediated by distributed interactive simulations.
Despite a large body of research in inductive modeling, there is little agreement on any recognized inductive modeling paradigm. Several software implementations exist, including one developed based on a well-defined framework for inductive modeling, and implemented in a Artificial Intelligence Truth Maintenance system supporting nonmonotonic reasoning (Sarjoughian, 1995). This type of reasoning is needed to support flexible assertion and retraction of abstractions and assumptions in model building. However, this work has only tackled
One example of work in this domain involves support to DOD's business reengineering, which must reflect the self-organizing formation of teams in business structures.
“toy problems,” and it is imperative to apply it to some real application areas. Fundamental research effort is needed to bring about a useful and mature methodology to support a multitude of DOD present and future activities within the next couple of years
The present and future mission of the DOD provides real-world problems for applying and validating an inductive modeling framework. Potential applications span all of the M&S activities of interest to DOD with significant implications for model characterization from behavior and model abstraction techniques. Examples are Advanced Imagery Exploitation and Defense Automated Warning Systems, as well as many other areas requiring nonmonotonic reasoning about abstraction and assumptions. An inductive modeling technology would help DOD to address problems where conventional M&S is inadequate because of an abundance of data together with a lack of a well-developed scientific knowledge base and the M&S know-how to make sense of it.
Experimental Frame Methodology
Experimental frames enable simulationists to translate the objectives and issues to be addressed into conditions under which a model or real system will be experimented with (Zeigler, 1976). As a major part of the initial requirements specification, experimental frames are critical to appropriate choices (e.g., level of resolution and accuracy) throughout the subsequent modeling and simulation effort. Experimental frames map into modules that actually do the experimentation (input generation, output summarization, and so on) when models/systems are operable.
While the concept of experimental frames has been around for some time, it is only recently that full support for their specification, manipulation, and management has been attempted. Experiment plans are supported in a Bomb Damage Assessment environment (Simard, 1996). However, such plans are formulated after model development, rather prior to it, as in true experimental frames. Some current environments support experimental frame construction as executable components but do not support the more abstract specification needed for symbolic manipulations.
DOD M&S efforts often are overly costly owing to their inability to make critical choices such as scope of representation and resolution level that should be driven by issues-oriented experimental frames specified in advance of model building. Moreover, archiving experimental frames and then matching them with existing models would enable a high level of model reuse.
Automatic Model Verification
Automatic model verification (AMV) differs from the conventional model verification methods in which verification is based on manually executed simulation runs. AMV aims toward automation of discrete event models verification. One promising approach is based on dual specification (Hong and Kim, 1996). The approach employs two specifications for a discrete event model: an operational specification for the behavior of a model and an assertional specification for its temporal properties. A model's verification is based on a language acceptance checking mechanism for which the assertional model constitutes a language grammar and the operational model acts as string generators.
Promising research in AMV has been performed. Although no software tool for AMV based on the dual specification approach has yet been developed, a prototype has successfully demonstrated the approach. Further research and development is needed to reduce the approach to usable tools.
Model Simplification Through Change in Formalism
Continuous systems are traditionally modeled with differential equation models. However, recent research has suggested that discrete event models may afford advantages for simulating continuous as well as hybrid systems (Zeigler, 1989). Several approaches exist for faithfully mapping differential equation systems into discrete event models such as analytic expression of transitions, application of algebraic solvers, and fuzzy representations.
A discrete event model, which meets certain steady state conditions, has been shown to be equivalent to a Markovian process. When analytic solutions are available for such processes, they can be solved in much less time than simulation requires. Markov lumped models can also replace their base model counterparts within the original simulation model, leading to more efficient simulation. Analytic expression of transitions has been shown to provide some 100 to 1,000 speedup over conventional time-stepped numerical integration (Moon, 1996). However, in many situations analytic (local) solution may not be possible. Therefore further research is needed to test general methods that do not rely on analytic solutions.
Simulations including both continuous and discrete event model components are common in DOD applications. For example, airplane motion is described with differential equations, while decisions of an intelligent autopilot are discrete. In such simulations, the speedups obtainable with a complete discrete event representation, with or without further Markov reduction, would enable simulations that are currently not feasible to be conducted. For example, it would be possible to simulate terrain models using digital elevation data from geographic information systems representing large areas in high enough resolution for realistic tests of sensor systems.
TOOLS AND ENVIRONMENTS
Environment for Simulation and Implementation of Discrete Event Control Systems
Discrete event system models have had a major impact on control system design for modern automation and real-time decision-making systems (Ho, 1989). The design of discrete event control systems usually employs discrete event simulation to verify functional requirements as well as to evaluate performance. Such simulation can be performed in discrete event simulation languages. Once simulation is done, the implementation of the designed discrete event system may proceed using a programming language, such as C or C++, which can be executed in real time. Since source code implementation totally differs from that of the simulation model, this approach to design cannot reuse the simulation model code in implementation. An ideal environment supports a close relation between simulation model and implementation code. In such an environment, a set of operating system-like system functions supports execution of a simulation model in real time. Thus, the same model analyzed in simulation can later be converted to real-time execution in a near-seamless manner.
Database Support for Simulation Model Reuse
Large-scale, complex-systems modeling often requires management of simulation models in an organized library or database (Zeigler, 1984, 1990). One major advantage is the potential for reuse of component models at different subsystem levels. Such model management can be effectively supported by employing object-oriented database technology. In this technology, a system can manage not only model structure in the form of coupling relations between component models, but also model behavior in the form of source codes or compiled codes. Such coupling relations and/or behavioral codes can be reused later on as building blocks to build larger models.
This technology area has already successfully been applied in the development of intelligent simulation environments. However, much research has to be done in order to apply the technology in the real world. For example, we need to develop a method for generating simulation models residing in an object-oriented database from modeling requirements and objectives.
Insertion of this technology would provide great benefits to DOD in large-scale, complex systems modeling, simulation, and analysis. It significantly reduces model development time by an efficient reuse of existing simulation models as building blocks.
SIMULATION-BASED OPTIMIZATION ON HIGH-PERFORMANCE PLATFORMS
Simulation-based optimization can be employed in most aspects of system modeling and design, as well as in higher-level decision-making processes. A wide variety of classic search and optimizing methods are available. In addition, there is now emerging a considerable literature on applications using nontraditional methods, which have both advantages and disadvantages. As examples here, evolutionary global optimization methods (Fogel, 1994), such as genetic algorithms (GAs) (Miachalewicz, 1992; Goldberg, 1992), were developed to apply the adaptive process of natural systems to search problems, and to develop artificial systems that mimic the adaptive mechanisms of natural systems. GAs encode a potential solution to a specific problem on a simple chromosome-like data structure and apply such operators as selection, recombination (or cross-over), and mutation to the structure in the hopes of getting closer to the solution. Although regarded as merely “trendy” by some, GAs have been applied to a wide variety of search and optimization problems by many researchers. For example, a class of parallel GAs (Gorges-Schleuter, 1989; Pettey et al., 1987) for simulation-based optimization was applied to fuzzy system design, optical interconnection network design (Louri et al., 1995), parameter tuning, and model abstraction of a large-scale ecosystem model (Moon, 1996). However, system design problems typically require optimization of models having a large number of parameters, each requiring high precision. These parameters increase the complexity of the problem, and working with all the parameters at the same time often causes GAs (or any other optimization algorithms) to stagnate at local minima. Existing approaches cannot exploit information about performance impacts to search parameter subspaces in relation to their criticality. To address these problems, a multi-resolution search strategy in a distributed, high-performance simulation environment was developed (Kim and Zeigler, 1996). 2
High-performance Parallel Discrete Event Simulation
Mapping large-scale discrete event models onto massively parallel architectures (Almasi and Gottlieb, 1989) requires the support of a higher level of abstraction in parallel simulation environments (Fujimoto, 1990). Recent approaches have employed object orientation to encapsulate the internode communication mechanism providing a user with a higher level of control (Zeigler et al., 1997). Mapping of models is also supported by its portability across platforms. Large-scale parallel and distributed discrete event simulation environments demonstrate the
For further discussion of some of these issues, see also the last portion of Appendix B .
capability to address very complex and time-consuming simulation problems while providing a high-level interface. High-performance simulation environments have been tested on several models, including a spatial watershed and a large cluster of ATM switch models. The simulation can help analyze the complex interactions in models consisting of up to 10 million components (e.g., landscape cells or ATM switch elements). Speedups of the order of 200 times have been obtained so that simulations that require several days to run in conventional platforms can be completed in under an hour. There are numerous large simulations that could benefit from this technology, for example, air traffic control and multimedia communication design problems.
Distributed Simulation of Heterogeneous Models
Although distributed interactive simulation (DIS) protocols do not provide for strict global time preservation among federated models, the high-level architecture (DMSO, 1996c) includes a more controllable runtime interface. There are still many issues that must be dealt with in HLA (Morgeson, 1996). This motivates the development of a methodology for distributed simulation of models written in different simulation languages/environments that preserves strict time correspondence. Formalisms for discrete event models can be used as a common communication means. A software bus and an associated protocol based on such formalisms can provide an interface among legacy models in such languages as SIMSCRIPT, MODSIM, and SLAM. Proposed also are protocol converters, which support communication standards for such models. The methodology can be implemented using a network programming language such as JAVA. Insertion of this technology would provide great benefits to DOD in network-based distributed simulation of a large-scale system in which models of subsystems are developed in different languages/environments. It significantly reduces model development by reuse of existing heterogeneous models.
ADVANCED M&S ENVIRONMENTS FOR INTELLIGENT/COGNITIVE SYSTEMS
Building models of intelligence, perception, and human performance has proved to be difficult due in part to the uncertainty in the psycho-physiological theories proposed to explain behavioral phenomena. Modern software engineering approaches such as spiral development suggest intelligent and cognitive model development using an incremental refinement approach (Young, 1992). They also provide the ability to develop multi-resolution models, although the underlying understanding of phenomenology is often the limiting factor. Recent developments in neuroscience have enabled us to envision behavior as the synergistic result of biological cells-neurons. Dynamic neural ensembles (DNEs) (Vahie
and Jouppi, 1996) provide a dynamic environment and the components necessary for the development of highly complex cognitive models aggregating cellular behavior to represent intelligence and learning.
DNEs are compositions of interconnected dynamic neurons. At a more abstract level, “holon” hierarchy models are being developed. Simulation environments supporting such models use object-oriented programming techniques to provide ease of parameter modification and specialization of both behavior and structure. Applications of DNEs to real-time learning, control, and decision making are currently being pursued. DOD systems and component designs for the 21st century will have to increasingly address the issue of human operability and performance. The development of autonomous systems capable of functioning in dynamic environments is also an issue of interest. The first issue, operability and performance, requires an approach that needs to be seamlessly integrated into design. The successive approximation provides a methodology for integration of cognition and intelligence into the systems design. New forms of neural and cognitive models, capable of dynamic behavioral modification, need to be explored to adequately capture flexible behavior.
Visualization and Significant-Event Detection in Discrete-Event Simulation
Any large-scale simulation is by definition complex owing to the size and diversity of the data. Events (in discrete-event simulations) represent a set of states (in one or more models) that are capable of influencing the states of other models in the environment. Therefore, an event may be determined as significant based on the values of specific state variables (in one or more models). Significant events are thus said to occur in a time period when a predefined set of conditions is met by a subset of the variables in the simulation. The user defines what he considers to be significant events using primitives and model parameters, before simulation. At run-time, event detectors sift through the data looking for significant events. This enables the user/model developer to effectively pursue his goal (conceptual or analytical). In essence, significant event detection allows any large-scale simulation to be viewed at various levels of abstraction, where the level of abstraction is determined by the significance of the event.
Due to the size and/or complexity of most DOD simulations, this technology would impact virtually all application areas where M&S is used. Being genetic in nature, the concept could be modularized as an independent entity in diverse discrete event simulations. In battle simulations where planning, resource and personnel deployment, and communication are independent entities, there are too many data to track. The same model can be used by commanders in charge of each of the battle spaces where a significant event for one may or may not be a significant event for another, radically reducing their output data set.
Graphical Description of Discrete Event Model Behavior
Many good graphical tools are in place for discrete event systems modeling. Such tools use icons to represent predefined models, most of which support users to add a new model definition and an associated icon to the existing library. However, little has been done in graphical notation for behavioral description of discrete event models. An excellent example for such notation in discrete event modeling is a stochastic Petri Nets graph. In spite of its generality in modeling stochastic systems, Petri Nets is limited to modeling a certain class of discrete event systems. Thus, graphical notation based on a sound semantics, which is easy to use and understand, needs to be developed for the rapid and accurate modeling of discrete event systems. The graphical notation should include such information as state transition function, output function, and sojourn time function for a basic component of a discrete event process. Of course, the graphical notation should generate executable simulation codes.
Anytime/Anyplace Concurrent, Collaborative Support of M&S Life Cycle
DOD decision makers are faced with the challenge of declining budgets for manpower and material, and for demands for flexible, cost-effective operations to meet the challenges of the post-Cold War world. M& S is being applied not only at technical and engineering levels to meet such challenges, but also at higher levels such as work-flow automation and business reengineering, where many stakeholders are affected. To undertake effective M&S throughout its life cycle requires the active involvement of the various groups involved with model development, simulation analysis, and implementation. Unfortunately, tools and methodologies currently available from commercial vendors and consultants are primarily single-user tools that provide inadequate support for the collaborative team-based environment that characterizes modern organizations. Moreover, this support is virtually nonexistent for distributed work involving groups that are geographically dispersed.
Group support systems research has developed a network-based set of flexible software tools that incorporate basic problem-solving techniques such as brainstorming, idea organization, voting, issue analyzing, policy formation, prioritizing, and stakeholder identification. Electronic communications allow all group members, whether distributed or co-located, to make contributions to the group's task both simultaneously and asynchronously. Such technology increases organizational productivity by decreasing manpower requirements and cycle times in projects. The scope of projects can also be expanded to include participants from several hierarchical levels, thus improving organizational communication while facilitating approval for decisions. In a competitive environment
where success is dependent on teams working together, collaborative software will increase the productivity and effectiveness of these teams.
Research is needed to extend advanced M&S capabilities by embedding them in the distributed group support tools environments, to enable distributed groups to construct, analyze, and implement model-based designs in concurrent engineering fashion.