Efficient mode enumeration of compositional hybrid systems

Abstract

A hyperplane arrangement is a polyhedral cell complex where the relative position of each cell of the arrangement and the composing hyperplanes are summarised by a sign vector computable in polynomial time. This tool from computational geometry enables the development of a fast and efficient algorithm to translate the composition of discrete-time linear hybrid systems into an equivalent piecewise affine model and to determine if the composition is well posed. The tool also provides information on the real combinatorial degree of the system which can be used to reduce the size of the search tree and the computation time of the optimisation algorithms underlying optimal and model predictive control. Examples are presented illustrating the algorithm and showing its computational effectiveness.

Keywords:

• hybrid system
• composition
• hyperplane arrangement
• mode enumeration
• discrete hybrid automaton

Acknowledgements

This work was partially supported by the EU research project IST-2001-33520 Control and Computation. The work was conceived and largely prepared when the first two authors were with the Automatic Control Laboratory at ETH Zurich. The authors would like to thank Alberto Bemporad and Komei Fukuda for inspiring discussions, and Mato Baotić and Komei Fukuda for sharing their tools.

Notes

Notes

1. Note that, in general, the sign vector is defined such that its image is {−, 0, +}, where the ‘0’ element corresponds to . Cells with ‘0’ markings are lower dimensional and not meaningful in the context of PWA systems.

2. 𝒥 = ℐ holds, if all modes ℐ of the SAS are feasible.

3. As in the last section x _i , u _i and y _i encompass both real and binary components. Furthermore, and accordingly for 𝒰 _i and 𝒴 _i .

4. Since the state-update functions do not influence the polyhedral partition, they are omitted here for brevity.

5. Note that the v ₁-axis has been artificially restricted to −2 ≤ v ₁ ≤ 7 to facilitate the plotting.