Stochastic Concurrent Constraint Programming and Differential Equations

We tackle the problem of relating models of systems (mainly biological systems) based on stochastic process algebras (SPA) with models based on differential equations. We define a syntactic procedure that translates programs written in stochastic Concurrent Constraint Programming (sCCP) into a set of Ordinary Differential Equations (ODE), and also the inverse procedure translating ODE's into sCCP programs. For the class of biochemical reactions, we show that the translation is correct w.r.t. the intended rate semantics of the models. Finally, we show that the translation does not generally preserve the dynamical behavior, giving a list of open research problems in this direction.     

Building Blocks for Computer Vision with Stochastic Partial Differential Equations

We discuss the basic concepts of computer vision with stochastic partial differential equations (SPDEs). In typical approaches based on partial differential equations (PDEs), the end result in the best case is usually one value per pixel, the “expected” value. Error estimates or even full probability density functions PDFs are usually not available. This paper provides a framework allowing one to derive such PDFs, rendering computer vision approaches into measurements fulfilling scientific standards due to full error propagation. We identify the image data with random fields in order to model images and image sequences which carry uncertainty in their gray values, e.g. due to noise in the acquisition process. The noisy behaviors of gray values is modeled as stochastic processes which are approximated with the method of generalized polynomial chaos (Wiener-Askey-Chaos). The Wiener-Askey polynomial chaos is combined with a standard spatial approximation based upon piecewise multi-linear finite elements. We present the basic building blocks needed for computer vision and image processing in this stochastic setting, i.e. we discuss the computation of stochastic moments, projections, gradient magnitudes, edge indicators, structure tensors, etc. Finally we show applications of our framework to derive stochastic analogs of well known PDEs for de-noising and optical flow extraction. These models are discretized with the stochastic Galerkin method. Our selection of SPDE models allows us to draw connections to the classical deterministic models as well as to stochastic image processing not based on PDEs. Several examples guide the reader through the presentation and show the usefulness of the framework.     

Stochastic linear quadratic regulation for discrete-time linear systems with input delay

This paper considers the stochastic LQR problem for systems with input delay and stochastic parameter uncertainties in the state and input matrices. The problem is known to be difficult due to the presence of interactions among the delayed input channels and the stochastic parameter uncertainties in the channels. The key to our approach is to convert the LQR control problem into an optimization one in a Hilbert space for an associated backward stochastic model and then obtain the optimal solution to the stochastic LQR problem by exploiting the dynamic programming approach. Our solution is given in terms of two generalized Riccati difference equations (RDEs) of the same dimension as that of the plant.     

Analysis of AIMD protocols over paths with variable delay

The throughput of AIMD protocols in general and of TCP in particular, has been computed in many existing works by modeling the round-trip time as a constant and thus replacing it by its expectation. There are however many scenarios in which the delays of packets vary, causing a variation of the round-trip time. Many typical scenarios occur in wireless and mobile networks. We propose in this paper an analytical model that accounts for the variability of delay, while computing the throughput of an AIMD protocol. We derive a closed-form expression for the throughput, that illustrates the impact of delay variability. We show by analysis and simulation, that an increase in the variability of delay improves the performance of an AIMD protocol. Thus, an analytical model that only considers the average delay could underestimate the performance of an AIMD protocol in scenarios where delay is variable.     

An Energy-Stable High-Order Central Difference Scheme for the Two-Dimensional Shallow Water Equations

An energy-stable high-order central finite difference scheme is derived for the two-dimensional shallow water equations. The scheme is mathematically formulated using the semi-discrete energy method for initial boundary value problems described in Olsson (1995, Math. Comput. 64, 1035–1065): after symmetrizing the equations via a change to entropy variables, the flux derivatives are entropy-split enabling the formulation of a semi-discrete energy estimate. We show experimentally that the entropy-splitting improves the stability properties of the fully discretized equations. Thus, the dependence on numerical dissipation to keep the scheme stable for long term time integrations is reduced relative to the original unsplit form, thereby decreasing non-physical damping of solutions. The numerical dissipation term used with the entropy-split equations is in a form which preserves the semi-discrete energy estimate. A random one-dimensional dam break calculation is performed showing that the shock speed is computed correctly for this particular case, however it is an open question whether the correct shock speed will be computed in generalMSC: 35Q35; 65M12; 65M06Supported in part by the New Zealand Marsden Fund, grant UOA827     

