Modular supervisory control of discrete-event systems

A modular approach to the supervisory control of a class of discrete-event systems is formulated, and illustrated with an example. Discrete-event systems are modeled by automata together with a mechanism for enabling and disabling a subset of state transitions. The basic problem of interest is to ensure by appropriate supervision that the closed loop behavior of the system lies within a given legal behavior. Assuming this behavior can be decomposed into an intersection of component restrictions, we determine conditions under which it is possible to synthesize the appropriate control in a modular fashion. The work of this author was supported by NSERC (Canada) under Grant No. A-7399. The work of this author was supported by the National Science Foundation through Grant No. ECS-8504584.     

Adaptive neuro-genetic control of chaos applied to the attitude control problem

Conventional adaptive control techniques have, for the most part, been based on methods for linear or weakly non-linear systems. More recently, neural network and genetic algorithm controllers have started to be applied to complex, non-linear dynamic systems. The control of chaotic dynamic systems poses a series of especially challenging problems. In this paper, an adaptive control architecture using neural networks and genetic algorithms is applied to a complex, highly nonlinear, chaotic dynamic system: the adaptive attitude control problem (for a satellite), in the presence of large, external forces (which left to themselves led the system into a chaotic motion). In contrast to the OGY method, which uses small control adjustments to stabilize a chaotic system in an otherwise unstable but natural periodic orbit of the system, the neuro-genetic controller may use large control adjustments and proves capable of effectively attaining any specified system state, with no a prioriknowledge of the dynamics, even in the presence of significant noise.This work was partly supported by SERC grant 90800355.     

Boundary control of stochastic reaction‐diffusion systems with Markovian switching

This article focuses on the boundary control of stochastic Markovian reaction‐diffusion systems (SMRDSs). Both the cases of completely known and partially unknown transition probabilities are taken into account. By using the Lyapunov functional method, a sufficient condition is obtained under the designed boundary controllers to guarantee the asymptotic mean square stability for SMRDSs with completely known transition probabilities. For the case of partially unknown transition probabilities, we introduce free‐connection weighting matrices to handle the boundary control problem. When external disturbance enters the system, a sufficient criterion of H‐infinity boundary control is developed. Furthermore, robust stabilization is investigated for parametric uncertain SMRDSs in both cases. Two examples are presented to demonstrate the efficiency of the proposed approaches.     

Minimizing channel density in standard cell layout

The problem of routing multiple rows of cells with linear nets is studied. In keeping with various local routing strategies, two separate optimization criteria are considered: maximum channel density and total channel density. In each case the problem is shown to be NP-complete for a fixed number of rows. In addition, for the total density problem, a polynomial-time heuristic is presented and is shown to produce total densities within 50% of the optimal.J. R. S. Blair and E. L. Lloyd were partially supported by the National Science Foundation under Grant MCS-8103713, S. Kapoor was partially supported by the National Science Foundation under Grant MCS-8117364, and K. J. Supowit was partially supported by the National Science Foundation under Grant DMC-8451214 and by a grant from IBM.     

Unsupervised neural network learning procedures for feature extraction and classification

