Control of dynamical systems with temporal logic specifications

This thesis is motivated by safety-critical applications involving autonomous air, ground, and space vehicles carrying out complex tasks in uncertain and adversarial environments. We use temporal logic as a language to formally specify complex tasks and system properties. Temporal logic specifications generalize the classical notions of stability and reachability that are studied in the control and hybrid systems communities. Given a system model and a formal task specification, the goal is to automatically synthesize a control policy for the system that ensures that the system satisfies the specification. This thesis presents novel control policy synthesis algorithms for optimal and robust control of dynamical systems with temporal logic specifications. Furthermore, it introduces algorithms that are efficient and extend to high-dimensional dynamical systems.

The first contribution of this thesis is the generalization of a classical linear temporal logic (LTL) control synthesis approach to optimal and robust control. We show how we can extend automata-based synthesis techniques for discrete abstractions of dynamical systems to create optimal and robust controllers that are guaranteed to satisfy an LTL specification. Such optimal and robust controllers can be computed at little extra computational cost compared to computing a feasible controller.

The second contribution of this thesis addresses the scalability of control synthesis with LTL specifications. A major limitation of the standard automaton-based approach for control with LTL specifications is that the automaton might be doubly-exponential in the size of the LTL specification. We introduce a fragment of LTL for which one can compute feasible control policies in time polynomial in the size of the system and specification. Additionally, we show how to compute optimal control policies for a variety of cost functions, and identify interesting cases when this can be done in polynomial time. These techniques are particularly relevant for online control, as one can guarantee that a feasible solution can be found quickly, and then iteratively improve on the quality as time permits.

The final contribution of this thesis is a set of algorithms for computing feasible trajectories for high-dimensional, nonlinear systems with LTL specifications. These algorithms avoid a potentially computationally-expensive process of computing a discrete abstraction, and instead compute directly on the system's continuous state space. The first method uses an automaton representing the specification to directly encode a series of constrained-reachability subproblems, which can be solved in a modular fashion by using standard techniques. The second method encodes an LTL formula as mixed-integer linear programming constraints on the dynamical system. We demonstrate these approaches with numerical experiments on temporal logic motion planning problems with high-dimensional (10+ states) continuous systems.

Efficient methods for stochastic optimal control

The Hamilton Jacobi Bellman (HJB) equation is central to stochastic optimal control (SOC) theory, yielding the optimal solution to general problems specified by known dynamics and a specified cost functional. Given the assumption of quadratic cost on the control input, it is well known that the HJB reduces to a particular partial differential equation (PDE). While powerful, this reduction is not commonly used as the PDE is of second order, is nonlinear, and examples exist where the problem may not have a solution in a classical sense. Furthermore, each state of the system appears as another dimension of the PDE, giving rise to the curse of dimensionality. Since the number of degrees of freedom required to solve the optimal control problem grows exponentially with dimension, the problem becomes intractable for systems with all but modest dimension.

In the last decade researchers have found that under certain, fairly non-restrictive structural assumptions, the HJB may be transformed into a linear PDE, with an interesting analogue in the discretized domain of Markov Decision Processes (MDP). The work presented in this thesis uses the linearity of this particular form of the HJB PDE to push the computational boundaries of stochastic optimal control.

This is done by crafting together previously disjoint lines of research in computation. The first of these is the use of Sum of Squares (SOS) techniques for synthesis of control policies. A candidate polynomial with variable coefficients is proposed as the solution to the stochastic optimal control problem. An SOS relaxation is then taken to the partial differential constraints, leading to a hierarchy of semidefinite relaxations with improving sub-optimality gap. The resulting approximate solutions are shown to be guaranteed over- and under-approximations for the optimal value function. It is shown that these results extend to arbitrary parabolic and elliptic PDEs, yielding a novel method for Uncertainty Quantification (UQ) of systems governed by partial differential constraints. Domain decomposition techniques are also made available, allowing for such problems to be solved via parallelization and low-order polynomials.

The optimization-based SOS technique is then contrasted with the Separated Representation (SR) approach from the applied mathematics community. The technique allows for systems of equations to be solved through a low-rank decomposition that results in algorithms that scale linearly with dimensionality. Its application in stochastic optimal control allows for previously uncomputable problems to be solved quickly, scaling to such complex systems as the Quadcopter and VTOL aircraft. This technique may be combined with the SOS approach, yielding not only a numerical technique, but also an analytical one that allows for entirely new classes of systems to be studied and for stability properties to be guaranteed.

