Method for improving the simulation of complex stochastic systems

This invention expresses the stochastic system in a tree branching structure form. Successive nodes of the tree each contain a finite state model of the system which maintains information of the state of the system attained to that point and the branches represent decisions made that take the system to subsequent nodes. The branching tree structure affords a general method of approximating a stochastic system in a form that affords specific methods of speeding up the computations required to predict its behavior. The methods exploit the nature of the finite state representation to efficiently identify the state and output transitions associated with branching, the branching probabilities. Moreover, once a (state, branch) pair have been encountered and the resulting (state, output) pair have been computed by simulation, the next time this (state, branch) pair is encountered the resulting (state, output) is found by table lookup, a faster process than simulation.

BACKGROUND

1. Field of Invention

The present invention relates to improving a simulation with uncertainty quantification in a computer simulation.

2. Background of the Art

Conventionally, in a computer simulation that includes a stochastic element, Monte Carlo simulation is used in which a statistical execution result is obtained by repeatedly executing a simulation. When performing a Monte Carlo simulation using a computer system for a large-scale scenario that assumes the behavior of various configuration systems in the real world, the scale and complexity of the scenario (for example, the number of units, parameters, and statistics of the system) demand very long execution times.

Because complex stochastic systems have multiple paths they can follow and because the decisions of which paths to take are random, complex stochastic systems take a long time to simulate. This makes it hard to predict their behavior with an acceptable degree of certainty in a reasonable time.

A simulation execution method that shortens the total execution time of a simulation by using the information found in the first simulation execution to improve the efficiency of the second and subsequent executions is known. If the occurrence time of an event that became known by the first execution is acquired and there is no stochastic element up to that time, the system can re-use the information obtained of the event that became known when executing the second and subsequent times. Thus, the total simulation execution time is shortened.

In the simulation execution method, some computation processing during the period when detailed simulation is unnecessary can be omitted, but simulation models of various units appearing in the scenario are generated for all units, and the execution result of the scenario is obtained. It is necessary to process a simulation for prediction. For this reason, there is a problem that the contribution of the shortening effect to the total execution time of the entire simulation is small.

SUMMARY

The present invention has been made to solve the problems and aims to reduce the total execution time of the simulation, thus increasing the performance of the system. The present invention expresses the stochastic system in a tree branching structure form. Here successive nodes of the tree each contain a finite state model of the system which maintains information of the state of the system attained to that point and the branches represent decisions made that take the system to subsequent nodes.

To solve the problem, current methods of stochastic system simulation work with the system representation as given and iteratively track its state from that initially given until a final state or condition of interest has been reached. They must perform a large number of replications of such sample trajectories to achieve statistical significance. While any particular method might employ the tree branching representation and the associated methods in an ad hoc manner, the proposed means provides a systematic way to apply and implement the associated methods in the most efficient manner possible.

The branching tree structure affords a general method of approximating a stochastic system in a form that affords specific methods of speeding up the computations required to predict its behavior. The methods exploit the nature of the finite state representation to efficiently identify the state and output transitions associated with branching, the branching probabilities. Moreover, once a (state, branch) pair have been encountered and the resulting (state, output) pair have been computed by simulation, the next time this (state, branch) pair is encountered the resulting (state, output) is found by table lookup, a much faster process than simulation.

Like reference numerals indicate similar parts throughout the figures.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

As shown inFIGS.1-10, the goal of the invention is to develop a method combining algorithms, tools, software and analyses for a paratemporal solution (called Para-DEVS) that improves upon traditional simulation of large system of system stochastic models with the objectives include: achieve speed-up and scalability as number of random draws increases; enable increased knowledge and statistical significance in scenario outcome/output distributions confidence; and minimize workload for models and simulation infrastructure for users.

This invention expresses the stochastic system in a tree branching structure form. Here successive nodes of the tree each contain a finite state model of the system which maintain information of the state of the system attained to that point and the branches represent decisions made that take the system to subsequent nodes.

