Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Modeling and Reach-Set Computation for Analysis and Optimal Control of Discrete Hybrid Automata


F.D. Torrisi

vol. Diss. ETH Nr 15064

In this thesis we present a computational framework for modeling hybrid systems in discrete-time. We introduce the class of discrete hybrid automata (DHA) and show its relation with several other existing model paradigms: piecewise affine systems, mixed-logical dynamical systems, (extended) linear complementarity systems, and min-max-plus-scaling systems. We present the language hysdel{} (HYbrid Systems DEscription Language), a high level modeling language for DHA, and a set of tools for translating DHA into any of the hybrid models mentioned above. We provide a tool to compute the real combinatorial degree of a compositional DHA. This information can be used to reduce the size of the search tree and the computational time of the optimization algorithms underlying optimal and model predictive control.

In order to solve analysis and control problems of hybrid systems, we extend the tools for polyhedral computation to deal with general problems. We address the issue of recognizing the convexity of the union of two or more polyhedra and the computation of the convex union. We also propose several techniques for approximating a polytope by a collection of axis parallel boxes.

We present a methodology for computing the set of states that a discrete-time affine hybrid system can reach by starting from a given set of initial conditions and under the effect of exogenous inputs to the system, such as disturbances, within a prescribed range. The importance of providing an efficient tool to compute this set is twofold. First, we show how to use reachability analysis to assess robust stability, safety, and liveness properties of the hybrid system. Second, we show how the reach-set computation machinery can be embedded in an optimization procedure to solve quite general hybrid optimal control problems.

Several examples and applications show the versatility of the presented tools. Among others, we present an automotive application where we model a power train using HYSDEL, we synthesize an optimal controller and we analyze an alternative heuristic cruise controller. We also discuss the application of our verification procedure to the batch evaporator benchmark problem.

Finally we show how a combination of multi-parametric quadratic programming and reachability analysis solves the infinite-time constrained linear quadratic regulator problem. The algorithm outperforms all comparable multiparametric quadratic programming approaches in terms of off-line and on-line computation speed.

Further Information


Type of Publication:

(03)Ph.D. Thesis

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@PhDThesis { Xxx:2003:IFA_51,
    author={F.D. Torrisi},
    title={{Modeling and Reach-Set Computation for Analysis and Optimal
	  Control of Discrete Hybrid Automata}},
Permanent link