Robust optimal control of regular languages

This paper presents an algorithm for robust optimal control of regular languages under specified uncertainty bounds on the event cost parameters of the language measure that has been recently reported in literature. The performance index for the proposed robust optimal policy is obtained by combining the measure of the supervised plant language with uncertainty. The performance of a controller is represented by the language measure of the supervised plant and is minimized over the given range of event cost uncertainties. Synthesis of the robust optimal supervisory control policy requires at most n iterations, where n is the number of states of the deterministic finite-state automaton (DFSA) model, generated from the regular language of the unsupervised plant behavior. The computational complexity of the control synthesis method is polynomial in n.     

使用模型检测解决概率布尔网络优化控制

系统生物学期望对复杂生物系统建立一个真实的、可计算的模型,以便于以系统的角度去理解生物系统的演变过程。在系统生物学中,一个重要的主题是通过外部的干预控制发展关于基因调控网络的控制理论,以作为未来基因治疗技术。目前,布尔网络及其扩展的概率布尔网络已经被广泛用于对基因调控网络进行建模。在控制问题的研究中,概率布尔控制网络的状态迁移本质上构成一条有限状态空间的离散时间马尔科夫决策过程。依据马尔科夫决策过程的理论,通过概率模型检测方法解决网络中有限范围优化控制问题和无限范围优化控制问题。针对带有随机干扰且上下文相关的概率布尔控制网络,使用概率模型检测器PRISM对其进行形式化建模,然后将两类优化控制问题描述为相应的时序逻辑公式,最后通过模型检测寻找出最优解。实验结果表明,提出的方法可以有效地用于生物网络的分析和优化控制。     

Signed real measure of regular languages for discrete-event automata

This paper presents the concept and formulation of a signed real measure of regular languages for analysis of discrete-event supervisory control systems. The measure is constructed based upon the principles of language theory and real analysis for quantitative evaluation and comparison of the controlled behaviour for discrete-event automata. The marked (i.e. accepted) states of finite-state automata are classified in different categories such that the event strings terminating at good and bad marked states have positive and negative measures, respectively. In this setting, a controlled language attempts to disable as many bad strings as possible and as few good strings as possible. Different supervisors may achieve this goal in different ways and generate a partially ordered set of controlled languages. The language measure creates a total ordering on the performance of the controlled languages, which provides a precise quantitative comparison of the controlled plant behaviour under different supervisors. Total variation of the language measure serves as a metric for the space of sublanguages of the regular language.     

On the history of diagnosability and opacity in discrete event systems

This paper presents historical remarks on key projects and papers that led to the development of a theory of event diagnosis for discrete event systems modeled by finite-state automata or Petri nets in the 1990s. The goal in event diagnosis is to develop algorithmic procedures for deducing the occurrence of unobservable events, based on a formal model of the system and on-line observations of its behavior. It also presents historical remarks on the early works on the property of opacity, which occurred about ten years later. Opacity can be seen as a strong version of lack of diagnosability and it has been used to capture security and privacy requirements. Finally, diagnosability is connected with the property of observability that arises in supervisory control. This paper is part of set of papers that review the emergence of discrete event systems as an area of research in control engineering.     

Protocol conversion

The problem of achieving communication between two processes across a network or an internetwork is considered. The notion of logical connectivity between processes in a protocol is formalized. The problem of constructing a protocol converter to achieve interoperability between processes that implement different protocols is addressed. A formal model is presented, based on the theory of protocol projection, for reasoning about the semantics of different protocols and conversions between them. Two kinds of converters are presented: memoryless converters and finite-state converters. The construction of some finite-state converters is illustrated, and examples are given     

Optimal control of noisy finite-state Markov processes

This paper treats the problem of optimal control of finite-state Markov processes observed in noise. Two types of noisy observations are considered: additive white Gaussian noise and jump-type observations. Sufficient conditions for the optimality of a control law are obtained similar to the stochastic Hamilton-Jacobi equation for perfectly observed Markov processes. An illustrative example concludes the paper.     

Jump linear quadratic Gaussian control in continuous time

