The use of Digital Twins is key in Industry 4.0, in the Industrial Internet of Things, engineering, and manufacturing business space. For this reason, they are becoming of particular interest for diferent ifelds in Artificial Intelligence (AI) and Computer Science (CS). In this work, we focus on the orchestration of Digital Twins. We manage this orchestration using Markov Decision Processes (MDP), given a specification of the behaviour of the target service, to build a controller, known as an orchestrator, that uses existing stochastic services to satisfy the requirements of the target service. The solution to this MDP induces an orchestrator that coincides with the exact solution if a composition exists. Otherwise, it provides an approximate solution that maximizes the expected discounted sum of values of user requests that can be serviced. We formalize stochastic service composition and we present a proof-ofconcept implementation, and we discuss a case study in an Industry 4.0 scenario.
The continuous evolution of technologies in the fields of communication, networking, storage and computing, applied to the more traditional world of industrial automation, in order to increase productivity and quality, to ease workers’ lives, and to define new business opportunities, has created the so-called smart manufacturing, or Industry 4.0. Digital Twins (DTs)1 are up-to-date digital descriptions of physical objects and their operating status. Modern information systems and industrial machines may natively come out with their digital twin; in other cases especially when the approach is applied to already established factories and production processes, digital twins are obtained by wrapping actors that are already in place. The main goal is to establish a tight integration between the physical world and the virtual world, in order to make production more eficient, reliable, flexible and faster. The Digital Twin is an ideal tool to accomplish the purpose of Industry 4.0, since it enables massive exchange of data that can be interpreted by analytical tools, in order to improve decision making.
Inspired by the research about automatic orchestration and composition of
software artifacts, such as Web services, in [
In this paper, we marry the vision of employing service composition
techniques to orchestrate digital twins. We propose a generalization to the service
composition in stochastic setting proposed in [
MDPs. A Markov Decision Process (MDP) M = ⟨S, A, T, R⟩ contains a set S
of states, a set A of actions, a transition function T : S × A → P rob(S) that
returns for every state s and action a a distribution over the next state, and a
reward function R : S × A → R that specifies the reward (a real value) received
by the agent when transitioning from state s to state s′ by applying action a.
A solution to an MDP is a function, called a policy, assigning an action to each
state, possibly with a dependency on past states and actions. The value of a
policy ρ at state s, denoted vρ (s), is the expected sum of (possibly discounted
by a factor λ , with 0 ≤ λ < 1) rewards when starting at state s and selecting
actions based on ρ . Typically, the MDP is assumed to start in an initial state
s0, so policy optimality is evaluated w.r.t. vρ (s0). Every MDP has an optimal
policy ρ ∗ . In discounted cumulative settings, there exists an optimal policy that is
Markovian ρ : S → A, i.e., ρ depends only on the current state, and deterministic
[
The Roman Model in stochastic settings. The problem of service
composition, i.e. the ability to generate new, more useful services from existing ones,
has been considered in the literature for over a decade [
Unfortunately, it is not always possible to synthesize a service that fully
conforms with the requirement specification. This zero-one situation, where we
can either synthesize a perfect solution or fail, often is not very applicable. Rather
than returning no answer, we may want notion of the “best-possible” solution.
A model with this notion has been developed in [
Before stating the problem, we give preliminary definitions. A stochastic service is a tuple S˜ = ⟨Σ s, σ s0, Fs, A, Ps, Rs⟩, where Σ s is the finite set of service states, σ s0 ∈ Σ is the initial state, Fs ⊆ Σ s is the set of the service’s final state, A is the ifnite set of services’ actions, Ps : Σ s × A → P rob(Σ s) is the transition function, and Rs : Σ s × A → R is the reward function. In short words, the stochastic service is the stochastic variant of the service defined in the classical Roman model, and it can be seen as an MDP itself.
A target service, as defined in [
A stochastic system service Z˜ of a community of stochastic services C˜ = {S˜1, . . . , S˜n} is a stochastic service where Z˜ = ⟨Σ z, σ z0, Fz, A, Pz, Rz⟩ are defined as follows: Σ z = Σ 1 × · · · × Σ n, σ z0 = (σ 10, . . . , σ n0), Fz = {(σ 1, . . . , σ n) | σ i ∈ Fi, 1 ≤ i ≤ n}, Az = A × { 1, . . . n} is the set of pairs (a, i) formed by a shared action a and the index i of the service that executes it, Pz(σ ′ | σ , (a, i)) = P (σ i′ | σ i, a), for σ = (σ 1 . . . σ n), σ ′ = (σ 1′ . . . σ n′) and a ∈ Ai(σ i), with σ i ∈ Σ i and σ j = σ j′ for j ̸= i, Rz(σ , (a, i)) = Ri(σ i, a) for σ ∈ Σ z, a ∈ Ai(σ i).
We define the set of joint histories of the target and the system service as Ht,z = Σ t × Σ z × (A × Σ t × Σ z)∗ . A joint history ht,z = σ t,0σ z,0a1σ t,1σ z,1a2 . . . is an element of Ht,z. The projection of ht,z over the target (system) actions is π t(ht,z) = ht (π z(ht,z) = hz). An orchestrator γ : Σ t × Σ z × A → {1, . . . , n}, is a mapping from a state of the target-system service and user action (σ t, σ z, a) ∈ Σ t × Σ z × A to the index j ∈ {1, . . . , n} of the service that must handle it. Crucially, since the stochasticity comes also from the services, the orchestrator does afect the probability of an history ht,z. Moreover, in general, there are several system histories associated to a given target history.
Let Pγ (h) = Q|ih=|0 Pt σ t,i, ai+1 Pz σ z,i+1 | σ z,i, ⟨ai+1, γ (σ t,i, σ z,i, ai+1)⟩) be the probability of a (joint) history h = σ t0σ z0⟨a1, j1⟩σ t1σ z1⟨a2, j2⟩ . . . under orchestrator γ . Intuitively, at every step, we take into account the probability, determined by Pt, that the user does action ai+1 in the target state σ t,i, in conjunction with the probability, determined by Pz, that the system service (ai+1,j) does the transition σ →z−,−i−− − σ z′,i+1, where j is the choice of the orchestrator at step i under orchestrator γ , i.e. j = γ (σ t,i, σ z,i, ai+1).
The value of a joint history under orchestrator γ is the sum of discounted reh wards, both from the target and the system services: vγ (h) = P|| λ i Rt σ t,i, ai+1 + i=0 Rz σ z,i, ⟨ai+1, γ (σ t,i, σ z,i, ai+1)⟩)
Intuitively, we take into account both the reward that comes from the execution of action ai+1 in the target service, but also the reward associated to the execution of that action in service j chosen by orchestrator γ . Now we can define the expected value of an orchestrator to be: v(γ ) = Eht,z∼ Pγ vγ (ht,z) · realizable(γ, π t(ht,z)) where realizable(γ, π t(ht,z)) is 1 if ht = π t(ht,z) is realizable in γ (i.e. all the possible target histories are processed correctly), and 0 otherwise. That is, v(γ ) is the expected value of histories realizable in γ . Finally, we define an optimal orchestrator to be γ = arg maxγ ′ v(γ ′).
It can be shown that, under certain assumptions (i.e. target is realizable, every history has strictly positive value, and the target’s rewards are always greater than services’ rewards), optimality of the orchestrator implies that the target is realized by the orchestrator.
The solution technique is based on finding an optimal policy for the composition MDP. The composition MDP is a function of the system service and ΣthZe˜ × tarΣgTe˜t× seArv∪ice{saMs 0f}o,llAowM˜s: =M˜{(aZM˜, 0T˜,)1, =.. .⟨,SnM}˜,, TAMM˜˜(,sTMM˜0,, aRMM˜0⟩,,(σ wzh0e,rσet0S,aM)˜) == Pt(σ t0, a), T ˜ ((σ z, σ t, a), i, (σ z′, σ t′ , a′)) = Pt(σ t′ , a′) · Pz(σ z′ | σ z, ⟨a, i⟩), if Pz(σ z′ |
M σ z, ⟨a, i⟩) > 0 and σ t→− a σ t′ and 0 otherwise, RM˜ ((σ z, σ t, a), i) = Rt(σ t, a) + Rz(σ z, ⟨a, i⟩), if (a, i) ∈ A(σ z) and 0 otherwise.
This definition is pretty similar to the construction proposed in [
To summarize, given the specifications of the set of stochastic services and the target service, first compute the composition MDP, then find an optimal policy for it, and then deploy the policy in an orchestration setting and dispatch the request to the chosen service according to the computed policy, 5
Consider the following scenario: there is an industrial process of ceramics production in which a product must be processed sequentially in diferent ways. Each sub-task can be completed by a set of available services. The tasks to be carried out in order to complete the industrial process are: provisioning, moulding, drying, rfist baking, enamelling, painting, second baking and shipping. Such tasks can be accomplished by diferent types of machines or human workers. Each available service that can perform the task can be seen as finite state machines with a probability and a reward associated to each action. There could be multiple services for the same task, e.g. multiple version of a machine (new one and old one) and a human that can perform the task required, and so on. When an available service is being assigned a task, this has a task cost in terms of time taken and resources needed for the completion of the operation on that specific service. Usually, in terms of task cost, machines are cheaper than human workers, because they can perform their task much faster. However, the machines have a certain probability to break when they perform their job. In such a case, the machine must be repaired as soon as the operation has been carried out, that incurs in a repair cost for that specific machine.
From the above description of the use case scenario, it is clear that the composition technique must be able to handle the stochasticity of the available services’ transitions, as well as their reward/cost. Indeed, an optimal orchestration depends on several parameters, like the task costs, the breaking probabilities and the repair costs, one for each candidate service for accomplishing a certain task. Therefore, it is not straightforward to determine a priori which service a certain task must be assigned to. For example, it might be the case that despite the task cost of a machine is low, its breaking probability might be high, and considering the repair cost it might let us to prefer a human worker for that task. We argue that our model can fit very well our use case. Indeed, we can reduce the problem to an instance of stochastic service composition suggested above in which a service can capture the task cost, the breaking probability, and the repair cost. 6
In this paper, we have proposed an extension to previous work on stochastic service composition, in which also the services are allowed to have stochastic behaviour and rewards on the state transitions. We formally specified the problem and proposed a solution based on a reduction to MDPs. Furthermore, we motivated the contribution by showing how it is well-suited for a realistic Industry 4.0 scenario. As a future work, we would like to investigate diferent improvements such as: the possibility of including exception handling, having separate rewards specicfiations for the target, employing high-level formalisms to express a non-Markovian reward (e.g. LTL), and to employ learning techniques to learn a model of the target behaviour from data.