G-networks with resets

Gelenbe networks (G-networks) are product form queuing networks which, in addition to ordinary customers, contain unusual entities such as “negative customers” which eliminate normal customers and “triggers” which move other customers from some queue to another. These models have generated much interest in the literature since the early 1990s. The present paper discusses a novel model for a reliable system composed of N unreliable systems, which can hinder or enhance each other’s reliability. Each of the N systems also tests other systems at random; it is able to reset another system if it is itself in working condition and discovers that the other system has failed, so that the global reliability of the system is enhanced. This paper shows how an extension of G-networks that includes novel “reset” customers can be used to model this behavior. We then show that a general G-network model with resets has product form, and prove existence and uniqueness of its solution.     

Continuity controlled hybrid automata

We investigate the connections between the process algebra for hybrid systems of Bergstra and Middelburg and the formalism of hybrid automata of Henzinger et al. We give interpretations of hybrid automata in the process algebra for hybrid systems and compare them with the standard interpretation of hybrid automata as timed transition systems. We also relate the synchronized product operator on hybrid automata to the parallel composition operator of the process algebra. It turns out that the formalism of hybrid automata matches a fragment of the process algebra for hybrid systems closely. We present an adaptation of the formalism of hybrid automata that yields an exact match.     

Inclusion dynamics hybrid automata

Hybrid systems are dynamical systems with the ability to describe mixed discrete-continuous evolution of a wide range of systems. Consequently, at first glance, hybrid systems appear powerful but recalcitrant, neither yielding to analysis and reasoning through a purely continuous-time modeling as with systems of differential equations, nor open to inferential processes commonly used for discrete state-transition systems such as finite state automata. A convenient and popular model, called hybrid automata, was introduced to model them and has spurred much interest on its tractability as a tool for inference and model checking in a general setting. Intuitively, a hybrid automaton is simply a “finite-state” automaton with each state augmented by continuous variables, which evolve according to a set of well-defined continuous laws, each specified separately for each state. This article investigates both the notion of hybrid automaton and the model checking problem over such a structure. In particular, it relates first-order theories and analysis results on multivalued maps and reduces the bounded reachability problem for hybrid automata whose continuous laws are expressed by inclusions (x′f(x,t)) to a decidability problem for first-order formulæ over the reals. Furthermore, the paper introduces a class of hybrid automata for which the reachability problem can be decided and shows that the problem of deciding whether a hybrid automaton belongs to this class can be again decided using first-order formulæ over the reals. Despite the fact that the bisimulation quotient for this class of hybrid automata can be infinite, we show that our techniques permit effective model checking for a nontrivial fragment of CTL.     

Infinite games on finitely coloured graphs with applications to automata on infinite trees

We examine a class of infinite two-person games on finitely coloured graphs. The main aim is to construct finite memory winning strategies for both players. This problem is motivated by applications to finite automata on infinite trees. A special attention is given to the exact amount of memory needed by the players for their winning strategies. Based on a previous work of Gurevich and Harrington and on subsequent improvements of McNaughton we propose a unique framework that allows to reestablish and to improve various results concerning memoryless strategies due to Emerson and Jutla, Mostowski, Klarlund.     

Weighted finite automata over strong bimonoids

We investigate weighted finite automata over strings and strong bimonoids. Such algebraic structures satisfy the same laws as semirings except that no distributivity laws need to hold. We define two different behaviors and prove precise characterizations for them if the underlying strong bimonoid satisfies local finiteness conditions. Moreover, we show that in this case the given weighted automata can be determinized.     

Dynamical properties of hybrid automata

Hybrid automata provide a language for modeling and analyzing digital and analogue computations in real-time systems. Hybrid automata are studied here from a dynamical systems perspective. Necessary and sufficient conditions for existence and uniqueness of solutions are derived and a class of hybrid automata whose solutions depend continuously on the initial state is characterized. The results on existence, uniqueness, and continuity serve as a starting point for stability analysis. Lyapunov's theorem on stability via linearization and LaSalle's invariance principle are generalized to hybrid automata.     

Time-optimal control for discrete-time hybrid automata

In this paper, the problem of time-optimal control for hybrid systems with discrete-time dynamics is considered. The hybrid controller steers all trajectories starting from a maximal set to a given target set in minimum time. We derive an algorithm that computes this maximal winning set. Also, algorithms for the computation of level sets associated with the value function rather than the value function itself are presented. We show that by solving the reachability problem for the discrete time hybrid automata we obtain the time optimal solution as well. The control synthesis is subject to hard constraints on both control inputs and states. For linear discrete-time dynamics, linear programming and quantifier elimination techniques are employed for the backward reachability analysis. Emphasis is given on the computation of operators for non-convex sets using an extended convex hull approach. A two-tank example is considered in order to demonstrate the techniques of the paper.     

Specifications for decidable hybrid games

