Efficient mode enumeration of compositional hybrid systems

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.