The analysis of the linear HJB is completed by the study of its implications in application. It is shown that the HJB and a popular technique in robotics, the use of navigation functions, sit on opposite ends of a spectrum of optimization problems, upon which tradeoffs may be made in problem complexity. Analytical solutions to the HJB in these settings are available in simplified domains, yielding guidance towards optimality for approximation schemes. Finally, the use of HJB equations in temporal multi-task planning problems is investigated. It is demonstrated that such problems are reducible to a sequence of SOC problems linked via boundary conditions. The linearity of the PDE allows us to pre-compute control policy primitives and then compose them, at essentially zero cost, to satisfy a complex temporal logic specification.

STAIR: Practical AIMD Multirate Congestion Control

Existing approaches for multirate multicast congestion control are either friendly to TCP only over large time scales or introduce unfortunate side effects, such as significant control traffic, wasted bandwidth, or the need for modifications to existing routers. We advocate a layered multicast approach in which steady-state receiver reception rates emulate the classical TCP sawtooth derived from additive-increase, multiplicative decrease (AIMD) principles. Our approach introduces the concept of dynamic stair layers to simulate various rates of additive increase for receivers with heterogeneous round-trip times (RTTs), facilitated by a minimal amount of IGMP control traffic. We employ a mix of cumulative and non-cumulative layering to minimize the amount of excess bandwidth consumed by receivers operating asynchronously behind a shared bottleneck. We integrate these techniques together into a congestion control scheme called STAIR which is amenable to those multicast applications which can make effective use of arbitrary and time-varying subscription levels.

A Self-Organizing Neural Network Model for Redundant Sensory-Motor Control, Motor Equivalence, and Tool Use

A neural network is introduced which provides a solution of the classical motor equivalence problem, whereby many different joint configurations of a redundant manipulator can all be used to realize a desired trajectory in 3-D space. To do this, the network self-organizes a mapping from motion directions in 3-D space to velocity commands in joint space. Computer simulations demonstrate that, without any additional learning, the network can generate accurate movement commands that compensate for variable tool lengths, clamping of joints, distortions of visual input by a prism, and unexpected limb perturbations. Blind reaches have also been simulated.

Neural Representations for Sensory-Motor Control I: Head-Centered 3-D Target Positions from Opponent Eye Commands

This article describes how corollary discharges from outflow eye movement commands can be transformed by two stages of opponent neural processing into a head-centered representation of 3-D target position. This representation implicitly defines a cyclopean coordinate system whose variables approximate the binocular vergence and spherical horizontal and vertical angles with respect to the observer's head. Various psychophysical data concerning binocular distance perception and reaching behavior are clarified by this representation. The representation provides a foundation for learning head-centered and body-centered invariant representations of both foveated and non-foveated 3-D target positions. It also enables a solution to be developed of the classical motor equivalence problem, whereby many different joint configurations of a redundant manipulator can all be used to realize a desired trajectory in 3-D space.

Measles virus and classical Hodgkin lymphoma: no evidence for a direct association.

A proportion of Hodgkin lymphoma (HL) cases are causally associated with the Epstein-Barr virus (EBV) but the aetiology of the remaining cases remains obscure. Over the last 3 decades several studies have found an association between HL and measles virus (MV) including a recent cohort study describing the detection of MV antigens in Hodgkin and Reed-Sternberg cells, the tumour cells in HL. In the present study we looked at the relationship between history of MV infection and risk of developing HL in a population-based, case/control study of HL. In addition we used immunohistochemistry and RT-PCR to look for direct evidence of MV in HL biopsies. There was no significant difference in the proportion of cases reporting previous measles compared to controls in the entire data set or when young adults were considered separately. Using a robust immunohistochemical assay for MV infection, we failed to find evidence of MV in biopsies from 97 cases of HL and RT-PCR studies similarly gave negative results. This study therefore provides no evidence that MV is directly involved in the development of HL. However, when age at first reported MV infection was investigated, significant differences emerged with children infected before school-age having higher risk, especially of EBV-ve HL, when compared with children infected at older ages; the interpretation of these latter results is unclear.

Reducing quantum control for spin-spin entanglement distribution

We present a protocol that sets maximum stationary entanglement between remote spins through scattering of mobile mediators without initialization, post-selection or feedback of the mediators' state. No time-resolved tuning is needed and, counterintuitively, the protocol generates two-qubit singlet states even when classical mediators are used. The mechanism responsible for this effect is resilient against non-optimal coupling strengths and dephasing affecting the spins. The scheme uses itinerant particles and scattering centres and can be implemented in various settings. When quantum dots and photons are used a striking result is found: injection of classical mediators, rather than quantum ones, improves the scheme efficiency.

