Results summary

A Modular Structural Analysis of DAE Systems

System modeling tools are key to the engineering of safe and efficient Cyber-Physical Systems (CPS). Although ODE-based languages and tools, such as Simulink  85, are widely used in industry, there are two main reasons why DAE-based modeling is best suited to the modeling of such systems: it enables a modeling based on first principles of the physics; it is physics-agnostic, and consequently accomodates arbitrary combinations of physics (mechanics, electrokinetics, hydraulics, thermodynamics, chemical reactions, etc.).

The pioneering work by Hilding Elmqvist  61 led to the emergence of the Modelica community in the 1990s, and the DAE-based modeling language of the same name  17 has become a de facto standard, with its object-oriented nature enabling a component-based modeling style. Its combined use with the port-Hamiltonian paradigm  91 results in a methodology that is instrumental to the scalable modeling of large systems, additionally ensuring that the model architecture preserves the system architecture, in stark contrast to ODE-based modeling  23, 25.

Consequently, DAE-based modeling requires that Modelica tools properly scale up to very large models. However, although Modelica enables the modeling of extremely large systems, its implementations  95, 66 are often not capable of compiling and simulating such large models. Scaling has been and still is a subject for sustained effort by the Modelica community  47, and although HPC issues belong to the landscape  37, a more specific issue is of uttermost importance for the Modelica language.

In the first steps of the compilation of a Modelica model, its hierarchical structure is flattened, thanks to a recursive syntactic inlining of the objects composing it. See  17, Section 5.6 for a complete definition of this flattening process. The result is an unstructured DAE that can be exponentially larger than the source model. The structural analyses that are required for the generation of simulation code (namely, the index reduction of the DAE system, followed by a block-triangular form transformation of the reduced-index system) are then performed on this monolithic DAE model. As the compilation process does not fully take advantage of the hierarchical nature of the models it has to handle, the modeling capabilities offered by the Modelica language are undermined by performance issues on the structural analysis itself  70, 69. Additionally, model flattening poses a challenge when attempting to extend DAE-based modeling to higher-order modeling or dynamically changing systems  38, 40, 39.

In 9, a new modular structural analysis algorithm is proposed that takes full advantage of the object tree structure of a DAE model. The bedrock of this method is a novel concept of structural analysis-aware interface for components. The essence of a component interface is to capture the necessary information about a Modelica class that needs to be exposed, in order to perform the structural analysis of a component comprizing instances of the former class, while hiding away useless information regarding the equations and all protected features it may contain.

In order to compute a component interface, one has to be able to perform the structural analysis of the possibly non-square DAE system that this component encapsulates, and to use the interfaces of the components it aggregates in this analysis. We base our algorithm on Pryce’s $\Sigma$ -method for index reduction  89, which essentially consists in the successive solving of two dual linear integer programs. The striking difference with Pryce’s algorithm is that these problems are solved by parts, in a scalable manner.

Putting all of this together, it is then possible to perform a modular structural analysis, in which structural analysis is performed at the class level, and the results can then be instantiated for each component of the system model, knowing its context. Hence, structural information at the system level is derived from composing the result of component-level analysis. Modular structural analysis yields huge gains in terms of memory usage and computational costs, as the analysis of a single large-scale DAE is replaced with that of multiple smaller subsystems. Moreover, the analysis is performed at the class level, meaning that a single structural analysis is needed for all system components that are instances of the same class.

Fault Diagnosability Analysis of Multi-Mode Systems

A new collaboration between the Hycomes and the University of Linköping (Sweden) has started this year on the topic of system diagnosis, based on multimode DAE systems.

Fault detection and diagnosis are important for the health monitoring of physical systems. Model-based approaches for single-mode, smooth, systems is a well-established field, supported by a large body of literature covering various approaches like structural methods  33, parity space techniques, and observer-based methods  72.

