Multi-Agent Cyber-Physical Systems

Introduction

In a previous article, we introduced the concept of cyber-physical systems (CPS). Moving further in our journey into CPS, agent is a term we will be encountering quite a lot. So let's get that off our plate first. Simply put, an agent is an autonomous entity that navigates through a given environment.

In the context of CPS, we can think of an agent as an entity that interacts with the environment in a manner defined by its hybrid automaton. Consider the bouncing ball example we discussed previously. Here, the ball can be though of as the agent, and the nature of its interactions with the environment, such as free fall and rebounding off the ground, is defined by the hybrid automata of the system.

Clearly, so far we've been only talking about single-agent systems - where the hybrid automaton describing the agent's behaviour is as good as describing the entire system itself. However, as we attempt to model complex systems in the real world, we shall soon find that in most cases a single agent will not suffice.

As such, we must talk about multi-agent CPS, where the behaviour of each agent (their interactions with the environment, which comprises mainly of the other agents) is described by their own individual hybrid automaton. Then, if we wish to study the system as a whole, we must look at the collective behaviour that emerges out of these individual hybrid automata. In order to do this, we must take the help of compositional hybrid automata (CHA).

And what is a compositional hybrid automaton?

Now that we are familiar with the language of hybrid automata, let us define a multi-agent CPS by describing a couple of hybrid automata - each representing a single agent in the system:

What does this system do? In order to understand the behaviour of the system as a whole, it is beneficial to talk first about the individual agents: the water tank, the burner, and the thermometer.

The tank initially has a constant temperature x of 20 degrees Celsius (location t4). Only if the burner is turned on (transition ON), the temperature will start to increase as the water starts heating (location t1). There seems to be some mechanism that caps the upper temperature limit to 100 degrees, and when this limit is reached (transition B to location t2) the heating stops. However, the burner must then be turned off (transition OFF) for the water to cool down naturally (location t3). Of course at any point during heating or cooling, we can turn the burner off or on to transition between locations t1 and t3. The dynamics for the tank is described by the hybrid automaton H1.

The burner is initially switched off (location b1). When it is switched on (transition TURN-ON to location b2) it takes about 0.1 seconds time y to actually start the heating process (transition ON to location b3). Similarly, when it is switched off (transition TURN-OFF to location b4) it takes about 0.1 seconds time y to actually stop the heating process entirely (transition OFF to location b1). The dynamics for the burner is described by the hybrid automaton H2.

Note. The ON and OFF transitions in the tank automaton have the same label as the ON and OFF transitions in the burner automaton. This is completely intentional, and this is how the agents communicate with each other. For example, when the burner sends an ON signal to the tank, only then the water in the tank actually starts heating. This is known as label synchronization. A multi-agent CPS may or may not exhibit label synchronization.

The thermometer is much simpler: it continuously measures the water temperature x and sends periodic signals at an interval of 0.1 seconds about whether the temperature is lower than 93 degrees (transition DW93), above 95 degrees (transition UP95) or somewhere in between (transition ε), based on which the managers of the water heating plant can manually switch off the burner if needed. The dynamics for the thermometer is described by the hybrid automaton H3.

Note. The variable x of the thermometer automaton is the same as the variable x of the tank automaton, so that the thermometer can be used to directly monitor the water temperature of the tank. This is another way for the agents to communicate with each other and is known as shared variables. A multi-agent CPS may or may not exhibit shared variables.

When considered together, these three components completely describe the entire system. Naturally, a question arises as to why not use a single automaton to H to describe the system. Of course we can do this, but this comes with a cost. Take a look at how the automaton H looks like based on our descriptions of H1, H2 and H3:

This is a complete mess and does not seem human-readable at all. Indeed we must use this hybrid automaton H in the backend when we are, say, mathematically verifying the safety specifications of the system. However, when we are describing the system itself, we are much better off describing the individual components each as a hybrid automaton. This is exactly where CHA comes in.

In this framework, we describe each agent (component) in our system as a hybrid automaton and the entire system can then be studied using the single automaton of the system which we showed above. This automaton is known as the CHA of the system, and is obtained by a mathematical operation known as composition (which we denote by the symbol '.'), from where CHA gets its name.

So how do I compose hybrid automata?

Of course, talking about the composition of the three hybrid automata into a single CHA seems daunting, but don't worry! The '.' operation is commutative as well as associative, which means that we can start with any two components of our choice and go on composing recursively, always ending up with the same final CHA! How does this help? Well, let us consider the tank and the thermometer first. Once we understand how to compose H1 and H3 to get (H1.H3), we can simply compose H2 and (H1.H3) to get H = H1.H2.H3 = H2.(H1.H3) without any ambiguity.

This is where the fun begins. At the heart of automata composition is a graph operation known as the product of two graphs. Generally speaking, graph products are binary operations on graphs which input two graphs to create a new graph. The vertex set of the new graph is the Cartesian product of the vertex sets of the input graphs, while the edge set is constructed via some rule. We are particularly interested in strong products. We'll talk about them in a bit. Before that, let us revisit the concept of Cartesian product of two sets. Given two sets, their Cartesian product is defined as all possible ordered pairs that can be formed by selecting one element from the first set and another element from the second.