Quasi-classical model of non-destructive wavepacket manipulation by intense ultrashort nonresonant laser pulses

A quasi-classical model (QCM) of nuclear wavepacket generation, modification and imaging by three intense ultrafast near-infrared laser pulses has been developed. Intensities in excess of 10(13) W cm(-2) are studied, the laser radiation is non-resonant and pulse durations are in the few-cycle regime, hence significantly removed from the conditions typical of coherent control and femtochemistry. The 1s sigma ground state of the D-2 precursor is projected onto the available electronic states in D-2(+) (1s sigma(g) ground and 2p sigma(u) dissociative) and D+ + D+ (Coulomb explosion) by tunnel ionization by an ultrashort 'pump' pulse, and relative populations are found numerically. A generalized non-adiabatic treatment allows the dependence of the initial vibrational population distribution on laser intensity to be calculated. The wavepacket is approximated as a classical ensemble of particles moving on the 1s sigma(g) potential energy surface (PES), and hence follow trajectories of different amplitudes and frequencies depending on the initial vibrational state. The 'control' pulse introduces a time-dependent polarization of the molecular orbital, causing the PES to be modified according to the dynamic Stark effect and the transition dipole. The trajectories adjust in amplitude, frequency and phase-offset as work is done on or by the resulting force; comparing the perturbed and unperturbed trajectories allows the final vibrational state populations and phases to be determined. The action of the 'probe' pulse is represented by a discrete internuclear boundary, such that elements of the ensemble at a larger internuclear separation are assumed to be photodissociated. The vibrational populations predicted by the QCM are compared to recent quantum simulations (Niederhausen and Thumm 2008 Phys. Rev. A 77 013404), and a remarkable agreement has been found. The applicability of this model to femtosecond and attosecond time-scale experiments is discussed and the relation to established femtochemistry and coherent control techniques are explored.

Feedforward Control of Shape Memory Alloy Actuators Using Fuzzy-Based Inverse Preisach Model

This brief investigates a possible application of the inverse Preisach model in combination with the feedforward and feedback control strategies to control shape memory alloy actuators. In the feedforward control design, a fuzzy-based inverse Preisach model is used to compensate for the hysteresis nonlinearity effect. An extrema input history and a fuzzy inference is utilized to replace the inverse classical Preisach model. This work allows for a reduction in the number of experimental parameters and computation time for the inversion of the classical Preisach model. A proportional-integral-derivative (PID) controller is used as a feedback controller to regulate the error between the desired output and the system output. To demonstrate the effectiveness of the proposed controller, real-time control experiment results are presented.

Internal model control for shape memory alloy actuators using fuzzy based Preisach model

This paper investigates a possible application of Preisach model to control shape memory alloy (SMA) actuators using an internal model control strategy. The developed strategy consists in including the Preisach hysteresis model of SMA actuator and the inverse Preisach model within the control structure. In this work, an extrema input hystory and a fuzzy inference is utilized to replace the classical Preisach model. This allows to reduce a large amount of experimental parameters and computation time of the classical Preisach model. To demonstrate the effectiveness of the proposed controller in improving control performance and hysteresis compensation of SMA actuators, experimental results from real time control are presented.

Computational methods in the fractional calculus of variations and optimal control

The fractional calculus of variations and fractional optimal control are generalizations of the corresponding classical theories, that allow problem modeling and formulations with arbitrary order derivatives and integrals. Because of the lack of analytic methods to solve such fractional problems, numerical techniques are developed. Here, we mainly investigate the approximation of fractional operators by means of series of integer-order derivatives and generalized finite differences. We give upper bounds for the error of proposed approximations and study their efficiency. Direct and indirect methods in solving fractional variational problems are studied in detail. Furthermore, optimality conditions are discussed for different types of unconstrained and constrained variational problems and for fractional optimal control problems. The introduced numerical methods are employed to solve some illustrative examples.

On the application of optimal control techniques in lossy fieldbuses

