Keywords:

This work is part of the GENETTA project granted by the Brittany region. Une approche contrainte pour raisonner avec un choix probabiliste partiellement connu (version tendue Résumé : La Programmation Concurrente par Contraintes Probabilistes (PCCP) tend la Programmation Concurrente par Contraintes par un oprateur de choix probabiliste. Cet oprateur a prouv son utilit par l'implantation d'algorithmes "randomiss" ainsi que dans la modlisation de processus stochastiques. Dans ce rapport, nous prsentons un nouvel algorithme de filtrage ddi l'oprateur de choix probabiliste nous permettant de modliser de nouvelles applications pour lesquelles les choix probabilistes ne sont que partiellement connus. Cet algorithme de filtrage nous permet d'obtenir de l'information sur les valeurs pouvant tre prises par le choix probabilistes tout en n'ayant qu'une connaissance partielle sur celui-ci. Une implantation prenant la forme d'une nouvelle librairie de SICStus Prolog est dcrite.

Introduction

Probabilistic Concurrent Constraint Programming (PCCP) was concurrently introduced by Di Pierro and Wiklicky [START_REF] Di Pierro | On probabilistic ccp[END_REF] and Gupta, Jagadeesan and Saraswat [START_REF] Gupta | Probabilistic concurrent constraint programming[END_REF] to model randomized algorithms [START_REF] Di Pierro | Implementing randomised algorithms in constraint logic programming[END_REF] and stochastic processes [START_REF] Gupta | Stochastic processes as concurrent constraint programs[END_REF] in a declarative way. In both cases, a probabilistic choice operator was added to Concurrent Constraint Programming (CCP) [START_REF] Saraswat | Concurrent Constraint Programming[END_REF] to introduce probabilistic behaviours in concurrent constraint processes. A probabilistic choice between two CCP processes can be thought of as flipping a coin : head the first process is triggered, tail the second process is triggered.

In CCP, concurrent processes interact via a common constraint store, a conjunction of constraints on the possible values of variables. The computational model acts by accumulating constraints into the constraint store and processes communicate by checking whether the store entails some constraints. In [START_REF] Di Pierro | On probabilistic ccp[END_REF], the classical non-deterministic choice operator [START_REF] Saraswat | Semantic foundations of concurrent constraint programming[END_REF] of CCP is redefined as a probabilistic choice operator whereas [START_REF] Gupta | Probabilistic concurrent constraint programming[END_REF] introduces an operator that constrains an internal random variable. In [START_REF] Di Pierro | On probabilistic ccp[END_REF], random choices operate over processes whereas in [START_REF] Gupta | Probabilistic concurrent constraint programming[END_REF] random choices operate over values of variables. It is worth noticing that for both operators, random draws shall be performed on an instantiated probability distribution. According to our knowledge, only a single implementation of PCCP was realized under the form of a meta-interpreter in Prolog [START_REF] Angelopoulos | Implementing randomised algorithms in constraint logic programming[END_REF].

In our work, we propose to extend the probabilistic choice operator introduced in [6] to deal with probability distribution only partially known. Our approach is based on the possibility of expressing probabilistic choice relations without requiring all the parameters to be instantiated and deducing information on it during the constraint solving. In particular, we allow expressing random draws over an unknown probability distribution. This increases the declarativity of the probabilistic choice operator and open the door to model new kind of problems. As a very basic example, consider the simulation of a dice draw. When the dice is unbiased (its probability distribution is then fully instantiated), the following PCCP process simulates the dice draw: choose(X, [START_REF] Angelopoulos | Implementing randomised algorithms in constraint logic programming[END_REF][START_REF] Carlsson | An Open-Ended Finite Domain Constraint Solver[END_REF][START_REF] Di Pierro | On probabilistic ccp[END_REF][START_REF] Di Pierro | Implementing randomised algorithms in constraint logic programming[END_REF][START_REF] Gupta | Stochastic processes as concurrent constraint programs[END_REF][START_REF] Gupta | Probabilistic concurrent constraint programming[END_REF]] -[1, 1, 1, 1, 1, 1], tell(X = Dice)).

The distribution probability is represented by a list of weights ([1, 1, 1, 1, 1, 1]) that yields to a 1 6 probability of drawing each of the six possible dice face. However, the simulation becomes non-feasible whenever the bias of the dice is unknown or just partially known via some constraints (for example, knowing that the 6-face of the dice is two times more overloaded than the 1-face). As previously said, PCCP requires the probability distribution of its probabilistic operator to be fully instantiated in order to simulate the draw. By defining the probabilistic choice operator as a constraint, such a problem can be simulated via the following request: [START_REF] Angelopoulos | Implementing randomised algorithms in constraint logic programming[END_REF][START_REF] Carlsson | An Open-Ended Finite Domain Constraint Solver[END_REF][START_REF] Di Pierro | On probabilistic ccp[END_REF][START_REF] Di Pierro | Implementing randomised algorithms in constraint logic programming[END_REF][START_REF] Gupta | Stochastic processes as concurrent constraint programs[END_REF][START_REF] Gupta | Probabilistic concurrent constraint programming[END_REF]

tell(W 6 = 2 * W 1 ) choose (X,
-[W 1 , W 2 , W 3 , W 4 , W 5 , W 6 ], tell(X = Dice))
The major contribution of this work is to propose a filtering algorithm dedicated to the probabilistic choice operator to reason with probabilistic choices partially known. This permits us to deal with new kind of applications where probabilistic choices are partially known. We implemented several probabilistic choice operators under the form of a SICStus Prolog library called PCC(FD) built over clp(fd) (a.k.a. finite domains constraints) and first experimental result is presented. A version of this library is available online [START_REF] Petit | Library of probabilistic constraint combinators (version 0)[END_REF].

The report is organized as follows : Section 2 briefly recalls the syntax and semantics of PCCP; Section 3 describes the operator with probabilistic choice partially known. While Section 4 presents the filtering algorithm associated to the operator, section 5 details the implementation of several probabilistic constraint choice operators in SICStus Prolog. Finally, Section 6 indicates several perspectives to this work.

Probabilistic Concurrent Constraint Programming

Before presenting PCCP, we start by recalling some syntax and semantics elements of the classical concurrent constraint programming paradigm (CCP) introduced by Saraswat [START_REF] Saraswat | Concurrent Constraint Programming[END_REF].

Concurrent Constraint Programming

In CCP, processes are executed concurrently and can interact with each other through a common constraint store. A CCP language is parameterized by a constraint system [START_REF] Saraswat | Semantic foundations of concurrent constraint programming[END_REF], which is a set of primitive constraints and an entailment relation. The syntax of a CCP language is given by the following grammar: A PCCP program is composed of procedure declarations and a process. A process is build on the classical operators: tell(C) adds the constraint C to the constraint store, if C then P rocess asks whether C is entailed by the current constraint store and adds the constraints of P rocess if C is entailed, new X in P rocess adds the constraints of P rocess to the store while hiding the variable X from other processes, represents the parallel composition that can be interpreted as a logical conjunction in a Logic Programming environment, and finally, p(X) represents a procedure call. Well known examples of CCP languages include cc(FD) [START_REF] Van Hentenryck | Design, implementation, and evaluation of the constraint language cc[END_REF], AKL [START_REF] Janson | Programming paradigms of the Andorra kernel language[END_REF] and Oz/Mozart [START_REF] Smolka | The Oz programming model[END_REF] just to name a few.

Probabilistic Choice Operator

In [START_REF] Gupta | Probabilistic concurrent constraint programming[END_REF], Gupta et al. proposed to add a probabilistic choice operator to CCP. The operator choose(X, Law X , P rocess) injects a random variable X along with a probabilistic law Law X into a concurrent process P rocess. Law X contains a list of possible values for X, [v 1 , . . . , v n ] along with a list of non negative weights [w 1 , . . . , w n ] associated to each v i . The scope of X is limited to P rocess. Operationally, choose(X, [v 1 , . . . , v n ] -[w 1 , . . . , w n ], P rocess) executes

INRIA

P rocess X←vi with a probability pr i where P rocess X←vi denotes the concurrent process P rocess where X has been substituted by v and pr i denotes the probability of the event X = v i which is computed by the following formulae:

pr i = w i n j=1 w j .

Operational semantics

Running processes of PCCP can be formally described by using a probabilistic transitions system (Γ, →) where Γ denotes the set of states of the transition system, also called configurations. A configuration is a pair P rocess, σ where P rocess denotes all the remaining processes to be executed while σ is the constraint store. As usual, the transition relation → is defined with the help of axiomatic rules that are available in [START_REF] Gupta | Stochastic processes as concurrent constraint programs[END_REF]. Let σ 0 be an initial constraint store, then the set of terminal configurations tc(P rocess, σ 0 ) in the operational semantics of PCCP are defined as:

tc(P rocess, σ 0 ) = {σ | P rocess, σ 0 → * σ →}.
where → * denotes the transitive closure of the transition relation. In PCCP, only consistent constraint stores (consistent terminal configurations ctc(P rocess, σ 0 )) are considered for further computations:

ctc(P rocess, σ 0 ) = {σ | P rocess, σ 0 → * σ → and consistent(σ)}
Just to make things more concrete, we illustrate the processing of a PCCP request on a basic example extracted from [START_REF] Gupta | Stochastic processes as concurrent constraint programs[END_REF]:

Example 1. P = choose(X, [0, 1] -[1, 1], tell(X = Z)) choose(Y, [0, 1] -[1, 1], if Z = 1 then tell(Y = 1)).
Roughly speaking, three possible terminal configurations can be obtained: Z is constrained to 0 with the probability 1 2 (event X = 0), Z is constrained to 1 with the probability 1 4

(event X = 1 ∧ Y = 1) and f alse is obtained with the probability 1 4 (event X = 1 ∧ Y = 0). By eliminating the third possible answer, we get ctc(P, true) = {Z = 0, Z = 1}.

PCCP in a constraint solver over finite domains

