IoT applications are often ad-hoc compositions of services o ered by connected devices that cooperate to satisfy user's goals. Sometimes, addressing full goal satisfaction is too stringent and replacing that with an easier to satisfy partial goal satisfaction is a good alternative to a complete failure. In this paper we propose a service composition approach that adopts a metrics for measuring the partial satisfaction of goal. The metrics adopts an electrical analogy extended for dealing with temporal goals.
Today, the Internet of Thing (IoT) plays a more and more important role in
our lives. According to a recent report from Cisco, the IoT will consist of 500
billion devices connected to the Internet by 2030. Each device includes sensors
that collect data, interact with the environment, and communicate over a
network. IoT applications are built as emerging compositions of devices' services
according to contingent user's goals[
The research topic of partial goal satisfaction yields to overcome the barrier
of utilizing existing planners when boolean satisfaction conditions are too strict.
Researchers study mechanisms for di erentiating between optimal and feasible
plans, thus, in case the optimal plan does not exist, the planner may still return
something more than the empty plan. In literature, there are many application
domains that lead to di erent proposal of partial satisfaction, often depending on
the speci c de nition of goals. In some domains, variables are continuous, and a
goal is de ned as the maximization/minimization of an utility value representing
how much the goal worths for the user. In these cases, partial satisfaction means
? Copyright c 2019 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0)
reaching a non-optimal value. This may often happens when reasoning with
incomplete information about the context [
In many cases, the goal model is de ned as a tree of goals, obtained through
AND/OR decompositions of a root goal. Here, partial satisfaction means relaxing
some of the goals thus to be dealt as weak constraints. In this view, a valid
plan may ful l only a subset of them. For instance, [
In this paper we propose a service composition approach that adopts a
metrics for measuring the partial satisfaction with respect to temporal goals. Our
idea of partial goal satisfaction has been already stated in [
The paper is structured as follows: Section 2 presents the framework used for service composition. Section 3 describes the resistance to goal satisfaction (R2S) metrics for measuring the partial goal satisfaction of a propositional formula. Section 4 extends the R2S formulation for the Finally and the Globally operators by adopting Petri-net models. The nal Section 5 reports some conclusions and future works. 2
The service composition domain is presented by means of a non-deterministic state-transition system, namely the World Transition System built for describing the e ects of actions, in order to address a speci ed goal.
De nition 1 (World Transition System). Given , the alphabet of predicates, and C the set of capabilities, the World Transition System (WTS) is a tuple W T S =< W; T; R; L > where: { W 2 is the set of states of the world
(where w 2 W is a vector of boolean variables, associated to { T : W C ! W is the transition relation { R : W ! R is the scoring function { L : W ! fS; F; W S; W F g is the temporal labeling function )
A capability c 2 C represents the non deterministic action associated to a service. It wraps the service by denoting a precondition (the condition necessary for executing the service) and a range of possible e ects. Each capability e ect describes one possible state evolution W ! W due to the service invocation.
In this context, the planning domain is identi ed by the tuple D =< I; Cav; G > where: { wI 2 W is the initial state of the world, { Cav C is a set of capabilities that are available at the time of planning, { G is a set of goals expressed in linear temporal logic (LTL).
The Linear Temporal Logic (LTL) [
are atomic formulas, i.e. simple predicates.
Brie y, LTL formulas are based on propositions and their combination through logical connectors and temporal operators. While logic connectors can only describe a static behaviour, limiting their arguments validation to only one state, temporal operators requires looking at multiple states for their validation. The basic and derived temporal operators are: { The X operator (Next) imposes that ' will be true in the next state. { The U operator (Until) states that ' will be true in every state until becomes true and imposes that sooner or later will become true. { The F operator (Finally, sometimes ) F = >U states that eventually, at least once, ' will be true in a future state. { The G operator (Globally, sometimes ) G = :F : means ' must be true in every state (current and future).
The WTS is non-deterministic because the same capability may be associated to many world evolutions. In practice, at planning time, these evolutions are alternative, and the planner must consider all of them. Indeed, the result of the planning encompasses plans with decision points and loops.
De nition 3 (Non-Deterministic Solution). A Non-deterministic Solution , is de ned inductively as = c j c j ( ) where c 2 Cav, is the concatenation operator, is the decision operator and is the exclusive or.
Intuitively, a plan identi es a work ow of actions. The de nition of includes sequences (classical plans), decision points (non-deterministic plans) and loops, as shown in Figure 1. Whereas classical planning produces plans which execution will address the given goal, in this paper, we front a slightly di erent problem. We search for plan which execution may not lead to the desired nal state.
Partial satisfaction of the given goal : may lead to either Full or {
is a full solution when the execution of the plan Exec( ) j= ; { otherwise, the plan is said partial solution.
c1 c1 c1 c2 c3 c2 c3 c2
The proposed planning algorithm for service-composition with partial goal satisfaction derives from a best- rst search in the state-of-world state. Data: w0,G,cap set Result: solutions Function service composition(w0,G,cap set): solutions ; W T S initialize W T S(w0) repeat nodei get highest from frontier(W T S) expansion set service composition(nodei; cap set) foreach state 2 expansion set do state:token check LT L(state; goal; nodei) if state:token = SUCCESS then
solutions search solutions(W T S; state) else end score W T S evaluate partial sat(state; token) update W T S(W T S; state; token; score) end until size(solutions) MAX SOL and size(W T S) partial solutions search partial(W T S) sort(partial solutions) End Function MAX SP ACE Algorithm 1: Planning Algorithm for Service Composition with Partial Goal Satisfaction
Algorithm 1 iteratively builds a WTS, starting from the initial state w0. At each step the algorithm looks at the frontier (the nodes that are not yet visited) and it expands the most promising node by using the applicable capabilities. The preference on the node to be selected for the expansion is evaluated using some user heuristic. In this planning algorithm, temporal aspects are useful for determining full and partial solutions. Each node is marked with four types of temporal markers: full success (S), total failure (F), partial success (WA) and partial failure (WF). These are explained in details in Section 4.
Indeed, W T S is a full solution when it starts from the initial state w0, it does not contain any Failure state, and all the subpaths terminate in a Success state (loops are valid if they have an exit condition towards a Success state). Typically the algorithm terminates when a su cient number of full solutions are discovered. However, it may be the case that such solutions do not exist. In this case the algorithm terminates when the WTS size is over a given threshold1. When the algorithm terminates, we explore the WTS for extracting partial solutions. W T S is a partial solution when the initial state is w0, but (di erently from full solutions) it can contain some Failure states, and subpath that terminates in a partial success state (WS) are allowed. Clearly, not all the partial solutions are equally acceptable. We de ned a metrics for ordering them according to a \Distance to Goal Satisfaction". This metrics will be discussed in details later, in subsection 3.1. 3
A goal is a logical formula composed by propositional variables, logical connectives and temporal operators, as seen in Section 2. 1 Alternatively, Algorithm 1 may terminate after a given time interval.
An example of goal may be the speci cation of the status of some tra c lights and direction signals for speeding up the evacuation of inhabitants in a city district in case of an emergency.
In our study we consider the possibility that some of the goal conditions cannot be achieved by the system itself without the intervention of the user. For instance, some tra c direction signals may not be activated by a remote system and therefore a human being has to correctly deploy them. 3.1
The R2S Metrics for the Propositional Logic In some situations, goals cannot be achieved even involving the human in their pursuit. Therefore we explicitly consider the possibility to nish our solution planning activity with a Not(Goal) condition that means the intended goal formula has not been veri ed. Usually, by employing the available services in one of the studied plans, the system may reach states where some of the variables composing the goal formula are satis ed. We call these Partial Solution States and, the problem becomes to nd a metrics for selecting the best partial solution state. Even a state where none of the propositional variables in the goal formula is veri ed may be seen as a partial solution state, of course that would be the least preferable one.
In considering what metrics could be useful for evaluating the goodness of
a partial solution state, we could refer to contributions from literature like [
Going back to the example of tra c lights and direction signals, suppose the best evacuation route may not entirely ruled by tra c lights and direction signals because one turn at a speci c point is not provided with any remotecontrolled device. Two options of partial satisfaction may be pursued: in the rst the system chooses an alternative (sub-optimal) route, in the second the system activates the best route and warns the user of the lack of a signal in a speci c location. A police unit may be dispatched to solve that in order to obtain the full satisfaction. Which of the two solutions is preferable strongly depends on the problem and on the speci c emergency (system status). For this reason, in many applications we suggest leaving the nal decision to the human. It is worth noting that adopting the rst option (good state for staying in a partial solution situation) may bring the system far from a state the ensures a viable solution at the next step (for instance with a human intervention).
In order to measure the distance of a state in the solution space from the
desired goal we introduce the following de nition [
According to this informal de nition, the Distance to Goal Satisfaction depends on two factors: { The number of variables to be changed: this is the minimum number of propositional variables in the goal formula that have to change their value in order to fully satisfy the goal. { The degree of freedom: sometimes the goal formula may be satis ed by changing the value of n variables chosen among m candidate variables (with m>n). An obvious case for this situation is represented by the OR condition where it is possible to verify the OR formula by changing to true the value of one of the two variables.
Intuitively we may justify this approach by saying that the more variables it is necessary to change in order to satisfy the goal, the more the point in the solution space is far from the point representing the goal. Indeed, this is not su cient in the proposed approach: two di erent points with the same number of required changes have di erent proximity to the goal if one of them o ers the possibility to choose the variables to be changed in a large number of options.
In order to operationalize the estimation of the Distance to Goal Satisfaction, we introduce a metrics, called Resistance to Goal Satisfaction that adopts an electric analogy for deducing an electric circuit from the goal formula. The equivalent resistance o ered by this circuit will be considered as an estimator of the distance to goal satisfaction. 3.2
Electrical Analogy: from Goal Formula to Equivalent Circuit The transformation of the goal formula to the equivalent circuit is based on some simple rules: { Each logic variable of the goal formula is represented by a resistor in the equivalent circuit. { The value of each resistor depends on the value of the logic variable. If that is true, the value will be Rmin, otherwise it will be Rmax. Such values are chosen very di erent in magnitude, ideally they would be Rmin= 0 (short circuit) for the true variable, Rmax= 1 (open circuit) for the false variable but this would create problems in calculating the equivalent resistance for some circuits. { Each AND operator corresponds to the series connection of the resistors representing the variables in the AND conjunction. { Each OR operator corresponds to the parallel connection of the resistors representing the variables in the OR disjunction. { Each NOT operator corresponds to inverting the value of the resistor representing the negated variable (if the variable is true, the corresponding resistor value is Rmax and so on).
This analogy allows calculating R2S of propositional formulas, as shown in Algorithm 2.
Data: ,wi,R = fRA; RB; :::g Result: R2S( ) Function r2s( ,wi,R = fRA; RB; :::g): case = p is a predicate do if wi j= p then
return Rp else
return 1=Rp case case case end
= do return^R2S( ) + R2S( )
= _ do return 1=(1=R2S( ) + 1=R2S( ))
= : do return 1=R2S( ) end
End Function Algorithm 2: Function for calculating the R2S of propositional formulas.
It is worth to note that di erent values may be chosen for the resistance representing each propositional variable. This would correspond to considering a di erent relevance for the variable in the goal formula. We are not studying this case since it would bind the R2S to the domain and we prefer to maintain that as general as possible.
Property 1 (De Morgan's Laws). The R2S metrics is valid with respect the following transformations:
R2S(:(A [ B)) = R2S(:A \ :B) and
R2S(:(A \ B)) = R2S(:A [ :B). also known as De Morgan's Laws.
This property may be easily veri ed by applying the above reported algorithm. Now, let us suppose we want to study the following goal formula:
G = (A ^ B) _ C
According to the proposed transformation rules, the equivalent circuit and the equivalent resistance R2S would be the ones represented in Fig. 2. The goal G will be veri ed for ve conditions of the A,B,C variables as reported in the table in Fig.3.
The columns of the table reports: the values of A,B,C, the corresponding value of the goal G, the minimum number of variable changes that are necessary in order to satisfy G, the degree of freedom in variable changes, the resistance to satisfaction R2S.
Three di erent conditions do not verify the goal, they are: (0,0,0), (0,1,0), (1,0,0). The aim of the proposed metrics is to estimate which one would be the best choice for our planner. By adopting the equivalent resistance formula reported in Fig.2, and supposing we adopt the value RX for Rmax and the value Rm for Rmin where the previous one is several orders of magnitude bigger than the second one (RX >> Rm) we obtain the following result for the R2S for the condition (0,0,0):
While the R2S for the condition (0,1,0) is:
R2S(0; 0; 0) = (RA + RB)RC RA + RB + RC (RX + RX )RX
RX + RX + RX R2S(0; 1; 0) = (RA + RB)RC RA + RB + RC (RX + Rm)RX
RX + Rm + RX = = =
RX 2 3 1 2
RX (2) (3)
The R2S for the last condition of partial goal satisfaction (1,0,0) may be easily calculated as the previous one (with the same result).
Finally, in order to verify the result provided by the proposed approach in case of full goal satisfaction, we can calculate the R2S for the (0,0,1) condition: R2S(0; 0; 1) = (RA + RB)RC RA + RB + RC = (RX + RX )Rm RX + RX + Rm
Rm 0 (4)
As it can be seen, the proposed metrics successfully discriminate among conditions where the same number of variable changes are needed but di erent degrees of freedom are available. In fact while all the conditions (0,0,0), (0,1,0), and (1,0,0) need one variable change to satisfy G, only the last two ones allow to achieve that by choosing the one variable between two options. Corresponding values of R2S are minor in the last situation thus proposing to the planner to rstly explore points of the solution space that have this value.
The proposed approach uses an extended notation of a Petri-net where places and transitions are semantically annotated. Due to the lack of space, this section only aims at giving an informal idea of the approach. In semantically annotated Petrinets, transitions may be annotated with propositional conditions. The annotated transition res i (if and only if) all the input places contain a token and the current state-of-the-world satis es the condition. At every discrete time instant only 1 transition may re, and the choice depends on the current state of the world.
In addition, Places may be associated to a \success indicator" and to a R2S value. The \success indicator" may be: { Accepting (A) meaning that the goal is fully addressed; an example is given when = F a and the current state satis es `a'. { Waiting, but Accepted (WA) in which the goal is not totally addressed but there are not violations. Consequently, if the system terminates, it concludes with an acceptance. An example occurs when the goal is = Ga and the path always satis es `a': we can never conclude with a success until the system terminates (because future events may lead to violations). { Failure (F) meaning that a violation of the goal happened. An example is given with = Ga and `:a' occurs. { Waiting, but Failure (WF) in which the goal is not yet addressed and if the system terminates, it concludes with a failure. An example is given when = F a and `a' has not yet happened.
Each LTL operator (X,U, F,G) may be translated into an annotated petrinet model with an initial token con guration. In the following we discuss only two of the most frequent cases, just to give a preliminary idea of the approach. 4.1
The Finally operator prescribes a condition will eventually hold. In a nite transition system, the condition must hold after a nite time instant. Until the condition does not hold, the system Wait (with Failure) to eventually move towards an Accepting state. Figure 4 shows a Petri-net with these two annotated places. In addition, there is a special counter place in which, at each step where the condition does not hold, a new token is accumulated: the number of tokens measures how long the system stays in the WF state. At each time instant, the state may be Waiting, but Failure or Accepting, and the R2S may be, respectively, calculated as R2S = f (n)Ra or 1=Ra.
When in state WF, the resistance to goal increases with the number of tokens in the counter place, thus modeling the urgency of reaching the Accepting state. The f (n) function may be chosen according to the speci c domain of application. On the right side of Figure 4 the f (n) function is drawn as linear, however other kinds of dependency may be modelled (exponential, logarithmic) as well.
Fa R2S=f(n)Ra
WF ¬a a
R2S=1/Ra
A n = num of tokens R2S
f(n)Ra The globally operator is generally used to represent safety properties, i.e. condition that must always hold (or undesired properties that must never happen). A nite transition system must continuously positively verify the condition (within a nite time instant) or conclude with a Failure. Figure 5 shows a petri-nets with a Waiting, but Accepted place and Failure place. Again, there is a special counter place in which, at each step where the condition holds, a new token is accumulated: the number of tokens measures how long the petri-net stays in the WF state. At each time instant, R2S may be, respectively, calculated as R2S = g(n)Rb until the condition holds or Rmax after a failure.
Gb R2S=g(n)Rb
WA ¬a a
R2S=Rmax
F n = num of tokens
R2S g(n)Rb n n
When in state WA, the resistance to goal decreases with the number of tokens in the counter place, thus modeling the cumulative probability to remain in a safe state. In this case too, the g(n) function may be linear as on the right side of Figure 4 or exponential, logarithmic, according to speci c needs.
Algorithm 3 describes the function evaluate partial sat, used during the planning (see Figure 1).
Data: wi,P N Result: R2S Function evaluate partial sat(wi,P N): update tokens(P N; wi) return Rarray getR2S from place with token(P N)
End Function Algorithm 3: Algorithm for the evaluation of Partial Satisfaction with temporal formulas.
Every time the planner generates a new state, it invokes Algorithm 3. First step: the update tokens function checks for all the formula petri-nets for activating transitions' ring. Second step: the getR2S places with tokens function explores all the semantic places (A, WA, WF, F) and, for each of them, calculates the corresponding R2S. Finally, Algorithm 3 sums the resulting array of R2S; the result representes the e ort yet to do for moving towards an accepting nal state. 5
This paper has presented a service composition algorithm that is based on a best- rst state search approach. The heuristic we adopted is the R2S, i.e. the resistance to satisfaction, inspired to an electrical analogy, in which the e ort to spend for moving from the current state towards the nal state is represented as a resistor. The temporal extension encompasses some Petri-Net patterns that provides variable resistances that increase/decrease with the time, thus rendering the urgency to reach the goal, or the risk to leave a safe property.