In this article, we review unsupervised neural network learning procedures which can be applied to the task of preprocessing raw data to extract useful features for subsequent classification. The learning algorithms reviewed here are grouped into three sections: information-preserving methods, density estimation methods, and feature extraction methods. Each of these major sections concludes with a discussion of successful applications of the methods to real-world problems.The first author is supported by research grants from the James S. McDonnell Foundation (grant #93–95) and the Natural Sciences and Engineering Research Council of Canada. For part of this work, the second author was supported by a Temporary Lectureship from the Academic Initiative of the University of London, and by a grant (GR/J38987) from the Science and Engineering Research Council (SERC) of the UK.     

基于强化学习的JLQ模型的直接自适应最优控制

研究离散时间跳变线性二次(JLQ)模型的直接自适应最优控制问题.将强化学习的理论和方法应用于JLQ模型,设计基于Q函数的策略迭代算法,以优化系统性能.在系统参数以及模态跳变概率未知的情况下,Q函数对应的参数矩阵,可通过观察给定策略下系统行为,应用递归最小二乘算法在线估计.基于此参数矩阵,可构造出新的策略使得系统性能更优.该算法可收敛到最优策略.     

Routing of multicast audio/video streams in reconfigurable WDM optical networks

Due to its low attenuation, fiber has become the medium of choice for point-to-point links. Using Wavelength-Division Multiplexing (WDM), many independent channels can be created in the same fiber. A network node equipped with a tunable optical transmitter can select any of these channels for sending data. An optical interconnection combines the signal from the various transmitters in the network, and makes it available to the optical receivers, which may also be tunable. By properly tuning transmitters and/or receivers, point-to-point links can be dynamically created and destroyed. Therefore, in a WDM network, the routing algorithm has an additional degree of freedom compared to traditional networks: it can modify the netowrk topology to create the routes. In this paper, we consider the problem of routing multicast audio/video streams in WDM networks and propose heuristic algorithms to solve it. The performance of these heuristics is evaluated in a number of scenarios, with a realistic traffic model, and from the evaluation we derive guidelines for usage of the proposed algorithms.This work was supported in part by NASA under grant NAG2-842, by the National Science Foundation under grant NCR-9016032 and by Pacific Bell. Ciro Noronha was supported by a graduate scholarship from FAPESP from Sept/89 to Aug/93 under grant 89/1658.     

Partially‐observable stochastic hybrid systems (poshss) state estimation and optimal control

This paper discusses the state estimation and optimal control problem of a class of partially‐observable stochastic hybrid systems (POSHS). The POSHS has interacting continuous and discrete dynamics with uncertainties. The continuous dynamics are given by a Markov‐jump linear system and the discrete dynamics are defined by a Markov chain whose transition probabilities are dependent on the continuous state via guard conditions. The only information available to the controller are noisy measurements of the continuous state. To solve the optimal control problem, a separable control scheme is applied: the controller estimates the continuous and discrete states of the POSHS using noisy measurements and computes the optimal control input from the state estimates. Since computing both optimal state estimates and optimal control inputs are intractable, this paper proposes computationally efficient algorithms to solve this problem numerically. The proposed hybrid estimation algorithm is able to handle state‐dependent Markov transitions and compute Gaussian‐ mixture distributions as the state estimates. With the computed state estimates, a reinforcement learning algorithm defined on a function space is proposed. This approach is based on Monte Carlo sampling and integration on a function space containing all the probability distributions of the hybrid state estimates. Finally, the proposed algorithm is tested via numerical simulations.     

Optimal Control of Switching Surfaces in Hybrid Dynamical Systems

This paper concerns an optimal control problem defined on a class of switched-mode hybrid dynamical systems. The system's mode is changed (switched) whenever the state variable crosses a certain surface in the state space, henceforth called a switching surface. These switching surfaces are parameterized by finite-dimensional vectors called the switching parameters. The optimal control problem is to minimize a cost functional, defined on the state trajectory, as a function of the switching parameters. The paper derives the gradient of the cost functional in a costate-based formula that reflects the special structure of hybrid systems. It then uses the formula in a gradient-descent algorithm for solving an obstacle-avoidance problem in robotics. The work of Boccadoro has been partially supported by MIUR under Grant PRIN 2003090090. The work of Wardi has been partly supported by a grant from the Georgia Tech Manufacturing Research Center. The work of Egerstedt has been partly supported by the National Science Foundation under Grant \# 0237971 ECS NSF-CAREER, and by a grant from the Georgia Tech Manufacturing Research Center.     

Dynamic routing and admission control for virtual circuit networks

The dynamic joint routing and admission control problem in multiple class multiple source-destination virtual circuit networks is considered. A nonlinear dynamic queueing model for virtual circuit networks that considers the dynamic interaction among the virtual circuit and packet processes is introduced. Then a multi-objective cost function of rejecting and maintaining virtual circuits, as well as of delaying and servicing packets is defined. The combined problem is formulated as an optimal control problem. Necessary optimality conditions are provided by Pontryagin's maximum principle. Sufficient optimality conditions based on the convexity of the Hamiltonian function are also given. For the finite horizon, the optimal controls can be found after numerically solving a Two-Point Boundary-Value Problem. For the longrun stationary equilibrium, the state-dependent routing and admission controls are derived.This work was supported by the National Science Foundation under Grant DMC-8452002 together with matching funds from AT&T Information Systems.     

Recurrent neural-network training by a learning automaton approachfor trajectory learning and control system design

We present a training approach using concepts from the theory of stochastic learning automata that eliminates the need for computation of gradients. This approach also offers the flexibility of tailoring a number of specific training algorithms based on the selection of linear and nonlinear reinforcement rules for updating automaton action probabilities. The training efficiency is demonstrated by application to two complex temporal learning scenarios, viz, learning of time-dependent continuous trajectories and feedback controller designs for continuous dynamical plants. For the first problem, it is shown that training algorithms can be tailored following the present approach for a recurrent neural net to learn to generate a benchmark circular trajectory more accurately than possible with existing gradient-based training procedures. For the second problem, it is shown that recurrent neural-network-based feedback controllers can be trained for different control objectives.     

Joint routing, scheduling, and power control for multichannel wireless sensor networks with physical interference

Reliability and real-time requirements bring new challenges to the energy-constrained wireless sensor networks, especially to the industrial wireless sensor networks. Meanwhile, the capacity of wireless sensor networks can be substantially increased by operating on multiple nonoverlapping channels. In this context, new routing, scheduling, and power control algorithms are required to achieve reliable and real-time communications and to fully utilize the increased bandwidth in multichannel wireless sensor networks. In this paper, we develop a distributed and online algorithm that jointly solves multipath routing, link scheduling, and power control problem, which can adapt automatically to the changes in the network topology and offered load. We particularly focus on finding the resource allocation that realizes trade-off among energy consumption, end-to-end delay, and network throughput for multichannel networks with physical interference model. Our algorithm jointly considers 1) delay and energy-aware power control for optimal transmission radius and rate with physical interference model, 2) throughput efficient multipath routing based on the given optimal transmission rate between the given source-destination pairs, and 3) reliable-aware and throughput efficient multichannel maximal link scheduling for time slots and channels based on the designated paths, and the new physical interference model that is updated by the optimal transmission radius. By proving and simulation, we show that our algorithm is provably efficient compared with the optimal centralized and offline algorithm and other comparable algorithms.     