The branching tree structure affords a general method of approximating a stochastic system in a form that affords specific methods of speeding up the computations required to predict its behavior. The methods exploit the nature of the finite state representation to efficiently identify the state and output transitions associated with branching, the branching probabilities. Moreover, once a (state, branch) pair have been encountered and the resulting (state, output) pair have been computed by simulation, the next time this (state, branch) pair is encountered the resulting (state, output) is found by table lookup, a much faster process than simulation.

Current methods of stochastic system simulation work with the system representation as given and iteratively track its state from that initially given until a final state or condition of interest has been reached. They must perform a large number of replications of such sample trajectories to achieve statistical significance. While any particular method might employ the tree branching representation and the associated methods in an ad hoc manner, the proposed means provides a systematic way to apply and implement the associated methods in the most efficient manner possible.

Current methods employ Monte Carlo techniques to sample trajectories with enough replications to achieve statistical confidence at the trajectory level. In contrast, the disclosed method samples on the level of individual branches which requires much less time to achieve the same level of confidence.

Further the disclosed method automatically speeds up the computation by filling out the state table and switching to its subsequent use as soon as possible.

The DEVS formalism is a set theory based on the set theory proposed by B. P. ZEIGLER (inventor) in 1976. The DEVS formalism provides a mathematical basis for modeling the discrete event system by module and hierarchical connection. The atomic model representing the system components and the coupled model that can construct a new model by combining several models can be used to represent the system hierarchically and modularly using these two types of models. This object-oriented modeling can increase the reusability, maintainability, and reliability of the model.

Discrete-event system specification (DEVS) is a modeling formalism that can be used to define a system's behavior and structure. DEVS provides a modular and hierarchical formalism for modeling and analyzing event-based systems and uses state-based specifications that can easily be translated into hardware designs. A timed sequence of events can cause changes to the system's state—these events may be external events (e.g., generated by another model) or internal events (e.g., generated by the model itself due to a time event). The system's next states are defined based on the previous state and the event, and the state does not change between events. In the DEVS formalism, a model can be atomic to capture the system component behavior or building blocks of a model. Alternatively, a model can be coupled, involving the combination of and communication between different atomic models, to capture the system structure. In its classic form, the DEVS atomic model can be defined as a 7-tuple with the structure:
M=<S,X,Y,δint,δext,λ,ta>

where S is the set of states, X is the set of inputs, Y is the set of outputs, δint is the internal transition function that changes the state after an internal event has occurred, δext is the external transition function that changes the state based on the arrival of an external event, λ: S→Y is the output function, and ta is the time advance function. A system is initially in a start state, and each state has a time advance that dictates the amount of time spent in the state before an internal transition is triggered. Apart from positive real-valued time advance, the time advance may also be zero, offering a convenient construct for transitory states. Finally, an infinite time advance represents passive (inactive) states. An internal transition may trigger an output function whose outputs may cause external transitions on other models' input ports.

FIG.1is a flow block diagram illustrating an example of event patterns. A Selection box at1selects input which is the branch given the state of the node to be expanded. A Decision box at2checks whether the (state, input) pair is a known input to the state table. A State table at3returns the corresponding (next state, output) pair if the (state, input) pair is a known input. At a Simulate box at4, if the (state, input) pair is not known to the state table, a simulation is started to obtain the needed result. Store in a table box at5places the (next state, output) pair into the table in association with the (state, input) pair. Join at6both paths stemming from the decision box converges. An Add a node box at7adds a node at the end the branch selected by the Selection box, setting up the iteration to continue.

FIG.2is a flow tree diagram illustrating an example of an event pattern according to the embodiment. The branching tree structure inFIG.2has a Root and nodes that are connected by edges. Each node represents a decision point at100where a random variable yields a label for an edge, or branch, to be taken. Each edge holds the probability of taking that branch at200. A leaf node accumulates the probabilities and values along the path from the root to the leaf at300. Value is the accumulated values along the path from root to leaf at400. The branching probabilities are identified by running to the simulation starting from the root node to the set of next decision points. Then the tree branching expansion is executed as described and the values and probabilities accumulated at the leaf nodes are combined to compute the probability distribution of interest to solve the given problem.

