An efficient algorithm for optimal control of PWA systems with polyhedral performance indices

We present an algorithm for the computation of explicit optimal control laws for piecewise affine (PWA) systems with polyhedral performance indices. The algorithm is based on dynamic programming (DP) and represents an extension of ideas initially proposed in Kerrigan and Mayne [(2003). Optimal control of constrained, piecewise affine systems with bounded disturbances. In Proceedings of the 41st IEEE conference on decision and control, Las Vegas, Nevada, USA, December], and Baoti? et al. [(2003). A new algorithm for constrained finite time optimal control of hybrid systems with a linear performance index. In Proceedings of European control conference, Cambridge, UK, September]. Specifically, we show how to exploit the underlying geometric structure of the optimization problem in order to significantly improve the efficiency of the off-line computations. An extensive case study is provided, which clearly indicates that the algorithm proposed in this paper may be preferable to other schemes published in the literature.     

Dynamic buffer management using optimal control of hybrid systems

This paper studies a dynamic buffer management problem with one buffer inserted between two interacting components. The component to be controlled is assumed to have multiple power modes corresponding to different data processing rates. The overall system is modeled as a hybrid system and the buffer management problem is formulated as an optimal control problem. Different from many previous studies, the objective function of the proposed problem depends on the switching cost and the size of the continuous state space, making its solution much more challenging. By exploiting some particular features of the problem, the best mode sequence and the optimal switching instants are characterized analytically using a variational approach. Simulation results based on real data shows that the proposed method can significantly reduce the energy consumption compared with another heuristic scheme in several typical situations.     

Dynamic programming and viscosity solutions for the optimal control of quantum spin systems

The purpose of this paper is to describe the application of the notion of viscosity solutions to solve the Hamilton-Jacobi-Bellman (HJB) equation associated with an important class of optimal control problems for quantum spin systems. The HJB equation that arises in the control problems of interest is a first-order nonlinear partial differential equation defined on a Lie group. Hence we employ recent extensions of the theory of viscosity solutions to Riemannian manifolds in order to interpret possibly non-differentiable solutions to this equation. Results from differential topology on the triangulation of manifolds are then used develop a finite difference approximation method for numerically computing the solution to such problems. The convergence of these approximations is proven using viscosity solution methods. In order to illustrate the techniques developed, these methods are applied to an example problem.     

Stabilizing low complexity feedback control of constrained piecewise affine systems

Piecewise affine (PWA) systems are powerful models for describing both non-linear and hybrid systems. One of the key problems in controlling these systems is the inherent computational complexity of controller synthesis and analysis, especially if constraints on states and inputs are present. In addition, few results are available which address the issue of computing stabilizing controllers for PWA systems without placing constraints on the location of the origin.This paper first introduces a method to obtain stability guarantees for receding horizon control of discrete-time PWA systems. Based on this result, two algorithms which provide low complexity state feedback controllers are introduced. Specifically, we demonstrate how multi-parametric programming can be used to obtain minimum-time controllers, i.e., controllers which drive the state into a pre-specified target set in minimum time. In a second segment, we show how controllers of even lower complexity can be obtained by separately dealing with constraint satisfaction and stability properties. To this end, we introduce a method to compute PWA Lyapunov functions for discrete-time PWA systems via linear programming. Finally, we report results of an extensive case study which justify our claims of complexity reduction.     

Synthesis of optimal controllers for piecewise affine systems with sampled-data switching

This paper discusses the optimal control problem of the continuous-time piecewise affine (PWA) systems with sampled-data switching, where the switching action is executed based upon a condition on the state at each sampling time. First, an algebraic characterization for the problem to be feasible is derived. Next, an optimal continuous-time controller is derived for a general class of PWA systems with sampled-data switching, for which the optimal control problem is feasible but whose subsystems in some modes may be uncontrollable in the usual sense. Finally, as an application of the proposed approach, the high-speed and energy-saving control problem of the CPU processing is formulated, and the validity of the proposed methods is shown by numerical simulations.     

Analysis of discrete-time piecewise affine and hybrid systems

In this paper, we present various algorithms both for stability and performance analysis of discrete-time piece-wise affine (PWA) systems. For stability, different classes of Lyapunov functions are considered and it is shown how to compute them through linear matrix inequalities that take into account the switching structure of the systems. We also show that the continuity of the Lyapunov function is not required in discrete time. Moreover, the tradeoff between the degree of conservativeness and computational requirements is discussed. Finally, by using arguments from the dissipativity theory for nonlinear systems, we generalize our approach to analyze the l₂-gain of PWA systems.     