结构不确定离散系统的最优非脆弱保成本控制

讨论了一类不确定线性离散系统的最优非脆弱保成本控制问题.考虑的系统和状态反馈控制器均具有时变的结构化的不确定性.基于线性矩阵不等式的方法,给出了存在和设计非脆弱保成本控制律的一个充分条件,以及在使二次成本函数上界最小意义下,最优非脆弱保成本控制律的凸优化设计方法.并用数值例子说明该方法降低了成本函数上界的保守性.     

Sailboat navigation control system based on spiking neural networks

In this paper, we presented the development of a navigation control system for a sailboat based on spiking neural networks (SNN). Our inspiration for this choice of network lies in their potential to achieve fast and low-energy computing on specialized hardware. To train our system, we use the modulated spike time-dependent plasticity reinforcement learning rule and a simulation environment based on the BindsNET library and USVSim simulator. Our objective was to develop a spiking neural network-based control systems that can learn policies allowing sailboats to navigate between two points by following a straight line or performing tacking and gybing strategies, depending on the sailing scenario conditions. We presented the mathematical definition of the problem, the operation scheme of the simulation environment, the spiking neural network controllers, and the control strategy used. As a result, we obtained 425 SNN-based controllers that completed the proposed navigation task, indicating that the simulation environment and the implemented control strategy work effectively. Finally, we compare the behavior of our best controller with other algorithms and present some possible strategies to improve its performance.     

输出重定义下的非线性非最小相位系统迭代学习控制

讨论非线性非最小相位系统实现完全跟踪的迭代学习控制方法, 适于在有限作业区间上重复运行的受控系统. 在控制器设计时, 通过输出重定义以使非最小相位系统的零动态变成渐近稳定特性. 分别采用部分限幅和完全限幅两种学习算法设计控制器, 理论分析表明两种算法能够保证学习系统中所有变量的有界性和跟踪误差在整个作业区间上渐近收敛于零. 数值仿真验证了两种迭代学习控制系统的跟踪性能.     

Learning control of finite Markov chains with unknown transition probabilities

For a Markovian decision problem in which the transition probabilities are unknown, two learning algorithms are devised from the viewpoint of asymptotic optimality. Each time the algorithms select decisions to be used on the basis of not only the estimates of the unknown probabilities but also uncertainty of them. It is shown that the algorithms are asymptotically optimal in the sense that the probability of selecting an optimal policy converges to unity.     

