Self-correction of errors in discrete dynamic systems

The ability of a discrete dynamic system for correcting functional errors is investigated. A method for enhancing the degree of self-correction is described.     

Observability of discrete event dynamic systems

A finite state automaton is adopted as a model for discrete event dynamic systems (DEDS). Observations are assumed to be a subset of the event alphabet. Observability is defined as having perfect knowledge of the current state at points in time separated by bounded numbers of transitions. A polynomial test for observability is given. It is shown that an observer may be constructed and implemented in polynomial time and space. A bound on the cardinality of the observer state space is also presented. A notion of resiliency is defined for observers, and a test for resilient observability and a procedure for the construction of a resilient observer are presented     

A new approach to the analysis of discrete event dynamic systems

We present a new, time domain approach to the study of discrete event dynamical systems (DEDS), typified by queueing networks and production systems. A general state-space representation is developed and perturbation analysis is carried out. Observation of a single sample realization of such a system can be used to predict behavior over other sample realizations, when some parameter is perturbed, without having to make additional observations. Conditions under which this is always possible are investigated and explicit results for some special cases are included.     

Constraint-based modeling of discrete event dynamic systems

Numerous frameworks dedicated to the modeling of discrete event dynamic systems have been proposed to deal with programming, simulation, validation, situation tracking, or decision tasks: automata, Petri nets, Markov chains, synchronous languages, temporal logics, event and situation calculi, STRIPS…All these frameworks present significant similarities, but none offers the flexibility of more generic frameworks such as logic or constraints. In this article, we propose a generic constraint-based framework for the modeling of discrete event dynamic systems, whose basic components are state, event, and time attributes, as well as constraints on these attributes, and which we refer to as CNT for Constraint Network on Timelines. The main strength of such a framework is that it allows any kind of constraint to be defined on state, event, and time attributes. Moreover, its great flexibility allows it to subsume existing apparently different frameworks such as automata, timed automata, Petri nets, and classical frameworks used in planning and scheduling.     

High-speed simulation of discrete dynamic probabilistic systems

The theory and design of a special purpose stochastic computer for the high-speed simulation of Markov chains and random walks is described. Experimental results are presented for the transient and steady response to Markov systems and for fundamental studies of random walks. The paper conlcludes with a discussion of the extension of the system to the Monte-Carlo solution of partial differential equations with arbitrary boundary conditions.     

A new approach to differential dynamic programming for discrete time systems

This paper proposes a new differential dynamic programming algorithm for solving discrete time optimal control problems with equality and inequality constraints on both control and state variables and proves its convergence. The present algorithm is different from differential dynamic programming algorithms developed in [10]-[15], which can hardly solve optimal control problems with inequality constraints on state variables and whose convergence has not been proved. Composed of iterative methods for solving systems of nonlinear equations, it is based upon Kuhn-Tucker conditions for recurrence relations of dynamic programming. Numerical examples show file efficiency of the present algorithm.     

A subject-indexed bibliography of discrete event dynamic systems

A subject-indexed bibliography of discrete event dynamic systems is given. Each subject is briefly described and some characteristic topics and references for each subject are listed. The complete reference list is provided on the ftp-site and instructions how to retrieve related files are given     

Full-state perturbation analysis of discrete event dynamic systems

Discrete event dynamic systems are studied within the framework of perturbation analysis in this paper. Perturbation is extended from the event times only to both event times and queue lengths. An approximate technique, full-state perturbation analysis (PA), is developed as an extension of the PA approach. Full-state PA is able to deal with problems involving queue length perturbations which often defy existing PA methods, while it still retains all the advantages of existing PA. Full-state PA is used to calculate the throughput sensitivity to the number of customers in closed queueing networks and the throughput sensitivity to routing change. Numerical examples are given. Experimental results verify the validity and accuracy.This work is supported in part by the National High Technology Project and by Southeast University Research Funds for Young Teachers.     

Stability and robustness of discrete event dynamic systems

In this paper, the general concepts of stability of discrete event dynamic systems are defined and investigated. We present the stability in the sense of Lyapunov with resiliency, by incorporating the Lyapunov stability concepts (Michel and Miller 1977, Passino et al. 1994) with the concept of stability in the sense of error recovery (Ozveren and Willsky 1991a). We also provide algorithms for verifying stability and obtaining the domain of attraction. Upon the proposed stability concepts, we address the issue of robust stability and stabilizability. We assume that the plant G is not known exactly but we only know that it belongs to a set of models. In robust stability, we analyse the stability of the common invariant states set of all possible plant models. Then we derive the necessary and sufficient conditions for the robust stabilizability, i.e. the existence of a supervisor which makes the uncertain system robustly stable.     

非线性DEDS的标准结构

非线性DEDS是指由极大极小函数描述的系统, 常见于计算机科学、控制论、运筹学等领域, 考虑非自治非线性DEDS的结构问题, 通过引入白色图和凝白色图, 得到了系统能达和能观的两个充要条件以及系统的标准结构, 同时还给出了它们的矩阵表示.     