Approximate explicit receding horizon control of constrained nonlinear systems

An algorithm for the construction of an explicit piecewise linear state feedback approximation to nonlinear constrained receding horizon control is given. It allows such controllers to be implemented via an efficient binary tree search, avoiding real-time optimization. This is of significant benefit in applications that requires low real-time computational complexity or low software complexity. The method has a priori guarantee of asymptotic stability with region of attraction being a close inner approximation to the stabilizable set. This is achieved by ensuring that the approximation error does not exceed the stability margin.     

Optimal control of sampled-data piecewise affine systems

This paper discusses the optimal continuous-time control problem of a class of piecewise affine (PWA) systems, where the switching action of the discrete state is determined at each sampling time according to a condition on the continuous state. Such a system is called here the sampled-data PWA (SD-PWA) system. First, important remarks on the control design of this system via the continuous-(or discrete-)time PWA model are pointed out, which motivate us to use the SD-PWA model. Next, based on the good properties of the proposed model, an optimal continuous-time controller of the SD-PWA systems is proposed.     

Partially observed non-linear risk-sensitive optimal stopping control for non-linear discrete-time systems

In this paper we introduce and solve the partially observed optimal stopping non-linear risk-sensitive stochastic control problem for discrete-time non-linear systems. The presented results are closely related to previous results for finite horizon partially observed risk-sensitive stochastic control problem. An information state approach is used and a new (three-way) separation principle established that leads to a forward dynamic programming equation and a backward dynamic programming inequality equation (both infinite dimensional). A verification theorem is given that establishes the optimal control and optimal stopping time. The risk-neutral optimal stopping stochastic control problem is also discussed.     

Exponential stabilization of discrete-time switched linear systems

This article studies the exponential stabilization problem for discrete-time switched linear systems based on a control-Lyapunov function approach. It is proved that a switched linear system is exponentially stabilizable if and only if there exists a piecewise quadratic control-Lyapunov function. Such a converse control-Lyapunov function theorem justifies many of the earlier synthesis methods that have adopted piecewise quadratic Lyapunov functions for convenience or heuristic reasons. In addition, it is also proved that if a switched linear system is exponentially stabilizable, then it must be stabilizable by a stationary suboptimal policy of a related switched linear-quadratic regulator (LQR) problem. Motivated by some recent results of the switched LQR problem, an efficient algorithm is proposed, which is guaranteed to yield a control-Lyapunov function and a stabilizing policy whenever the system is exponentially stabilizable.     

Probabilistic reachability and safety for controlled discrete time stochastic hybrid systems

In this work, probabilistic reachability over a finite horizon is investigated for a class of discrete time stochastic hybrid systems with control inputs. A suitable embedding of the reachability problem in a stochastic control framework reveals that it is amenable to two complementary interpretations, leading to dual algorithms for reachability computations. In particular, the set of initial conditions providing a certain probabilistic guarantee that the system will keep evolving within a desired ‘safe’ region of the state space is characterized in terms of a value function, and ‘maximally safe’ Markov policies are determined via dynamic programming. These results are of interest not only for safety analysis and design, but also for solving those regulation and stabilization problems that can be reinterpreted as safety problems. The temperature regulation problem presented in the paper as a case study is one such case.     

Event-driven optimization-based control of hybrid systems with integral continuous-time dynamics

In this paper we introduce a class of continuous-time hybrid dynamical systems called integral continuous-time hybrid automata (icHA) for which we propose an event-driven optimization-based control strategy. Events include both external actions applied to the system and changes of continuous dynamics (mode switches). The icHA formalism subsumes a number of hybrid dynamical systems with practical interest, e.g., linear hybrid automata. Different cost functions, including minimum-time and minimum-effort criteria, and constraints are examined in the event-driven optimal control formulation. This is translated into a finite-dimensional mixed-integer optimization problem, in which the event instants and the corresponding values of the control input are the optimization variables. As a consequence, the proposed approach has the advantage of automatically adjusting the attention of the controller to the frequency of event occurrence in the hybrid process. A receding horizon control scheme exploiting the event-based optimal control formulation is proposed as a feedback control strategy and proved to ensure either finite-time or asymptotic convergence of the closed-loop.     

