Iterative convergence of passage-time densities in semi-Markov performance models

Passage-time densities are important for the detailed performance analysis of distributed computer and communicating systems. We provide a proof and demonstration of a practical iterative algorithm for extracting complete passage-time densities from expressive semi-Markov systems. We end by showing its application to a distributed web-server cluster model of 15.9 million states.     

Reward model solution methods with impulse and rate rewards: an algorithm and numerical results

Reward models have become an important method for specifying performability models for many types of systems. Many methods have been proposed for solving reward models, but no method has proven itself to be applicable over all system classes and sizes. Furthermore, specification of reward models has usually been done at the state level, which can be extremely cumbersome for realistic models. We describe a method to specify reward models as stochastic activity networks (SANs) with impulse and rate rewards, and a method by which to solve these models via uniformization. The method is an extension of one proposed by de Souza e Silva and Gail in which impulse and rate rewards are specified at the SAN level, and solved in a single model. Furthermore, we propose a new technique for discarding paths in the uniformized process whose contribution to the reward variable is minimal, which greatly reduces the time and space required for a solution. A bound is calculated on the error introduced by this discarding, and its effectiveness is illustrated through the study of the performability and availability of a degradable multi-processor system.     

Specification techniques for Markov reward models

Markov reward models (MRMs) are commonly used for the performance, dependability, and performability analysis of computer and communication systems. Many papers have addressed solution techniques for MRMs. Far less attention has been paid to the specification of MRMs and the subsequent derivation of the underlying MRM. In this paper we only briefly address the mathematical aspects of MRMs. Instead, emphasis is put on specification techniques. In an application independent way, we distinguish seven classes of specification techniques: stochastic Petri nets, queuing networks, fault trees, production rule systems, communicating processes, specialized languages, and hybrid techniques. For these seven classes, we discuss the main principles, give examples and discuss software tools that support the use of these techniques. An overview like this has not been presented in the literature before. Finally, the paper addresses the generation of the underlying MRM from the high-level specification, and indicates important future research areas. This work was supported in part by the Naval Surface Warfare Center under contract N60921-92-C-0161 and by the National Science Foundation under grant CCR-9108114.     

On Markov reward modelling with FSPNs

In this paper, fluid stochastic Petri nets (FSPNs) will be used for modelling reward in a performability model. Two variations of a known performability model are presented in order to demonstrate the ability of FSPNs in modelling accumulated rate reward as well as accumulated impulse reward. In the first model two fluid places are used, one of which represents the profit (reward) obtained by operating the system and the other one the buffer that is approximated continuously. In the second model only one fluid place is used, representing the costs (negative reward) arising due to repair of system components. The costs increase continuously at deterministic rate while the system is in state of repair (which is a rate reward in the model). Additional costs incur each time the buffer fails (which is an impulse reward in the model). With a numerical solution algorithm the distribution of the reward and its mean are computed. The accuracy of the numerical algorithm is studied by showing for the first model the impact of the choice of the discretization stepsizes on the obtained solution. Different boundary conditions are discussed for the second model.     

Markov regenerative stochastic Petri nets with general execution policies: supplementary variable analysis and a prototype tool

Stochastic Petri nets (SPNs) with general firing time distributions are considered. Generally timed transitions can have general execution policies: the preemption policy may be preemptive repeat different (prd) or preemptive resume (prs) and the firing time distribution can be marking-dependent. A stationary analysis method covering all possible combinations is presented by means of supplementary variables. The method is implemented in a prototype tool SPNica which is based on Mathematica. The use of the general execution policies is illustrated by a WWW server model.     

Lumping partially symmetrical stochastic models

The performance and dependability evaluation of complex systems by means of dynamic stochastic models (e.g. Markov chains) may be impaired by the combinatorial explosion of their state space. Among the possible methods to cope with this problem, symmetry-based ones can be applied to systems including several similar components. Often however these systems are only partially symmetric: their behavior is in general symmetric except for some local situation when the similar components need to be differentiated.In this paper two methods to efficiently analyze partially symmetrical models are presented in a general setting and the requirements for their efficient implementation are discussed. Some case studies are presented to show the methods’ effectiveness and their applicative interest.     

Robot introspection through learned hidden Markov models

