Deterministic and stochastic control of discrete-time bilinear systems

Optimal control of a class of time invariant single-input, discrete bilinear systems is investigated in this paper. Both deterministic and stochastic problems are considered.

In the deterministic problem, for the initial state in a certain set ∑₀, the solution is the same as the solution to the associated linear system. The optimal path may be a regular path or a singular path.

The stochastic control problem is considered with perfect state observation, and additive and multiplicative noise in the state equation. It is demonstrated that the presence of noise simplifies the analysis compared to that in the determinstic case.     

Stochastic Cellular Automata Solutions to the Density Classification Problem

In the density classification problem, a binary cellular automaton (CA) should decide whether an initial configuration contains more 0s or more 1s. The answer is given when all cells of the CA agree on a given state. This problem is known for having no exact solution in the case of binary deterministic one-dimensional CA. We investigate how randomness in CA may help us solve the problem. We analyse the behaviour of stochastic CA rules that perform the density classification task. We show that describing stochastic rules as a “blend” of deterministic rules allows us to derive quantitative results on the classification time and the classification time of previously studied rules. We introduce a new rule whose effect is to spread defects and to wash them out. This stochastic rule solves the problem with an arbitrary precision, that is, its quality of classification can be made arbitrarily high, though at the price of an increase of the convergence time. We experimentally demonstrate that this rule exhibits good scaling properties and that it attains qualities of classification never reached so far.     

Synchronisation analysis for stochastic T–S fuzzy complex networks with coupling delay

In this paper, we investigated synchronisation problem for stochastic Takagi–Sugeno (T-S) fuzzy complex networks model with discrete and distributed time delays. By constructing a new Lyapunov functional and employing Kronecker product, we developed delay-dependent synchronisation criterions. By applying stochastic analysis techniques, we derive starting conditions for synchronisation complex networks of the addressed with mixed time-varying delays and stochastic disturbances are achieved. A numerical examples are provided to demonstrate the effectiveness and usefulness of the proposed results.     

Stochastic Boolean Satisfiability

Satisfiability problems and probabilistic models are core topics of artificial intelligence and computer science. This paper looks at the rich intersection between these two areas, opening the door for the use of satisfiability approaches in probabilistic domains. The paper examines a generic stochastic satisfiability problem, SSAT, which can function for probabilistic domains as SAT does for deterministic domains. It shows the connection between SSAT and well-studied problems in belief network inference and planning under uncertainty, and defines algorithms, both systematic and stochastic, for solving SSAT instances. These algorithms are validated on random SSAT formulae generated under the fixed-clause model. In spite of the large complexity gap between SSAT (PSPACE) and SAT (NP), the paper suggests that much of what we have learned about SAT transfers to the probabilistic domain.     

On the global nonlinear stochastic dynamical behavior of a class of exothermic CSTRs

The problem of assessing the short and long time effects of stochastic fluctuations on the global-nonlinear dynamics of a class of closed-loop continuous exothermic reactors with temperature control and mono or bistable isothermal dynamics is addressed. The consideration of the problem within a Fokker–Planck (FP) stochastic framework yields: (i) the characterization of the global-nonlinear stochastic dynamics, and (ii) the connection between the deterministic and stochastic modeling approaches. The evolution of the state probability density function (PDF) is explained as the result of a complex interplay between deterministic dynamical features, initial PDF shape, and noise intensity. The correspondence between stationary PDF mono (or bi) modality and deterministic mono (or bi) stability is established, and the stochastic settling time is put in perspective with the deterministic, noise-diffusion, and escape times. The conditions for the occurrence of a retarded response, with respect to deterministic and noise-diffusion times, are identified. The proposed approach: (i) is illustrated with representative case class example, and (ii) constitutes an inductive step towards the development of a general-purpose stochastic modeling approach in chemical process systems engineering.     

Combining two-stage stochastic programming and recoverable robustness to minimize the number of late jobs in the case of uncertain processing times