Solution for state constrained optimal control problems applied to power split control for hybrid vehicles

This paper presents a numerical solution for scalar state constrained optimal control problems. The algorithm rewrites the constrained optimal control problem as a sequence of unconstrained optimal control problems which can be solved recursively as a two point boundary value problem. The solution is obtained without quantization of the state and control space. The approach is applied to the power split control for hybrid vehicles for a predefined power and velocity trajectory and is compared with a Dynamic Programming solution. The computational time is at least one order of magnitude less than that for the Dynamic Programming algorithm for a superior accuracy.     

A novel optimal tracking control scheme for a class of discrete-time nonlinear systems using generalised policy iteration adaptive dynamic programming algorithm

In this paper, a novel iterative adaptive dynamic programming (ADP) algorithm, called generalised policy iteration ADP algorithm, is developed to solve optimal tracking control problems for discrete-time nonlinear systems. The idea is to use two iteration procedures, including an i-iteration and a j-iteration, to obtain the iterative tracking control laws and the iterative value functions. By system transformation, we first convert the optimal tracking control problem into an optimal regulation problem. Then the generalised policy iteration ADP algorithm, which is a general idea of interacting policy and value iteration algorithms, is introduced to deal with the optimal regulation problem. The convergence and optimality properties of the generalised policy iteration algorithm are analysed. Three neural networks are used to implement the developed algorithm. Finally, simulation examples are given to illustrate the performance of the present algorithm.     

Energy-based control for hybrid port-controlled Hamiltonian systems

In this paper we develop an energy-based hybrid control framework for hybrid port-controlled Hamiltonian systems. In particular, we obtain constructive sufficient conditions for hybrid feedback stabilization that provide a shaped energy function for the closed-loop system, while preserving a hybrid Hamiltonian structure at the closed-loop level. Furthermore, an inverse optimal hybrid feedback control framework is developed that characterizes a class of globally stabilizing energy-based controllers that guarantee hybrid sector and gain margins to multiplicative input uncertainty of hybrid Hamiltonian systems.     

Regulator problem for uncertain linear discrete-time systems with constrained control

A necessary and sufficient condition to test the robustness of a regulator of uncertain linear systems with constrained control is given. The candidate regulator for this test is that stabilizing nominal systems. An illustrative example is also given.     

Multistage linear programming for discrete optimal control with distributed-lags

A multistage decomposition scheme is developed for optimizing discrete-time dynamic systems, which include distributed and/or multiple pure delays. The discrete optimal control problem in this paper consists of a system dynamics described by a multidimensional linear difference equation of high-order which is called the distributed-lag model, a linear objective function, and linear state and control constraints. This problem may be solved as a linear program by, for example, a revised simplex method. However, this leads to excessive storage requirement for large problems. Instead, by taking advantage of the staircase-structure of equality constraints (system equation), Dantzig-Wolfe decomposition principle is applied repeatedly in each stage, and an effective multistage decomposition algorithm for distributed-lag models is obtained. Significant advantage of the optimization technique in this paper is that it can handle any number of delay terms in the system without reducing the multidimensional high-order system equation to a conventional larger dimensional first-order system equation (state equation of normal form). Therefore, a substantial reduction of computational burden, the so called curse of dimensionality, in the existing discrete optimal control algorithms, is obtained. A numerical example of a congested urban road traffic control problem with many delays is included.     

A formula for the optimal cost in the general discrete-time LEQG problem

This paper is aimed at deriving an explicit formula for the optimal cost for discrete-time linear exponential-of-quadratic Gaussian (LEQG) control problems. We make direct calculations for the general case with cross terms in the cost and noise covariance matrices using an information-state approach.     

Reachability analysis of continuous-time piecewise affine systems

This paper proposes an algorithm for the characterization of reachable sets of states for continuous-time piecewise affine systems. Given a model of the system and a bounded set of possible initial states, the algorithm employs an LMI approach to compute both upper and lower bounds on reachable regions. Rather than performing computations in the state-space, this method uses impact maps to find the reachable sets on the switching surfaces of the system. This tool can then be used to deduce safety and performance results about the system.     

Robust control of linear discrete-time systems

Given a linear discrete-time system with additive disturbances, a general methodology for designing a stable control algorithm is shown. The approach is Lyapunov-based with certain liberty of tailoring the candidate function for a given problem. Comparison to the existing solutions based on a variable structure approach is given.