Stochastic approximation with two time scales

Asymptotic behaviour of a two time scale stochastic approximation algorithm is analysed in terms of a related singular ordinary differential equation.     

Stochastic algorithms for robustness of control performances

In recent years, there has been a growing interest in developing statistical learning methods to provide approximate solutions to “difficult” control problems. In particular, randomized algorithms have become a very popular tool used for stability and performance analysis as well as for design of control systems. However, as randomized algorithms provide an efficient solution procedure to the “intractable” problems, stochastic methods bring closer to understanding the properties of the real systems. The topic of this paper is the use of stochastic methods in order to solve the problem of control robustness: the case of parametric stochastic uncertainty is considered. Necessary concepts regarding stochastic control theory and stochastic differential equations are introduced. Then a convergence analysis is provided by means of the Chernoff bounds, which guarantees robustness in mean and in probability. As an illustration, the robustness of control performances of example control systems is computed.     

A Single-Step Characteristic-Curve Finite Element Scheme of Second Order in Time for the Incompressible Navier-Stokes Equations

In this paper we present a new single-step characteristic-curve finite element scheme of second order in time for the nonstationary incompressible Navier-Stokes equations. After supplying correction terms in the variational formulation, we prove that the scheme is of second order in time. The convergence rate of the scheme is numerically recognized by computational results.     

A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars

We provide a strongly polynomial algorithm for determining whether a given multi-type branching process is subcritical, critical, or supercritical. The same algorithm also decides consistency of stochastic context-free grammars.     

Spectral Difference Method for Unstructured Grids II: Extension to the Euler Equations

An efficient, high-order, conservative method named the spectral difference method has been developed recently for conservation laws on unstructured grids. It combines the best features of structured and unstructured grid methods to achieve high-computational efficiency and geometric flexibility; it utilizes the concept of discontinuous and high-order local representations to achieve conservation and high accuracy; and it is based on the finite-difference formulation for simplicity. The method is easy to implement since it does not involve surface or volume integrals. Universal reconstructions are obtained by distributing solution and flux points in a geometrically similar manner for simplex cells. In this paper, the method is further extended to nonlinear systems of conservation laws, the Euler equations. Accuracy studies are performed to numerically verify the order of accuracy. In order to capture both smooth feature and discontinuities, monotonicity limiters are implemented, and tested for several problems in one and two dimensions. The method is more efficient than the discontinuous Galerkin and spectral volume methods for unstructured grids.     

Stability of Neutral Impulsive Nonlinear Stochastic Evolution Equations with Time Varying Delays

In this paper, we consider the stability of mild solutions to neutral impulsive nonlinear stochastic evolution equations with time varying delays. With the non‐Lipschitz condition, the Lipschitz condition being taken as a special case, on the impulsive term, the existence, uniqueness and sufficient conditions for the exponential stability in the pth moment and the almost sure exponential stability of the mild solutions are derived by employing a fixed point approach. An example is provided to illustrate the efficiency of the obtained theorems.     

基于随机过程的容侵系统可信性量化方法

运用马尔可夫过程分析了容侵系统的可信性,结合SITAR容侵系统体系中的状态迁移模型,给出了一种基于随机过程的容侵系统可信性的可用度量化方法。最后在此基础上讨论了入侵容忍系统的性质。     

Stochastic optimal control via Bellman''s principle