Recurrent learning algorithms for designing optimal controllers ofcontinuous systems

Proposes a recurrent learning algorithm for designing the controllers of continuous dynamical systems in optimal control problems. The controllers are in the form of unfolded recurrent neural nets embedded with physical laws from classical control techniques. The learning algorithm is characterized by a double forward-recurrent-loops structure for solving both temporal recurrent and structure recurrent problems. The first problem results from the nature of general optimal control problems, where the objective functions are often related to (evaluated at) some specific time steps or system states only, causing missing learning signals at some steps or states. The second problem is due to the high-order discretization of continuous systems by the Runge-Kutta method that we perform to increase accuracy. This discretization transforms the system into several identical interconnected subnetworks, like a recurrent neural net expanded in the time axis. Two recurrent learning algorithms with different convergence properties are derived; first- and second-order learning algorithms. Their computations are local and performed efficiently as net signal propagation. We also propose two new nonlinear control structures for the 2D guidance problem and the optimal PI control problem. Under the training of the recurrent learning algorithms, these controllers can be easily tuned to be suboptimal for given objective functions. Extensive computer simulations show the controllers' optimization and generalization abilities     

安全强化学习算法及其在CPS智能控制中的应用

信息物理系统(cyber-physicalsystem,CPS)的安全控制器设计是一个热门研究方向,现有基于形式化方法的安全控制器设计存在过度依赖模型、可扩展性差等问题.基于深度强化学习的智能控制可处理高维非线性复杂系统和不确定性系统,正成为非常有前景的CPS控制技术,但是缺乏对安全性的保障.针对强化学习控制在安全性方面的不足,围绕一个工业油泵控制系统典型案例,开展安全强化学习算法和智能控制应用研究.首先,形式化了工业油泵控制的安全强化学习问题,搭建了工业油泵仿真环境;随后,通过设计输出层结构和激活函数,构造了神经网络形式的油泵控制器,使得油泵开关时间的线性不等式约束得到满足;最后,为了更好地权衡安全性和最优性控制目标,基于增广拉格朗日乘子法设计实现了新型安全强化学习算法.在工业油泵案例上的对比实验表明,该算法生成的控制器在安全性和最优性上均超越了现有同类算法.在进一步评估中,所生成神经网络控制器以90%的概率通过了严格形式化验证;同时,与理论最优控制器相比实现了低至2%的最优目标值损失.所提方法有望推广至更多应用场景,实例研究的方案有望为安全智能控制和形式化验证领域其他学者提供借鉴.     

Two-loop reinforcement learning algorithm for finite-horizon optimal control of continuous-time affine nonlinear systems

This article proposes three novel time-varying policy iteration algorithms for finite-horizon optimal control problem of continuous-time affine nonlinear systems. We first propose a model-based time-varying policy iteration algorithm. The method considers time-varying solutions to the Hamiltonian–Jacobi–Bellman equation for finite-horizon optimal control. Based on this algorithm, value function approximation is applied to the Bellman equation by establishing neural networks with time-varying weights. A novel update law for time-varying weights is put forward based on the idea of iterative learning control, which obtains optimal solutions more efficiently compared to previous works. Considering that system models may be unknown in real applications, we propose a partially model-free time-varying policy iteration algorithm that applies integral reinforcement learning to acquiring the time-varying value function. Moreover, analysis of convergence, stability, and optimality is provided for every algorithm. Finally, simulations for different cases are given to verify the convenience and effectiveness of the proposed algorithms.     

On computing minimal models

This paper addresses the problem of computing the minimal models of a given CNF propositional theory. We present two groups of algorithms. Algorithms in the first group are efficient when the theory is almost Horn, that is, when there are few non-Horn clauses and/or when the set of all literals that appear positive in any non-Horn clause is small. Algorithms in the other group are efficient when the theory can be represented as an acyclic network of low-arity relations. Our algorithms suggest several characterizations of tractable subsets for the problem of finding minimal models.This work was partially supported by an IBM graduate fellowship to the first author, by NSF grants IRI-9157636 and IRI-9200918, by Air Force Office of Scientific Research grant AFOSR 900136, by a grant from Xerox Palo Alto research center, and by Toshiba of America. Part of this work was done while the first author was a graduate student at the Cognitive Systems Laboratory, Computer Science Department, University of California, Los Angeles, California, USA.