Falsification of hybrid systems with symbolic reachability analysis and trajectory splicing

The falsification of a hybrid system aims at finding trajectories that violate a given safety property. This is a challenging problem, and the practical applicability of current falsification algorithms still suffers from their high time complexity. In contrast to falsification, verification algorithms aim at providing guarantees that no such trajectories exist. Recent symbolic reachability techniques are capable of efficiently computing linear constraints that enclose all trajectories of the system with reasonable precision. In this paper, we leverage the power of symbolic reachability algorithms to improve the scalability of falsification techniques. Recent approaches to falsification reduce the problem to a nonlinear optimization problem. We propose to reduce the search space of the optimization problem by adding linear state constraints obtained with a reachability algorithm. An empirical study of how varying abstractions during symbolic reachability analysis affect the performance of solving a falsification problem is presented. In addition, for solving a falsification problem, we propose an alternating minimization algorithm that solves a linear programming problem and a non-linear programming problem in alternation finitely many times. We showcase the efficacy of our algorithms on a number of standard hybrid systems benchmarks demonstrating the performance increase and number of falsifyable instances.     

Parallel solver for trajectory optimization search directions

A key algorithmic element of a real-time trajectory optimization hardware/software implementation is presented, the search step solver. This is one piece of an algorithm whose overall goal is to make nonlinear trajectory optimization fast enough to provide real-time commands during guidance of a vehicle such as an aeromaneuvering orbiter or the National Aerospace Plane. Many methods of nonlinear programming require the solution of a quadratic program (QP) at each iteration to determine the search step. In the trajectory optimization case, the QP has a special dynamic programming structure, an LQR-like structure. The algorithm exploits this special structure with a divide-and-conquer type of parallel implementation. A hypercube message-passing parallel machine, the INTEL iPSC/2, has been used. The algorithm solves a (p·N)-stage problem onN processors inO(p + log₂ N) operations. The algorithm yields a factor of 8 speed-up over the fastest known serial algorithm when solving a 1024-stage test problem on 32 processors.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NAG-1-1009.     

Sequential generation ofD-optimal input designs for linear dynamic systems

This paper considers the problem of sequentially generating test signals for parameter estimation in linear, single-input, single-output, discrete-time systems using a frequency-domain approach based on the theory of optimal experiments in regression analysis. The input signals are power constrained and are optimal in the sense that system information is maximized, where the criterion employed is the determinant of the Fisher information matrix (D-optimality). A class of algorithms is investigated, each member of which generates a sequence of input designs converging to aD-optimum. A number of these algorithms are compared computationally.     

Dynamic material handling for a class of flexible manufacturing systems

A real-time hierarchical routing control scheme for a large class of material handling systems is presented. The higher level (coordinator) performs resource allocation tasks and supplies parameter values to the lower (local control) level. The lower level operates in an autonomous (without continuous supervision) and distributed fashion. If state information is made available to the coordinator, the routing strategy can furthermore be adaptively adjusted.     

Estimating the cycle time of three-stage material handling systems

Because of high investment costs, the productivity of material handling systems must be accurately estimated before various logistical, industrial, or transportation systems can be implemented. This paper proposes analytical models for three-stage material handling systems. Two possible approaches to the estimation of the productivity of three-stage material handling systems are considered: one, the continuous Markov chain model, and two, approximated mathematical models. The approximated models are based on the probability theory and permit very accurate calculations of the compound cycle time in cases when the probability distribution of the “technical” cycle times of each stage is known. Finally, some numerical results obtained by the proposed models are compared with those results obtained by a simulation study.     

A hypothetical learning trajectory for conceptualizing matrices as linear transformations

In this paper, we present a hypothetical learning trajectory (HLT) aimed at supporting students in developing flexible ways of reasoning about matrices as linear transformations in the context of introductory linear algebra. In our HLT, we highlight the integral role of the instructor in this development. Our HLT is based on the ‘Italicizing N’ task sequence, in which students work to generate, compose, and invert matrices that correspond to geometric transformations specified within the problem context. In particular, we describe the ways in which the students develop local transformation views of matrix multiplication (focused on individual mappings of input vectors to output vectors) and extend these local views to more global views in which matrices are conceptualized in terms of how they transform a space in a coordinated way.     

On non-equilibrium stochastic dynamics for interacting particle systems in continuum

We propose a general scheme for construction of Markov stochastic dynamics on configuration spaces in continuum. An application to the Glauber-type dynamics with competitions is considered.     