While single-mode systems are often described using differential algebraic equations (DAEs), the modeling of non-smooth physical systems yields switched DAEs, also known as multimode DAEs (mDAEs), which combine continuous behaviors, defined as solutions of a set of DAE systems, with discrete mode changes  98, 27. Direct application of traditional fault diagnosis methods to all possible configurations of multi-mode systems quickly becomes intractable, as the number of modes tends to be exponential in the size of the system. The method proposed by  75 works around this issue by coupling a mode estimation algorithm with a single-mode diagnosis methodology, akin to just-in-time compilation in computer science. This approach unfortunately puts the burden on solving mode estimation problems, which often turn out to be intractable for the same reason.

Structural fault detectability and isolability is a graph-based method to evaluate diagnosability properties on DAEs  65. It is based on the Dulmage-Mendelsohn decomposition (DM), a building block of the structural analysis of equation systems. In 11, we show how its extension to multimode systems, introduced in 4, can be applied in the context of structural fault detectability and isolability of mmDAEs  68. Building upon our previous research studies, the methods presented in this paper represent advancements in diagnostic methodologies for multi-mode systems, providing novel ways to study the diagnosability of multi-mode systems without enumerating their modes.

The case study used throughout this article is a model of a reconfigurable battery system, in which switching strategies enable to produce an AC output without relying on a central inverter  19. This model is parametrized by the number of battery cells, so that both the inherent complexity associated with the diagnostics of such systems and the scalability of our approaches can be addressed.

Mixed Nondeterministic-Probabilistic Automata

Graphical models in probability and statistics are a core concept in the area of probabilistic reasoning and probabilistic programming-graphical models include Bayesian networks and factor graphs. For modeling and formal verification of probabilistic systems, probabilistic automata were introduced. A coherent suite of models consisting of Mixed Systems, Mixed Bayesian Networks, and Mixed Automata is proposed in 8. This framework extends factor graphs, Bayesian networks, and probabilistic automata with the handling of nondeterminism. Each of these models comes with a parallel composition, and we establish clear relations between these three models. Also, we provide a detailed comparison between Mixed Automata and Probabilistic Automata.

On Continuous Solutions for Linear Complementarity Systems

Hybrid systems are dynamical systems alternating between continuous-time dynamics, called modes, and nonsmooth transitions between modes. Linear complementarity systems (LCS) form a special class of hybrid systems with an exponential number of modes and a linear differential algebraic equation in each mode. LCS are for instance used to describe mechanical and electrical systems featuring perfect contacts or ideal switches. For example, the ideal (Zener) diode is a 1-dimensional LCS with two modes: a passing mode in one direction and a blocking mode in the other direction. While seemingly simple, little is known about the existence, and eventually uniqueness, of continuous solutions (in the state space). The only known sufficient condition is too strong as it requires the existence and uniqueness of solutions for the underlying linear complementarity problem (LCP) which, for a fixed matrix $M$ and a given vector $q$ , asks whether there exists a pair of vectors $(w,z)$ satisfying $w–Mz=q$ , $w,z\ge 0$ , and $w.z=0$ . $M$ is said to be a Q-matrix when a solution exists for all $q$ . It’s worth noting that characterizing Q-matrices is an open problem since the sixties even for low dimensions. Motivated by generalizing the known sufficient conditions for the existence of continuous solutions for LCS, we were naturally led to better understand Q-matrices. In this work, we focused on the regions where no solution for a given LCP exists. We showed that such holes occur only in specific locations. We then exploited this property to fully characterize Q-matrices for $n\le 3$ .

Characterizing Q-matrices for any finite dimension $n$ is still an open problem despite a large palette of attempts ranging from linear algebra to convex analysis all the way to the homology of simplicial sets. The novelty of our approach 10 relies on using geometric and topological intuitions to locate the regions for which the LCP doesn’t have a solution. This property allowed us to reduce the spatial case to finite planar problems that we were able to enumerate and solve. Our characterization is a program enumerating a long list of (symbolic) constraints on the entries of the matrix $M$ . The matrix is a Q-matrix if and only if all the constraints are satisfied. Such approach is for instance useful to generate examples (or counter-examples) to either solve existing conjectures or to improve our current understanding of the problem. For instance, we were able to find an example of a non-regular Q-matrix in dimension 3 (the smallest dimension for which such an example was known was $n=5$ ). This is a joint work with Christelle Kozaily.