Conventional methods employ Monte Carlo techniques to sample trajectories with enough replications to achieve statistical confidence at the trajectory level. In contrast, the disclosed method samples on the level of individual branches which requires much less time to achieve the same level of confidence.

As shown inFIG.3, a stochastic model is a timed non-deterministic model defined at all of its states. A deterministic model is a timed non-deterministic model deterministic at all its states. Clearly, deterministic models are a subset of stochastic models. In application to Para-DEVS simulation, a non-deterministic state is known as a random draw state. A state trajectory connecting a pair of states's and s′ is a sequence s1, s2, . . . , sn which starts with s and ends with s′ and satisfies the transition relation, i.e., where s1=s, sn=s′ and δ(si, si+1) for i=1, . . . , n−1.

A deterministic state trajectory is a state trajectory containing only deterministic states. The time to traverse a deterministic state trajectory is the sum of the transition times associated with the successive pairs of states in its sequence.

The invention can remove deterministic states from a stochastic model and replace multi-step deterministic trajectories with single step trajectories to represent the effect of cloning simulations. Given a stochastic model, M=<S, δ, ta> it is defined that the reduced model as:
M′=<S′,δ′,ta′>
whereS′⊆S is the subset of non-deterministic states of Mδ′⊆S′×S′={(s, s′)| if there is a deterministic state trajectory connecting s and s′ }
ta′: δ′→R0∞

As shown inFIG.4, the reduced model is a homomorphic image of the original based on a correspondence restricted to non-deterministic states and multi-step deterministic sequences mapped into corresponding single step sequences.

It is noted that the transversal time from any non-deterministic state to any other is preserved in the reduced version. However, the advantage of constructing this representation is that the computation (in simulation) of a multistep sequence can be replaced by a look up when the branching is subsequently encountered.

As the embodiment, a Stochastic Input-Free DEVS has the structure:
MST=<Y,S,Gint,Pint,λ,ta>
where Y, S, λ, ta have the usual definitions and Gint: S→2Sis a function that assigns a collection of sets Gint(s)⊆2Sto every state s. Given a state s, the collection Gint(s) contains all the subsets of S that the future state might belong to with a known probability, determined by a function Pint: S×2S→[0, 1]. When the system is in state s the probability that the internal transition carries it to a set G∈Gint(s) is computed by Pint (s, G).For S finite, it let.
Pint(s,G)=ΣPr(s,s′)
S_∈G
where Pr(s, s′) is the probability of transitioning from s to s′.Probability Transition Structure
PTS=<S,Pr>
and
Time Transition Structure
TTS=<Sτ>
gives rise to an Input-Free DEVS Markov Model
MDEV S=<Y,SDEV S,δint,λ,ta>where SDEV S=S×[0, 1]S×[0, 1]Swith typical element (s, γ1, γ2) with γi: S→[0, 1], i=1, 2
whereδint: SDEV S→SDEV Sis given by:δint(s, γ1,γ2)=s′=(SelectPhaseGint(s, γ1), γ1′, γ2′)and ta: SDEV S→R+0,∞is given by:ta(s,γ1,γ2)=SelectSigmaTTS(s,s,γ2)and γi′=Γ(γi), i=1,2

The input-free DEVS Markov Model is introduced as a concrete implementation for non-deterministic models. On the one hand such models are constructible in computational form in such environments. On the other hand, it can explicitly define how such models give rise to non-deterministic models as in the following:

Essentially, this assertion shows how a transition from state s1 to s2 is possible if there is a random selection of s2 from the set of possible next states of s1 and the time for such a transition is given by a sampling from the distribution for traversal times.

As shown inFIG.5, it is formulated as a framework for Para-DEVS simulation based on system theory and DEVS. To capture the effect of cloning on the source stochastic simulation, it is considered other representations including concepts of non-deterministic, stochastic, deterministic models and semigroup monoid algebras. It is also defined as a reduced non-deterministic model.