Minimizing the number of late jobs on a single machine is a classic scheduling problem, which can be used to model the situation that from a set of potential customers, we have to select as many as possible whom we want to serve, while selling no to the other ones. This problem can be solved by Moore–Hodgson’s algorithm, provided that all data are deterministic. We consider a stochastic variant of this problem, where we assume that there is a small probability that the processing times differ from their standard values as a result of some kind of disturbance. When such a disturbance occurs, then we must apply some recovery action to make the solution feasible again. This leads us to the area of recoverable robustness, which handles this uncertainty by modeling each possible disturbance as a scenario; in each scenario, the initial solution must then be made feasible by applying a given, simple recovery algorithm to it. Since we cannot accept previously rejected customers, our only option is to reject customers that would have been served in the undisturbed case. Our problem therefore becomes to find a solution for the undisturbed case together with a feasible recovery to every possible disturbance. Our goal hereby is to maximize the expected number of served customers; we assume here that we know the probability that a given scenario occurs. In this respect, our problem falls outside the area of the ‘standard’ recoverable robustness, which contains the worst-case recovery cost as a component of the objective. Therefore, we consider our approach as a combination of two-stage stochastic programming and recoverable robustness. We show that this problem is \(\mathcal{NP}\)-hard in the ordinary sense even if there is only one scenario, and we present some sufficient conditions that allow us to find a part of the optimal solution in polynomial time. We further evaluate several solution methods to find an optimal solution, among which are dynamic programming, branch-and-bound, and branch-and-price.     

Barycentric interpolation of interface solution for solving stochastic partial differential equations on non-overlapping subdomains with additive multi-noises

The purpose of this paper is to develop a new numerical method for solving a class of stochastic partial differential equations with additive multi-noise. Based on the domain decomposition method, we combine the deterministic method of lines and the stochastic Itô-Taylor method to construct high-order stochastic numerical method. For numerical approximation of the interface solutions, we introduce the Barycentric interpolation method. The solution is then carried out by collecting the interior solutions on the subdomains and the updated interface solutions. Finally, we computationally analyse on meaningful subdomains with linear and nonlinear interfaces, the case of a stochastic advection–diffusion with additive multi-noise and Dirichlet boundary conditions.     

On the partial stochastic realization problem

We describe a complete parameterization of the solutions to the partial stochastic realization problem in terms of a nonstandard matrix Riccati equation. Our analysis of this covariance extension equation (CEE) is based on a complete parameterization of all strictly positive real solutions to the rational covariance extension problem, answering a conjecture due to Georgiou (1987) in the affirmative. We also compute the dimension of partial stochastic realizations in terms of the rank of the unique positive semidefinite solution to the CEE, yielding some insights into the structure of solutions to the minimal partial stochastic realization problem. By combining this parameterization with some of the classical approaches in partial realization theory, we are able to derive new existence and robustness results concerning the degrees of minimal stochastic partial realizations. As a corollary to these results, we note that, in sharp contrast with the deterministic case, there is no generic value of the degree of a minimal stochastic realization of partial covariance sequences of fixed length     

Adaptive stepsizes for recursive estimation with applications in approximate dynamic programming

We address the problem of determining optimal stepsizes for estimating parameters in the context of approximate dynamic programming. The sufficient conditions for convergence of the stepsize rules have been known for 50 years, but practical computational work tends to use formulas with parameters that have to be tuned for specific applications. The problem is that in most applications in dynamic programming, observations for estimating a value function typically come from a data series that can be initially highly transient. The degree of transience affects the choice of stepsize parameters that produce the fastest convergence. In addition, the degree of initial transience can vary widely among the value function parameters for the same dynamic program. This paper reviews the literature on deterministic and stochastic stepsize rules, and derives formulas for optimal stepsizes for minimizing estimation error. This formula assumes certain parameters are known, and an approximation is proposed for the case where the parameters are unknown. Experimental work shows that the approximation provides faster convergence than other popular formulas. Editor: Prasad Tadepalli     

Uplink scheduling for joint wireless orthogonal frequency and time division multiple access networks