The optimal quadratic control of continuous-time linear systems that possess randomly jumping parameters which can be described by finite-state Markov processes is addressed. The systems are also subject to Gaussian input and measurement noise. The optimal solution for the jump linear-quadratic-Gaussian (JLQC) problem is given. This solution is based on a separation theorem. The optimal state estimator is sample-path dependent. If the plant parameters are constant in each value of the underlying jumping process, then the controller portion of the compensator converges to a time-invariant control law. However, the filter portion of the optimal infinite time horizon JLQC compensator is not time invariant. Thus, a suboptimal filter which does converge to a steady-state solution (under certain conditions) is derived, and a time-invariant compensator is obtained     

Mixed risk-neutral/minimax control of discrete-time, finite-stateMarkov decision processes

Addresses the control design problem for discrete-time, finite-state Markov decision processes, when both risk-neutral and minimax objectives are of interest. We introduce the mixed risk-neutral/minimax objective and utilize results from risk-neutral and minimax control to derive an information state process and dynamic programming equations for the value function. We synthesize optimal control laws both on the finite and the infinite horizons. We study the effectiveness of both the mixed risk-neutral/minimax family and the risk-sensitive family of controllers as tools to tradeoff risk-neutral and minimax objectives. We conclude that the mixed risk-neutral/minimax family is more effective, at the cost of increased controller complexity     

Finitely recursive process models for discrete event systems

A class of discrete-event models called finitely recursive processes (FRP) is introduced. These models are motivated by problems in supervisory control, while some of the formal structure is based on C.A.R. Hoare's (1985) communicating sequential processes. Although only preliminary work is presented, it is believed that for many problems it offers a formalism that is superior to that of finite-state machines recently introduced in control theory. Simple examples illustrate the calculus of operators for FRPs. A more complex exercise is worked out to show how the formalism is used to construct a scheme for handling connections in a data network. This preliminary work needs to be extended in several directions, especially in directions that can assist implementation of real controllers based on the FRP formalism. Some specific suggestions towards this end are made     

Robustness of policies in constrained Markov decision processes

We consider the optimization of finite-state, finite-action Markov decision processes (MDPs), under constraints. Cost and constraints are discounted. We introduce a new method for investigating the continuity, and a certain type of robustness, of the optimal cost and the optimal policy under changes in the constraints. This method is also applicable for other cost criteria such as finite horizon and infinite horizon average cost.     

A relational algebraic approach to protocol verification

Communications protocols are usually modeled by a pair of finite-state machines that generate the interaction between processes. Protocol verification is a procedure to validate the logical correctness of these interaction sequences and to detect potential design errors. A relational approach is proposed to represent a finite-state machine as a transition table. On this basis, the well-established theory of relational databases can be utilized to derive the global-state transitions of the system. Furthermore, logical errors of a protocol such as deadlocks, incomplete specifications and nonexecutable interactions can be formulated in terms of relational algebra. This approach has been implemented on the INGRES database system and applied to the verification of several protocols     

On finite-state approximants for probabilistic computation tree logic

We generalize the familiar semantics for probabilistic computation tree logic from finite-state to infinite-state labelled Markov chains such that formulas are interpreted as measurable sets. Then we show how to synthesize finite-state abstractions which are sound for full probabilistic computation tree logic and in which measures are approximated by monotone set functions. This synthesis of sound finite-state approximants also applies to finite-state systems and is a probabilistic analogue of predicate abstraction. Sufficient and always realizable conditions are identified for obtaining optimal such abstractions for probabilistic propositional modal logic.     

Simulation-based optimization of Markov reward processes

This paper proposes a simulation-based algorithm for optimizing the average reward in a finite-state Markov reward process that depends on a set of parameters. As a special case, the method applies to Markov decision processes where optimization takes place within a parametrized set of policies. The algorithm relies on the regenerative structure of finite-state Markov processes, involves the simulation of a single sample path, and can be implemented online. A convergence result (with probability 1) is provided     

Ergodic control of partially observed Markov chains

The ergodic or long-run average cost control problem for a partially observed finite-state Markov chain is studied via the associated fully observed separated control problem for the nonlinear filter. Dynamic programming equations for the latter are derived, leading to existence and characterization of optimal stationary policies.     

Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks

