A unified framework for hybrid control: model and optimal control theory

We propose a very general framework that systematizes the notion of a hybrid system, combining differential equations and automata, governed by a hybrid controller that issues continuous-variable commands and makes logical decisions. We first identify the phenomena that arise in real-world hybrid systems. Then, we introduce a mathematical model of hybrid systems as interacting collections of dynamical systems, evolving on continuous-variable state spaces and subject to continuous controls and discrete transitions. The model captures the identified phenomena, subsumes previous models, yet retains enough structure to pose and solve meaningful control problems. We develop a theory for synthesizing hybrid controllers for hybrid plants in all optimal control framework. In particular, we demonstrate the existence of optimal (relaxed) and near-optimal (precise) controls and derive "generalized quasi-variational inequalities" that the associated value function satisfies. We summarize algorithms for solving these inequalities based on a generalized Bellman equation, impulse control, and linear programming.

Related papers:

title: Hybrid Dynamical Systems 1
abstract: The control of a continuous state dynamical plant is often divided into two layers. At the lower or servo layer is a controller that regulates the plant in the traditional manner. At the upper layer the supervisor issues symbolic commands. Some time after a command is issued the supervisor receives a symbolic response indicating either that the command has been executed or that an error condition occurred. Mathematically, the servo layer and plant are modeled together as a diierential equation evolving in real time. The supervisor, however, views the lower layer as a discrete event system whose behavior is described by sequences of events that unfold in logical time. The two models must be related so that consistency is maintained. It is the objective of this paper to pose and address several aspects of model consistency. The discussion is put in the context of a particular hybrid system | the disk controller. This multilayer hybrid dynamical system is extended to include two other layers: a user layer at the top to deene more complex tasks, and a sequencer between the supervisor and the servo layer to permit synchronous control.

title: Hybrid Models for Motion Control Systems
abstract: This paper presents a mathematical framework for modeling motion control systems and other families of computer controlled devices that are guided by symbol strings as well as real valued functions. It discusses a particular method of organizing the lower level structure of such systems and argues that this method is widely applicable. Because the models used here capture important aspects of control and computer engineering relevant to the real-time performance of symbol/signal systems, they can be used to explore questions involving the joint optimization of instruction set and speed of execution. Finally, some comparisons are made between engineering and biological motion control systems, suggesting that the basic ideas advanced here are consistent with some aspects of motor control in animals.

title: A Dynamical Simulation Facility for Hybrid Systems
abstract: This paper establishes a general framework for describing hybrid dynamical systems which is particularly suitable for numerical simulation. In this context, the data structures used to describe the sets and functions which comprise the dynamical system are crucial since they provide the link between a natural mathematical formulation of a problem and the correct application of standard numerical algorithms. We describe a partial implementation of the design methodology and use this simulation tool for a specific control problem in robotics as an illustration of the utility of the approach for practical applications.

title: Smart cars on smart roads: problems of control
abstract: Key features of one automated intelligent vehicle/highway system (IVHS) are outlined, it is shown how core driver decisions are improved, a basic IVHS control system architecture is proposed, and a design of some control subsystems is offered. Some experimental work is summarized. A system that promises a threefold increase in capacity is outlined, and a four-layer hierarchical control architecture that decomposes this problem into more manageable units is proposed.

title: Reduction of Timed Hybrid Systems
abstract: We consider a class of hybrid dynamical systems and obtain conditions under which the behavior of these systems can be reduced to a finite state automaton. Specifically, we consider timed automata with more general enabling regions coupling the continuous and discrete dynamics than those previously considered. We provide a necessary condition for the existence of a finite state reduction, together with examples showing that this condition is not sufficient. We then give two sufficient conditions that provide a large class of systems with general enabling regions which admit finite reductions.

title: Universal Computation and Other Capabilities of Hybrid and Continuous Dynamical Systems
abstract: We explore the simulation and computational capabilities of hybrid and continuous dynamical systems. The continuous dynamical systems considered are ordinary differential equations (ODEs). For hybrid systems we concentrate on models that combine ODEs and discrete dynamics (e.g., finite automata). We review and compare four such models from the literature. Notions of simulation of a discrete dynamical system by a continuous one are developed. We show that hybrid systems whose equations can describe a precise binary timing pulse (exact clock) can simulate arbitrary reversible discrete dynamical systems defined on closed subsets of R n . The simulations require continuous ODEs in IR2n with the exact clock as input. All four hybrid systems models studied here can implement exact clocks. We also prove that any discrete dynamical system in rn can be simulated by continuous ODEs in Rt2n+1. We use this to show that smooth ODEs in RI3 can simulate arbitrary Turing machines, and hence possess the power of universal computation. We use the famous asynchronous arbiter problem to distinguish between hybrid and continuous dynamical systems. We prove that one cannot build an arbiter with devices described by a system of Lipschitz ODEs. On the other hand, all four hybrid systems models considered can implement arbiters even if their ODEs are Lipschitz.