In this paper, we present a deterministic resource allocation model for a hybrid uplink wireless orthogonal frequency and time division multiple access network. Since the input data of the model may be affected by uncertainty, we further consider a stochastic formulation of the problem which we transform into an equivalent deterministic binary second-order conic program (SOCP). Subsequently, we use this binary SOCP to derive an equivalent integer linear programming formulation. The proposed models are aimed at maximizing the total bandwidth channel capacity subject to user power and sub-carrier assignment constraints while simultaneously scheduling users in time. As such, the models are best suited for non-real-time applications where sub-channel multiuser diversity can be further exploited simultaneously in frequency and time domains. Finally, in view of the large execution times required by CPLEX to solve the proposed models, we propose a variable neighborhood search metaheuristic procedure. Our numerical results show tight bounds and near optimal solutions for most of the instances when compared to the optimal solution of the problem. Moreover, we obtain better feasible solutions than CPLEX in the stochastic case. Finally, these bounds are obtained at a very low computational cost.     

Integral representations of solutions for linear stochastic equations with multiplicative perturbances

We consider the problem of explicitly representing the solutions of multiplicatively perturbed stochastic equations. We represent the solution as an integral Cauchy formula whose transition matrix is random in the case of multiplicative perturbations. Similar to deterministic theory, the transition matrix can be expressed in terms of the fundamental matrix or given by a stochastic Peano series. We give equations for statistical moments of the state vector and explicit integral representations of their solutions. For computing transition matrices of equations on moments, we use some group-theoretical notions and results whose usefulness is illustrated with simple examples.     

Stochastic optimal LQR control with integral quadratic constraintsand indefinite control weights

A standard assumption in traditional (deterministic and stochastic) optimal (minimizing) linear quadratic regulator (LQR) theory is that the control weighting matrix in the cost functional is strictly positive definite. In the deterministic case, this assumption is in fact necessary for the problem to be well-posed because positive definiteness is required to make it a convex optimization problem. However, it has recently been shown that in the stochastic case, when the diffusion term is dependent on the control, the control weighting matrix may have negative eigenvalues but the problem remains well-posed. In this paper, the completely observed stochastic LQR problem with integral quadratic constraints is studied. Sufficient conditions for the well-posedness of this problem are given. Indeed, we show that in certain cases, these conditions may be satisfied, even when the control weighting matrices in the cost and all of the constraint functionals have negative eigenvalues. It is revealed that the seemingly nonconvex problem (with indefinite control weights) can actually be a convex one by virtue of the uncertainty in the system. Finally, when these conditions are satisfied, the optimal control is explicitly derived using results from duality theory     

Reach a nonlinear consensus for MAS via doubly stochastic quadratic operators

This technical note addresses the new nonlinear protocol class of doubly stochastic quadratic operators (DSQOs) for coordination of consensus problem in multi-agent systems (MAS). We derive the conditions for ensuring that every agent reaches consensus on a desired rate of the group's decision where the group decision value in its agent's initial statuses varies. Besides that, we investigate a nonlinear protocol sub-class of extreme DSQO (EDSQO) to reach a consensus for MAS to a common value with nonlinear low-complexity rules and fast time convergence if the interactions for each agent are not selfish. In addition, to extend the results to reach a consensus and to avoid the selfish case we specify a general class of DSQO for reaching a consensus under any given case of initial states. The case that MAS reach a consensus by DSQO is if each member of the agent group has positive interactions of DSQO (PDSQO) with the others. The convergence of both EDSQO and PDSQO classes is found to be directed towards the centre point. Finally, experimental simulations are given to support the analysis from theoretical aspect.     

A Multiobjective Optimization Model for Dynamic Reconfiguration of Ring Topologies with Stochastic Load

In this paper we describe a heuristic procedure to generate solutions to a multiobjective stochastic, optimization problem for a dynamic telecommunications network. Generating Pareto optimal solutions can be difficult since the optimization problem is computationally challenging and moreover the network must be reconfigured in near real time, for example, to recover connectivity after a severe weather event. There are two main contributions of this paper. First, we show mathematically how a certain deterministic equivalent optimization problem can be solved instead of the stochastic one, thus facilitating computations. Second, we test our heuristic under a wide set of simulated conditions (e.g., atmospheric obscuration due to differing levels of cloud cover, different demand patterns) and show that it achieves near Pareto optimality in a short amount of time.     