The performance of real-time networks is under continuous improvement as a result of several trends in the digital world. However, these tendencies not only cause improvements, but also exacerbates a series of unideal aspects of real-time networks such as communication latency, jitter of the latency and packet drop rate. This Thesis focuses on the communication errors that appear on such realtime networks, from the point-of-view of automatic control. Specifically, it investigates the effects of packet drops in automatic control over fieldbuses, as well as the architectures and optimal techniques for their compensation. Firstly, a new approach to address the problems that rise in virtue of such packet drops, is proposed. This novel approach is based on the simultaneous transmission of several values in a single message. Such messages can be from sensor to controller, in which case they are comprised of several past sensor readings, or from controller to actuator in which case they are comprised of estimates of several future control values. A series of tests reveal the advantages of this approach. The above-explained approach is then expanded as to accommodate the techniques of contemporary optimal control. However, unlike the aforementioned approach, that deliberately does not send certain messages in order to make a more efficient use of network resources; in the second case, the techniques are used to reduce the effects of packet losses. After these two approaches that are based on data aggregation, it is also studied the optimal control in packet dropping fieldbuses, using generalized actuator output functions. This study ends with the development of a new optimal controller, as well as the function, among the generalized functions that dictate the actuator’s behaviour in the absence of a new control message, that leads to the optimal performance. The Thesis also presents a different line of research, related with the output oscillations that take place as a consequence of the use of classic co-design techniques of networked control. The proposed algorithm has the goal of allowing the execution of such classical co-design algorithms without causing an output oscillation that increases the value of the cost function. Such increases may, under certain circumstances, negate the advantages of the application of the classical co-design techniques. A yet another line of research, investigated algorithms, more efficient than contemporary ones, to generate task execution sequences that guarantee that at least a given number of activated jobs will be executed out of every set composed by a predetermined number of contiguous activations. This algorithm may, in the future, be applied to the generation of message transmission patterns in the above-mentioned techniques for the efficient use of network resources. The proposed task generation algorithm is better than its predecessors in the sense that it is capable of scheduling systems that cannot be scheduled by its predecessor algorithms. The Thesis also presents a mechanism that allows to perform multi-path routing in wireless sensor networks, while ensuring that no value will be counted in duplicate. Thereby, this technique improves the performance of wireless sensor networks, rendering them more suitable for control applications. As mentioned before, this Thesis is centered around techniques for the improvement of performance of distributed control systems in which several elements are connected through a fieldbus that may be subject to packet drops. The first three approaches are directly related to this topic, with the first two approaching the problem from an architectural standpoint, whereas the third one does so from more theoretical grounds. The fourth approach ensures that the approaches to this and similar problems that can be found in the literature that try to achieve goals similar to objectives of this Thesis, can do so without causing other problems that may invalidate the solutions in question. Then, the thesis presents an approach to the problem dealt with in it, which is centered in the efficient generation of the transmission patterns that are used in the aforementioned approaches.

Shape control of laminated panels using piezoelectric actuators

This paper presents a finite element formulation based on the classical laminated plate theory for laminated structures with integrated piezoelectric layers or patches, acting as actuators.The finite element model is a single layer trinaguular nonconforming plate/shell element with 18 degrees of fredom for the generalized displacements, and one electrical potential degree of freedom for each piezoelectric element elemenet layer or patch. An optimization of the patches position is perfomed to maximize the piezoelectric actuators efficiency as well as,the electric potential distribution is serach to reach the specified strusctura transverse displacement distribution is search to reach the specified structures trsnsverse displacement distribution (shape control). A gradient based algorithm is used for this purpose.Results are presented and discussed.

Optimal dynamic control of laminated adaptive structures using a higher order model and a genetic algorithm

This paper deals with a finite element formulation based on the classical laminated plate theory, for active control of thin plate laminated structures with integrated piezoelectric layers, acting as sensors and actuators. The control is initialized through a previous optimization of the core of the laminated structure, in order to minimize the vibration amplitude. Also the optimization of the patches position is performed to maximize the piezoelectric actuator efficiency. The genetic algorithm is used for these purposes. The finite element model is a single layer triangular plate/shell element with 24 degrees of freedom for the generalized displacements, and one electrical potential degree of freedom for each piezoelectric element layer, which can be surface bonded or embedded on the laminate. To achieve a mechanism of active control of the structure dynamic response, a feedback control algorithm is used, coupling the sensor and active piezoelectric layers. To calculate the dynamic response of the laminated structures the Newmark method is considered. The model is applied in the solution of an illustrative case and the results are presented and discussed.

Finit element model for active control of adaptive laminated structures

A finite element formulation for active vibration control of thin plate laminated structures with integrated piezoelectric layers, acting as sensors and actuators in presented. The finite element model is a nonconforming single layer triangular plate/shell element with 18 degrees of freedom for the generalized displacements and one electrical potential degree of freedom for each piezoelectric element layer, and is based on the kirchhoff classical laminated theory. To achieve a mechanism of active control of the structure dynamic response, a feedback control algorithm is used, coupling the sensor and active piezoelectric layers, and Newmark method is used to calculate yhe dynamic response of the laminated structures. The model is applied in the solution of several illustrative cases, and the results are presented and discussed.