Fuzzy guaranteed cost controller for trajectory tracking in nonlinear systems

In this paper, we propose a fuzzy logic based guaranteed cost controller for trajectory tracking in nonlinear systems. Takagi–Sugeno (T–S) fuzzy model is used to represent the dynamics of a nonlinear system and the controller design is carried out using this fuzzy model. State feedback law is used for building the fuzzy controller whose performance is evaluated using a quadratic cost function. For designing the fuzzy logic based controller which satisfies guaranteed performance, linear matrix inequality (LMI) approach is used. Sufficient conditions are derived in terms of matrix inequalities for minimizing the performance function of the controller. The performance function minimization problem with polynomial matrix inequalities is then transformed into a problem of minimizing a convex performance function involving standard LMIs. This minimization problem can be solved easily and efficiently using the LMI optimization techniques. Our controller design method also ensures that the closed-loop system is asymptotically stable. Simulation study is carried out on a two-link robotic manipulator tracking a reference trajectory. From the results of the simulation study, it is observed that our proposed controller tracks the reference trajectory closely while maintaining a guaranteed minimum cost.     

Holomorphic Bogoliubov functionals for interacting particle systems in continuum

Combinatorial harmonic analysis techniques are used to develop new analytical methods for the study of interacting particle systems in continuum based on a Bogoliubov functional approach. Concrete applications of the methods are presented, namely, conditions for the existence of Bogoliubov functionals, a uniqueness result for Gibbs measures in the high temperature regime. We also propose a new approach to the study of non-equilibrium stochastic dynamics in terms of evolution equations for Bogoliubov functionals.     

Interval-type and affine arithmetic-type techniques for handling uncertainty in expert systems

Expert knowledge consists of statements _Sj$S_j$ (facts and rules). The facts and rules are often only true with some probability. For example, if we are interested in oil, we should look at seismic data. If in 90% of the cases, the seismic data were indeed helpful in locating oil, then we can say that if we are interested in oil, then with probability 90% it is helpful to look at the seismic data. In more formal terms, we can say that the implication “if oil then seismic” holds with probability 90%. Another example: a bank A trusts a client B, so if we trust the bank A, we should trust B too; if statistically this trust was justified in 99% of the cases, we can conclude that the corresponding implication holds with probability 99%.     

An optimal control approach to the design of periodic orbits for mechanical systems with impacts

In this paper we study the problem of designing periodic orbits for a special class of hybrid systems, namely mechanical systems with underactuated continuous dynamics and impulse events. We approach the problem by means of optimal control. Specifically, we design an optimal control based strategy that combines trajectory optimization, dynamics embedding, optimal control relaxation and root finding techniques. The proposed strategy allows us to design, in a numerically stable manner, trajectories that optimize a desired cost and satisfy boundary state constraints consistent with a periodic orbit. To show the effectiveness of the proposed strategy, we perform numerical computations on a compass biped model with torso.     

Cell-to-cell mapping method for time-optimal trajectory planning of multiple robot arm systems

This paper presents the results obtained by applying the cell-to-cell mapping method to solve the problem of the time-optimal trajectory planning for coordinated multiple robotic arms handling a common object along a specified geometric path. Based on the structure of the time-optimal trajectory control law, the continuous dynamic model of multiple arms is first approximated by a discrete and finite cell-to-cell mapping on a two-dimensional cell space over a phase plane. The optimal trajectory and the corresponding control are then determined by using the cell-to-cell mapping and a simple search algorithm. To further improve the computational efficiency and to allow for parallel computation, a hierarchical search algorithm consisting of a multiple-variable optimization on the top level and a number of cell-to-cell searches on the bottom level is proposed and implemented in the paper. Besides its simplicity, another distinguishing feature of the cell-to-cell mapping methods is the generation of all optimal trajectories for a given final state and all possible initial states through a single searching process. For most of the existing trajectory planning methods, the planning process can be started only when both the initial and final states have been specified. The cell-to-cell method can be generalized to any optimal trajectory planning problem for a multiple robotic arms system.     

Trajectory tracking for a class of switched nonlinear systems: Application to PMSM

This paper proposes a state-dependent switching control for a class of switched nonlinear systems, whose model describes a permanent magnet synchronous machine (PMSM) fed by a three-phase voltage source inverter. Due to its high torque density, high efficiency and wide velocity range, this electrical drive is widely used for traction and several applications in robotics, aerospace, electric vehicles among others. The proposed design conditions are based on a non-quadratic Lyapunov function, dependent on the machine shaft displacement, and assure asymptotic tracking of a pre-specified time-varying rotational velocity profile with guaranteed performance. Properties of the nonlinear system under consideration are used to derive design conditions expressed in terms of linear matrix inequalities that can be solved efficiently. Special cases involving asymptotic stability toward step and ramp velocity profiles are presented. Experimental results are used to validate the proposed technique.     