In this paper we describe a machine learning approach for acquiring a model of a robot behaviour from raw sensor data. We are interested in automating the acquisition of behavioural models to provide a robot with an introspective capability. We assume that the behaviour of a robot in achieving a task can be modelled as a finite stochastic state transition system.Beginning with data recorded by a robot in the execution of a task, we use unsupervised learning techniques to estimate a hidden Markov model (HMM) that can be used both for predicting and explaining the behaviour of the robot in subsequent executions of the task. We demonstrate that it is feasible to automate the entire process of learning a high quality HMM from the data recorded by the robot during execution of its task.The learned HMM can be used both for monitoring and controlling the behaviour of the robot. The ultimate purpose of our work is to learn models for the full set of tasks associated with a given problem domain, and to integrate these models with a generative task planner. We want to show that these models can be used successfully in controlling the execution of a plan. However, this paper does not develop the planning and control aspects of our work, focussing instead on the learning methodology and the evaluation of a learned model. The essential property of the models we seek to construct is that the most probable trajectory through a model, given the observations made by the robot, accurately diagnoses, or explains, the behaviour that the robot actually performed when making these observations. In the work reported here we consider a navigation task. We explain the learning process, the experimental setup and the structure of the resulting learned behavioural models. We then evaluate the extent to which explanations proposed by the learned models accord with a human observer's interpretation of the behaviour exhibited by the robot in its execution of the task.     

Simulation-based sequential analysis of Markov switching stochastic volatility models

We propose a simulation-based algorithm for inference in stochastic volatility models with possible regime switching in which the regime state is governed by a first-order Markov process. Using auxiliary particle filters we developed a strategy to sequentially learn about states and parameters of the model. The methodology is tested against a synthetic time series and validated with a real financial time series: the IBOVESPA stock index (São Paulo Stock Exchange).     

Performance analysis using Petri nets

The purpose of this paper is to focus on the implementation issues associated with using Petri nets for the performance analysis of discrete event dynamic systems while demonstrating several applications in manufacturing systems. Practical modeling issues will be discussed and several applications will be presented that illustrate the advantages and limitations of this methodology. These issues lead to the definition of several research problems in Petri nets for performance analysis.     

Discovering simulation models

Process mining is a tool to extract non-trivial and useful information from process execution logs. These so-called event logs (also called audit trails, or transaction logs) are the starting point for various discovery and analysis techniques that help to gain insight into certain characteristics of the process. In this paper we use a combination of process mining techniques to discover multiple perspectives (namely, the control-flow, data, performance, and resource perspective) of the process from historic data, and we integrate them into a comprehensive simulation model. This simulation model is represented as a colored Petri net (CPN) and can be used to analyze the process, e.g., evaluate the performance of different alternative designs. The discovery of simulation models is explained using a running example. Moreover, the approach has been applied in two case studies; the workflows in two different municipalities in the Netherlands have been analyzed using a combination of process mining and simulation. Furthermore, the quality of the CPN models generated for the running example and the two case studies has been evaluated by comparing the original logs with the logs of the generated models.     

计算机系统与计算机网络中的动态优化:模型、求解与应用

动态优化是计算机系统与计算机网络中进行资源分配与任务调度等方面研究所采用的主要理论工具之一.目前,国内外已开展大量研究,致力于深化动态优化的理论研究与工程应用.文中从模型、求解与应用3个角度,对马尔可夫决策过程动态优化理论模型进行了综述,并重点介绍了将动态优化理论与随机Petri网理论相结合的马尔可夫决策Petri网和随机博弈网模型,详细讨论了这些模型的建模方法、求解算法与一些应用实例.最后,对全文进行了总结,并对未来可能的研究方向进行了展望.     

Integrating synchronization with priority into a Kronecker representation

The compositional representation of a Markov chain using Kronecker algebra, according to a compositional model representation as a superposed generalized stochastic Petri net or a stochastic automata network, has been studied for a while. In this paper we describe a Kronecker expression and associated data structures, that allows to handle nets with synchronization over activities of different levels of priority. New algorithms for these structures are provided to perform an iterative solution method of Jacobi or Gauss–Seidel type. These algorithms are implemented in the APNN Toolbox. We use this implementation in combination with GreatSPN and exercise an example that illustrates characteristics of the presented algorithms.     

Optimal decisions for continuous time Markov decision processes over finite planning horizons