The reduced model is a homomorphic image of the original based on a correspondence restricted to non-deterministic states and multi-step deterministic sequences mapped into corresponding single step sequences.

This result formalizes the reduction in computing time that can be achieved by storing the multistep transition from a draw state to another draw state. When this can be retrieved from a repository it obviates the need to recompute the intermediate steps taken.

The Stochastic Input-Free DEVS is defined as Probability Transition Structure, and Time Transition Structure. On the one hand such models are constructible in computational form in such modeling and simulation environments. On the other hand, it is shown how such models give rise to non-deterministic models, it is shown how a transition from state s1 to s2 is possible if there is a random selection of s2 from the set of possible next states of s1 and the time for such a transition is given by a sampling from the distribution for traversal times.

Embodiments of the invention described herein are implemented as a baseball game as an example. The baseball game is integrated into DEVS simulator and obtains data for abstract model, cross-verification and validation of models.FIG.6illustrates the coupled model representation of the baseball game as implemented in a system, the DEVS-based modeling and simulation environment developed by inventor. TheFIG.6reflects a focus on the set of batter outcomes {Single, Double, . . . } as random draw decisions to be exposed in line with the proposed methodology. At this level of resolution, the state of the game as perceived by a batter is configuration of the bases {First base, Second base, Third base} in {Empty, Occupied} condition thus forming 8 configuration The DEVS coupled model inFIG.6has components for each base which adjust their respective occupation states in accordance with the rules governing the effects of batter outcomes which become inputs to the model. states. Also included is a component representing home plate that is continually updated on the states of the bases and computes runs scored as determined by the rules.

As shown inFIG.7, coupled Model representation of Baseball Game: Each node represents a batter along with the state of the game; State of the game={runners on bases}, Input=Batter outcome={single, double, . . . }, Output=Runs scored; Branching corresponds to random variable outcome of the batter.

As shown inFIG.7, the coupled model of DEVS-based framework for Para-DEVS Simulation can be encapsulated in a system specification at the state system level in the form of a Mealy Machine [1]:
M=<X,S,Y,δ,λ>X={out, single, double, triple, homer}S={BasesEmpty, . . . , BasesLoaded}Y=Non-negative integersδ(s,x)=as shown inFIG.7λ(s,x)=runs scored in transition caused by batter outcome on state (e.g., a homer acting on bases loaded state causes 4 runs to be scored.)

The branching tree expansion potentially affords much greater speedup and scalability than the baseline approach of generating individual state trajectories. In examining this comparison, it is realized that the system state table exemplified by the Mealy machine could significantly speed up the computation by replacing simulation by table lookup. This would be especially applicable to tree expansion since it offers many more opportunities for reuse of earlier encountered computations. The implementation of this idea is illustrated inFIG.7and summarized as follows:Define the disclosure depth=minimum depth of branching tree such that all states are accessibleThe state table can be completely filled out by simulating to disclosure depth+1The computational cost of table inclusion=cost of initial additional state table construction,The benefit=reduction in tree expansion time afforded by lookup vs simulation.

In application to the baseball game, it observes up to 2300 speedup for tree expansion for depth up to 7 (also tree expansion without table lookup could not exceed depth7vs with table lookup could continue to depth9).

FIG.8sets up a workflow to compare a) identifying the branch (batter outcome) probabilities of the model and subsequently using the model in predictive form and b) simulating the given stochastic system to get the same level of statistical significance as baseline. An Input box10provides a state to a In State Table11. The In State Table11is a decision box and decides to go to a Look Up table box12if the decision is Yes. If the decision is No, the next step goes to a Simulate box13. A Join box14joins with the Look up table12and Simulate13. The Join box14provides a next state as a current state. This comparison is illustrated inFIG.9, where the advantage in sampling to identify branch probabilities vs leaf outcome probabilities for the same statistical significance is shown to be the ratio of computation time to get a sample for a leaf outcome (i.e., number of runs scored in a 9 inning game) to the time needed to get a sample to estimate the branching probabilities. To get a game sample requires at least 27 batter outcomes (we assume 30 for simplicity) while one batter outcome gives an estimate of the branching probabilities. Thus, the expected speedup of the model-based approach is in the order of 30 fold.

