Regional controllability for infinite-dimensional bilinear systems: approach and simulations

In this study, we consider a regional controllability problem for a class of distributed bilinear systems evolving in a spatial domain Ω. A feedback control is used to steer the system state close to a desired profile at a final time T, only on ω a subregion of the system domain which may be interior or on the boundary of Ω. Our purpose is to prove that an optimal control exists, and characterised as a solution to an optimality system. Numerical algorithm is given and successfully illustrated by simulations.     

二叉树型结构的细胞自动机同构性构造

用状态转移矩阵方程表示加性细胞自动机的状态转移,通过状态转移矩阵及其特征多项式来分析加性细胞自动机的状态转移特性,从而求出其状态转移图.2k-1单元的零边界90线性细胞自动机的状态转移矩阵的秩为2k-2,从而可以确定其状态转移图具有二叉树型结构.同时,根据其状态转移矩阵方程可以求出2k-1单元的零边界90线性细胞自动机对应的22k-1个2k-1单元的零边界90加性细胞自动机具有相同的状态转移结构,即这22k-1个90加性细胞自动机同构.这样可系统构造一簇具有相同二叉树型状态转移结构的细胞自动机.     

A novel matrix approach to observability analysis of finite automata

In this paper, the observability of finite automata (acronym is FA) that contain both deterministic finite automata and non-deterministic finite automata is investigated under the framework of the semi-tensor product of matrices. For both initial state and current state cases, two different observability definitions with or without input information are considered, respectively. First, we show that how the observability problem of initial state of FA can be transformed to the construction problem of an initial state-outputs matrix that presents the relationship between initial state and outputs. Second, a current state-outputs matrix to verify the observability problem of current state is given. When two matrices are obtained, four theorems to verify the observability of initial state and current state are presented, respectively. In particular, compared with the existing approach, the proposed approach not only provides a unified verification for the two types of observability of both initial state and current state but also reduces the computational complexity considerably. An illustrative example is presented to show the theoretical results.     

Synthesis of controllers for target problems of hybrid systems using approximate computation

This paper presents methodologies based on approximate computations for the target control problem of hybrid systems modelled by hybrid automata. The problem of backward reachability and its relation to the control synthesis is studied using approximate analysis techniques. The reachability operators, considering non-linear and linear dynamics with affine disturbances, are under-approximated using state space discretization that involves hyper-cubes. The timing information provided by the backward reachability computation is used in order to design a sub-optimal controller. The computational techniques are applied to the batch evaporator benchmark process which has practical interest.     

Simulation of pedestrian flow through a “T” intersection: A multi-floor field cellular automata approach

There are several ways to study pedestrian dynamics, such as the macroscopic hydrodynamics, molecular dynamics with social force, and cellular automata (CA) with mean field approach. In recent years, the cellular automata approach has received growing interest from researchers. Because this approach is not only to save the computing time but also to reduce the complexity of the problem. In this presentation, we report the study of the conformation of congestion in a “T” intersection by using a cellular automata procedure with multi-floor fields. By using the multi-floor fields, we can mimic the pedestrian flow from several entrances to different exits firstly, and we can simulate the different pedestrian speed by changing the controlling parameter. Our results show, there are some kinds of phase transition in this system.     

Progresses in the analysis of stochastic 2D cellular automata: A study of asynchronous 2D minority

Cellular automata are often used to model systems in physics, social sciences, biology that are inherently asynchronous. Over the past 20 years, studies have demonstrated that the behavior of cellular automata drastically changes under asynchronous updates. Still, the few mathematical analyses of asynchronism focus on 1D probabilistic cellular automata, either on single examples or on specific classes. As for other classic dynamical systems in physics, extending known methods from 1D to 2D systems is a long lasting challenging problem.In this paper, we address the problem of analyzing an apparently simple 2D asynchronous cellular automaton: 2D Minority where each cell, when fired, updates to the minority state of its neighborhood. Our simulations reveal that in spite of its simplicity, the minority rule exhibits a quite complex response to asynchronism. By focusing on the fully asynchronous regime, we are however able to describe completely the asymptotic behavior of this dynamics as long as the initial configuration satisfies some natural constraints. Besides these technical results, we have strong reasons to believe that our techniques relying on defining an energy function from the transition table of the automaton may be extended to the wider class of threshold automata. ²     

A “lifegame” approach to surface modeling and rendering

Conway's Lifegame is a trivial and wellknown application of a more general theory called the theory of cellular automata. Complex systems modeling may be based on the theory of cellular automata, originated by John von Neumann. Our approach is to define simple components that we call analog automata. An analog automaton is a finite state automaton where the state is defined in terms of real numbers representing physical quantities such a position, velocity, mass or color. Deterministic state transition function are applied to these automata using information from the state of neighboring automata. In our case, successive generations in the evolution of these cellular automata are mapped onto polygonal meshes in order to build and texture arbitrary surfaces.     