The computation of ϵ-optimal policies for continuous time Markov decision processes (CTMDPs) over finite time intervals is a sophisticated problem because the optimal policy may change at arbitrary times. Numerical algorithms based on time discretization or uniformization have been proposed for the computation of optimal policies. The uniformization based algorithm has shown to be more reliable and often also more efficient but is currently only available for processes where the gain or reward does not depend on the decision taken in a state. In this paper, we present two new uniformization based algorithms for computing ϵ-optimal policies for CTMDPs with decision dependent rewards over a finite time horizon. Due to a new and tighter upper bound the newly proposed algorithms cannot only be applied for decision dependent rewards, they also outperform the available approach for rewards that do not depend on the decision. In particular for models where the policy only rarely changes, optimal policies can be computed much faster.     

Numerical analysis of continuous time Markov decision processes over finite horizons

Continuous time Markov decision processes (CTMDPs) with a finite state and action space have been considered for a long time. It is known that under fairly general conditions the reward gained over a finite horizon can be maximized by a so-called piecewise constant policy which changes only finitely often in a finite interval. Although this result is available for more than 30 years, numerical analysis approaches to compute the optimal policy and reward are restricted to discretization methods which are known to converge to the true solution if the discretization step goes to zero. In this paper, we present a new method that is based on uniformization of the CTMDP and allows one to compute an ε-optimal$\epsilon \text{-optimal}$ policy up to a predefined precision in a numerically stable way using adaptive time steps.     

Simulation-based analysis of UML statechart diagrams: methods and case studies

We present a comprehensive unified modeling language (UML) statechart diagram analysis framework. This framework allows one to progressively perform different analysis operations to analyze UML statechart diagrams at different levels of model complexity. The analysis operations supported by the framework are based on analyzing Petri net models converted from UML statechart diagrams using a previously proposed transformation approach. After introducing the general framework, the paper emphasizes two simulation-based analysis operations from the framework: direct MSC inspection, which provides a visual representation of system behavior described by statechart diagrams; and a pattern-based trace query technique, which can be used to define and query system properties. Two case-study examples are presented with different emphasis. The gas station example is a simple multi-object system used to demonstrate both the visual and query-based analysis operations. The early warning system example uses only one object, but features composite states and includes analysis specifically aimed at one composite state feature, history states.

基于随机时间Petri网的安全性分析方法

在分析了现有的Petri网与安全性结合的方法的缺陷后,提出了一种基于随机时间Petri网(stochastic Time Petri Nets,sTPN)的系统安全性分析方法,利用sTPN建立的系统模型不局限于指数分布和确定分布的变迁,也不局限于一般分布的变迁的使能限制。通过修改后的瞬态随机状态类图以及sTPN的瞬态分析算法可以得到基于路径的安全性指标。最后给出核反应堆冷却循环系统的例子,说明了所提方法的可用性和合理性。     

Fluid Stochastic Petri Nets Augmented with Flush-out Arcs: Modelling and Analysis

Fluid(or Hybrid) Petri Nets are Petri net based models with two classesof places: discrete places that carry a natural number of distinctobjects (tokens), and fluid places that hold a positive amountof fluid, represented by a real number. With respect to previousformulations, the FSPN model presented in this paper, is augmentedwith a new primitive, called flush-out arc. A flush-out arc connectsa fluid place to a timed transition, and has the effect of instantaneouslyemptying the fluid place when the transition fires. The paperdiscusses the modeling power of the augmented formalism, andshows how the dynamics of the underlying stochastic process canbe analytically described by a set of integro-differential equations.A procedure is presented to automatically derive the solutionequations from the model specifications. The whole methodologyis illustrated by means of various examples.     

广义随机Petri网在生态产业园区性能分析中的应用*

为了对生态产业园区规划方案进行定量描述和评价,利用基于广义随机Petri网的建模分析方法,根据广义随机Petri网模型与马尔可夫链的同构关系,得到生态产业园区的Petri网模型和马尔可夫链模型。并通过马尔可夫链理论与相关数学方法,得到生态产业园区规划方案的吞吐性能、时间性能以及关键资源利用率和重点加工环节运作效率等性能指标,诊断出现有规划中存在的问题,为生态产业园区规划方案的评价和改进提供了一个思路。