In addition, it is considering the approximation introduced in the simplification of the rules made to assume that the transition and output functions of the Mealy machine could be taken as single valued (which corresponds to assuming that the underlying system is deterministic.) For example, the assumption that an out does not change the state of the field can be violated by a sacrifice fly ball or bunt in which the batter is out but the runner advances. Also, a double play not only causes the batter to be out but also the runner on first base. How such approximation can be accounted for using approximate morphism concepts. This approach sets up the mechanism to address such questions as “How does error propagate?”, “How big a difference does it make in final outcome?”.

To implement the ParaDEVS prototype requires the following behaviors: Enable DEVS model to detect encounter of random draw states; Inform simulator of the branching point; Provide the branch probabilities; Store state information.

The implementation requires us to design tree-like structures to support cloning, state merging, and exploration as discussed above. Also, it seeks a design that minimizes the amount of information that the user has to provide beyond the basic model. To do so, it is considered exploiting:Modular separation of DEVS model and simulator.Its existing simulator implementation based on well-defined DEVS abstract simulator and Object-oriented principles.Java reflection class properties (Java program can “introspect” and manipulate class attributes and methods while executing.)

FIG.10, the system of the present invention may include at least one computer501with a user interface. The computer may include any computer including, but not limited to, a desktop, laptop, and smart device, such as, a tablet and smart phone. The computer501includes a computer software program product including a non-transitory machine-readable program code for causing, when executed, the computer to perform steps. The program product may include software which may either be loaded onto the computer or accessed by the computer. The loaded software may include an application on a smart device. The software may be accessed by computer using a web browser502. The computer may access the software via the web browser using the internet500, extranet, intranet504, host server505, internet cloud503and the like.

The computer-based data processing system and method described above is for purposes of example only and may be implemented in any type of computer system or programming or processing environment, or in a computer program, alone or in conjunction with hardware. The present invention may also be implemented in software stored on a non-transitory computer-readable medium and executed as a computer program on a general purpose or special purpose computer. For clarity, only those aspects of the system germane to the invention are described, and product details well known in the art are omitted. For the same reason, the computer hardware is not described in further detail. It should thus be understood that the invention is not limited to any specific computer language, program, or computer. It is further contemplated that the present invention may be run on a stand-alone computer system or may be run from a server computer system that can be accessed by a plurality of client computer systems interconnected over an intranet network, or that is accessible to clients over the Internet. In addition, many embodiments of the present invention have application to a wide range of industries. To the extent the present application discloses a system, the method implemented by that system, as well as software stored on a computer-readable medium and executed as a computer program to perform the method on a general purpose or special purpose computer, are within the scope of the present invention. Further, to the extent the present application discloses a method, a system of apparatuses configured to implement the method are within the scope of the present invention.

While the above description contains many specifics, these specifics should not be construed as limitations of the invention, but merely as exemplifications of preferred embodiments thereof. Those skilled in the art will envision many other embodiments within the scope and spirit of the invention as defined by the claims appended hereto.

Where this application has listed the steps of a method or procedure in a specific order, it may be possible, or even expedient in certain circumstances, to change the order in which some steps are performed, and it is intended that the particular steps of the method or procedure claim set forth herein below not be construed as being order-specific unless such order specificity is expressly stated in the claim.

While the preferred embodiments of the devices and methods have been described in reference to the environment in which they were developed, they are merely illustrative of the principles of the inventions. Modification or combinations of the above-described assemblies, other embodiments, configurations, and methods for carrying out the invention, and variations of aspects of the invention that are obvious to those of skill in the art are intended to be within the scope of the claims.