In this paper we study systems containing uncertainty about quantitative aspects, like delays etc. System design for such systems faces the problem that usually the system's initial configuration is chosen in a sub-optimal way due to these uncertainties. An adaptive system will adjust its configuration whenever it obtains new knowledge about the uncertain aspects. In our setting we like to derive the optimal configuration from the system's model. Therefore our models have to include a description of the uncertainties as well. To handle the change of knowledge at run-time, we integrate the model into the run-time system: models@run.time Adaptation of the configuration often requires to evaluate diferent variations of the model, which arise from the uncertainties. To evaluate the impact of diferent configurations, we simulate a digital twin of the system. Therefore, we need a formalism that allows for an easy simulation of models. To simplify the approach, we would like to use the same formalism for the simulator and the system model, i.e. we use a formalism that is able to execute itself as a sub-system. As our system model is based on Petri nets we use the reflexive approach of Hornets, which follow the Nets-within-Nets principle. In this paper, we will specify a Hornet model to handle digital twins during the planning phase of the well-known MAPE-loop (monitor-analyse-plan-execute). A simple scenario based on stochastic workflow Petri nets will serve as a proof-of-concept.
Process models are usually based on quantitative aspects – like duration, delays etc. While the general process structure is often well-understood, there are often uncertainties about the quantitative aspects. Assume that we have to configure the system w.r.t. these quantitative aspects, e.g. we have to define a selection logic that minimizes total delay. Due to the uncertainties in the parameters it is highly likely that the chosen configuration is sub-optimal and has to be adjusted whenever our knowledge about these quantitative aspects improves over the running time via observations.
Therefore we advocate to follow the models@run.time approach and use the system model
as a part of our running system that describes the knowledge about it (K). This knowledge is
used in the following way: We monitor our system at run-time (M); observations are analysed
whether we have to correct our estimation of the quantitative parameters (A); whenever we
adjust, this may lead to (re-)planning of our configuration (P); the new configuration is rolled
out in the execution step (E). These four steps constitutes the phases of the well-known MAPE-K
execution loop [
Adaptation of the configuration often requires to evaluate diferent variations of the model ranging over the regions of uncertainty. Here, we evaluate by simulating variations of a digital twin of the system. So we need a formalism that allows for an easy simulation of models. We advocate a reflexive approach, i.e. we use a formalism that is able to execute itself as a sub-system.
As we model our processes with Petri nets (including time and stochastic operations), we
follow the nets-as-tokens approach, also known as Nets-within-Nets [
The paper has the following structure: In Section 2 we introduce our basic process model:
probabilistic Workflow Nets (PWFN), which are a special variant of workflow nets [
As our basic process model we use the well-known Workflow Nets [
The choice between diferent transitions in the conflict set annotated by a stochastic distribution () : () → R≥ 0, i.e. we have 0 ≤ ()() ≤ 1 and ∑︀∈() ()() = 1. Semantics of Probabilistic Choices The basic semantics of parametric workflow nets (enabled transitions, successor markings etc.) is given the standard way – ignoring the additional stochastic information. However, we can extend the reachability graph into a Markov chain: Each marking enables a set of transitions En() that is the disjoint union of conflict sets due to the free-choice property: En() = 1 ∪ . . . ∪ , ∈ . For each conflict set we have a stochastic distribution , which we can convert into a stochastic distribution over En() via normalisation:
1
En()() = · () for the unique s.t. ∈
Note, that our model is quite similar to Probabilistic Timed Automata [
is either internal or external: = int ⊎ ext . For the internal choice the system itself controls between the alternatives, while for the external choice the environment does.1
The distribution of environmental choices are uncertain. A concrete assignment of distribution functions to the set of external choices is called a scenario and is denoted as . We have : ext → (⋃︀ → R≥ 0) where () : → R≥ 0 for each ∈ ext and undefined otherwise. From this we have to distinguish the internal parameters, which we denote by : int → (⋃︀ → R≥ 0) where () : → R≥ 0 for each ∈ int and undefined otherwise. Let Conf denote the set of all configurations.
The two distribution assignments could be combined into one single an assignment : → (⋃︀ → R≥ 0): We define () := (), if ∈ ext and () := (), if ∈ int .
1In the case of coloured WF-Nets the internal choice could be expressed more appropriate by a function which maps the actual binding to a selection of one alternative.
Given a scenario and a configuration we denote the resulting Petri net as ( ). In our setting we control the distribution of internal choices and we have to configure them in way that optimises our model wrt. some evaluation criteria.2 Whenever is a workflow net we call ( ) a probabilistic workflow net (PWFN) .
Example Figure 2 shows the workflow to perform a study of courses in parallel. The external uncertainty is the failure probability of examinations. Students react on the examination failure rate (given as an external parameter) by adjusting their probability to take additional preparation time and skip the examination (the internal parameter).
We make the assumption that the failure probability decreases with the number of extra
preparation courses: = (· ) where is the basic failure probability and > 0 is some
form parameter (the learning impact).
The Multi-Party Setting Note, that the distinction between internal and external choices
assume a single agent acting in its environment. In a multi-party setting we have diferent
agents = {ag 1, . . . , ag } where each agent controls only a part of the workflow. This
extension is similar to that from LTL/CTL to ATL [
Therefore, each agent observes the actions taken by the other agents to predict their
underlying selection logic, i.e. the decision tree and the succeeding random variables. Once an agent
2Note, that this formulation has a analogy to game models [
Adding Colour: The Adapt-OR We like to discuss an extension for coloured tokens in PWFN. Assume a situated choice: Agents observe a sensor input ⃗ = (1, . . . , ) and have to select one action from a set {1, . . . , }. Assume that agents learn to discriminate diferent situations via a decision tree. Assume further, that for each diferent situation the agent selects the action based on an internal decision logic. We assume that the decision logic is unknown from the outside, so we model it by a random variable.
This selection process is modelled as the Petri Net fragment of Fig. 3. The fragment shows a block where an agent observes the given situation by the sensor values . Here, the variable is compared against the constant 10. Depending on the agent considers himself to be in situation1 or in situation2. Each situation leads to a choice between action 1 and 2, but whenever the agent considers himself to be in situation1 the decision difers from that in situation2. We assume that from an internal perspective the action is chosen in a deterministic way, but from an observer’s perspective the decision process can be described as a random selection in the ratio of 20 to 80 in situation1, while it is 40 to 60 in situation2.
In general we assume that our system is not exactly – it can be any model ′ with ≈ ′, where ≈ ′ denotes that and ′ are (in some sense) similar. We assume that a level of uncertainty induces a set of similar settings for , i.e. the set ( ) = { ′ | ≈ ′}. Usually, a higher uncertainty in increases the size of ( ). We assume that ( 0) is weighted, i.e. we have a weight : ( 0) → R≥ 0 such that ∑︀ ∈( 0) ( ) = 1.3 We can extend this function to a function : Conf → R≥ 0 to all configurations by setting ( ) = 0 for ̸∈ ( 0). When we speak of similar scenarios and ′ this is meant w.r.t. this probability function.
New observations lead to a new estimation of . So, we write where denotes the time. Observations also lead to a recalculation of the uncertainty. Thus we have a time dependent definition of similarity: ( ).
New observations lead to (1) a new estimation +1 and (2) to a new calculation of uncertainty, which induces a new similarity class +1 := ( +1). To decide whether we have to adapt we have to compare and +1. We define the overlap of the current class with its successor +1 as the weighted sum of squares:
∑︁ ∈Conf overlap := 1 −
( ) · (+1( ) − ( ))2
The sensitivity wrt. the overlap is controlled by a meta-parameter that defines how eagerly the system responds: • Whenever overlap ≥ , i.e. these two classes have a high overlap, then is reasonable that is also good configuration for +1, i.e. +1 := . • Whenever overlap < , we trigger the adaption phase, i.e. we have to recompute +1 for +1.
The design goal is to select the optimal configuration * for a given environment model with respect to an evaluation function. Let us assume for a moment that we have perfect knowledge about , i.e. there is no uncertainty; then the choice of the optimal configuration * is straightforward:
* = argmax (eval ( ( )))
However, as our knowledge about the environment model is rather bounded, we cannot assume, that system is exactly – it can be any model ′ with ≈ ′.
Major Challenge: We like to select the value for that maximises the evaluation for a large fraction of the similar models ( ′). So, we have to balance both aspects – quantity and quality (or: large fraction and maximal evaluation) – somehow.
In the following, we propose a selection mechanism based on rankings. We define a weighted score to select the best configuration: For each ∈ ( 0) we evaluate the reward of each configuration ∈ Conf and order them by calculating their rank rank ( ) for a fixed .
Then, we must combine the ranking rank ( ) for all the scenarios into one single evaluation eval ( ). This combination has to balance large fraction vs maximal evaluation somehow.
3For example, if similarity is measured with some distance metrics we could use a -nearest neighbours (KNN) algorithm to compute this set ( ) and we define the probability proportional to the distance. (1) (2)
Here, we assign values to ranks: The first rank is assigned 1 point, a second rank points, a
third rank 2 points, etc. For ∈ [
( ) · (rank ( )− 1)
Here, is a meta-parameter that controls the balance: Assume e.g. that = 1/2, then one scenario with first rank counts as much as two scenarios with rank two or four scenarios with rank four. For a smaller value, e.g. = 1/4, then one scenario with first rank counts as much as four scenarios with rank two or 16 scenarios with rank four. Therefore, a smaller prefers higher rankings in a small spectrum of scenarios over a more broader spectrum with lower rankings. For = 0 we only consider the winning for a scenario, i.e. the evaluation is proportional to the number of scenarios won by . On the other hand, for = 1 all have the same evaluation: eval ( ) = ∑︀ ∈( 0) ( ) · (rank ( )− 1) = ∑︀ ∈( 0) ( ) · 1 = 1. In this case the choice of * is purely random.
In the following we propose a simulation-based way of approximating this configuration ⋆ by exploring the run-time model (i.e. the digital twin). The main idea is to sample the value, i.e. to compute the rankings only for some configurations and for some scenarios.
We use Hornets [
Example We consider a Hornet with two workflow nets 1 and 2 as tokens – cf. Figure 4. To model a run-time adaption, we combine 1 and 2 resulting in the net 3 = (1‖2), i.e. the parallel composition. This modification is modelled by transition of the Hornets in Fig. 4. In a binding with ↦→ 1 and ↦→ 2 the transition is enabled. Assume that (‖) evaluates to 3 for . If fires it removes the two net-tokens from and and generates one new net-token on place . The net-token on has the structure of 3 and its marking is obtained as a transfer from the token on in 1 and the token on in 2 into 3. This transfer is possible since all the places of 1 and 2 are also places in 3 and tokens can be transferred in the obvious way.
Here, the system net is used to describe the MAPE-loop and all ( ) for all and are used as object nets. }Z
Z ⊐
q ZslHHj sl p ⌃ t (‖-)
r l N1 i1- - i- - ri- - i1
N3 3 h net-token produced on by h-1 - h- - rh- - h1
- h3 - rh - - h2
introduce adaptation here:
Hornets uses algebraic operations on the structure of net-tokens, i.e. the formalism allows to
change the net-topology at run-time. This is very useful to model block-structured nets (like
e.g. [
Obviously, second order adaption has a much bigger impact on the change of the system when compared to the first order changes where the fundamental workflow structure remains unchanged. .
Whenever we adjust our environment model from 1 to 2, we change our run-time model from 1 ( ) to 2 ( * ) where * is the new configuration adapted to 2. The complete system net describing the MAPE-Loop is shown in
For the second-order adaption we also change the net itself, e.g. we may replace an action by a complete workflow or replace an and-split ‖ by an sequence ; etc. We adapt by replacing the net with the modified net ′. This extends the MAPE-Loop from Figure 5 by the transition modify model structure via (online) model mining. The resulting loop is shown Figure 6.
A modification of the model structure at run-time demands for a
meta-level model that
specifies which transformations are allowed under which circumstances. We study this
metalevel specification in ongoing work in the context of our specification framework for multi-agent
organisations: Sonar [
In the following we propose a simulation-based way of approximating the optimal configuration ⋆ by exploring the run-time model (i.e. the digital twin). The main idea is to compute scores only for a small set of scenarios and a subset of configurations.
When selecting the best configuration * to react on the environment we are facing two problems: Firstly, usually it is not easy to determine the reward of a given configuration directly. Instead of calculating the value, we advocate for a simulation-based approach, i.e. we evaluate 4Note, that this naturally induces a distributed MAPE-loop. Some authors reserve the term adaption for conceptually centralised systems, and speak of self-organisation in case of distributed systems. We do not make this diferentiation. runs of ( ). Secondly, in most cases the models are too complex to perform an exhaustive evaluation of the complete configuration space, i.e. usually we have a huge (sometimes even infinite) set of scenarios and possible configurations .
In this case we have to operate with a double sampling method, i.e. we generate a sample set of scenarios and a sample of configurations; for each scenario we evaluate the configurations from the sample and combine the evaluation of all scenarios into one overall evaluation.
The planning part including this simulation step is shown in Figure 7. Whenever we adjust our estimation for we generate a family of similar parameters 1, . . . , . We generate several configuration candidates 1, . . . , . For each scenario we evaluate all these ( ), = 1...
However, the relationship of and depend on the uncertainty about : Whenever our uncertainty about is high we have to consider a larger number of similar parameter sets 1, . . . , . Since we like to keep the evaluation time constant, the product · is bounded/fixed. Therefore, a high uncertainty about results in a large number of parameter sets , which restricts the number of configuration candidates under evaluation to a relatively small number. Conversely, a higher certainty in parameter allows for a broader exploration of configuration parameters , i.e. a higher value of .
In the following we demonstrate our method for the example given in Figure 2. The presented Petri nets are freely available online.5 First, we have to describe the (expected) value for a workflow. Each examination comes with some costs and costs increase with the resources spent (e.g. time and money) and the number of additional preparation courses:
costs = (resources spent) · (no of prep courses) We assume that the spent resources increases with the number of failed examinations – to model the increased stress level after a failed examination. Assume that we have − 1 failures and is the first successful examination, then the resources are calculated as (where is some form parameter):
resources spent = , > 0 The reward is the inverse of the costs: reward = (costs)− 1 = ( · )− 1 (5)
Both values, the number of failures − 1 and the number of extra preparation courses taken , are random numbers. Throughout the paper, we approximate the expected reward [reward ] by simulating the SWFN ( ).
Before starting with the planing part of the MAPE-loop (which is done in the following section) we evaluate the reward obtained for a variation of and .
We have the following hypothesis about the model’s behaviour: As we assume that the costs increase with the numbers of failed examinations, it seems reasonable to skip a few examinations (i.e. to increase ) in the case of a high failure probability to increase the chance to succeed. Therefore, we assume that there is an optimal balance between these antagonistic forces.
The workflow net itself is shown in Figure 8; it is an stochastically annotated version (using Renew syntax) of the Petri net shown in Figure 2. Each token is a tuple [, , , ], where is the course id, is the number of extra preparation courses, is the number of examination tries, and is a random number used to resolve the choices. reward ∖ 0.1 The average value for diferent , variants (for = 3.0, = 3.0)
We use Renew [
For each pair of and we calculate the average rewards over the runs. The simulation results are given in Table 1. Here, one can observe, that with increasing failure probability the maximal reward is obtained for increasing training probability . Our hypothesis that students should adapt to higher failure probabilities with longer preparation times is supported by our calculation of rewards. Additionally, we observe that an increasing failure probability reduces the reward in general, i.e. the extra learning time is used to minimise the damage, but cannot compensate the higher use of resources completely.
For our running toy example we can perform a complete parameter sweep, but in general this is out of reach for real models. Instead, as we explained before with Figure 7, our MAPE-loop selects only some variants of (the explore phase) and measure how a sample of values would perform w.r.t. a given (the exploit phase). Finally, we pick that value of that performs well in most of the scenarios, i.e. is a good balance. This could be considered as a tournament situation. above. In the following, we use the value of = 0.5 as our score meta-parameter in (3) to compute eval ( ). The Net of Figure 9 shows the system net which contains net-tokens which have the basic topology of the PWFN from Figure 8 as net-tokens. We use the net-tokens as digital twins to evaluate the parameter settings and select the best value * .
We like to evaluate how well this approach operates when compared to a full parameter search as done before. Therefore, we perform this evaluation many times to reduce random efects. This is done by
Renew itself (the corresponding net is given in Figure 11). We evaluate = 500 tournaments of digital twins.
Table 2 shows the evaluation of several tournaments of digital twins. Note, that the tournament is rather restricted as it considers only = 2 -scenarios for a sample of only = 3 -variants. Therefore, we assume a lot of ‘noise’ in the selection of the tournament’s winner * when compared to the complete parameter sweep as shown in Table 1.
Of course, we know in advance that these values for exploration and exploitation, i.e. and , are too small to result in reliable results. The setting used here is intended for presentation mainly and not intended to be used as a decision method. Nevertheless, the values are in accordance with the general evaluation given in Table 1.
Let us point out some observations for the tournament results given in Table 2: We see that the best value * for all the scenarios is given as * = 0.9, i.e. agents decide to have a rather high probability to go for an extra training time before taking the examination. This is also # wins ∖
Tournament for = 2 scenarios and = 3 configurations (parameters: = 3.0, = 3.0). The table denotes the number of wins for in 500 repetitions. the best choice for for = 0.9, but is diferent from the the best choice of * = 0.7, which has the highest reward value for the scenarios ∈ {0.1, . . . , 0.7} (cf. Tab. 1). Secondly, we can observe that at least the frequency of * = 0.7 is very close to that of * = 0.9 for the smaller values of
∈ {0.1, . . . , 0.7}, while the diference is much bigger for = 0.9.
The reason for this is most likely the nature of the tournament: Since we pick only a small sample of = 3 values for , it is likely that the values = 0.7 and = 0.9 are not both present in a sample. However, they both will outperform the smaller values = 0.1, 0.3, 0.5, which leads to a frequency of equal quality for = 0.7 and = 0.9.
A possible mechanism to overcome this problem will be to iterate the tournament and to increase the selection probability for winning values to increase the probability that interesting candidates will be in the same tournament. This extension will be evaluated in future work.
In this paper we studied a process model, namely probabilistic workflow nets, that allows to model uncertainty. The model distinguished with external and internal choices to express that the system has the ability to adapt to changes in the external environment by changing the probabilistic distribution over internal choices. This adaption mechanism is embedded into our Hornet-model of the MAPE-loop. As the Hornet-model is formulated to support selfmodification, our MAPE-loop does not only support the first-order adaption of internal choices only, but also of the complete net topology itself. To formalise this second-order adaption we use a formalism for multi-agent organisation, called Sonar. In this contribution we concentrate on first-order adaption. We have introduced a selection mechanism that defines how the system should select its best configuration in the presence of uncertainty about the environment . This mechanism should guarantee a good reward for a large fraction of scenarios compatible with . Our mechanism uses a scoring approach of rankings to balance these two dimension simultaneously:
In our MAPE-loop model we use our PWFN model as a digital twin during the planning phase. We implement an approximation of our mechanism via a double sampling approach: As we usually cannot evaluate all scenarios and all configurations, we approximate the score value using a --sample of and . Our case study of an examination process based on randomisation of failure rates and extra preparation times shows that this sampling approach leads to results consistent with the real values even in the setting of very small sample sizes (here: = 2 and = 3).
We like to mention some lines of research that arise from our work:
In ongoing work we investigate the second-order adaption in more detail. We study MAS
organisations within our Sonar-approach. From the perspective of adaption Sonar provides a
mechanism to change the internal configuration, which leads to a change in group formation
processes and team interaction processes. More specifically, a change of the team structure, e.g.
as a reaction to an imbalance of the agents’ work load, generates a diferent team and also an
adapted multi-party workflow. As a consequence, the Sonar-model defines the state space of
all second-order adaptations within the MAS organisation (cf. [
We are also working on a more elaborated evaluation of the MAPE-loop processes based on
our previous work on the analysis of adaption processes [
In future work we like to extend the MAPE-loop in the following way: There is a close
connection of models@run-time and Process Mining [