An Introduction to Cyber-Physical Systems

Introduction

Put in simple terms, a cyber-physical system (CPS), as the name suggests, is a dynamical system that exhibits both discrete (cyber) and continuous (physical) dynamic behavior. Due to their distinct mixed discrete-continuous dynamics, they are also known as hybrid systems.

We model such systems using mathematical structures aptly named hybrid automata. Let us now look into these structures to get a deeper understanding of what a CPS is.

What exactly is a hybrid automaton?

Consider as an example of CPS a bouncing ball. Any object under the influence of gravity will certainly act according to the laws of Newtonian mechanics, which are given by ordinary differential equations (ODE). If the ball in question has a height x and a velocity v, and we assume the acceleration due to gravity to be g, we can then come up with a set of ODEs for the ball's physics:

• x' = v
• v' = -g

One more thing to keep in mind is that the value of x can never be negative, because a negative height does not make sense. This condition is always true, and is known as the invariant of the continuous state defined by the aforementioned flow.

Nothing too fancy, right? Let us name this state as B1. This set of ODEs is then known as the flow of the state, which is sufficient to describe the continuous dynamics of the state. The set of all such states (locations) together with their flow defines the continuous dynamics of the system. In our case, there is only one location.

Note. The nature of flow in a hybrid automaton is often used to classify hybrid automata into different classes. The example we are dealing with has a set of linear ODEs as its flow, hence is known as a linear hybrid automaton (LHA). If the flows are given by a set of affine ODEs, we call it an affine hybrid automaton (AHA), or more generally, a nonlinear hybrid automaton (NHA).

Now, consider the case when the ball hits the ground. Obviously, the ball will bounce back with a reduced velocity based on some dampening coefficient, which we denote by c. This c depends upon several factors such as the hardness of the surface, the air resistance, and so on, but let us not get into that mess.

In other words, when x reaches 0 value and velocity is in the downward direction, then the ball bounces back with a reduced velocity cv in the opposite direction. Mathematically, we express this as

• When x <= 0 && v < 0, then set v to -cv (where 0 < c < 1).

Let us call this discrete event as rebound. This is an example of a jump, which checks for a guard condition (x <= 0 && v < 0) which, when met, triggers an assignment, namely setting v to -cv. The set of all such jumps together defines the discrete dynamics of the system. In our case, there is only one jump.

Note. We define the guard condition as x <= 0 instead of x == 0. This is because computers can't really handle continuous dynamics, and any ODE computation must be done in very tiny discrete steps, creating an approximation of continuity. As such errors may often creep up, resulting in x jumping from a very negligible positive value to a very negligible negative value instead of actually hitting zero.

All of this looks too verbose. So we must find some way to represent all of this more compactly. This is exactly where the hybrid automata comes in. One can think of hybrid automata as a finite state automata with each state having its own set of ODEs to describe different continuous dynamics that the system can attain, while the state transitions describe the discrete dynamics in the system.

Consider the following diagram:

This diagram represents every information we just covered, while noting that the ball was dropped from a height h without applying any additional force (free fall under gravity). This is known as the init or initial condition. We also observe that the execution of the automaton begins at B1, which is our initial location.

Of course, this is a very simplistic example with a single location B1 and only two variables. In real world, we often deal with complex CPS which may contain tens of locations and hundreds of variables.

Note. At x = 0, both the invariant of B1 and the guard of the transition Rebound is satisfied. As such, the automaton has a choice to either dwell in the location B1 until the invariant is no longer satisfied, or take the transition. This introduces nondeterminism in the system, but we won't be getting into that today.

Okay, I get it. Now give me some code!

I'm glad you asked. Let us code this simple bouncing ball example in Python. We will use networkx for implementing the discrete structure and store the continuous dynamics as a set of strings.

import networkx as nx

''' Must use digraphs to model the discrete structure
because having a transition A -> B does not mean
we also have the transition B -> A '''

G = nx.DiGraph()
G.add_node('B1')
G.add_edge('B1','B1',label="Rebound")

''' Now let us add the dynamics as meta-data.
Let c be 0.7 and g be the usual 9.8. '''

loc_dict = {} # Stores flow and invariant for each location
flow = ["x'=v", "v'=-9.8"]
inv = "x>=0"
loc_dict['B1'] = (flow, inv)

trans_dict = {} # Stores guard and assignment for each transition
guard = "x<=0 && v<0"
asgn = "v=-0.7*v"
trans_dict["Rebound"] = (guard, asgn)