title: Laboratory for Information and Decision Systems
abstract: The Laboratory for Information and Decision Systems (LIDS) is an interdepartmental laboratory for research and education in systems, control, optimization, communication, networks, and statistical inference. These disciplines, which span the domain of the analytical information and decision sciences, play a critical and pervasive role in science, engineering, and society more broadly. LIDS continues to be at the forefront of research in traditional core disciplines in this area. Over the past few years, the scope of LIDS research has broadened to include new emerging areas at the intersection of several fields including game theory, social and economic networks, efficient large-scale inference (using optimization, statistics, and algorithms), and autonomous systems. LIDS provides an intellectually cohesive and interactive environment that fosters the research needed for the future and instills in our students the disciplinary depth and interdisciplinary understanding required of research and engineering leaders of today and tomorrow.

title: A class of hybrid-state continuous-time dynamic systems
abstract: A class of continuous time systems with part continuous, part discrete state is described by differential equations combined with multistable elements. Transitions of these elements between their discrete states are triggered by the continuous part of the state and not directly by inputs. The dynamic behavior of such systems, in response to piecewise continuous inputs, is defined under suitable assumptions. A general Mayer-type optimization problem is formulated. Conditions are given for a solution to be well-behaved, so that variational methods can be applied. Necessary conditions for optimality are stated and the jump conditions are interpreted geometrically.

title: Impulse control of piecewise-deterministic processes via linear programming
abstract: In previous papers a state-space discretization technique in which the continuous-time discretized piecewise-deterministic Markov process (discretization on the post-jump location) approaches the original process uniformly on compact sets has been presented. Under the assumptions of continuity and boundedness of the cost function, it follows that the total discounted cost will also approach the original total cost, at least for epsilon -optimal strategies, which means that the optimal cost of the discretized process should converge to the original optimal cost. The author considers a time discretization so that the new discretized problem (state space and intervention times discretizations) will be finite-dimensional and linear programming (LP) can be used to solve it. The author presents a method that can considerably reduce the number of inequalities of the LP problem. An application to the maintenance of complex systems is given.

title: Systems governed by ordinary differential equations with continuous, switching and impulse controls
abstract: Optimal control problem for systems governed by ordinary differential equations with continuous, switching and impulse controls are studied. It is proved that the value function of the problem is the unique viscosity solution of the corresponding Hamilton-Jacobi-Bellman system.

title: Optimal control of systems with continuous and discrete states
abstract: We consider optimal control design for systems that involve continuous and discrete states. The discontinuous nature of such a system results in the inconsistency of the derivatives of the objective function used by gradient-based numerical optimization algorithms. To avoid this difficulty, we propose a novel algorithm using constrained differential dynamic programming to solve the optimal control problem.<<ETX>>

title: Viable control of hybrid systems
abstract: We study hybrid systems with nondeterministic discrete and continuous behaviors. We use nondeterministic finite automata to model the discrete behavior and state dependent differential inclusions to model the continuous behavior. By viability we mean the system's ability to take an infinite number of discrete transitions. Viability can be used to express safety and fairness properties over the system's state trajectories. To ensure viability, the system's evolution must be restricted so that discrete transitions occur within specific subsets of their enabling conditions which we call the system's viability kernel. We give results pertaining to continuity properties of the viability kernel, we give conditions under which the viability kernel can be computed in a finite number of steps, and we synthesize a hybrid controller that yields all viable trajectories.

title: Viability in Hybrid Systems
abstract: Hybrid systems are interacting systems of digital automata and continuous plants subject to disturbances. The digital automata are used to force the state trajectory of the continuous plant to obey a performance specification. For the basic concepts and notation for hybrid systems, see Kohn and Nerode (1993), and other papers in the same volume. Here we introduce tools for analyzing enforcing viability of all possible plant state trajectories of a hybrid system by suitable choices of finite state control automata. Thus, the performance specification considered here is that the state of the plant remain in a prescribed viability set of states at all times (Aubin, 1991). The tools introduced are local viability graphs and viability graphs for hybrid systems. We construct control automata which guarantee viability as the fixpoints of certain operators on graphs. When control and state spaces are compact, the viability set is closed, and a non-empty closed subset of a viability graph is given with a sturdiness property, one can extract finite state automata guaranteeing viable trajectories. This paper is a sequel to Kohn and Nerode (1993), especially Appendix II.

title: Hybrid System Modeling and Autonomous Control Systems
abstract: Hybrid control systems contain two distinct types of systems, continuous state and discrete-state, that interact with each other. Their study is essential in designing sequential supervisory controllers for continuous-state systems, and it is central in designing control systems with high degree of autonomy.