Reachability and optimal control for linear hybrid automata: a quantifier elimination approach

This paper considers an optimal control problem for linear hybrid automata (LHA). First, we present a controller synthesis algorithm based on reachability analysis. The algorithm computes the maximal initial set from which the controller drives the system to a given target set. It is shown that, using quantifier elimination (QE), an under-approximation of the maximal reachable set can be derived. Next, a weighted time-optimal control problem is solved by transforming it into a constrained optimization problem whose constraints are a set of inequalities with quantifiers. Quantifier elimination (QE) techniques are employed in order to derive the quantifier free inequalities that are shown to be linear. Thus, the optimal cost is obtained using linear programming. For any state belonging to the maximal initial set the optimal switching times and the optimal continuous control inputs are computed. These are used in order to derive a hybrid controller which is optimal with respect to the cost function. Our results are applied to an air traffic management example which is of practical interest.     

Complexity of control on finite automata

We consider control questions for finite automata viewed as input/output systems. In particular, we find estimates of the minimal number of states of an automaton able to control a given automaton. We prove that, on average, feedback closed-loop control automata do not have fewer states than open-loop control automata when the control objective is to steer the controlled automaton to a target state. We compare our approach to other ways of formalizing of formalizing analogous control objectives.     

Optimal stopping and control with two kinds of boundary conditions: application to dynamic routeing in networks

A stochastic optimal stopping and optimal control problem concerning the dynamic routeing of a randomly perturbed flow is considered. Equations for the solution of the optimal stopping and control problem are given. These equations lead to the solution of an elliptic problem with a given condition on a ‘ free boundary’ within a given domain D and a condition given on the boundary ? D of D. An example is given and a numerical study is conducted on it     

Garden of eden configurations for 2-D cellular automata with rule 2460 N

An important problem in cellular automata theory is the reversibility of a cellular automaton which is related to the existence of Garden of Eden configurations in cellular automata. In this paper, we study new local rules for two-dimensional cellular automata over the ternary field Z₃ (the set of integers modulo three) with some of their important characteristics. We obtain necessary and sufficient conditions for the existence of Garden of Eden configurations for two-dimensional ternary cellular automata. Also by making use of the matrix representation of two-dimensional cellular automata, we provide an algorithm to obtain the number of Garden of Eden configurations for two-dimensional cellular automata defined by rule 2460 N. We present an application of the reversible two-dimensional ternary cellular automata to cryptography.     

Regional optimal control of a bilinear wave equation

We study a regional optimal control problem of a bilinear wave equation evolving on a spatial domain Ω with a distributed controls. We search a distributed control which aims to minimise a given functional cost that contains the gap between a desired state and the reached one. This latter is defined only on a subregion ω of Ω. Therefore, we prove existence and we give characterisation of an optimal control. The obtained results lead to an algorithm that we illustrate by simulations.     

MINIMAL VALID AUTOMATA OF SAMPLE SEQUENCES FOR DISCRETE EVENT SYSTEMS

Minimal valid automata (MVA) refer to valid automata models that fit a given input‐output sequence sample from a Mealy machine model. They are minimal in the sense that the number of states in these automata is minimal. Critical to system identification problems of discrete event systems, MVA can be considered as a special case of the minimization problem for incompletely specified sequential machine (ISSM). While the minimization of ISSM in general is an NP‐complete problem, various approaches have been proposed to alleviate computational requirement by taking special structural properties of the ISSM at hand. In essence, MVA is to find the minimal realization of an ISSM where each state only has one subsequent state transition defined. This paper presents an algorithm that divides the minimization process into two phases: first to give a reduced machine for the equivalent sequential machine, and then to minimize the reduced machine into minimal realization solutions. An example with comprehensive coverage on how the associated minimal valid automata are derived is also included.     

The Narrow Escape Problem—A Short Review of Recent Results

The narrow escape problem in diffusion theory, which goes back to Lord Rayleigh, is to calculate the mean first passage time, also called the narrow escape time (NET), of a Brownian particle to a small absorbing window on the otherwise reflecting boundary of a bounded domain. The renewed interest in the NET problem is due to its relevance in molecular biology and biophysics. The small window often represents a small target on a cellular membrane, such as a protein channel, which is a target for ions, a?receptor for neurotransmitter molecules in a neuronal synapse, a?narrow neck in the neuronal spine, which is a target for calcium ions, and so on. The leading order singularity of the Neumann function for a regular domain strongly depends on the geometric properties of the boundary. It can give a smaller contribution than the regular part to the absorption flux through the small window when it is located near a boundary cusp. We review here recent results on the dependence of the absorption flux on the geometric properties of the domain and thus reveal geometrical features that can modulate the flux. This indicates a possible way to code information physiologically.     