We introduce STORMED hybrid games (SHG), a generalization of STORMED hybrid systems, Vladimerou et al. (2008) [33], which have natural specifications that allow rich continuous dynamics and various decidable properties. We solve the control problem for SHG using a reduction to bisimulation on finite game graphs. This generalizes to a greater family of games, which includes o-minimal hybrid games, Bouyer et al. (2006) [6]. We also solve the optimal-cost reachability problem for Weighted SHG and prove decidability of WCTL for Weighted STORMED hybrid systems.     

Multiscale topology optimization for non-uniform microstructures with hybrid cellular automata

Based on hybrid cellular automata (HCA), we present a two-scale optimization model for heterogeneous structures with non-uniform porous cells at the micros     

Determinization of weighted finite automata over strong bimonoids

We consider weighted finite automata over strong bimonoids, where these weight structures can be considered as semirings which might lack distributivity. Then, in general, the well-known run semantics, initial algebra semantics, and transition semantics of an automaton are different. We prove an algebraic characterization for the initial algebra semantics in terms of stable finitely generated submonoids. Moreover, for a given weighted finite automaton we construct the Nerode automaton and Myhill automaton, both being crisp-deterministic, which are equivalent to the original automaton with respect to the initial algebra semantics, respectively, the transition semantics. We prove necessary and sufficient conditions under which the Nerode automaton and the Myhill automaton are finite, and we provide efficient algorithms for their construction. Also, for a given weighted finite automaton, we show sufficient conditions under which a given weighted finite automaton can be determinized preserving its run semantics.     

Design of materials using hybrid cellular automata

This paper presents a new approach for the topological design of materials with extreme properties. The method is based on hybrid cellular automaton (HCA), which is an implicit optimization technique that uses local rules to update design variables iteratively until meeting the described optimality conditions. By means of an energy-based homogenization approach, the effective properties of the considered material are calculated in terms of element mutual energies. By this method, no sensitivity information is required to find the optimal topology for the considered design objectives: bulk modulus, shear modulus, and negative Poisson’s ratio. The proposed method is validated by a series of numerical examples.     

Using hybrid automata for set-membership state estimation with uncertain nonlinear continuous-time systems

This paper deals with set-membership state estimation for continuous-time systems from discrete-time measurements, in the unknown but bounded error framework. The classical predictor–corrector approach to state estimation uses interval Taylor methods for solving the prediction phase, which are known to have poor performance in presence of large model or input uncertainty. In this paper, we show how to derive more efficient predictors by using a nonlinear hybridization method which builds hybrid automata to characterize the boundaries of reachable sets. The derived continuous–discrete set-membership predictor–corrector estimator is then tested with simulated data from a bioreactor. Our method is compared to classical continuous-time interval observers and is shown to have promising performance.     

Specification and synthesis of hybrid automata for physics-based animation

Physics-based animation programs can often be modeled in terms of hybrid automata. A hybrid automaton includes both discrete and continuous dynamical variables. The discrete variables define the automaton’s modes of behavior. The continuous variables are governed by mode-dependent differential equations. This paper describes a system for specifying and automatically synthesizing physics-based animation programs based on hybrid automata. The system presents a program developer with a family of parameterized specification schemata. Each schema describes a pattern of behavior as a hybrid automaton passes through a sequence of modes. The developer specifies a program by selecting one or more schemata and supplying application-specific instantiation parameters for each of them. Each schema is associated with a set of axioms in a logic of hybrid automata. The axioms serve to document the semantics of the specification schema. Each schema is also associated with a set of implementation rules. The rules synthesize program components implementing the specification in a general physics-based animation architecture. The system allows animation programs to be developed and tested in an incremental manner. The system itself can be extended to incorporate additional schemata for specifying new patterns of behavior, along with new sets of axioms and implementation rules. It has been implemented and tested on over a dozen examples. We believe this research is a significant step toward a specification and synthesis system that is flexible enough to handle a wide variety of animation programs, yet restricted enough to permit programs to be synthesized automatically.     

Convergence analysis of hybrid cellular automata for topology optimization

The hybrid cellular automaton (HCA) algorithm was inspired by the structural adaptation of bones to their ever changing mechanical environment. This methodology has been shown to be an effective topology synthesis tool. In previous work, it has been observed that the convergence of the HCA methodology is affected by parameters of the algorithm. As a result, questions have been raised regarding the conditions by which HCA converges to an optimal design. The objective of this investigation is to examine the conditions that guarantee convergence to a Karush-Kuhn-Tucker (KKT) point. In this paper, it is shown that the HCA algorithm is a fixed point iterative scheme and the previously reported KKT optimality conditions are corrected. To demonstrate the convergence properties of the HCA algorithm, a simple cantilevered beam example is utilized. Plots of the spectral radius for projections of the design space are used to show regions of guaranteed convergence.     

Benchmarking hybrid algorithms for distributed constraint optimisation games