This paper presents a strategy for finding optimal controls of non-linear systems subject to random excitations. The method is capable to generate global control solutions when state and control constraints are present. The solution is global in the sense that controls for all initial conditions in a region of the state space are obtained. The approach is based on Bellman's principle of optimality, the cumulant neglect closure method and the short-time Gaussian approximation. Problems with state-dependent diffusion terms, non-closeable hierarchies of moment equations for the states and singular state boundary condition are considered in the examples. The uncontrolled and controlled system responses are evaluated by creating a Markov chain with a control dependent transition probability matrix via the generalized cell mapping method. In all numerical examples, excellent controlled performances were obtained.     

随机控制在进港航班调度中的应用

民航机场航班进港问题是一类典型的离散事件动态系统问题,但在合理的假设条件下能够转化为以进港事件发生序列为自变量,进港时间间隔为受控量的随机系统控制问题.利用某机场航班进港时间的实测数据,通过模型辨识的方法建立航班进港过程的离散随机系统ARMA模型,采用最小方差控制的策略对航班进港实施模拟调度,结果表明进港时间间隔趋于平均,最终减小总体方差.在空中交通流量日益增长的情况下,为提高航班运行效率,进一步在航班进离港辅助决策系统中应用控制理论提供了新的思路.     

Convolutional solutions of partial difference equations

A significant part of the theory of one-dimensional linear shift-invariant systems is based on the concept of weighting function (or impulse response): the output is the convolution of the weighting function with the input. This paper introduces the concept of linear translation-invariant systems and uses this notion in studying impulse response, z-transforms, and transfer functions for multidimensional systems.     

On Time Staggering for Wave Equations

Grid staggering for wave equations is a validated approach for many applications, as it generally enhances stability and accuracy. This paper is about time staggering. Our aim is to assess a fourth-order, explicit, time-staggered integration method from the literature, through a comparison with two alternative fourth-order, explicit methods. These are the classical Runge-Kutta method and a symmetric-composition method derived from symplectic Euler.     

图像放大的偏微分方程方法

在分析一些常见的图像放大方法的基础上,根据图像像素值特点及近期偏微分方程在图像处理中的应用,将图像的像素值看作是平面物体的温度;利用偏微分方程理论中的热传导数学模型,提出了基于一种新颖的热传导方程初边值问题的图像放大法;并根据其物理意义,设计相应的差分算法．实验证明,这是一种有效的图像放大方法．     

Some Ergodic Results on Stochastic Iterative Discrete Events Systems

This paper deals with the asymptotic behavior of the stochastic dynamics of discrete event systems. In this paper we focus on a wide class of models arising in several fields and particularly in computer science. This class of models may be characterized by stochastic recurrence equations in ^K of the form T(n+1) = _n+1(T(n)) where _n is a random operator monotone and 1—linear. We establish that the behaviour of the extremas of the process T(n) are linear. The results are an application of the sub-additive ergodic theorem of Kingman. We also give some stability properties of such sequences and a simple method of estimating the limit points.     

A new critical theorem for adaptive nonlinear stabilization

It is fairly well known that there are fundamental differences between adaptive control of continuous-time and discrete-time nonlinear systems. In fact, even for the seemingly simple single-input single-output control system y_t+1=θ₁f(y_t)+u_t+w_t+1 with a scalar unknown parameter θ₁ and noise disturbance {w_t}, and with a known function f(⋅) having possible nonlinear growth rate characterized by |f(x)|=Θ(|x|^b) with b≥1, the necessary and sufficient condition for the system to be globally stabilizable by adaptive feedback is b<4. This was first found and proved by Guo (1997) for the Gaussian white noise case, and then proved by Li and Xie (2006) for the bounded noise case. Subsequently, a number of other types of “critical values” and “impossibility theorems” on the maximum capability of adaptive feedback were also found, mainly for systems with known control parameter as in the above model. In this paper, we will study the above basic model again but with additional unknown control parameter θ₂, i.e., u_t is replaced by θ₂u_t in the above model. Interestingly, it turns out that the system is globally stabilizable if and only ifb<3. This is a new critical theorem for adaptive nonlinear stabilization, which has meaningful implications for the control of more general uncertain nonlinear systems.