Before switching on the description of the probabilistic choice partially known, we presents in this section the introduction of PCCP in a constraint solver over finite domains. As the Concurrent Constraint framework is generally considered as an extension CLP scheme [START_REF] Jaffar | Constraint logic programming : A survey[END_REF], we decides to translate a PCCP process into a CLP(X ) goal, more precisely we restricts our approach to finite domain constraints. We decide to restrict our work to finite domains because of the probabilistic choice operates over a finite domain, noted val(X). We also assume that [v 1 , . . . , v n ] is ordered set.

We supposed that previously the procedure declarations have been translated into predicate declarations. Then, the translation is obtained by a translation of each PCCP operator into CLP(FD ) goals or constraint. The translation is given by Fig. 1. (choose) P rocess → Goal choose(X, LawX, P rocess) → choose(X, LawX, Goal)

(proc) p(x) → p(x)
The meaning of → is " is translated into". The operator tell(C) is translated into the constraint C. The implication operator ask introduced by P. Van Hentenryck et al. in [START_REF] Van Hentenryck | Design, implementation, and evaluation of the constraint language cc[END_REF] is used to model the operator of synchronisation if then. We do not modelled the introduction of a local variable X in a P rocess. It supposes that X is only used in P rocess. The parallel composition operator || is considered as a logical conjunction represented by ",". The choose operator is translated into a new constraint of CLP(FD ) solver. This new constraint is more detailed in the section 4. A procedure call is considered as a predicate call.

This translation aims at using the CLP(FD ) constraint solving engine to simulate the behaviour of a PCCP process. As find solutions of CLP(FD ) problem is a decidable but NPcomplete problem, a constraint propagation process based on domain and interval reasoning is used to deduce information on the problem during a P rocess run. During constraint propagation, the constraint is fallen asleep if only a partial solution is found. The constraint solver can be seen as a scheduler. Indeed, constraints are incrementally introduced into a propagation queue. A fix point algorithm manages each constraint one by one into this queue by filtering the domains of finite domain variables of their inconsistent values. Filtering algorithms will consider only the bounds of the domains to eliminate inconsistent values. When the domain of a variable is pruned then the algorithm reintroduces in the queue the INRIA asleep constraints. The algorithm iterates until the queue becomes empty, which corresponds to a state where no more pruning can be performed (a fix point). The interval propagation process reaches a fix point because only a finite number of values can be removed from the domains. This fix point is a conservative approximation (intervals) of the possible values for the variables.

Note that the mechanism of backtracking is avoided when a process failure takes place. Indeed, a process failure is considered as an programming or modelling error in the PCCP. More precisely, it is supposed that when a choice is made, it is the programmer's responsibility to ensure that it is the good one. Thus PCCP languages provide "don't care nondeterminism" if more than one choice is enabled, we don't care which of the corresponding rules are used since will be correct.

An operator with a probabilistic choice partially known

In PCCP, the probabilistic choice operator requires the pair Domain Distribution to be fully instantiated. In this section, we relax this requirement by introducing the probabilistic choice operator choose with a probability distribution only partially known. This partial knowledge is represented by constraints on variables of the probability distribution.

Partial knowledge on a probabilistic law

The simulation (random draw) of values for the random variable X is always possible when Law X is fully determined. A partial knowledge of Law X is represented by a list a finite domain variables for the distribution probability. Then, partial knowledge on the probability distribution only appears whenever the variables of the probability distribution can take several possible values. This partial knowledge is characterized by the following definition:

Definition 1. Let X be a random variable, Law X = [v 1 , . . . , v n ] -[W 1 , . . . , W n ]
its probability law where W 1 , . . . , W n are finite domain variables. The set of the possible probability distributions associated to X is:

SL X = [v, . . . , v n ] -[w 1 , . . . , w n ] w 1 ∈ dom(W 1 ), . . . , w n ∈ dom(W n )
where dom(W ) represents the domain of a variable W .

Example 2. Consider again the example of dice

tell(W 6 = 2 * W 1 ) || choose(X, [1, 2, 3, 4, 5, 6] -[W 1 , W 2 , W 3 , W 4 , W 5 , W 6 ], tell(X = Dice)) Suppose that dom(W 1 ) = 1..2, dom(W 2 ) = 2..2, dom(W 3 ) = 2..2, dom(W 4 ) = 2..2, dom(W 5 ) = 2.
.2 and dom(W 6 ) = 2..4, then the partial knowledge on the unknown bias of the dice is given by the following set:

SL X = { [1, 2, 3, 4, 5, 6] -[1, 2, 2, 2, 2, 2], [1, 2, 3, 4, 5, 6] -[1, 2, 2, 2, 2, 3], [1, 2, 3, 4, 5, 6] -[1, 2, 2, 2, 2, 4], [1, 2, 3, 4, 5, 6] -[2, 2, 2, 2, 2, 2], [1, 2, 3, 4, 5, 6] -[2, 2, 2, 2, 2, 3], [1, 2, 3, 4, 5, 6] -[2, 2, 2, 2, 2, 4]}.
The operator choose(X, [v 1 , . . . , v n ] -[W 1 , . . . , W n ], P rocess) builds a relation between the simulation of values for X and the set of finite domain variables of its probabilistic law that can be exploited to filter the domain of random variable X during the constraint propagation.

Constraint propagation on choose

The constraint choose succeeds whenever X is valuated and P rocess succeeds. When the probabilistic choice is only partially known, the constraint choose is introduced into the propagation queue of the constraint solver and then, a filtering algorithm is launched to prune val(X). When no more pruning can be performed, the constraint falls asleep. The constraint is awoken whenever the domain of at least one variable of the distribution probability is modified and it is reintroduced in the propagation queue. This process iterates until a fix point is reached, i.e. a state where no more deduction on the domain of X is obtained.

The choose filtering algorithm

As usual, the behaviour of random variables over a finite domain is simulated with the values of a uniform random variable over [0; 1], noted U . The algorithm exploits an a priori random value of U to prune val(X). Given a value for U , we reason of the element of SL X to deduce information on val(X).

Simulation of a random variable with a finite probability law

The value of a random variable with a finite law is generated from the value of a uniform random variable U over [0 ; 1]. The link between the values of X and U is established by the distribution function f as follows.