Robust formation control of thrust-propelled vehicles under deterministic and stochastic topology

ABSTRACT

Formation control of multiple thrust-propelled vehicles (TPVs) under deterministic and stochastic switching topologies and communication delay is addressed. Introducing a new version of variable structure control and based upon sliding mode technique, adaptive control and projection operator, we effectively handle the impact of uncertainties on the mass and inertia matrix and a set of time-varying disturbances affecting the translational and rotational dynamics. Global stability of the whole closed-loop system is guaranteed through Lyapunov stability theory. For the deterministic topology, sufficient condition in terms of LMIs is derived to achieve formation in the presence of jointly connected switching topology. In the case of stochastic topology, based on the concept of super-martingales, it is shown that if the probability of existing a connected topology is not zero, under some conditions, formation is almost surely solved in the network. Finally, numerical simulations verify the effectiveness of the proposed control framework.     

On the open-loop solution of linear stochastic optimal control problems

We consider open-loop solutions of linear stochastic optimal control problems with constraints on control variables and probabilistic constraints on state variables. It is shown that this problem reduces to an equivalent linear deterministic optimal control problem with similar constraints and with a new criterion to minimize. Concavity or convexity is preserved. Hence, the machinery available for solving deterministic optimal control problems can be used to get an open-loop solution of the stochastic problem. The convex case is investigated and a bound on the difference between closed-loop and open-loop optimal costs is given.     

On stochastic incentive control problems with partial dynamic information

In this paper we consider a stochastic incentive decision problem with N > 1 followers and decentralized static information, where the leader's dynamic information comprises only a linear combination of the followers' actions. We obtain an incentive policy, affine in this dynamic information, which yields the same overall performance as the one the leader would obtain if he had observed the followers' actions separately. The existence conditions involved have been obtained explicitly for the case of finite probability spaces, and some challenging issues have been identified when the random variables are infinite valued. The results presented here have no counterparts in deterministic incentive problems.     

Noise suppressing sensor encoding and neural signalorthonormalization

In this paper we regard first the situation where parallel channels are disturbed by noise. With the goal of maximal information conservation we deduce the conditions for a transform which "immunizes" the channels against noise influence before the signals are used in later operations. It shows up that the signals have to be decorrelated and normalized by the filter which corresponds for the case of one channel to the classical result of Shannon. Additional simulations for image encoding and decoding show that this constitutes an efficient approach for noise suppression. Furthermore, by a corresponding objective function we deduce the stochastic and deterministic learning rules for a neural network that implements the data orthonormalization. In comparison with other already existing normalization networks our network shows approximately the same in the stochastic case, but by its generic deduction ensures the convergence and enables the use as independent building block in other contexts, e.g., whitening for independent component analysis.     

Minimax control of switching systems under sampling

We consider a general class of systems subject to two types of uncertainty: A continuous deterministic uncertainty that affects the system dynamics, and a discrete stochastic uncertainty that leads to jumps in the system structure at random times, with the latter described by a continuous-time finite state Markov chain. When only sampled values of the system state is available to the controller, along with perfect measurements on the state of the Markov chain, we obtain a characterization of minimax controllers, which involves the solutions of two finite sets of coupled PDEs, and a finite dimensional compensator. For the linear-quadratic case, a complete characterization is given in terms of coupled generalized Riccati equations, which also provides the solution to a particular H^∞ optimal control problem with randomly switching system structure and sampled state measurements.     

Robust and perfect tracking of discrete-time systems

We study in this paper the problem of robust and perfect tracking for discrete-time linear multivariable systems. By robust and perfect tracking, we mean the ability of a controller to track a given reference signal with arbitrarily small settling time in the face of external disturbances and initial conditions. A set of necessary and sufficient conditions under which the proposed problem is solvable is obtained and, under these conditions, constructive algorithms are given that yield the required solutions. As is general to discrete-time systems, the solvability conditions to the above problem are quite restrictive. To relax these conditions, we propose an almost perfect tracking scheme, which is capable of tracking references precisely after certain initial steps.