Constructing the grid orthogonal and having the given nodal clustering near the boundary of a two-dimensional domain

A problem of constructing a structured countable grid in a two-dimensional domain by mapping a parametric domain with the given quadratic grid onto this two-dimensional domain is considered. The Dirichlet problem is solved for a system of quasi-linear elliptic differential second-order equations to find mapping functions. An additional local mapping that gives the control metric is used to control coordinate lines of the grid. The additional mapping helps obtain the grid with the grid lines of one family orthogonal near the boundary of the domain and having the given clustering of the grid lines of another family towards the boundary of the domain. An example that constructs the grid around the airfoil is given.     

Regional stabilization for infinite-dimensional systems

The purpose of this paper is to discuss an output stabilization problem for linear infinite dimensional systems--regional stabilizability--and consists in studying the asymptotic behaviour of a distributed system on a subregion of its evolution domain. So we give definitions and some properties of this kind of stability. Also, we concentrate on the determination of the control which ensures regional stabilizability on a subregion interior to the system domain, with bounded state on the residual part and minimizing a given cost of performance. The obtained results are illustrated by many examples and simulations.     

Emulating cellular automata in chemical reaction–diffusion networks

Chemical reactions and diffusion can produce a wide variety of static or transient spatial patterns in the concentrations of chemical species. Little is known, however, about what dynamical patterns of concentrations can be reliably programmed into such reaction–diffusion systems. Here we show that given simple, periodic inputs, chemical reactions and diffusion can reliably emulate the dynamics of a deterministic cellular automaton, and can therefore be programmed to produce a wide range of complex, discrete dynamics. We describe a modular reaction–diffusion program that orchestrates each of the fundamental operations of a cellular automaton: storage of cell state, communication between neighboring cells, and calculation of cells’ subsequent states. Starting from a pattern that encodes an automaton’s initial state, the concentration of a “state” species evolves in space and time according to the automaton’s specified rules. To show that the reaction–diffusion program we describe produces the target dynamics, we simulate the reaction–diffusion network for two simple one-dimensional cellular automata using coupled partial differential equations. Reaction–diffusion based cellular automata could potentially be built in vitro using networks of DNA molecules that interact via branch migration processes and could in principle perform universal computation, storing their state as a pattern of molecular concentrations, or deliver spatiotemporal instructions encoded in concentrations to direct the behavior of intelligent materials.     

Multi-vehicle consensus with a time-varying reference state

In this paper, we study the consensus problem in multi-vehicle systems, where the information states of all vehicles approach a time-varying reference state under the condition that only a portion of the vehicles (e.g., the unique team leader) have access to the reference state and the portion of the vehicles might not have a directed path to all of the other vehicles in the team. We first analyze a consensus algorithm with a constant reference state using graph theoretical tools. We then propose consensus algorithms with a time-varying reference state and show necessary and sufficient conditions under which consensus is reached on the time-varying reference state. The time-varying reference state can be an exogenous signal or evolve according to a nonlinear model. These consensus algorithms are also extended to achieve relative state deviations among the vehicles. An application example to multi-vehicle formation control is given as a proof of concept.     

Hybrid Solution Method for Dynamic Programming Equations for MDOF Stochastic Systems

An optimal control problem is considered for a multi-degree-of-freedom (MDOF) system, excited by a white-noise random force. The problem is to minimize the expected response energy by a given time instantT by applying a vector control force with given bounds on magnitudes of its components. This problem is governed by the Hamilton-Jacobi-Bellman, or HJB, partial differential equation. This equation has been studied previously [1] for the case of a single-degree-of-freedom system by developing a hybrid solution. Specifically, an exact analitycal solution has been obtained within a certain outer domain of the phase plane, which provides necessary boundary conditions for numerical solution within a bounded in velocity inner domain, thereby alleviating problem of numerical analysis for an unbounded domain. This hybrid approach is extended here to MDOF systems using common transformation to modal coordinates. The multidimensional HJB equation is solved explicitly for the corresponding outer domain, thereby reducing the problem to a set of numerical solutions within bounded inner domains. Thus, the problem of bounded optimal control is solved completely as long as the necessary modal control forces can be implemented in the actuators. If, however, the control forces can be applied to the original generalized coordinates only, the resulting optimal control law may become unfeasible. The reason is the nonlinearity in maximization operation for modal control forces, which may lead to violation of some constraints after inverse transformation to original coordinates. A semioptimal control law is illustrated for this case, based on projecting boundary points of the domain of the admissible transformed control forces onto boundaries of the domain of the original control forces. Case of a single control force is considered also, and similar solution to the HJB equation is derived.