Supervisory control theory is a well-established theoretical framework for feedback control of discrete event systems whose behaviours are described by automata and formal languages. In this article, we propose a formal constructive method for optimal fault-tolerant scheduling of real-time multiprocessor systems based on supervisory control theory. In particular, we consider a fault-tolerant and schedulable language which is an achievable set of event sequences meeting given deadlines of accepted aperiodic tasks in the presence of processor faults. Such a language eventually provides information on whether a scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. Moreover, we present a systematic way of computing a largest fault-tolerant and schedulable language which is optimal in that it contains all achievable deadline-meeting sequences.     

An optimal effective controller for discrete event systems

An approach to the online synthesis of an optimal effective controller for discrete event systems is presented. The optimal effective controller can achieve the prescribed (cumulative) effectiveness measure while minimizing the total cost incurred for the execution of events. This approach is constructed over a generalized control framework for automata‐based discrete event systems, which allows event enforcement in addition to the (original) event disablement/enablement as the control mechanism. The optimal effective control policy generated by this approach is proved to be the least restrictive among all the possible optimal effective control policies for the given online expansion tree of the system behavior. Copyright © 2008 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Discrete approximation and supervisory control of continuoussystems

Addresses the following hybrid control problem: a continuous plant (its state evolving in Euclidean space) is to be controlled via symbolic output feedback-both measurement and control signal “live” on finite sets of symbols. We adopt the following approach: the hybrid problem is first translated into a purely discrete problem by approximating the continuous plant model by a (nondeterministic) finite-state machine. By taking into account past measurement and control symbols, approximation accuracy can be improved and adjusted to the specification requirements. Supervisory control theory for discrete-event systems (DES) is then applied to find the optimal controller which enforces the specifications. As the behavior of the approximating automaton is guaranteed to contain the behavior of the underlying continuous plant model, the controller also forces the latter to obey the specifications     

On optimal control of a class of partially observed discrete event systems

We are interested in a new class of optimal control problems for discrete event systems. We adopt the formalism of supervisory control theory (Proc. IEEE 77(1) (1989) 81) and model the system as a finite state machine (FSM). Our control problem is characterized by the presence of uncontrollable as well as unobservable events, the notion of occurrence and control costs for events and a worst-case objective function. We first derive an observer for the partially unobservable FSM, which allows us to construct an approximation of the unobservable trajectory costs. We then define the performance measure on this observer rather than on the original FSM itself. We then use the algorithm presented in Sengupta and Lafortune (SIAM J. Control Optim. 36(2) (1998)) to synthesize an optimal submachine of the C-observer. This submachine leads to the desired supervisor for the system.     

Simulation Preorder over Simple Process Algebras

We consider the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones. First, we describe a general method how to utilize the decidability of bisimulation problems to solve (certain instances of) the corresponding simulation problems. For certain process classes, the method allows us to design effective reductions of simulation problems to their bisimulation counterparts and some new decidability results for simulation have already been obtained in this way. Then we establish the decidability border for the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones w.r.t. the hierarchy of process rewrite systems. In particular, we show that simulation preorder (in both directions) and simulation equivalence are decidable in EXPTIME between pushdown processes and finite-state ones. On the other hand, simulation preorder is undecidable between PA and finite-state processes in both directions. These results also hold for those PA and finite-state processes which are deterministic and normed, and thus immediately extend to trace preorder. Regularity (finiteness) w.r.t. simulation and trace equivalence is also shown to be undecidable for PA. Finally, we prove that simulation preorder (in both directions) and simulation equivalence are intractable between all classes of infinite-state systems (in the hierarchy of process rewrite systems) and finite-state ones. This result is obtained by showing that the problem whether a BPA (or BPP) process simulates a finite-state one is PSPACE-hard and the other direction is co -hard; consequently, simulation equivalence between BPA (or BPP) and finite-state processes is also co -hard.     

Robust sampled-data control for Markovian jump linear systems

In this paper, we consider the problem of robust control for uncertain sampled-data systems that possess random jumping parameters which is described by a finite-state Markov process. The conditions for the existence of a stabilizing control and optimal control for the underlying systems are obtained. The desired controllers are designed which are in terms of matrix inequalities. Finally, a numerical example is given to show the potential of the proposed techniques.