From Equations to Code with Constraint Graphs

February 2, 2022

Share This Article

Are you an automotive engineer who uses mathematical models for the development of embedded controls? And have you ever looked inside your math problem? This question sounds ridiculous, doesn’t it?
Well, with constraint graphs you can do this!

Chances are you’re not familiar with constraint graphs. Luckily, you’re only two paragraphs away from finding out more! In this blog series you’ll learn – and see! – how ETAS SCODE-CONGRA helps to analyze mathematical models graphically and solves difficult computational problems automatically with the use of computer algebra systems in the back, or numerical methods eventually.

But let’s start more general: Which math problems are we talking about?

Physical Models in Embedded Control Systems

It’s not a secret: Mathematical models of physical processes, or just physical models, are essential in modern embedded function development. Many tasks as systems analysis, controls design and optimization can be done efficiently if a precise model is available. Some other applications as virtual validation or offline calibration would never be possible without a process model.

We also deploy physical models directly in the embedded software. Ultimately, we want to reason physically on complex control tasks online: Can the system performance be increased, even at safety-critical situations and can we still operate economically with limited compute and bounded actuation signals? Many advanced concepts presume to have an executable model in the ECU software. Here are some applications:

Infer internal variables with virtual sensors (state observers) to replace costly physical sensors
Online diagnosis functions to find defects early, reducing the risk of damaged components
Feed-forward and feed-back control schemes which rely on predicted states

We at ETAS know the objectives as we support our customers developing best-in-class embedded systems on a daily basis.

Manual Model Implementation

Having obtained a model that is based on equations, implementation often enough means to solve math puzzles.
Here’s an algebraic example to demonstrate the procedure. Depicted below in Figure 1 you see a rectangular triangle and the related math. Assume you want to write a program that computes the angle $\beta$ from the area $A$ and the side length $b$ .

Is that possible? What would it take to implement the model?

Figure 1: Rectangular triangle and corresponding equations. If you don’t recognize the equations, a quick web search will help you with the first principles.

Solving for the Unknowns

Independent of the programming language, what must be found is a sequence of assignments from knowns to unknowns. I did that for you with the triangle.

Given $A$ and $b$ , compute $a$ from Equation $R_4$ .
With $a$ and $b$ , via Equation $R_1$ , infer $c$ .
(Take the positive of both solutions as we’re talking about lengths!)
Having $a$ and $c$ , obtain the angle $\alpha$ from Equation $R_3$ .
Knowing $\alpha$ , find the value of $\beta$ with Equation $R_2$

We have found what we call a computational path through the model. That was fun, wasn’t it?
The triangle is by far not the most complicated model – this is why I chose it. But it already shows that finding a solution typically requires some brainpower and enthusiasm. And maybe a coffee to double-check the results…

Coding

Now, what about the program that returns $\beta$ according to the inputs $A$ and $b$ ?
The sequence of assignments from above must be transferred into our favorite programming language, but I guess you know how to proceed from here.
Just keep in mind that coding requires extra attention because small implementation errors are easier to produce than to find.
My personal experience: There will be bugs or undesired exceptions in the first attempt.

Testing

Finally*, who asserts that the original model equations are really happening in the code? You better design some test cases to qualify the program before merging into the stakeholder’s repository.
*Some might argue that writing tests should happen simultaneously or even previous to coding – I’m with you but that would break my argumentation.

So much about the problem statement – how does SCODE-CONGRA help?

Acausal Modeling with Constraint Graphs

Model implementation with SCODE-CONGRA is done in 3 steps – and they are remarkably quicker than the manual procedure above.

Undirected System: Linking Variables

The origins of constraint graphs stem from a branch of set theory in mathematics which is known as constraint theory. The compelling idea is that variables in systems of equations are constrained either by their own allowed ranges or by the constraints of adjacent variables, propagated through the equations then. If you want to dive deeper into the topic, you’ll find those links useful 1, 2.
For us, constraint graphs represent mathematical systems, well, graphically and they reveal the underlying structure of the model. The basic principles are easy:

Variables and Equations are Nodes
(of two different types, we therefore speak of Bi-partite Graphs)
Variables are linked with an Equation if and only if the Equation contains these Variables

A Constraint Graph Model has no computational direction initially. We can set up the system in SCODE-CONGRA by defining four equations just as we read them from Figure 1. Implicit formulas are totally allowed and thus no manual reformulation must be considered. Variables are created (or recognized if already exist) and connected automatically.