A classic example of Cartesian products is the standard deck of 52 cards. The ranks {A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2} form a 13-element set. The card suits {♠, ♥, ♦, ♣} form a four-element set. Ranks × Suits returns a set of the form {(A, ♠), (A, ♥), (A, ♦), (A, ♣), (K, ♠), ..., (3, ♣), (2, ♠), (2, ♥), (2, ♦), (2, ♣)}. Suits × Ranks returns a set of the form {(♠, A), (♠, K), (♠, Q), (♠, J), (♠, 10), ..., (♣, 6), (♣, 5), (♣, 4), (♣, 3), (♣, 2)}. Since the order of elements in the pair are irrelevant in our case, these two products are bijective (that is, can be treated as one and the same), and can be expressed as {{A, ♠}, {A, ♥}, {A, ♦}, {A, ♣}, {K, ♠}, ..., {3, ♣}, {2, ♠}, {2, ♥}, {2, ♦}, {2, ♣}}.

Similarly, let us consider two directed graphs as follows:

The vertex sets of the two graphs are given as {1, 2, 3, 4} and {5}. The Cartesian product of the two sets is given as {{1, 5}, {2, 5}, {3, 5}, {4, 5}}. This is the vertex set of the graph product. For strong products, an edge exists between vertices {u, u'} and {v, v'} if and only if either of the following conditions are met:

• u = v and u' is adjacent to v', or
• u' = v' and u is adjacent to v, or
• u is adjacent to v and u' is adjacent to v'.

Following these rules, the strong product for the given two graphs will look like this:

Note. There are several other kinds of graph products based on what rule is being used to construct the edge set. One such product is the lexicographic product, which confusingly enough is also called graph composition. Don't get confused though; strong products are but a special case of graph composition - all strong products are graph compositions but all graph compositions are not strong products.

Let us now return to the subject of hybrid automata composition. In our discussion of strong products, we talked about taking the Cartesian product of the two graphs as the vertex set of the new graph. But in case of hybrid automata, it's not just about the graph structure anymore. Each location in an automaton also has its own flow and invariant. Aptly then, the flow/invariant of the product location is given as one where the flow/invariant of both the constituent locations hold.

Similarly, each transition has a guard and an assignment. In cases where one location in the pair is fixed and the other is undergoing the transition, the guard/assignment of the transition in the CHA is same as the guard/assignment of the corresponding transition in the input automaton. In cases where both the locations are undergoing a transition, the guard/assignment of the product transition is given as one where the guard/assignment of both the constituent transitions hold.

In case of the inits, the init of the CHA is similarly given as one where the inits of both the components hold. The initial location {u1, u2, ..., uk} for the CHA H1.H2...Hk is chosen such that u1 is the initial location of H1, u2 is the initial location of H2 and so on.

As an example, let us finally take a look at the composition H1.H3, which we are now well-equipped to understand:

Similarly, the chaotic mess that is H = H1.H2.H3 should hopefully make a bit more sense to you now.

Why do you think it seems reasonable to use strong products for the composition of hybrid automata?
(Hint: Think about the simulation of a two-agent CPS. Each agent is moving autonomously in the system following their hybrid automaton. At any point in time, the state of the CHA can be given by looking at the states of the components simultaneously.)

Um... where's the code?

CHA is not a easy affair. Different authors define it in a slightly different manner. The fringe cases are particularly heavily debated. For example, HyST (Hybrid Source Transformer/Translation) is a tool developed by Bak et al. that provides a framework for working with hybrid automata, including a flatten transformation pass for automata composition. While HyST allows composition in cases where inits, invariants or guards are unsatisfiable, it does not in cases where flows or assignments are unsatisfiable.

In the previous article, we already talked about the Verse library and how it makes the modelling of CPS accessible. Verse is extremely capable when it comes to multi-agent systems, but it also ships with certain limitations - such as all agents requiring the same state, and lack of support for shared variables. As such, implementing the tank-burner-thermometer system in Verse is complicated to the point of near-impossibility. However, the model editor tool of SpaceEx provides a GUI interface for this and is suited for modelling this system.

In the upcoming article, we discuss about robot swarms as multi-agent CPS. Verse proves its mettle such scenarios, and therein we discuss in detail how to implement a swarm of robots in Verse.

Note. It is important to distinguish between homogeneous multi-agent CPS and heterogeneous multi-agent CPS in this context. Homogeneous multi-agent CPS consists of agents of the same type, characterized by a single component hybrid automaton (with the same underlying structure) - for example, a swarm of robots. Heterogeneous multi-agent CPS, on the other hand, consists of agents of different types, characterized by several different component hybrid automata in the system - as was the case in our tank-burner-thermometer CPS.

Conclusion

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

• what a multi-agent CPS is,
• how we model multi-agent CPS using compositional hybrid automata (CHA),
• how we compose several components into a single CHA, and
• challenges of modelling heterogeneous multi-agent CPS in Verse and how SpaceEx excels in this.

In the future, we will explore homogeneous multi-agent CPS in greater detail.