Liouville-type theorems for semilinear elliptic systems

In this paper, we provide two Liouville-type theorems for some semilinear elliptic systems. Our proofs are based on the moving spheres method and the general Kelvin transformed function. Four previously established results by different authors as consequence are obtained.     

Evolutionary hybrid approaches for generation scheduling in power systems

Generation scheduling (GS) in power systems is a tough optimisation problem which continues to present a challenge for efficient solution techniques. The solution is to define on/off decisions and generation levels for each electricity generator of a power system for each scheduling interval. The solution procedure requires simultaneous consideration of binary decision and continuous variables. In recent years researchers have focused much attention on developing new hybrid approaches using evolutionary and traditional exact methods for this type of mixed-integer problems. This paper investigates how the optimum or near optimum solution for the GS problem may be quickly identified. A design is proposed which uses a variety of metaheuristic, heuristics and mathematical programming techniques within a hybrid framework. The results obtained for two case studies are promising and show that the hybrid approach offers an effective alternative for solving the GS problems within a realistic timeframe.     

The reproducing kernel algorithm for handling differential algebraic systems of ordinary differential equations

The aim of the present analysis is to implement a relatively recent computational method, reproducing kernel Hilbert space, for obtaining the solutions of differential algebraic systems for ordinary differential equations. The reproducing kernel Hilbert space is constructed in which the initial conditions of the systems are satisfied. While, two smooth kernel functions are used throughout the evolution of the algorithm in order to obtain the required grid points. An efficient construction is given to obtain the numerical solutions for the systems together with an existence proof of the exact solutions based upon the reproducing kernel theory. In this approach, computational results of some numerical examples are presented to illustrate the viability, simplicity, and applicability of the algorithm developed. Finally, the utilized results show that the present algorithm and simulated annealing provide a good scheduling methodology to such systems. Copyright © 2016 John Wiley & Sons, Ltd.     

Smoothing algorithms for nonlinear finite-dimensional systems

Systems are considered where the state evolves either as a diffusion process or as a finitestate Markov process, and the measurement process consists either of a nonlinear function of the state with additive white noise or as a counting process with intensity dependent on the state. Fixed interval smooting is considered, and the first main result obtained expresses a smoothing probability or a probability density symmetrically in terms of forward filtered, reverse-time filterd and unfiltered quantities; an associated result replaces the unfiltered and reverse-time filtered qauantities by a likelihood function. Then stochastic differential equationsare obtained for the evolution of the reverse-time filtered probability or probability density and the reverse-time likelihood function. Lastly, a partial differential equation is obtained linking smoothed and forward filterd probabilities or probability densities; in all instances considered, this equation is not driven by any measurement process. The different approaches are also linked to known techniques applicable in the linear-Gaussian case.     

A parameter estimation scheme for a class of sequential hybrid systems

It may happen that the equations governing the response of dynamical systems have some parameters whose values may not be known a priori and have to be obtained using parameter estimation schemes. In this article, we present a parameter estimation scheme for a class of sequential hybrid systems. By hybrid systems, we refer to those systems whose response is described by different governing equations corresponding to various regimes/modes of operation along with some criteria to switch between the same. In a sequential hybrid system, the different modes are arranged in a specific sequence and the system can switch from a given mode to either the previous mode or the following mode in this sequence. Here, we consider those systems whose governing equations consist of ordinary differential equations and algebraic equations. The conditions for switching between the various modes (referred to as transition conditions) are in the form of linear inequalities involving the system output. We shall first consider the case where the transition conditions are known completely. We present a parameter update scheme along with sufficient conditions that will guarantee bounded parameter estimation errors. Then, we shall consider the case where the transition conditions are not known in the sense that some parameters in these conditions are not known. We present a parameter estimation scheme for this case. We illustrate the performance of the parameter estimation scheme in both cases with some examples.     

Fixed-point smoothing algorithm for discrete multiplicative systems

A fixed-point smoothing algorithm is proven for discretetime systems with additive and multiplicative noise in the plant and measurement equations. Such systems, although linear, differ in a number of aspects from systems with only additive noise. The algorithm depends on the multiplicative terms, as expected. Steady-state results are derived.