title: Design of Flight Vehicle Management Systems
abstract: As the operation of large systems becomes ever more dependent on extensive automation, the need for an effective solution to the problem of design and validation of the underlying software becomes more critical. Large systems possess much detailed structure, typically hierarchical, and they are hybrid. Information processing at the top of the hierarchy is by means of formal logic and sentences; on the bottom it is by means of simple scalar differential equations and functions of time; and in the middle it is by an interacting mix of nonlinear multi-axis differential equations and automata, and functions of time and discrete events. The lecture will address the overall problem as it relates to flight vehicle management, describe the middle level, and offer a design approach that is based on Differential Geometry and Discrete Event Dynamic Systems Theory.

title: Control of hybrid systems
abstract: This report focuses on the control of hybrid systems. The authors first describe specification and control of the closed loop behavior of the system in terms of propositional linear temporal logic. Control and coordination models are given in the formalism. The authors next present a continuous event model of the plant and formulate the hybrid system control problem. The report concludes with an application domain of hybrid system control theory.

title: TO VISCOSITY SOLUTIONS OF SECOND ORDER PARTIAL DIFFERENTIAL EQUATIONS
abstract: The notion of viscosity solutions of scalar fully nonlinear partial differential equations of second order provides a framework in which startling comparison and uniqueness theorems, existence theorems, and theorems about continuous dependence may now be proved by very efficient and striking arguments. The range of important applications of these results is enormous. This article is a self-contained exposition of the basic theory of viscosity solutions.  The theory of viscosity solutions applies to certain partial differential equations of the form F(x ,u,Du, D2u) = 0 where F:RN xRxRN x S"(N) -* R and S"(N) is the set of symmetric N x N matrices. The primary virtues of this theory are that it allows merely continuous functions to be solutions of fully nonlinear equations of second order, that it provides very general existence and uniqueness theorems and that it yields precise formulations of general boundary conditions. Moreover, these features go hand-in-hand with a great flexibility in passing to limits in various settings and relatively simple proofs. In the expression F(x, u, Du, D2u) u will be a real-valued function defined on some subset cf of R^, Du corresponds to the gradient of u and D2u corresponds to the matrix of second derivatives of u. However, as explained below, Du and D2u will not have classical meanings and, in fact, the examples exhibited in § 1 will convince the reader that the theory encompasses classes of equations that have no solutions that are differentiable in the classical sense. In order that the theory apply to a given equation F = 0, we will require F to satisfy a fundamental monotonicity condition (0.1) F(x, r, p, X) < F(x, s, p, Y) whenever r < s and Y < X ; where r,s eR, x,p eRN, X,Y e S"{N) and S"(N) is equipped with its usual order. Received by the editors November 16, 1990.

title: Algorithms for optimal hybrid control
abstract: The authors previously (1994) proposed a general, unified framework for hybrid control problems that encompasses several types of hybrid phenomena and several models of hybrid systems. An existence result was obtained for optimal controls. The value function associated with this problem satisfies a set of "generalized quasi-variational inequalities" (GQVIs). We give a classification of the types of hybrid systems models covered by our framework and algorithms. We review our general framework and results. Then, we outline three explicit approaches for computing the solutions to the GQVIs that arise in optimal hybrid control. The approaches are generalizations to hybrid systems of shooting methods for boundary value problems, impulse control for piecewise-deterministic processes (PDPs), and value and policy iteration for piecewise-continuous dynamical systems. In the central case, we make clear the strong connection between impulse control for PDPs and optimal hybrid control. This allows us to give exact and approximate ("epsilon-optimal") algorithms for computing the value function associated with such problems and give some theoretical results. Also following previous work, we find that we can compute optimal solutions via linear programming (LP). The resulting LP problems are in general large, but sparse. In each case, the underlying feedback controls can be subsequently computed. Illustrative examples of each algorithm are solved in our framework.

title: Impulse control of piecewise-deterministic processes
abstract: In a recent paper we presented a numerical technique for solving the optimal stopping problem for a piecewise-deterministic process (P.D.P.) by discretization of the state space. In this paper we apply these results to the impulse control problem. In the first part of the paper we study the impulse control of P.D.P.s. under general conditions. We show that iteration of the single-jump-or-intervention operator generates a sequence of functions converging to the value function of the problem. In the second part of the paper we present a numerical technique for computing optimal impulse controls for P.D.P.s. This technique reduces the problem to a sequence of one-dimensional minimizations. We conclude by presenting some numerical examples.

title: The hierarchical lattices of a finite machine
abstract: The concept of dynamical consistency is introduced to define a high-level transition function for an arbitrary partition of the state space of a finite input-state machine M. The existence of a dynamically consistent transition from a partition member Xi to a member Xj corresponds to the existence, for every state x in Xi, of some (x dependent) control sequence which takes that state directly into Xj. This paper analyses what are termed in-block controllable partition machines and between-block controllable partition machines, and establishes the existence of the associated in-block controllable hierarchical lattice IBCP(M). It is shown that any partition machine in IBCP(M) is between-block controllable if and only if the base machine M is controllable. This setting allows the specification of state to state control trajectories of M to be decomposed into high-level and low-level components.