''' Let us add the initial conditions, assume h = 10'''
init = ["x=10", "v=0", 'B1']

In order to execute (simulate) the hybrid automaton in question, we must have some mechanism to parse these expressions and pass them to some ODE solver, which will solve these and give solutions. All that and we haven't even implemented the invariant anywhere in our code yet. This added complexity makes the entire affair extremely cumbersome.

Ah, great. What do we do then?

Of course one could go about implementing their own hybrid automata library, but several great ones already exist. The industry standard is SpaceEx (not to be confused with Elon Musk's SpaceX) which was developed by the VERIMAG lab of the University of Grenoble.

SpaceEx provides a standardized format to describe hybrid automata as .xml files and implements a tool to parse and execute these files. One can write their own CPS in the easy-to-understand .xml format and run them using SpaceEx. Alternatively, one can also use the SpaceEx model creator, a GUI CPS modelling tool for the more visually inclined.

A more flexible library indeed exists in Python itself called Verse, which was developed by the Reliable Autonomy Group at the University of Illinois Urbana-Champaign and funded by NASA. Verse not only makes the modelling of CPS intuitive but also allows users to design custom algorithms for verifying safety properties in such systems. For a taster, here's how one would model the bouncing ball example in Verse.

The continuous dynamics:

from verse.plotter.plotter2D import *
from verse import Scenario, ScenarioConfig
from enum import Enum, auto

class BallAgent(BaseAgent):

    def __init__(self, id, code=None, file_name=None):
        super().__init__(id, code, file_name)

    # Define the flow
    def dynamics(self, t, state):
        x, v = state # Get the continuous variable values at that step
        dxdt = v
        dvdt = -9.8
        return [dxdt, dvdt]

The discrete dynamics:

# Define the continuous and discrete variables
class BallMode(Enum):
    B1 = auto()

class State:
    x = 0.0
    v = 0.0
    mode: BallMode

    def __init__(self, x, v, ball_mode: BallMode):
        pass

# Define the transitions
def decisionLogic(ego: State):
    c = 0.7
    output = copy.deepcopy(ego)
    if ego.x <= 0: # Guard condition
        output.vx = -ego.vx*c # Assignment
        output.x = 0 # Assignment
    assert all(ego.x >= 0), "No negative height" # Invariant
    return output

And we would simply execute the hybrid automaton as follows:

if __name__ == "__main__":
        # Initialize a scenario and set the decision logic (discrete dynamics)
        bouncingBall = Scenario(ScenarioConfig(parallel=False))
        myball = BallAgent("ball", file_name="./bouncing_ball.py")
        bouncingBall.add_agent(myball)
        
        # Set the initial conditions
        bouncingBall.set_init([[[10, 0]], # Lower bound for init x, v
            [[10, 0]], # Upper bound for init x, v
            [(BallMode.B1)]) # Initial location 

        # Simulate for 40 seconds, where ODE computation is done every 0.01 seconds
        traces = bouncingBall.simulate_simple(40, 0.01)
        
        # Print the trajectory (x vs. t graph)
        fig = go.Figure()
        fig = simulation_tree(traces, None, fig, 0, 1, [0, 1], "fill", "trace")
        fig.show()

And that's it! Upon simulation, we would get a trajectory similar to this:

Take a moment to ponder on that. Why do you think the trajectory looks like this?

Note. Verse's framework is designed for multi-agent CPS (more on that in the future) and offers an alternative way to model CPS than hybrid automata. However, the framework is designed in such a way that every agent in Verse (such as our ball agent) will have an equivalent hybrid automaton, and vice versa. As such, Verse can be effectively used to model, simulate and verify any given hybrid automaton.

But what is it good for?

Excellent question! CPS are found everywhere - in highly autonomous vehicles (think Tesla's self-driving cars and NASA's unmanned satellites), robotics and telecommunication networks, distributed realtime systems, distributed artificial intelligence, surveillance systems, industrial control systems, power systems and smartgrids, coordinated defence systems, and healthcare.

In fact, most of these use cases are often safety-critical, where ensuring the operational correctness is absolutely necessary. Consider, for example, autonomous vehicles, insulin infusion pumps, and so on. Therefore, the formal verification of these system becomes a critical area of study in theoretical computer science and control theory.

Conclusion

To sum up, in this article at OpenGenus, you learnt:

• what a cyber-physical system (CPS) is,
• how we model CPS using hybrid automata,
• how to code your own hybrid automata in Python, and
• application domains of CPS.

In the future, we will dive deeper by exploring more complex types of CPS.