Figure 2: Undirected Constraint Graph: Variables and Equations are represented as circles and boxes respectively. Only Variable $\pi$ is connected with an arrow because it was specified as fixed Variable with numerical value $\pi \approx 3.14159$ .

See in Figure 2 what a constraint graph for the triangle example looks like. Note that the computational direction hasn’t been modeled yet – you might recognize this concept from other acausal modeling languages.

Computational Flow: Assigning Inputs

Only after setting up the system we consider the actual task: Compute $\beta$ from $A$ and $b$ .
Such a computational flow is viewed as an instance of the System, and within this flow we decide which variables we know. Selecting $A$ and $b$ as inputs, shown colorized blue in Figure 3. What happens simultaneously is that SCODE-CONGRA shows which variables can be computed, green variables, and in which order, marked by the arrows.

Figure 3: A computational flow of a SCODE-CONGRA system: Decide on the variables you know – Input variables become blue– and decide which variables you want to compute explicitly – Designated output variables are marked with a bold border.

Compare with the previous section: You’ll find exactly the computational path as described verbally – with ultimately no manual efforts but automated structural analysis from constraint graph theory.

Automated Code Generation & Verification

From a user perspective, the last step to create a program that implements the computational flow actually demands no additional work. Once a legal computational flow (that is the flow is neither under nor over constraint and the desired output variables can be computed) has been found, SCODE-CONGRA generates code automatically. The preferred programming language and options can be specified in the tool preferences – and you’re done.

Enjoy your model implementation as a class method in plain C code or compiled as FMU, as ETAS ASCET, or as MATLAB® function or packed in a SIMULINK® block with only one click from here.

The testing procedure is beyond the scope of this article, but it is worth to mention that we offer a mechanism to ensure the original equations have been implemented in the program.

The Second Flow is for Free!

Here comes the trick! Acausal, or equation-based modeling, as with SCODE-CONGRA has a major advantage over classic block-diagram modeling: The math is not directed in the first place. But what does that mean?

Think of another computational request to the triangle: What’s the area $A$ given the lengths $b$ and $c$ ?
Since the conceptual separation between (undirected) system to store the model information and (directed) computational Flow to define the implementation details we can only create a second flow from the same System.

Figure 4: The computational Flow from $b$ and $c$ to $A$ does not require all model equations – what is greyed out will not appear in the code.

See Figure 4 for the resulting flow: The structural analysis shows that we must only make use of half of the model equations. Also the code generator is designed in such a way that the generated program will only contain what is needed – hence it avoids dead code and helps saving resources and runtime.

One of the major strengths of SCODE-CONGRA is that once the system modeling has been completed – and we can easily review the undirected equations – we can create as many computational flows as we want. The additional efforts are negligible: No manual math, no error-prone coding and no tedious software (component) testing.

Think about writing the program from the second flow manually: You would have to start from scratch! Ouch!

What about the third Flow?

Because it’s so easy, here comes another flow: Given the variables $A$ and $c$ , can we compute the other variables? Let’s try!

Figure 5: Constraint graph analysis reveals an algebraic loop. There underlying problem is a circular argumentation: To compute variable $a$ , either way from equation $R_1$ and $R_4$ , we must know $b$ but the value of $b$ in turn depends on $a$ .

Something is different in the flow from Figure 5: The yellow part of the constraint graph has no arrows. Actually we have detected an algebraic loop, which tells us that finding a sequence of assignments is not as straightforward as in the previous flows.

What algebraic loops are exactly, and how SCODE-CONGRA can solve them with some tricks – symbolically or numerically – will be discussed in the next article of this series.

Constraints graphs allow inspection and solving!

Summary

In this article we learned why our customers like constraint graphs to increase productivity in their embedded systems development:

Bring mathematical equations to code – easy, fast and safe modeling
Understand the model – deep insights from structural analysis
Acausal modeling – reuse and invert models at no efforts
Reformulation and solving is done by computer algebra systems
Seamlessly integrate generated components into existing software projects
Automatic verification – the original equations are in the code
Detect and resolve computability issues immediately

If you want to know more about SCODE-CONGRA, or if you’re curious about what your models look like as constraint graphs, don’t hesitate to contact me directly at Henner.Schmidt@etas.com.