In this paper, we consider algorithms for distributed constraint optimisation problems (DCOPs). Using a potential game characterisation of DCOPs, we decompose eight DCOP algorithms, taken from the game theory and computer science literatures, into their salient components. We then use these components to construct three novel hybrid algorithms. Finally, we empirical evaluate all eleven algorithms, in terms of solution quality, timeliness and communication resources used, in a series of graph colouring experiments. Our experimental results show the existence of several performance trade-offs (such as quick convergence to a solution, but with a cost of high communication needs), which may be exploited by a system designer to tailor a DCOP algorithm to suit their mix of requirements.     

Engineering constraint solvers for automatic analysis of probabilistic hybrid automata

In this article, we recall different approaches to the constraint-based, symbolic analysis of hybrid discrete-continuous systems and combine them to a technology able to address hybrid systems exhibiting both non-deterministic and probabilistic behavior akin to infinite-state Markov decision processes. To enable mechanized analysis of such systems, we extend the reasoning power of arithmetic satisfiability-modulo-theories (SMT) solving by, first, reasoning over ordinary differential equations (ODEs) and, second, a comprehensive treatment of randomized (also known as stochastic) quantification over discrete variables as well as existential quantification over both discrete and continuous variables within the mixed Boolean-arithmetic constraint system. This provides the technological basis for a constraint-based analysis of dense-time probabilistic hybrid automata, extending previous results addressing discrete-time automata [33]. Generalizing SMT-based bounded model-checking of hybrid automata [5], [31], stochastic SMT including ODEs permits the direct analysis of probabilistic bounded reachability problems of dense-time probabilistic hybrid automata without resorting to approximation by intermediate finite-state abstractions.     

Improved hybrid cellular automata for crashworthiness optimization of thin-walled structures

Thin-walled structures are of great importance in automotive crashworthiness design, because of their high crash energy absorption capability and their high potential for light weighting. To identify the best compromise between these two requirements, numerical optimization is needed. Size and shape optimization is relatively well explored while topology optimization for crash is still an open issue. Hence, this paper proposes an approach based on hybrid cellular automata (HCA) for crashworthiness topology optimization with a special focus on thin-walled structures. First approaches have been published, e.g. Duddeck et al. (Struct Multidiscip Optim 54(3):415–428, 2016), using a simple rule to define the target mass for the inner loop of the HCA. To improve the performance, a modified scheme is proposed here for the outer optimization loop, which is based on a bi-section search with limited length. In the inner loop, hybrid updating rules are used to redistribute the mass and a mass correction technique is proposed to make the real mass converge to the target mass strictly. The efficiency and correctness of the proposed method is compared with LS-OPT for axial crash case. Two different methods of defining the target mass in the outer loop are studied, the proposed bi-section search with limited length shows its advantage in two types of three-point bending crash optimization cases. Another advantage of this method is that it requires no significantly increasing number of evaluations when the number of design variables increases. This is demonstrated by applying this method to a crashworthiness optimization problem with 380 design variables.     

A hybrid optimization approach to conformance testing of finite automata

Unique Input–Output sequences (UIOs) are quite commonly used in conformance testing. Unfortunately finding UIOs of minimal length is an NP hard problem. This study presents a hybrid approach to generate UIOs automatically on a basis of the finite state machine (FSM) specification. The proposed hybrid approach harnesses the benefits of hill climbing (Greedy search) and heuristic algorithm. Hill climbing, which exploits domain knowledge, is capable of quickly generating good result however it may get stuck in local minimum. To overcome the problem we used a set of parameters called the seed, which allows the algorithm to generate different results for a different seed. The hill climbing generates solutions implied by the seed while the Genetic Algorithm is used as the seed generator. We compared the hybrid approach with Genetic Algorithm, Simulated Annealing, Greedy Algorithm, and Random Search. The experimental evaluation shows that the proposed hybrid approach outperforms other methods. More specifically, we showed that Genetic Algorithm and Simulated Annealing exhibit similar performance while both of them outperform Greedy Algorithm. Finally, we generalize the proposed hybrid approach to seed-driven hybrid architectures and elaborate on how it can be adopted to a broad range of optimization problems.     

Synthesis of supervisory controllers for hybrid systems based onapproximating automata

The paper concerns the synthesis of supervisory controllers for a class of continuous-time hybrid systems with discrete-valued input signals that select differential inclusions for continuous-valued state trajectories and event-valued output signals generated by threshold crossings in the continuous state space, the supervisor is allowed to switch the input signal value when threshold events are observed. The objective is to synthesize a nonblocking supervisor such that the set of possible sequences of control and threshold event pairs for the closed-loop system lies between given upper and lower bounds in the sense of set containment. We show how this problem can be converted into a supervisor synthesis problem for a standard controlled discrete-event system (DES). A finite representation may not exist for the exact DES model of the hybrid system, however. To circumvent this difficulty, we present an algorithm for constructing finite-state Muller automata that accept outer approximations to the exact controlled threshold-event language, and we demonstrate that supervisors that solve the synthesis problem for the approximating automata achieve the control specifications when applied to the original hybrid system