f : [0; 1] → {v 1 , . . . , v n } u →        v 1 if u ∈ [0, pr 1 [ . . . . . . v n if u ∈ n-1 j=1 pr j , 1 . (1)
It is trivial to see that the probability of the event X = v i is equal to P (u ∈ [pr 1 + . . . + pr i-1 , pr 1 + . . . + pr i ]) = (pr 1 + . . . + pr i ) -(pr 1 + . . . + pr i-1 ) = pr i , as expected.

INRIA

As an example, consider the distribution function f associated to an unbiased dice given by Fig. 2. Here, the distribution probability is represented by [START_REF] Angelopoulos | Implementing randomised algorithms in constraint logic programming[END_REF][START_REF] Carlsson | An Open-Ended Finite Domain Constraint Solver[END_REF][START_REF] Di Pierro | On probabilistic ccp[END_REF][START_REF] Di Pierro | Implementing randomised algorithms in constraint logic programming[END_REF][START_REF] Gupta | Stochastic processes as concurrent constraint programs[END_REF][START_REF] Gupta | Probabilistic concurrent constraint programming[END_REF]] -[1, 1, 1, 1, 1, 1].Let 0.6 be a random value generated for U , then we get X = 4.

Figure 2 Simulation of the random variable X with a uniform probability distribution on {1, 2, 3, 4, 5, 6}

X=1 X=2 X=3 X=4 X=5 X=6 0 1/6 1/3 1/2 2/3 5/6 1 X=f(0.6)=4 u f
The set of distribution functions is noted F X . Note that for each element of SL X corresponds a distribution function of F X . For example, the set F X of the example 2 dice is represented by Fig. 3.

Properties of the choose constraint

In this section, we propose to characterize correction properties of any filtering algorithm on the choose constraint. Our filtering algorithm exploits information on the probabilistic choice, i.e the value u of U the random variable associated to the simulation of values for X and SL X , to prune val(X). Then, these correction properties are dependent on the value of u. Given u known, the first one states that each element of val(X) can be randomly choosen, i.e it exists a distribution function such as this element can be chosen.

Property 1. [Correction of choose]

Let X be a random variable with a probability distribution law [v 1 , . . . , v n ] -[W 1 , . . . , W N ] and u the value of the random variable U associated to the simulation of values for X. Let consider F X as the set of probability distribution. Then, property 1 states that

∀v i ∈ val(X), ∃f ∈ F X such that f (u) = v i
Given u, the second one states that the bounds of val(X) can be randomly choosen.

Property 2. [Partial Correction of choose]

Let us know that v min = min(val(X)) and v max = max(val(X)), then property 2 states that

∃f 1 ∈ F X such that f 1 (u) = v min and ∃f 2 ∈ F X such that f 2 (u) = v max
From the definitions, it is clear that property 1 entails the property 2.

Filtering on the domain of the possible values for X

Given a value u for U , the principle of the filtering algorithm is to detect values for X than cannot be randomly chosen by reasoning on the set of the possible probability distributions. In this section, it assumes that [v 1 , . . . , v n ] the domain associated to the probabilistic choice is sorted.

The algorithm

To detect that a value v i can not be randomly chosen, we reason on F X and then on SL X . In fact, we reason on the range of values for u associated to the event X = v i for each distribution function of F X . This set of ranges defines the set of values for u such that v i can be randomly chosen. More formally, this set is defined as follows:

∀v i ∈ [v 1 , . . . , v n ], Int vi = [v1...,vn]-[w1,...,wn]∈SLX i-1 j=1 w j n j=1 w j , i j=1 w j n j=1 w j (2)
If u does not belong into Int vi , then v i cannot be randomly chosen for X. However, the computation of Int vi is based on the enumeration of each element SL X . In the worst case, enumerating each element of SL X is equivalent to enumerate each element of the cartesian product of the weights domain. When the size of the domains of the weights increase, this computation becomes intractable. We decides to approximate the computation of Int v in computing its bounds.

INRIA Algorithme 1 : Filteralgo

Input : X,Law X and u

forall v ∈ V al(X) do [M in Int v ; M ax Int v ] ← IntProba(v, Law X ); if u / ∈ [M in Int v ; M ax Int v ] then v is removed from V al(X) end end
The filtering algorithm takes as inputs X, Law X and u and removes values of val(X) which cannot randomly chosen. For each value v ∈ val(X), the bounds of

Int v , M in Int v and M ax Int v is computed by Intproba. If u / ∈ [M in Int v ; M ax Int v ], v is removed from val(X).
The efficiency of filtering algorithm is due to our efficiency to compute the bounds of each Int vi . Hopefully, theses bounds are obtained by an analytical result.

An efficient method to compute an approximation of Int vi

The method is looking for the element of SL X such that Int vi is minimizes and maximizes.

It is based on the computation of the minimum (resp. maximum) value of

∀v i ∈ [v 1 , . . . , v n ], max [v1...,vn]-[w1,...,wn]∈SLX i-1 j=1 w j n j=1 w j = i j=1 max(W j ) i j=1 max(W j ) + n j=i+1 max(W j ) (4) Proof. Proof by refutation. Suppose that ∃ [v 1 , . . . , v n ] -[w 1 , . . . , w n ] ∈ SL X such as i-1 j=1 w j n j=1 w j < i-1 j=1 min(W j ) i-1 j=1 min(W j ) + n j=i max(W j ) (5) RR n°6165
By hypothesis, n j=1 min(W j ) > 0, then n j=1 w j and i-1 j=1 min(W j ) + n j=i max(W j ) are superior to nought. From (5), we can deduce that i-1 j=1

w j •   i-1 j=1 min(W j ) + n j=i max(W j )   < i-1 j=1 min(W j ) • n j=1 w j Then, i-1 j=1 w j • n j=i max(W j ) < i-1 j=1 min(W j ) • n j=i w j But, 0 ≤ i-1 j=1 min(W j ) ≤ i-1 j=1 w j and 0 ≤ n j=i w j ≤ n j=i max(W j )
We obtain a contradiction because of

i-1 j=1 w j • n j=i max(W j ) cannot be lesser than i-1 j=1 min(W j ) • n j=i w j . Then, we prove that ∀[v 1 , . . . , v n ] -[w 1 , . . . , w n ] ∈ SL X , i-1 j=1 min(W j ) i-1 j=1 min(W j ) + n j=i max(W j ) ≤ i-1 j=1 w j n j=1 w j
The following equality ∀v i ∈ Dom(X), max can also be proved with the same reasoning.

Termination and correctness

Termination is trivially obtained just by noticing that the set val(X) is finite. Correction of the filtering is more difficult to state. As an approximation is done during the computation of Int vi , the constraint choose is said partially correct after the Filteralgo, i.e. we guarantee that the bound of V al(X) can be randomly chosen after the propagation process.

Proof.

Case 1:

v i = v 1 Let us consider the probability law: [v 1 , . . . , v i-1 , v i , . . . , v n ] -[max(W 1 ), min(W 2 ), . . . , min(W n )].

INRIA

The maximum of Int v1 is obtaineed from this probability law. We notes by f 1 its distribution function. Let us prove that f 1 (u) = v 0 .

Given the equation 3 and 4, the computation of Int v0 is approximated by [0;

max(W1) max(W1)+ n i=2 min Wj . As v 0 ∈ V al(X) after Filteralgo run, then u ∈ [0; max(W1) max(W1)+ n i=2 min Wj . Then, we can conclude that f 1 (u) = v 1
Case 2: min(V al(X) = v n Let us consider the probability law:

[v 1 , . . . , v i-1 , v i , . . . , v n ] -[min(W 1 ), . . . , max(W n )].
The minimum of Int vn is obtained from this probability law. We notes by f 1 its distribution function. Let us prove that f 1 (u) = v n . Given the equation 3 and 4, the computation of Int vn is approximated by

n-1 j=1 (Wj ) n-1 j=1 (Wj )+max(Wn) ; 1[. As v n ∈ V al(X)
after Filteralgo run, we can conclude that

f 1 (u) = v n
Case 3: Suppose that v i = min(V al(X)) after a FilterAlgo run and that v 1 < v i < v n Let us consider the probability law: The maximum of Int vi is obtained with this probability law. We notes by f 1 its distribution function. Let us prove that f 1 (u) = v i , i.e. after Filteralgo run

u ∈ i-1 j=1 max(W j ) i-1 j=1 max(W j ) + n j=i min(W j ) ; i j=1 max(W j ) i j=1 max(W j ) + n j=i+1 min(W j )
.

We obtains immediatly that u ≤ i j=1 max(Wj ) i j=1 max(Wj )+ n j=i=1 min(Wj ) because of v i ∈ V al(X) after Filteralgo run.

Recall that [v 1 , . . . , v n ] is an ordered set. Let suppose that this following affirmation is true. ∀k, j ∈ {1, . . . , n}, such as k < j, min(Int v k ) ≤ min(Int vj ) and max(Int v k ) ≤ max(Int vj ).

(6) This result can be proved in using of inductive reasonning, developping each terms and comparing them. The equations 3 and 4 give the following equalities:

min(Int vi-1 ) = i-1 j=1 min(W j ) i-1 j=1 min(W j ) + n j=i max(W j ) RR n°6165 and max(Int vi-1 ) = i-1 j=1 max(W j ) i-1 j=1 max(W j ) + n j=i max(W j )
.

As ∀j such as 1 ≤ j < i, v j / ∈ V al(X) after Filteralgo run because of v i is the minimum of V al(X). Then, ∀j such as 1 ≤ j < i, u / ∈ [min(Int vj ), max(Int vj )]. By extension in using of the result 6, we can deduce that max(Int vi-1 ) < u. Moreover,

max(Int vi-1 ) - i-1 j=1 max(W j ) i-1 j=1 max(W j ) + n j=i+1 min(W j ) = i-1 j=1 max(W j ) i-1 j=1 max(W j ) + n j=i min(W j ) - i-1 j=1 max(W j ) i-1 j=1 max(W j ) + n j=i-1 min(W j ) = (max(W i ) -min(W i )) • i-1 j=1 max(W j ) i-1 j=1 max(W j ) + n j=i min(W j ) + i j=1 max(W j ) + n j=i+1 min(W j )
As (max(Wi) -min(Wi)) • i-1 j=1 max(Wj) and i-1 j=1 max(Wj) + n j=i min(Wj) + i j=1 max(Wj) + n j=i+1 min(Wj) are non negative number, we conclude that

i-1 j=1 max(W j ) i j=1 max(W j ) + n j=i+1 min(W j ) ≤ max(Int vi-1 )
Then, we can conclude that

u ∈ i j=1 -1 max(W j ) i j=1 max(W j ) + n j=i=1 min(W j ) ; i j=1 max(W j ) i j=1 max(W j ) + n j=i=1 min(W j )
and then that

f 1 (u) = v i
Finally, we have proved that after Filteralgo run that

∃f 1 ∈ F X such that f 1 (u) = min(V al(X))
In using the same reasonning, we can prove that

∃f 2 ∈ F X such that f 2 (u) = max(V al(X)) INRIA

Example

Consider again the example 2.

The set F X is given by Fig. 3. The values of Int vi can be easily computes. Int 6 = 9 13 ; 1[ X = 1 is removed from dom u (X) by the filtering algorithm when u / ∈ [0; 1 6 [, X = 2 is removed from dom u (X) when u / ∈ 1 13 ; 1 3 and so one.

Complexity

The complexity of the pruning algorithm is associated to the complexity of the computation of Int vi . Each bounds of Int vi is obtained in computing ∀i ∈ 1 . . . n, i-1 j=1 min(W j ) and i j=1 max(W j ). The result is computed in a linear time in comparaison with the size of X domain. As the rest of the algorithm is restricted to a "membership testing", Filteralgo runs in O(n) where n is the size of [v 1 , . . . , v n ] the domain of X.

A version of the efficient filtering algorithm is implemented for each probabilistic choice operator of the PCC(FD) library.

Empirical computation of the set of terminal configurations

Given a Prolog goal Goal along with a list of variables Var_List, the ptc predicates launches a given number of Goal runs, records the resulting constraint store projection (i.e. projection of domains on Var_List) after the constraint propagation step, and computes the occurrence rate of each constraint store projection. By using this predicate, one can study the probabilistic behaviour of our constraint combinators in PCC(FD).

Probabilistic combinators in PCC(FD)

The three new constraints distinguish themselves on the three possible notations of the probabilistic choice we gave above. In all the three cases, the probabilistic choice Domain -Distribution takes the form of Prolog terms that can be either closed or disclosed. A closed term is associated to a fully instantiated probabilistic choice whereas a disclosed term represents uncertainty on the probabilistic choice. The three probabilistic choices are:

choose, where Domain is a list of values and Distribution is a list of finite domain variables that represent weights;

-choose_range, where Domain is a range represented with two distinct FD variables M in and M ax, and Distribution is a list of finite domain variables that represent weights;

-choose_decision, where Domain is the boolean domain {0, 1} and Distribution is a couple of distinct finite domain variables that represent weights.

The choose constraint

The syntax of the constraint choose is as follows:

choose(X,[v1,..vn]-[W1,..,Wn],Goal,Options)

where W1,..,Wn are finite domain variables. Options is used to parameterize the filtering capacities of the operator into the constraint propagation mechanism. Three options are currently available:

-no_filtering can be employed to switch off the pruning capacities of the filtering algorithm. This option is useful for experiments ;

-consistency_check can be used to check the consistency of all the possible values V of X with respect to Goal. This option allows one to parameterize the filtering algorithm by trying to refute Goal ∧X = V . This option is useful to improve the pruning capacities of the combinator but is less efficient;

lvar(L) can be used to enrich the list of variables on which the constraint is awaked. This option is useful to parameterize the awaking conditions of the combinator.

By default, the filtering algorithm associated to the constraint is the algorithm 1.

Let us illustrate the behaviour of the choose costraint on the example 2 of the biased dice given above. The results show the different constraint store projections on X obtained after the constraint propagation step. For example, (Dice=1,0.07735) means that Dice is equal to 1 with a probability 0.07735. For some cases, the dice has been instantiated although the probability distribution was not fully known. On the contrary, some other constraint store projections show domains that contain two values. In this case, the filtering process failed to instantiate X but dramatically pruned the domain of possible values for X. On this example, our implementation permits valuating X with a probability of 0.4018 which is an good performance as these cases correspond to obtaining the dice face without knowing the bias of the dice. The choose range constraint has been used on an implementation of the (weak) Miller-Rabin primality test. This example shows that randomized algorithm can be employed to define new probabilistic relations which are easily implemented within PCC(FD). The implementation in PCC(FD) allows to constraint a variable to be a prime number given a certain probability. The implementation of the randomized algorithm is available on [START_REF] Petit | Library of probabilistic constraint combinators (version 0)[END_REF].

The choose range constraint

The choose decision combinator

The choose decision combinator implements a probabilistic boolean choice between two processes. This probabilistic boolean choice is represented as a list [W1,W2] of two finite domain variables. The term neg(Constraint) denotes the negation of Constraint. The probabilistic choice arises between Constraint,Goal1 and neg(Constraint),Goal2: choose_decision(Constraint,[W1,W2],Goal1,Goal2,Options) no_filtering, inconsistency_check and lvar(L) options are available.

Note that choose_decision(Constraint,[W1,W2],Goal1,Goal2,Options) can be rewritten as choose(X,[0,1]-[W1,W2],[ask(X=0,[Constraint,Goal1]),ask(X=1, [neg(Constraint),Goal2],Options)]).

This constraint has been introduced to simulate the behaviour of the conditional and loop statements in imperative programming. Indeed, we used this constraint to address a problem of Software Testing: the statiscal structural testing [START_REF] Thévenod-Fosse | An investigation of statistical software testing[END_REF]. The purpose of the statistical structural testing is to randomly generate test data such as the coverage of structural criterion is guaranteed. A first translation of the problem into a probabilistic constraint problem has been proposed in [START_REF] Petit | An ongoing work on statistical structural testing via probabilistic concurrent constraint programming[END_REF]. A new model of the problem which uses the new ability of the probabilistic choice operator to reason on probabilistic choice only partially known is in progress. It seems useful to reason on probabilistic partially known to improve dynamically our problem of statistical test data generation

First experimental validation with the 421 dice playing

The first experimental validation of the filtering algorithm is built on a toy example: 421 dice playing with unknown biased dice. This game consists in drawing three dice. The game is won when 4, 2 and 1 is drawn without taking care of the valuation order. Your game hypothesis is: the person who proposes the dice playing is dishonest. To estimate the luck to win the game, you decide to model the dice bias as follows: the probability to draw 4 is two times lower than the probability to draw 3, the probability to draw 2 is two times lower than the probability to draw 5 and the probability to draw 1 is two times lower than the probability to draw 6. The game is modelled by four_two_one/3 given by the Fig. The experimental validation, named Exp is based on the search of solution by propagation and labelling processes of the constraint solver. The experiment is based on a toy request which tries to find all the valuation of Distribution such as the game is won. Note that for sake of clarity, we do not model the labelling process based on the search in a tree in PCCP framework. We used the classical backtracking algorithm to search all the solutions of the problem. The parameter of experiment is W max . It represents the maximal bound of non negative variables W1,..,W6. Two requests are compared. The first one uses the option no_filtering whereas the second one uses an efficient filtering algorithm. The request is reiterated 50000 times. The number of iteration has been chosen to obtain a significant sampling of request behaviours. The performance has been evalated in using of SICStus 3.11 on a Windows XP machine powered by a 2GHz Intel Pentium processor and 1Go memory.

The result given by Fig. 5 allows to expecting that the filtering algorithm permits to increase the request run time. This gain in the time running is linked to the pruning capacity of the probabilistic choice domain of the filtering algorithm. In the worst case, no domain pruning is obtained when the filtering algorithm is used. As the probabilistic choice is frozen when no filtering algorithm is used, overtime can appear. However, this overtime stays reasonable because of the filtering algorithm is efficient.

Future work

This report has introduced an extension of PCCP which permits to reason on probabilistic choices partially known. In this paper, we proposed a dedicated filtering algorithm of the probabilistic choice operator to deduce information on the possible values of the probabilistic choice. An implementation under the form of a SICStus Prolog library has been built over clp(fd) and has been validated by a first experimental validation. Soon, we will propose to address a real world problem, namely statistical structural testing [START_REF] Thévenod-Fosse | An investigation of statistical software testing[END_REF]. The problem aims at finding distribution probability over the input domain of a program that maximizes the coverage of some structural criteria, such as all statements or all paths. Our purpose is to model this problem as a probabilistic constraint problem where probabilistic choices are only partially known.

P

  rogram ::= Declaration.P rocess Declaration ::= ε | Declaration.Declaration | p(X) : -P rocess P rocess ::= tell(C) | if C then P rocess | new X in P rocess | P rocess P rocess | p(X)

Figure

  Figure 1 Translation of PCCP process into a CLP(FD ) goal

Figure 3

 3 Figure 3 Set of the probability distributions of the example 2 dice

  2,3,4,5,6]-[2,2,2,2,2,3] [1,2,3,4,5,6]-[2,2,2,2,2,4]

  ) for each of SL X . A efficient way to compute min [v1...,vn]-[w1,...,wn]∈SLX max [v1...,vn]-[w1,...,wn]∈SLX i j=1 wj n j=1 wj is given by the two analytical results: Let X be a random variable and its probabilistic law [v 1 , . . . , v n ] -[W 1 , . . . , W N ]. Let us assume that n j=1 min(W j ) > 0. Then, ∀v i ∈ [v 1 , . . . , v n ], min [v1...,vn]-[w1,...,wn]∈SLX

[

  v1...,vn]-[W1,...,wn]∈SLX

[

  v1, . . . , vi-1, vi, vi+1, . . . , vn] -[max(W1), . . . , max(Wi-1), max(Wi), min(Wi+1), . . . , min(Wn)].

Int 1 =

 1

The

  choose range constraint implements a probabilistic choice operator for a range of values. The range is given by [Min,Max], where Min and Max are two finite domain variables. Min denotes the lower bound of X wheras Max denotes its upper bound. The probability distribution takes the form of a list of weights. Its size evolves with new information on Min or Max. choose_range(X,[Min,Max]-[W1,..,Wn]-Q,Goal,Options) no_filtering, consistency_checking and lvar(L) options are available. choose_range(X,[Xmin,Xmax]-[W1,..,Wn|Q]-Q,Goal,Options) can be rewritten as choose(X,[min(Min),..,max(Xmax)]-[W1,..,WN],[Goal],Options) where N is equal to max(Xmax)-min(Xmin)+1.

4

 4

  . The predicate four_two_one([D1,D2,D3],Distribution, Options) is said true iff the D1, D2 and D3 have been valued to 4, 2 and 1 without taking care of the valuation order.

Figure 4

 4 Figure 4 421 dice playing with bias partially known four_two_one([D1,D2,D3],[W1,W2,W3,W4,W5,W6],Options) :tell(2*W1=W6)||tell(2*W2=W5)||tell(2*W4=W3)|| choose(X, [1,2,3,4,5,6]-[W1,W2,W3,W4,W5,W6],[D1=X],Options)|| choose(Y, [1,2,3,4,5,6]-[W1,W2,W3,W4,W5,W6],[D2=Y],Options)|| choose(W, [1,2,3,4,5,6]-[W1,W2,W3,W4,W5,W6], [D3=W], Options)|| tell(all_different([D1,D2,D3]))||tell(D1+D2+D3#=7).

INRIA

Figure 5 7 ?

 57 Figure 5 Result of Exp for W max = 10, W max = 20, W max = 30, W max = 40 and W max = 50 Meaning of the request run time in ms Wmax = 10 Wmax = 20 Wmax = 30 Wmax = 40 Wmax = 50 No filtering 5.3 38.9 129.3 309.2 603 Filtering 6 12.5 33.5 66.1 123.7

  Goal 1 and P rocess 2 → Goal 2 P rocess 1 ||P rocess 2 → Goal 1 , Goal 2

	1 Translation of PCCP process into a CLP(FD ) goal
	(tell)	tell(C) → C
	(if then)	P rocess → Goal if C then P rocess → ask(C, Goal)
	(new in)	P rocess → Goal new X in P rocess → Goal
	(||)	P rocess 1 →

RR n°6165

The PCC(FD) libraryIn this section, a library of three probabilistic choice operators defined as new constraints is presented. The implementation of these constraints is based on the clp(FD) library of SICStus prolog[START_REF] Carlsson | An Open-Ended Finite Domain Constraint Solver[END_REF], by making use of its global constraint definition interface. We presented also a first validation experimental build on a toy example. The translation of PCCP program into clp(F D) program is obtained via the meta-interpreter pccfdtoclpfd wroten in Prolog. Before switching on the description of probabilistic choices, let us just explain the predicate ptc(Goal,Var List,Result) which empirically computes the set of terminal configurations in PCC(FD).


Yuqian Lu

Xun Xu
email: x.xu@auckland.ac.nz

Protecting intellectual property in a cloud manufacturing environment: requirements and strategies

Keywords: Cloud manufacturing, Intellectual property protection, security policy

In today's knowledge economy, intangible knowledge assets have become the key drivers of organisational success. Protection of intellectual properties for all parties is a challenging issue in cloud manufacturing environment. This paper focuses on the protection of intellectual property in the cloud manufacturing environment. Several strategies for protecting intellectual properties are proposed in this paper. In addition, a privacy enhanced business interaction mechanism is presented. Furthermore, this paper discusses some practical technologies in the cloud context.

Introduction

In recent years, cloud manufacturing has been regarded as a novel way of organising fast collaborative product development [START_REF] Xu | From cloud computing to cloud manufacturing[END_REF]. Cloud manufacturing is a service-oriented business model, whereby distributed manufacturing resources are encapsulated as consumable services over the Web [START_REF] Lu | Development of a Hybrid Manufacturing Cloud[END_REF]. This business model is anticipated to bring unique opportunities; it turns a capital investment model (of a typical manufacturing business) into a recurring expenditure model. In the ever-increasing distributed, networked and crowd-sourced cloud environment, the protection of intellectual property (IP) is a critical challenge. World Intellectual Property Organisation (WIPO) [START_REF] Organization | WIPO Intellectual Property Handbook: Policy, Law and Use[END_REF] gave the definition of intellectual property as "inventions, literary and artistic work, symbols, names, images, and designs used in commerce." IP contains two categories [START_REF] Organization | WIPO Intellectual Property Handbook: Policy, Law and Use[END_REF]: industrial property and copyright, both of which can be represented by intangible proprietary information. In cloud manufacturing environment, IP refers to the confidential information (product design, process, etc.) of industrial design and manufacturing. Therefore, the main objective of IP protection is to prevent leakage of confidential information in cloud manufacturing environment.

One of the prerequisites for cloud manufacturing is to share product information, which is the core IP of some businesses. Therefore, it is very likely that participants will face a dilemma in trying to balance protection of intellectual capital with the openness and information sharing needed to successfully carry out the joint tasks. To the best knowledge of authors, there has not been a satisfactory solution for protecting IP in cloud manufacturing environment, though some studies investigated the security [START_REF] Xu | From cloud computing to cloud manufacturing[END_REF] [4] and user privacy [START_REF] Lu | Development of a Hybrid Manufacturing Cloud[END_REF] issues.

This paper focuses on the protection of intellectual property in the cloud manufacturing environment. The emphasis is placed upon proposing a feasible mechanism to ensure the privacy of confidential information from service consumers and service providers. The reminder of this paper is organised as follows. The next section presents a brief discussion on the significance of IP protection in a cloud manufacturing environment and reviews related approaches reported in the literature. Section 3 proposes several strategies for maximum protection of IP from all parties in cloud manufacturing environment. Following these strategies, a privacy enhanced business process is also proposed. Section 4 further discusses the enabling technologies for IP protection. Section 5 summarises the outcomes of this research and discuss future trends.

Significance of IP protection

The existing research on cloud manufacturing has recognised the significance of data security and user privacy in a cloud manufacturing environment. However, there is very little work on these aspects. This section summaries the significance of IP protection by analysing the pain point for each party in the cloud and reviews the existing approaches.

Requirements on IP protection

In cloud manufacturing, there are two fundamental business roles, namely service consumers and service providers (Fig. 1). Consumers request manufacturing services from the cloud, whereas service providers receive orders or sub-orders from the cloud system by outsourcing resources [START_REF] Lu | Development of a Hybrid Manufacturing Cloud[END_REF]. From the technical perspective, requests from service consumers should contain the specifications of a product design, which is often in a form of computer aid manufacture file (like .dxf file for 2D design and .asm file for 3D design). After a design file is uploaded to the cloud, it will be sent to potential service providers for assessment and then some of them will be selected as the service providers. This process inevitably discloses product design to unwanted parties in the cloud. On the other hand, intelligent cloud systems require manufacturing resources being connected to the cloud and production activities being monitored all the time. In addition, some of the proposed system frameworks even ask service providers to provide detailed machining operations to the cloud for simulation and cost estimation purposes. In fact, this is not a good practice for manufacturers. Knowledge on optimal machining processes is often regarded as intangible assets of a business. Storing this information on a remote server potentially put it at risk. It has to be noted that the cloud manufacturing environment is a much more open environment than traditional PLM environment. In cloud manufacturing, model models, resource capability information and other business-critical information are all stored remotely in the cloud. For a manufacturing project, a global search and match process of task-service pairs is required to be carried out. In contrast, in the conventional PLM environment, there is a clear closed boundary for product data and knowledge exchange.

In summary, the requirements around IP protection in cloud manufacturing can be extracted as follows:

1. Complete product designs can only be seen by authorised users. 2. Complete product designs can only be visible to confirmed service providers. 3. Only a minimum amount of data should be sent to relevant service providers. 4. Exclusive know-how about manufacturing resources should not be visible to service consumers.

These basic requirements should be taken as ground rules when designing a manufacturing cloud.

Approaches to achieving data security and IP protection

Data security is one of the bottlenecks that hinders the application of cloud manufacturing [START_REF] Lu | Development of a Hybrid Manufacturing Cloud[END_REF]. The security and privacy management in cloud manufacturing environment is still in the early stage. This is because things are more complicated in cloud manufacturing environment. Xu [START_REF] Xu | From cloud computing to cloud manufacturing[END_REF] point out that manufacturers are more concerned about the confidentiality and privacy of their data. Lu et al. [START_REF] Lu | Development of a Hybrid Manufacturing Cloud[END_REF] discussed the importance of authorisation mechanisms for resource access in cloud environment. Resource sharing in cloud manufacturing is conditional: each service provider makes resources available, subject to constraints on who, when, where and what can be done. Access policies change dynamically over time, in terms of the resources involved, the nature of the access permitted, and the participants to whom access is available. A semantic web-based approach is proposed for setting resource access policies. By defining unique sharing policies for each manufacturing resource, enhanced privacy can be achieved as only authorised users can have access to a service in the cloud.

Kim et al. [START_REF] Kim | Multi-Level modeling and access control for data sharing in collaborative design[END_REF] proposed a multi-level modelling technique based on feature-based modelling and mesh simplification to enable information protection in computeraided collaborative design. The techniques are integrated with an access control mechanism to enable role-based user authorization. In a more recent research, Deng et al. [START_REF] Deng | Product decomposition using design structure matrix for intellectual property protection in supply chain outsourcing[END_REF] proposed an original approach to decompose product structures for the purpose of controlling IP leakage risk in supply chains using design structure matrix.

Following the notion of information partition in collaborative environment, Wang and Xu [START_REF] Wang | A collaborative product data exchange environment based on STEP[END_REF] proposed a product data exchange mechanism based on STEP/STEP-NC data models to provide information with the right level of detail to partners in a supply chain. In this mechanism, data extracting algorithms were developed to generate data packets.

IP protection strategies for cloud-based business interaction

This section discusses the overall strategy for preventing IP leakage in a cloud-based environment. As this is a new topic in cloud manufacturing research, we first present some general rules for protecting IP and then examine how rational business processes can enhance data confidentiality.

Rules of thumb for protecting IP in cloud environment

As mentioned earlier, service consumers send product designs to the cloud for matched manufacturers. This process can potentially put product designs at risk. Similarly, service providers need to detail the capability of manufacturing resources, which can disclose manufacturing know-how to other parties. In addition to diffusing critical knowledge, the open environment may allow a partner a window to gauge the strengths, weaknesses, and strategic orientation of its competitors, providing advantages in future competition with them. Therefore, this issue put service consumers and service providers in a dilemma in trying to balance protection of intellectual capital with the openness and information sharing needed to successfully carry out the product development tasks.

In terms of approaches to securing intellectual property, the most common strategy is the trusted-entry approach. This approach only works well for the first tier of trusted partners; the control of document is lost as the production activities move farther to multiple tiers of suppliers. Nevertheless, there are still some general rules to follow in complex engineering environments, especially in cloud manufacturing environment.

It is best to share as little information as possible for all the parties in cloud manufacturing. This means for service consumers, it is better to outsource only peripheral items, keeping all core IP at home. Even for a product design, it is not necessary to share all the details with manufacturers at the bid point. Only a simplified version of the product manufacturing information is required for potential manufacturers to tell if they are able to take the job. For service consumers, they only share a minimum amount of information for resource description and service monitoring. The detailed manufacturing processes for a task cannot be disclosed to other parties.

A second strategy is to break up the IP -not giving all of it to any one business entity, which is especially critical for service consumers. In other words, a cloud manufacturing system should balance the centralisation of manufacturing activities with the separation of whole IP into multiple pieces. The optimal scenario is to let a contract manufacturer see one part of the overall design and give it only the information needed to do the job.

Privacy enhanced business process in cloud environment

Following the above strategies, we highlighted the critical business processes requiring special attention on IP protection in cloud manufacturing as in the following UML sequential diagram (Fig. 2). This business process is a simplified version of the business interaction process in [START_REF] Lu | Development of a Hybrid Manufacturing Cloud[END_REF]. A typical service provision process is as follows. A service consumer submit a service request to the cloud by uploading a customised design file. This design file is often in a computer-aided manufacturing file, such as .dxf file, .step file and .asam file. During this process, the membership management module checks the identity of the service consumer before sending a request to the request processing module. The request processing module provides a comprehensive analysis for service requests by comparing new service request with historical data. The manufacturability of a service request is assessed in this process, and thereafter a response is sent back the service consumer. If a service request passes the assessment process, the PMI (Product Manufacturing Information) parser in this module is triggered to convert the product information in user-uploaded file into a simplified PMI file following an abstract product data model. This process is critical to the protection of product designs as only abstract PMI information is extracted for down-stream decision-making processes. This abstract file only contains a small portion of the original product data that is enough for manufacturing resource selection. Once this PMI file is generated, it will be sent to the knowledge base for resource searching and matching. When feasible manufacturing resources are outputted, the service composition module goes through all the possible combinations of service units and the best solutions are send to the service consumer for reviewing. Once the service consumer confirms the final decision, the detailed product designs will be passed to participated service providers for service provision. It has to be noted that in this process, only the right amount of information will be send to service providers. The data a service provider receives is only enough for processing the anticipated tasks. On the other hand, a service provider updates available manufacturing resources in the knowledge base by changing their physical descriptions and working schedule. Manufacturing know-how regarding a specific manufacturing resource is not part of the required descriptive information. Enabling technologies for IP protection

The business processes in Fig. 2 reveal that there are at least two technological challenges to be addressed for protecting intellectual properties in the cloud environment. These challenges are (1) developing a unified data model to represent abstract PMI information, and (2) developing a unified scheme for representing manufacturing resources without disclosing detailed manufacturing process for each resource.

Data model for simplification of product design

The most straightforward approach for protecting IP in a product design is to hide the detailed geometrical information in a design. Feature-based approach can be a potential solution. Feature technology is integral to the integration of CAD/CAM. This is because almost all CAPP systems function on the basis of features. One critical step in process planning is to covert a geometric model of lower-level entities (lines, points, etc.) into a feature based model of higher-level entities (holes, pockets, etc.). Hence, there is a need to develop a description model for all the manufacturing features. Parameters on all the machining features of a product are the main data that are required for selecting the right manufacturing resources. This means a mechanical part is described as a combination of a list of elementary machining features. For each of the machining features, the required attributes are the information merely sufficient for determining feasible manufacturing resources that can be used to carry out the required machining process. This approach potentially reveals little information about the geometry of a part. Manufacturing features can be classified by means of manufacturing processes, namely milling feature, turning feature, and holemaking feature. There are several machining features under each category. For example, milling features include pocket, slot, planar surface, chamfer, etc. Feature-based product description creates a way of meta-data modelling for service requests. It has to be noted that the feature-based approach introduced in this paper is different from the feature-based approaches used in commercial CAPP systems or STEP-NC data format. In STEP-NC file, features are still in geometrical representation. For instance, for the feature of General outside profile, the contour of the spare is given by the attribute feature_boundary, which is a type of profile. This means the detailed shape of a profile is still given in a STEP-NC file. In contrast, in the metadata model the definition of a profile only pays attention to the minimum radius in the concave corner, which is one of the critical attributes for selecting feasible cutters. Figure 4 gives an overview of the level of detail for three different data description methods. CAD files contain all the details of a product design. STEP-NC file simplifies the product design, neglecting the detailed geometry of an overall workpiece and some geometry information of some features. This could compress a CAD file to 80% of its original volume. If these machining features are further simplified as only providing the key information for selecting manufacturing resources, the whole file can be compressed down to 50% of its original volume. In this way, most of the geometrical information of a product design is removed, and the associated core IP is protected.

Description framework for resource virtualisation

Protecting the IP associated with a manufacturing resource is equivalently important. One feasible approach is to exclude manufacturing know-how and detailed manufacturing process as part of the description model. The description of a manufacturing resource should include its technical properties and functional capabilities. Take CNC milling machine as an example. Technical properties include its manufacturer, manufacturer instructions, machining envelope, control system, maximum spindle speed, mass, etc., whereas functional capabilities include planar face milling, 3D free-form surface milling, drilling, boring, pocketing, etc. These data should be all the information for describing a manufacturing resource.

Conclusions

Intellectual property protection is critical to business success in cloud manufacturing environment. This paper analysed the requirements of intellectual property protection in cloud manufacturing environment and proposed some strategies for preventing IP leakage. Furthermore, several technological approaches were proposed for implementing a privacy enhanced cloud manufacturing environment. In general, it is best to share as little information as possible for all the parties in cloud manufacturing. This means for service consumers, it is better to outsource only peripheral items, keeping all core IP at home. For a product design, only the information for selection of manufacturing resources can be disclosed at the bid point. For service consumers, they only share a minimum amount of information for resource description and service monitoring. A second strategy is to break up the IP -not giving all of it to any single business entity.

Fig. 1 .

 1 Fig. 1. High-level business interactions in cloud manufacturing[START_REF] Lu | Development of a Hybrid Manufacturing Cloud[END_REF]

Fig. 2 .

 2 Fig. 2. Simplified business process in cloud manufacturing environment

Fig. 3 .

 3 Fig. 3. Classification of machining features

Fig. 4 .

 4 Fig. 4. Level of details for different data description methods


Shiqiang Yu

Xun Xu
email: xun.xu@auck-land.ac.nz

Development of a Product Configuration System for Cloud Manufacturing

Keywords: Product Configuration, Cloud Manufacturing, Everything-as-a-service, Ontology

For Configure-to-Order manufacturing firms, Product Configuration System (PCS) is one of a key components. PCS has been introduced for decades and its technology has matured, providing the industry with a set of usability standards and best practices. However, even the state-of-the-art PCS performs poorly in terms of connectivity, customisation freedom management and implementation. In this regard, this paper first reviews the impact of manufacturing paradigms on product customisation and take Cloud Manufacturing, a nascent manufacturing model, as a disruptive technology to surmount existing obstacles. Then, a general architecture of PCS for Cloud Manufacturing (CM-based PCS) is proposed to conduct configuration reasoning based on cloud-sourced configuration knowledge, to diversify configurable options by introducing proper Cloud Manufacturing services and to fulfil configuration orders through a cloud-based design and manufacturing platform.

Introduction

With emerging disruptive technologies and changing of Customer Needs (CNs) and market demand, manufacturing industry has experienced several paradigms. Mass Customisation (MC) emerged from the 1980s, emphasising the need to provide outstanding service to customers in providing products that meet CNs at a low cost [START_REF] Ferrer | Open architecture, inventory pooling and maintenance modules[END_REF]. Due to trend of globalisation, paradigms complying with more specific CNs emerged, such as oneof-a-Kind Production (OKP) emphasising the "market-of-one", and Mass Personalization (MP) aiming to reveal latent CNs [START_REF] Zhou | Affective and cognitive design for mass personalization: status and prospect[END_REF].

Recently, a new service-oriented manufacturing model, Cloud Manufacturing (CM), emerged. As a nascent paradigm, CM is considered as a promising paradigm that will change the way manufacturing businesses operate. In the literature, Cloud Manufacturing-related definitions have been elaborated by different researchers. Main stream definitions of CM contain key words like networked manufacturing, ubiquitous access, multi-tenancy and virtualization, big data and the IoT, everything-as-a-service (e.g., infrastructure-as-a-service, platform-as-a-service, hardware-as-a-service, and software-as-a-service), scalability, and resource pooling [START_REF] Xu | From cloud computing to cloud manufacturing[END_REF][START_REF] Li | Cloud manufacturing: a new service-oriented networked manufacturing model[END_REF][START_REF] Wu | Enhancing the Product Realization Process with Cloud-Based Design and Manufacturing Systems[END_REF].

It is obvious that the evolvement of manufacturing paradigms is affecting the way of producing customised products. To achieve increased customisation requirement, manufacturers' resource and capability for design and manufacturing are met with challenges. Customisation freedom, to a certain degree, depends on the volume of manufacturing resources at hand, so new emerging manufacturing paradigms will boost indepth customisation.

Comparing to conventional manufacturing paradigms, Cloud Manufacturing makes manufacturing firms more accessible to external manufacturing resources. From this point of view, Cloud Manufacturing is a remedy bridging the gap between diverse CNs and insufficient internal manufacturing resources and capability. Obviously, manufacturing enterprises, in particular Small and Medium-sized Enterprises (SMEs), can deliver more in-depth customisation by adopting Cloud Manufacturing.

Product configuration is an activity of customising a product to meet the needs of a particular customer. Product Configuration System (PCS) is a tool to conduct an activity of customising a product to meet the needs of a particular customer. To utilise manufacturing resources in a "cloud", a new generation PCS is a necessity for configuration in a cloud environment.

2

Challenges of Developing the Next Generation PCS

Issues of Existing PCS

With the introduction of AI and cloud technologies, cloud-based PCS is currently the most advanced. Recently, numerous PCS vendors have launched their "cloud-based product configuration solutions", in which cloud concept is embedded.

In fact, those cloud-based PCSs in use are far from being perfect. Firstly, none of cloud-based PCSs could quickly respond to changes in the production systems and the supply chain. Such a drawback results in an array of issues like non-support of dynamically processing Request for Quotation (RFQ) and lower degrees of product customisation freedom to customer. Besides, the cost of the maintenance and management of configuration system is truly high especially when the configurator aims at structural and compositional configuration of a complex Engineering-to-Order (ETO) product. It is because any change of manufacturing capability or disruption of supply chain may incur momentous adjustment of configuration options and pricing/quote. Another factor restricting the application of PCS is that implementing a new PCS requires significant and potentially painful changes in the way the order acquisition and fulfilment activities are organised, and necessitate a high initial investment in terms of man-hours.

Future of PCS

Main stream ERP vendors (e.g. SAP and Infor), CAx software vendors (e.g. Autodesk) and some other software vendors (Tacton, KBMAX and Mycustomizer) have delivered their cloud-based product configuration systems. With features of PaaS and IaaS, these cloud-based solutions enable manufacturing firms to provide engineers, sales reps, and end customers with web and even mobile access to a configuration as a thin client (i.e. with nothing to install). Those cloud solutions only enhanced accessibility and computing capability of PCS, but made very little difference to above-mentioned gaps.

As mentioned in Section 1, phasing in Cloud Manufacturing will facilitate more indepth product customisation. Meanwhile, manufacturing resources and capability encapsulated as cloud services in Manufacturing Cloud is promising to revolutionise PCS in future. For instance, numerous manufacturing services could greatly increase the customisation freedom of products; an open architecture PCS platform integrated with Manufacturing Cloud is much easier for an enterprise to develop a brand new PCS or to upgrade dated one. As manufacturing services can be published in terms of real-time information, any changes happened in supply chain and outsourced supply chain are able to be taken into account in each configuration.

For those reasons, this research considers Cloud Manufacturing as a disruptive technology to upgrade its precedents and focuses on developing Product Configuration System for Cloud Manufacturing (abbreviated as CM-based PCS in following paper). In comparison with conventional cloud-based PCSs getting access to computing cloud, storage cloud and etc., CM-based PCSs further integrate with Manufacturing Cloud which encapsulated a wide range of manufacturing services stemmed from distributed manufacturing service providers. Such connectivity to manufacturing resources and capability makes CM-based PCS able to react to dynamic requirements from customers, and meanwhile enhances configurability of products by discovering new manufacturing services which can be applied to the development of new product variants.

Implementation of CM-based PCS

Nowadays, ever-increasing resources from the plant floor and headquarter are virtualised and encapsulated as cloud services, and next generation applications (e.g., PCS) definitely require connectivity to ubiquitous clouds. Integrating a PCS with Manufacturing Cloud will facilitate scalability and utilisation of facilities [START_REF] Yip | A Product Configurator for Cloud Manufacturing[END_REF]. So far, there is no literature on any systematic methodology of implementing CM-based PCS.

Integration with Manufacturing Cloud

The research utilises the cloud computing concept and service-oriented principles to enhance conventional PCS technology. To achieve that, the concept of Manufacturingas-a-Service (MaaS) and Design-as-a-Service (DaaS) are embedded here. Based on the concept of MaaS, to fulfil product configuration, production systems on the basis of accessibility of PCS can be integrated with manufacturing services via a certain Cloudbased Design and Manufacturing (CBDM) platform [START_REF] Lu | Development of a Hybrid Manufacturing Cloud[END_REF]. It provides users with a level of product customisation freedom that is directly integrated to the available manufacturing capabilities of production sites within a cloud manufacturing infrastructure. Meanwhile, manufacturing services stemmed from the visualisation of pool of manu-facturing resource are promising to boost the capability of product design within configuration process by creating a dynamic co-design environment for the interaction between customers and manufacturers. Manufacturing services may be internal (i.e. the manufacturer itself) or external (i.e. supplier, outsourced supplier, etc.). Manufacturing Cloud can be classified similarly by introducing the concept of cloud computing embracing four types of deployment models, including 1) private cloud: a centralised management effort in which manufacturing services are shared within one company or its subsidiaries; 2) community cloud: a collaborative effort in which manufacturing services are shared between several organisations from a specific community with common concerns; 3) public cloud: a set of manufacturing services in which manufacturing services are available to the general public [START_REF] Lu | Development of a Hybrid Manufacturing Cloud[END_REF]. To seek proper manufacturing resource, manufacturing firms would typically give priority to their internal manufacturing resources, then, if necessary, cooperation within community would be another good choice, and an anonymous supplier from public cloud will be the last option.

Architecture of the Reasoning Engine

Considering incremental changes and updates on products due to new technology advances and the expansion of the Internet, a configuration model supports knowledge reuse and sharing is crucial. In order to utilise ubiquitous cloud and realise configuration based on CM, an ontology-based approach is adopted in this research.

Fig. 1. Four-layer modelling architecture

Ontology is a formal, explicit specification of a shared conceptualisation. There has been literature of addressing the modelling of product configuration knowledge with an ontology-based approach in which structural knowledge is formalized in OWL (Ontology Web Language) [START_REF] Mcguinness | OWL web ontology language overview[END_REF] and constraint knowledge in SWRL [START_REF] Horrocks | SWRL: A semantic web rule language combining OWL and RuleML[END_REF], (Semantic Web Rule Language). Through the transformation of configuration knowledge into Jess facts and Jess rules, actual configuration processes are carried out with the support of Jess [START_REF] Friedman | Jess in action: rule-based systems in java[END_REF], a rule engine for the Java platform.

To encourage reuse of configuration models and flexibility in representing knowledge, the presented modelling approach for product configuration knowledge follows four-layer architectures [START_REF] Yang | Development of a product configuration system with an ontology-based approach[END_REF]. Unlike a usual ontology-based configuration engine, the instance layer and the model layer are integrated cloud-sourced knowledge for extension in this research (see Fig. 1). The difficulties in modelling product configuration knowledge can be dramatically reduced by constructing configuration models based on existing configuration knowledge instead of starting for scratch.

The advantage of OWL-based configuration models is that the reuse of configuration models can be ensured since OWL, as an ontology language, supports knowledge reuse and sharing. This is especially crucial, considering incremental changes and updates on products due to new technology advances.

Prototype of the CM-based PCS

To integrate the ontology-based PCS with Manufacturing Cloud, we propose a novel way to obtain constraint knowledge in SWRL by extracting and parsing distributed configuration knowledge stemmed from the resource pool of manufacturing resources.

The thorny problems here include: 1) to establish a communication mechanism enabling the interaction between PCS and Manufacturing Cloud; 2) to depict configuration-relevant manufacturing resources and external inventory information in a unified way which supports the reasoning of Ontology-based PCS engine; 3) to archive CMbased request for manufacturing (RFM), including production documentation and product information model, in an easily accessible and retrievable manner.

Fig. 2. Communication between PCS and Manufacturing Cloud

The communication mechanism, to address the first issue, proposed in this paper is shown as Fig. 2. According to the diagram, the interaction between PCS domain and Manufacturing domain mainly depend on the introducing of Manufacturing Cloud retrieving engine which is actually an ontology-based reasoning engine.

To address the second issue, a shared ontology for all service providers describing available product catalogues, inventories, manufacturing resources and manufacturing capability is proposed. In this way, supplementary configuration knowledge from cloud encoded in the format of OWL and SWRL could be transformed into Jess facts and rules for inference. The advantage of OWL-based configuration models is that the reuse of configuration models can be ensured since OWL, as an ontology language, supports knowledge reuse and sharing. The Jess rules mentioned in this diagram are developed by using the Extensible Style-sheet Language Transformations (XSLT) to perform the transformation from XML documents to Jess files.

After configuration reasoning, the CM-based PCS will generate not only a configuration but also a CM-based RFQ which may include request of procurement and outsourced manufacturing task enabled by manufacturing service provider via CBDM platform. This research utilise the interoperability of the STEP format to carry necessary information the RFM needed. In consideration of increasingly large product model, a new edition of Part 21 of ISO 10303 is adopted to archive and compress (in ZIP format) possible gigantic RFM information in configuration of complex ETO product. Part 21 is a specification for how to format entities describing product data [12]. It is a public domain file format for the geometry of assemblies and is widely used by industry to describe design and manufacturing specifications for airplanes, automobiles, ships, buildings and other products. This research archive RFM data by Part 21 Edition 3, so a parser capable of automatically interpreting configuration results into an EXPRESS schema is necessary to generate RFM.

4

Case study

To implement and validate methodologies proposed in this paper, this work chooses a local manufacturing firm, Compac Sorting Equipment (abbreviated as Compac in the following paper) to conduct a case study. Compac's headquarter is located in Auckland, New Zealand, and its branches and suppliers are around the world. Compac is a manufacturing firm producing sorting machines which are ETO products with high complexity. Typically, a sorting machine produced by Compac is a streamline machine system mainly including infeeding, sorting and grading, bagging and packing sub systems. To be specific, an infeed system is capable of tipping, washing and treatment of fruits, sorting and grading sector support sorting fruits by weight, colour, density, size, shape, surface defects and internal properties of fruits. One thorny issue is configuration rules coding due to the complexity of their product. The company is working on developing a traditional rule-based configuration system. However, as above mentioned, knowledge reuse and sharing is essential in a configuration in cloud environment. This research therefore transforms their codes into the ontology model of product configuration and associated rules in parallel.

As above-mentioned methodologies, this research adopts ontology-based PCS to tackle configuration task, and the ontology model of the main component of sorting machine are built. The ontology model proposed is modularised according to the features of the sorting machine which typically consist of a sorter, washer and packer. The constraint knowledge is modularised as different cluster. The essential data for CMbased RFM is compressed as a ZIP archive.

As Fig. 3 shown, a configuration is generated according to CNs and cloud-sourced knowledge, then configuration result is compressed in accordance with P21 Edition 3.

Fig. 3. Product configuration of sorting machine

This case study only establishes a prototype of product configuration system for cloud manufacturing. Due to the complexity of products, a complete PCS for a whole streamline equipment required more endeavour to achieve. Even so, the current prototype has demonstrated that such a methodology of developing CM-based PCS is practical and feasible.

Conclusions

This paper has first presented the survey on existing commercial cases of product configuration solutions and a literature review on technologies associated with PCS. The research concluded that even state-of-the-art product configuration tools are far from being satisfactory and the introduction of cloud manufacturing has the potential to enhance conventional PCS by boosting connectivity, enabling customisation freedom management and facilitating implementation with a low effort. To integrate Manufacturing Cloud with PCS, this paper proposed a methodology for implementing CMbased PCS. In order to utilise huge amount of cloud-sourced configuration knowledge, an ontology configuration model has been adopted to realise knowledge reuse and sharing in a ubiquitous cloud. The prototype of CM-based PCS proposed here is accessible to internal and external manufacturing resources via Manufacturing Cloud. Meanwhile, inclusive manufacturing services could enrich configuration options to some extent. Most importantly, an open architecture platform based on general ontology configuration model could be developed to reduce the cycle of PCS implementation. This research validates methodologies through a case study of complex ETO products.

The prototype of CM-based PCS described in this paper promises to transform existing PCSs into full-fledged cloud solution. Nevertheless, it has some limitations. For example, ontology models in this paper were built manually. This is because so far there has not been an effective way to generate ontology automatically. Additionally, further study has been planned to retrieve, filter and optimise available cloud services in complex cloud environment.

Acknowledgements. The work presented in this paper has been financially supported by the China Scholarship Council and the University of Auckland Joint Scholarship. The authors also wish to acknowledge the contribution from partner company, Compac.


Jiří Faist
email: faist@ntis.zcu.cz

Milan Štětina

Webservice-Ready Configurable Devices for Intelligent Manufacturing Systems

Keywords: structured text, control system, embedded device, Web Service, IEC 61131-3

This paper takes closer look at inner structure of an eScop RTU device, a highly configurable PLC-like embedded device developed in Node.js environment for low level physical layer of Intelligent Manufacturing Systems.

Introduction

Embedded system for Service-based Control of Open manufacturing and Process automation (eScop) is a system that aims to overcome the current problems of production systems integration at shop-floor control level by semantically integrating embedded devices. The main idea behind the eScop architecture is to use embedded devices together with an ontology-driven service-oriented architecture (SOA). This approach allows the system to be automatically configured based on the ontology using embedded devices at the physical layer. This reduces setup time during which the manufacturing system stops.

eScop Device

eScop system is based on embedded devices -eScop devices. Profile of these devices is introduced in [START_REF] Severa | INDIN 2015 IEEE International Conference on Industrial Informatics[END_REF] where basic behavior and REST interface of device are described. Purpose of this article is to give closer insight into inner structure of eScop device.

Components of eScop Device (or eScop Remote Terminal Unit -RTU) are depicted in figure 1. Apart from the REST-API, eScop device consists of three components that enable the device to execute scripts written in Structured Text. Structured Text Language(STL) is one of five languages supported by the IEC 61131-3 standard and is designed for programming PLC devices.

STL Parser/Interpreter

One of the main goals to reach when developing eScop device was to create easily reconfigurable PLC like device. Configuration of the device is done through scripts written in Structured Text. An STL Parser/ Interpreter was created using Bison and Flex. Bison is a general-purpose parser generator that converts an annotated context-free grammar into a deterministic or generalized parser [2]. Flex is a tool for generating programs that perform pattern-matching on given text [START_REF]The Flex Project, Lexical Analysis With Flex[END_REF].

Detailed description of STL Parser/Interpreter interface can be found in table 1. First part of the interface contains functions for manipulation with STL files in interpreter like loading new file to interpreter or removing file from interpreter. Second part of the interface contains functions for calling STL functions. STL interpreter currently also supports functions with parameters that are passed into the function by reference. These references can be created and destroyed by functions PushArray() and PopArray(). This mechanism is necessary for calling functions with arrays as parameters or with in-out parameters that serve as input and also as output.

The function for calling STL functions CallFunction() has an option to specify how many instructions in STL language should the interpreter process. This enables to suspend the STL function execution and gives the option to trace the program's execution and can be used for debugging purposes. If function's execution has not finished, CallContinue() function must be called to continue the execution.

Last part of interface contains functions for handling events. Event is raised when the STL Interpreter reaches instruction EVENT(X), where X is an integer that identifies the event. Raising an event will cause the interpreter to stop exe-cution and give the programmer opportunity to react to this event. This mechanism was later generalized for defining external functions. External functions are defined as functions that are only declared in STL file but they are implemented elsewhere. External function in STL file is declared by its header with specified parameters and with an instruction EXTERN in its body. This specific instruction is just a macro for raising special event that denotes external function execution. Example of definition of external function can be found in code snippet 1. If a parameter should be passed to the function by reference than this function must be called before actual call of the function to push parameter to the interpreter and obtain reference (pointer).

PopArray()

After argument passed in by reference is not used anymore than this function should be called to clean up.

Events and Extern functions interface GetEventFunction() Returns function that the event was raised in. GetEventParam() Returns parameters of function that the event was raised in. GetEventArray() Returns parameters passed in by reference.

4 Integration of STL Interpreter with Node.js STL Interpreter is a component where computing power is very important aspect. That is also one of the reasons why this component is implemented in C programming language. However for the development of eScopdevice was chosen the Node.js runtime environment mainly for its event-driven architecture and a non-blocking I/O API that optimizes an application's throughput and scalability. Now the question has been raised how to integrate these two environments together.

Node.js supports two options how to use libraries written in C/C++ from JavaScript code. First of them is to use FFI (Foreign Function Interface) mechanism and that allows to call a function from one program in another program usually even across programming languages. Using FFI involves loading shared library at runtime and marshalling the arguments of function from one program to another before each call. This mechanism is very simple to use but not very efficient.

The other option is to write a specific so called native addon in C/C++ that wraps functions from desired library. This addon than can be used in JavaScript code in same manner as any other JavaScript object. This approach is about hundred times faster than FFI but developer needs to handle every conversion between JavaScript types and C/C++ types by himself.

The approach using FFI might still be useful for calling functions containing heavy calculations and/or if these functions are not called very often but for the purpose of eScop device its performance is insufficient. That is why it was chosen to implement native addon for Node.js that serves only as a thin wrapper for STL Interpreter. This wrapper is denoted as NodeSTL component in figure 1.

STL Manager

A Service Manager Core component was introduced in [START_REF] Severa | INDIN 2015 IEEE International Conference on Industrial Informatics[END_REF]. This component is partially implemented by the component STL Manager that manages adding and building services simply by using NodeSTL component and its STL Interpreter to load STL file and expose functions defined inside as new services.

Task management

STL functions can be designated as one of three types of services defined by [START_REF] Severa | INDIN 2015 IEEE International Conference on Industrial Informatics[END_REF] as process, operation and query. Execution of services defined in STL files must be controlled to avoid deadlocks and collisions in STL interpreter. Thus a simple task management have been introduced.

Every service invocation creates a task that is assigned a priority based on its service type. The task is than pushed to a priority queue and executed once it is popped as the first in line. Task management algorithm also uses the concept of specifying how many instructions should the STL Interpreter execute. That enables the manager to suspend task before it has finished and execute task with higher priority.

Number of instructions to execute depends on the priority of task. For example services designated as query should be very fast performing only small number of instructions. Thus they should have high priority and high number of instruction to be executed since these services probably should not be suspended at all. On the other hand services designated as process are usually long life services performing large number of instructions and thus should have small priority and small number of instructions to execute since these services should be suspendable in case that new tasks with higher priority occur.

To avoid deadlocks and collisions, it was decided to use one STL interpreter per STL file with assumption that every interpreter can have only one function running or in pending state. The STL Interpreter can be taken as a critical section and each executed task blocks every other task coupled with the same interpreter.

However this approach can lead to so called Priority Inversion Problem. That is a situation when task with higher priority is blocked by a task with lower priority. This creates a deadlock since lower priority task cannot continue its execution since a task with higher priority occurred. Thus The Basic Priority Inheritance Protocol suggested in [START_REF] Sha | Computers[END_REF] was adopted. Simply put this simple algorithm assigns the lower priority task with the highest priority of the tasks that are blocked by it. Due to this change of priority the lower priority task can be executed first and thus unlocks the interpreter for task with higher priority as soon as possible.

STL IO

Since the eScop device should serve as PLC like device it must be able to read physical inputs and write to physical outputs. Raspberry Pi was chosen as a hardware platform in combination with UniPi.

Raspberry Pi is a low cost single chip credit-sized computer based on BCM2835 unit. It can be used in many ways as regular computer but in addition it also features GPIO (general purpose input/output) pins that serve as a physical interface between Raspberry Pi and other devices [START_REF]RASPBERRY PI Documentation[END_REF]. To make Raspberry Pi more PLC-like device a UniPi board was added. UniPi board was designed with Raspberry Pi in mind. It features 8 relays, 14 digital inputs, single channel 1-wire interface, 2 analog inputs, one analog output and Real Time Clock module [6].

For communication and for handling of physical signals were developed 3 drivers that a developer can use. STL IO is a component that serves for registering and deployment of drivers to STL Interpreters. With these drivers can eScop device communicate with many already existing real world systems.

STL IO drivers:

1. UniPiDrv -This driver serves for reading digital inputs and setting relays on UniPi board. It allows the system to read input signals and control physical processes.

2. RESTDrv -This driver allows to call various REST services by serializing inputs to JSON data format in request and deserializing JSON data from response. It allows the system to communicate with various systems on network. 3. RexDrv -This driver communicates with the system REX -Control System for Advanced Process and Machine Control [START_REF]REX Control system[END_REF]. It allows the system to manage real-time control processes in REX.

Drivers implementation

Drivers use the mechanism of calling external functions in STL Interpreter introduced earlier. STL file contains declaration of external function and its implementation lays in the JavaScript code. An example of external function declaration can be found in code snippet 1 and its implementation in code snippet 2. It is a function taken from UniPiDrv driver for reading relays on UniPi board. The implementation in JavaScript is a function that takes 3 arguments. First argument is an array of inputs, second is an array of outputs and third is a callback that must be called after execution of external function is finished. The reason for using callback is that the function can be asynchronous as it is in our example in code snippet 2. Callback takes a return value of the function in STL as argument.

Few special attributes are set under the function implementation. They serve like annotations. First annotation is mandatory and helps to distinguish regular JavaScript functions from those implementing external functions. The rest of annotations are optional and allows to specify data types of external function parameters and return value in STL. This helps to ensure that both the STL code and JavaScript code use same data types right after compilation of STL file. This prevents from using incompatible drivers during STL function execution.

Pragmas

As it was stated before services should be divided by their type into tree classes: process, operation and query. Every service is than represented by a STL function. The information about the type of service must be presented in STL source code. It was therefore decided to introduce pragmas as a way to annotate STL source code. Example of service function annotated with pragmas is in code snippet 3.

Pragmas can be viewed as additional comments inserted into code but unlike comments that are ignored by the interpreter, pragmas are recognized and can affect the behavior of the program. The IEC 61131-3 only states that pragmas exist, they are delimited by curly braces ({ ... }) and contain attributes separated by comma but their definition is implementation specific. Pragmas attributes:

name -Specifies an alias to identify service. Use only if it is different than name of function. description -Should contain user friendly description of service.

type -Specifies type of service (process, operation, query). This attribute can also contain type 'event' that denotes that this function is not a service but an event.

schedule -Specifies the scheduling of the service in case it is a process.

• periodic -Service is called periodically by the device in the defined period. • continuous -Service is called cyclically without sleep between calls.

• init -Service is called upon device initialization.

• exit -Service is called upon termination of the device.

• error -Service is called when error happens on the device.

period -Specifies the period of calling the service in ms.

-externFunction -Specifies the identifier of external function in JavaScript if the name differs from the name of function declared in STL. This allows to use one external function from driver for multiple STL functions.

Pragmas can also be used to annotate parameters of function however no specific format was defined for it yet.

Conclusion

The purpose of this article is to give closer insight into inner structure of eScop device. These units' functionality is controlled by scripts written in Structured Text language. This article describes components developed for this functionality such as STL Parser/Interpreter for interpreting Structured Text code, STL-Manager for task management and collection of drivers for control of physical signals and for communication with other devices. eScop Device framework can be used for managing and seamless expanding of Intelligent Manufacturing Systems. Software was tested on Raspberry Pi and will be part of INCAS pilot application described in [START_REF] Balda | INDIN 2015 IEEE International Conference on Industrial Informatics[END_REF].

Acknowledgement

This work was supported by the ARTEMIS Joint Undertaking grant No. 332946 and by University of West Bohemia -SGS-2010-036.

Fig. 1 .

 1 Fig. 1. eScopRTU device

1 FUNCTION 1 .

 11 Declaration of external function in STL.

1 { 2 FUNCTION serviceName ; 3 VAR_INPUT 4 { 8 END_FUNCTIONCode snippet 3 .

 123483 type = ' process ' , schedule = ' periodic ' , period =1000 , externFunction =" postService " , description =" myDescription " } description =" this is my input " } ; Example of function with pragmas annotation.

Table 1 .

 1 STL Parser/Interpreter interface

	File manipulation interface
	AddStl()	Loads new file into the parser and returns list of
		functions it contains.
	RemoveStl()	Removes specified file from the parser.
	ResetStl()	Resets parser. Used when errors occur.
	Function handling interface
	CallFunction()	Calls specified STL function.
	CallContinue() Continues execution of the function if the execu-
		tion have not finished by calling CallFunction().
	PushArray()