Optimizing discrete event dynamic systems via the gradient surface method

In this paper we propose a gradient surface method (GSM) for the optimization of discrete event dynamic systems. GSM combines the advantages of response surface methodology (RSM) and efficient derivative estimation techniques like perturbation analysis (PA) or likelihood ratio method (LR). In GSM, the gradient estimation is obtained by PA (or LR), and the performance gradient surface is obtained from observations at various points in a fashion similar to the RSM. Zero points of the successive approximating gradient surface are then taken as the estimates of the optimal solution. GSM is characterized by several attractive features: it is a single-run method and more efficient than RSM; it uses at each iteration step the information from all data points rather than just the local gradient; it tries to capture the global features of the gradient surface and thereby quickly arrives at the vicinity of the optimal solution. A number of examples are exhibited to illustrate this method.This work was supported by the Office of Naval Research Grants Nos. N00014-90-K-1093 and N00014-89-J-1023, by National Science Foundation Grant No. ECS-85-15449 and by Army Grant No. DAAL-03-86-K-0171.     

Reduced ellipsoidal state observer of multidimensional discrete dynamic systems

The problem of synthesis of a reduced ellipsoidal state observer is considered for multidimensional linear stationary dynamic systems. The algorithms developed possess the robustness property, i.e., they are not sensitive to violation of a priori assumptions ah he system. Computer simulation of an adaptive spacecraft attitude control system confirms the cjjiciency of the algorithm developed. The study was carried out with the partial support of the Ukrainian Scientific and Technical Center. Project No. 548. Translated frorr Kibernetika i Sistemnyi Analiz, No. 2. pp. 99–105, March–April, 2000.     

Performance evaluation and perturbation analysis of discrete event dynamic systems

This is a conceptual and speculative paper concerning the future development of system and control theory in operational and discrete event systems with particular emphasis to the techniques of perturbation analysis.     

Non-linear state smoothing for discrete dynamic systems with past histories

A state smoothing scheme is presented for dynamic systems with past histories. The state in the future is a given (linear or non-linear) function of the disturbance noise and both the present and N — I past discrete values of the state. An observation in the present is a given function of the observation noise and both the present and N — 1 past discrete values of the state. The proposed scheme is based upon multiple hypothesis testing and the Viterbi algorithm of information theory, Simulation results, some of which are presented, have shown that the proposed scheme performs well.     

Covariance factorization algorithms for fixed-interval smoothing oflinear discrete dynamic systems

Efficient factorized covariance smoothers designed to work with factorized covariance filters are derived for linear discrete dynamic systems. The approach to factorized covariance smoothers (either U -D or square root) uses outputs from factorized covariance filters and is closely derived from the G.J. Bierman's earlier algorithm (1974), the Dyer-McReynolds covariance smoother. These algorithms are more efficient than the Bierman's newer smoother (1983) based upon rank 1 process noise updates. The efficiency of the new algorithms increases significantly as the order of process noise increases. For full process noise, they can be implemented in a way that avoids the inverse of the transition matrix     

A state prediction scheme for discrete time nonlinear dynamic systems

A state prediction scheme is proposed for discrete time nonlinear dynamic systems with non-Gaussian disturbance and observation noises. This scheme is based upon quantization, multiple hypothesis testing, and dynamic programming. Dynamic models of the proposed scheme are as general as dynamic models of particle predictors, whereas the nonlinear models of the extended Kalman (EK) predictor are linear with respect to the disturbance and observation noises. The performance of the proposed scheme is compared with both the EK predictor and sampling importance resampling (SIR) particle predictor. Monte Carlo simulations have shown that the performances of the proposed scheme, EK predictor, and SIR particle predictor are all model-dependent, that is, one performs better than the others for a given example. Some examples, for which the proposed scheme performs better than the others do, are also given in the paper.     

A numerical method for dynamic response analysis of discrete systems

A numerical method that permits the calculation of the time-dependent response of linear discrete systems is presented. The approach presented in this paper differs from direct integration methods, and is based on the concept of complex frequency response and fast Fourier transform which has been adapted for dynamic analysis. The method is unconditionally stable and very effective for the dynamic analysis of a system served by proportional and inertial feedback compared with direct integration methods. A Fortran coded program for dynamic analysis has been employed to calculate the transient-state response of the turning machine-tool structure.     

A note on filtering in queueing networks and discrete event dynamic systems

In this short tutorial paper, we give a simple Bayesian derivation of the optimal filtering formula for queueing networks. No measure theoretic knowledge is needed.     

Application of the Lyapunov vector functions to the stability study of fixed points in the sets of discrete dynamic systems

Stability conditions for fixed points of the dynamic systems in the space of nonempty convex compacts in finite-dimensional space were obtained. For the sets of dynamic systems, a methods was proposed to construct the Lyapunov vector functions. The study was carried out using the Matrosov method of comparison in combination with the methods of the convex geometry. In some special cases, the results obtained are applicable to the study of the sets of trajectories of dynamic systems.