Robustness, stability, recoverability, and reliability in constraint satisfaction problems

Abstract

Many real-world problems in Artificial Intelligence (AI) as well as in other areas of computer science and engineering can be efficiently modeled and solved using constraint programming techniques. In many real-world scenarios the problem is partially known, imprecise and dynamic such that some effects of actions are undesired and/or several unforeseen incidences or changes can occur. Whereas expressivity, efficiency, and optimality have been the typical goals in the area, there are several issues regarding robustness that have a clear relevance in dynamic Constraint Satisfaction Problems (CSPs). However, there is still no clear and common definition of robustness-related concepts in CSPs. In this paper, we propose two clearly differentiated definitions for robustness and stability in CSP solutions. We also introduce the concepts of recoverability and reliability, which arise in temporal CSPs. All these definitions are based on related well-known concepts, which are addressed in engineering and other related areas.

Full text

Translate

Turn on search term navigation

http://crossmark.crossref.org/dialog/?doi=10.1007/s10115-014-0778-3&domain=pdf

Web End = http://crossmark.crossref.org/dialog/?doi=10.1007/s10115-014-0778-3&domain=pdf

Web End = Knowl Inf Syst (2015) 44:719734

DOI 10.1007/s10115-014-0778-3

REGULAR PAPER

Federico Barber Miguel A. Salido

Received: 13 November 2012 / Revised: 21 May 2014 / Accepted: 1 August 2014 / Published online: 14 August 2014 Springer-Verlag London 2014

Abstract Many real-world problems in Articial Intelligence (AI) as well as in other areas of computer science and engineering can be efciently modeled and solved using constraint programming techniques. In many real-world scenarios the problem is partially known, imprecise and dynamic such that some effects of actions are undesired and/or several unforeseen incidences or changes can occur. Whereas expressivity, efciency, and optimality have been the typical goals in the area, there are several issues regarding robustness that have a clear relevance in dynamic Constraint Satisfaction Problems (CSPs). However, there is still no clear and common denition of robustness-related concepts in CSPs. In this paper, we propose two clearly differentiated denitions for robustness and stability in CSP solutions. We also introduce the concepts of recoverability and reliability, which arise in temporal CSPs. All these denitions are based on related well-known concepts, which are addressed in engineering and other related areas.

Keywords Constraint satisfaction problems Robustness Stability Dynamic CSPs

1 Introduction

Nowadays, many real problems can be modeled as Constraint Satisfaction Problems (CSP) that are solved using constraint programming techniques [3]. Much effort has been spent to increase the efciency of constraint satisfaction algorithms: ltering, learning and distributed techniques, improved backtracking, use of efcient representations, heuristics, etc. This effort has resulted in the design of constraint reasoning tools which have been used to solve numerous real problems. However, all these techniques assume that the set of variables and constraints, which compose the CSP, is completely known and xed. This is a strong

Electronic supplementary material The online version of this article (doi:http://dx.doi.org/10.1007/s10115-014-0778-3

Web End =10.1007/s10115-014-0778-3 ) contains supplementary material, which is available to authorized users.

F. Barber (B) M. A. Salido

Instituto de Automtica e Informtica Industrial,

Universitat Politcnica de Valncia, Valencia, Spain e-mail: [email protected]

http://crossmark.crossref.org/dialog/?doi=10.1007/s10115-014-0778-3&domain=pdf

Web End = http://crossmark.crossref.org/dialog/?doi=10.1007/s10115-014-0778-3&domain=pdf

Web End = Robustness, stability, recoverability, and reliability in constraint satisfaction problems

123

720 F. Barber, M. A. Salido

limitation when dealing with real situations where the CSP under consideration may evolve because of (i) changes in the environment or in its execution conditions, (ii) evolution of user requirements in the framework of an interactive design, and (iii) changes in other agents in the framework of a distributed system [19].

Since the nature of the real world is dynamic, techniques that attempt to model it should take this dynamicity into consideration [21]. It is easy to see that all possible changes to a CSP (constraint or domain modications, addition or removal of variables) can be expressed in terms of addition or removal of constraints [19]. We remark that we only deal with aspects of pure satisfaction (i.e., CSP). In the context of constraint optimization, it is well known that relaxations do not preserve optimality. This is an interesting, but much more complex issue.

By reading the research carried out in dynamic constraint satisfaction, we found that the terms robustness and stability are sometimes used interchangeably. Some authors refer to robust solutions with the same meaning that others use for stable solutions. For instance, one of the recent papers regarding dynamic constraint satisfaction [20] states that the strategies that have been devised to handle CSPs are methods for nding robust solutions that are either more likely to remain solutions after change or are guaranteed to produce a valid solution to the altered problem with a xed number of assignment changes. In the Handbook of Constraint Programming [16], the authors state that There are three key concerns in solving dynamic CSPs. The rst is to minimize the need for change, and thus to nd robust solutions that are likely to remain solutions even after the change has occurred, or to need only minor repairs .

In engineering, there is a clear agreement to distinguish between stable and robust concepts. However, the difference between stable and robust CSP solutions is not clearly stated. Robustness in CSP has multiple, sometimes conicting, interpretations [11]. In some areas, robustness has been assimilated to stability [23] and more appropriately, CSPs with temporal constraints has been related to noise tolerance [14], etc. Even in related areas such as Operation Research, the multiple meanings accorded to the term robust are open to debate [17]: Robustness can be related to, or integrated into, the notions of exibility, stability, sensitivity, and even equity. In constraint satisfaction, only a few works make a tiny distinction between robustness and stability [6,9]. However, we consider that robustness and stability terms should be clearly distinguished, since they represent different behaviors of a CSPs solution after changes in the environment: Robust solutions refer to solutions that are either more likely to remain valid after change, whereas stable solutions are solutions that can adapt to a new valid solution with only few assignment changes to variables.

In this paper, we focus our attention on the robustness and stability concepts in CSPs. We propose general engineering-based and clearly different denitions for robust and stable CSP solutions. Moreover, we also introduce the concepts of recoverability and reliability which are relevant in real-world temporal-CSP domains. Clear and common denitions are needed to be able to evaluate different alternatives. Afterwards, new research lines will arise: How can we assess the robustness or stability of a solution? What does it guarantee? How can we get a more robust solution? What is the relationship between robustness and other problem parameters, such as optimality and constrainedness? Is it possible to obtain a model of robustness?, etc.

Following some standard notations and denitions in the literature, we have summarized the basic denitions that will be used throughout this paper.

Denition 1 A Constraint Satisfaction Problem (CSP) is a triple P = X, D, C , where X

is a nite set of variables {x1, x2, ..., xn}, D is a set of domains D = {d1, d2, ..., dn} such that

each variable xi X has a nite set of possible values di, and C is a nite set of constraints

C = {C1, C2, ..., Cm} that restricts the values that the variables can simultaneously take.

123

Robustness, stability, recoverability, and reliability in CSPs 721

Denition 2 The Solution Space is the portion of the search space ([producttext]i=1,n di) that satises

all constraints. A solution S is a feasible instantiation of all variables, that is, it satises all constraints.

2 Incidences (or changes) in CSPs

Since many real problems are dynamic, unexpected incidences in the problem scenario occur due to its dynamism, spurious actions, lack of complete knowledge, etc. Let Z =

{z1, z2, ..., zi, ...zm} be the nite set of possible incidences that can occur in the future, which

give rise to the nite set of possible changes in the CSP that models the problem. Let us also assume that each zi Z is causally independent and has a probability p(zi) to occur. By

applying the concept of probability distribution over Z, we introduce pd(zi) =

p(zi ) [summationtext]z j Z p(z j )

as the normalized probability function over Z, such that pd(zi) describes the relative likelihood for zi to occur and [summationtext]m

i=1 pd(zi) = 1.

Each incidence zi Z can be modeled as a nite set of changes in variable domains

or constraints. Since changes in domains can be represented as unary constraints, it can be assumed that each incidence zi can be represented by a nite set of changes (restriction or relaxation) of constraints. In this paper, we are interested in robustness issues and how a CSP solution maintains its feasibility after occurrence of possible incidences. Therefore, we assume that, as incidences occur, the previous set of constraints always remains, so that the solution space can only be reduced. Thus, we will only consider changes that restrict the solution space (i.e., add new constraints to the previous existing ones). The removal or relaxation of constraints is not considered here since it does not restrict the solution space. Therefore, each possible incidence zi Z is modeled as a new set of constrains

Czi to be added to the initial set of constraints, making the problem more restricted, or even inconsistent. Thus, the nal CSP, after the occurrence of the whole set of incidences

{z1, z2, ..., zm} is C SPZ = X, D, C Cz1 Cz2 ....Czm . Due to the declarative nature

of the model, the order is not relevant.

We assume the incidences only restrict, but do not make empty the initial solution space; otherwise the problem would become inconsistent. Therefore, some of the feasible solutions of the initial CSP are also solutions of the nal CSP. We also assume that we know the typology of expected incidents (and their probability). For example, in scheduling, we can expect delays in tasks durations, ready-times, etc. Obviously, it is not possible to determine the robustness-related features of a system if no information about the incidences is given. In this last case, we can obtain a rough estimation by means of the inclusion of random incidences (and random values for p(zi)) [5]. However, it is important to remark that, in the same way that a CSP models the real-world problem, the set of incidences Z should also model the set of expected incidences that can occur in the real world. Thus, Z should not be a set of randomly generated modications of the constraints and domains of the CSP, but rather the result of modeling ({Czi}) representing the set of possible changes ({zi}) that can

occur in the real-world problem that it is modeled by the CSP.

3 Robustness

Robustness is a common feature in our environment. Systems that belong to biological life, chemical compositions, physical structures, isolated objects, etc. [18] persist, remain running,

123

722 F. Barber, M. A. Salido

and maintain their main features despite continuous perturbations, changes, incidences or aggressions. Thus, robustness is a concept related to the persistence of the system, its structure, its functionality, etc., against external interference: A system is robust, if it persists.

Thus, in a general way, robustness can be dened as the ability of a system to withstand stresses, pressures, perturbations, unpredictable changes, or variations in its operating environment without loss of functionality. A system that is designed to perform functionality in an expected environment is robust if it is able to maintain its functionality under a set of incidences. For example, an algorithm is robust if it continues to operate despite unexpected inputs or erroneous calculations.

Intuitively, the notion of robustness is easy to dene, but its formalization depends on the system, on its expected functionality, and on the specic set of incidences to be confronted [15]. No general formal denition of robustness has been proposed, except a few exceptions or particular cases. Specically, Kitano [12] mathematically denes the robustness (R) of a functional system (SYS) with regard to function (F) against a set of perturbations (Z) as (in a simplied way):

RSYSF,Z =

[integraldisplay] Z p(z) F(SYS, z)dz (1)

where, p(z) is the probability for incidence z Z, and F(SYS, z) is an evaluation function

that returns zero when the system SYS fails under z or it returns a relative viability ]0, 1]

otherwise. For instance, if production drops 20 % under a certain perturbation (z) compared with standard production, then 0.8 is returned.

Expression (1) formalizes how a system (SYS) is able to maintain a certain level of its expected functionality (F) against a given set of perturbations (Z). According to (1), a system SYS1 is more robust than SYS2 with regard to an expected functionality F against a set of perturbations Z when:

RSYS1F,Z > RSYS2F,Z (2)

The application of expression (1) is highly dependent on the system being assessed. Let us apply (1) to CSPs:

S is a solution of the CSP, whose robustness we want to assess. Robustness is a concept related to CSP solutions, not to CSP itself. Thus, the system SYS in (1) can be related to the solution S in a CSP.

Z is the discrete set of unexpected incidences. F is the expected functionality of the system. In CSP, the expected functionality of a solution is its feasibility.

Therefore, by applying (1), the robustness of a CSP solution (S) can be dened as follows:

Denition 3 A solution (S) of a CSP is r-robust with respect to a set of incidences Z, where each zi Z has a normalized probability of occurrence pd(zi), when:

r(S, Z, P) = RSF,Z,P =

[summationdisplay]

zi Z

pd(zi) F(S, zi) (3)

where P is the set of normalized probabilities (P = {pd(zi), zi Z}) and function F(S, zi)

is the consistency of S after zi:

F(S, zi) = 1 iff S also satises C Czi.

F(S, zi) = 0, iff S does not satisfy C Czi. More concretely, iff S does not satisfy Czi.

123

Robustness, stability, recoverability, and reliability in CSPs 723

Robustness of a solution represents its probability of remaining a solution of the new problem after Z and it varies from 0 to 1 since [summationtext]zi Z pd(zi) = 1 and F(S, zi) {0, 1}. The

greater its r-robust, the more robust a solution is and more likely to remain feasible after Z.

From expression (3), we can see that the algorithm for calculating the robustness r-robust of a solution S against a set of incidences Z is straightforward. It only requires to check whether S maintains its feasibility F(S, zi) for each incidence zi Z. Thus, for each zi Z, the cost

of checking its feasibility is O(n).

On the other hand, note that robustness does not require insensitiveness of the problem modeled by the CSP. For instance, the constraints of the problem could dramatically vary due to zi, such that Czi could greatly reduce the solution space. However, a robust solution

S with respect Czi would remain feasible after the incidence.

Note that the robustness of a solution S does not depend on the behavior of S against an incidence zi, but on how the feasibility of S is maintained over a set of unexpected incidences

Z. Thus, the robustness of S depends on the probability p(zi) of each possible incidence zi Z and how Czi affects to the feasibility of the solution F(S, zi). In other words, the

only way to characterize the robustness level of a given CSP solution is to determine how its feasibility is maintained over several levels of probability of incidences.

Note that we do not take into account other aspects, that have usually been taken into account when the robustness of a CSP solution is assessed by other authors (e.g., the number of variables that must change their values to make the initial solution feasible after the incidence, the number of unsatised constraints by the initial solution, etc.). In our approach, a solution is not more/less robust under a given incidence if the solution needs to be more/less repaired to deal with the incidence. We claim that robustness cannot be assessed on the basis that only small changes are necessary to obtain a new feasible solution. In problems related with satisability, robustness should be related to feasibility maintenance.

3.1 Example

Let us apply the above denition (3) to the following example. Let P be a CSP with two variables x1 and x2 with domains D1 : {3..7} and D2 : {2..6}, respectively. The constraints are: C1 : x1 + x2 12

C2 : x2 + x1 6

C3 : x2 x1 2

C4 : x1 x2 4

Figure 1 represents the solution space of the CSP, which is composed of 21 solutions. Let us suppose the following set Z of expected incidences:

Incidence zi Probability p(zi ) Likelihood pd(zi ) zi Czi

z1 0.45 0.15 {x1 + x2 9, x2 5}

z2 0.30 0.10 {x1 + x2 10, x1 4}

z3 0.75 0.25 {x1 + x2 0}

z4 0.90 0.30 {x1 x2 2}

z5 0.60 0.20 {x1 > 4}

The robustness of each solution can be assessed according to expression 3. Then, we can deduce that (x1 = 5, x2 = 3) and (x1 = 5, x2 = 4) are the most robust solutions,

according to the above set of expected incidences: R(x1=5,x2=3)Z = R(x1=5,x2=4)Z = pd(z1) +

123

724 F. Barber, M. A. Salido

Fig. 1 CSP P and its solution space

pd(z3) + pd(z4) + pd(z5) = 0.9. Likewise, (x1 = 4, x2 = 6) is the least robust solution:

R(x1=4,x2=6)Z = pd(z2) + pd(z4) = 0.4.

Even though the solution space of the above example is convex, note that it is not required for assessing the robustness of CSP solutions, nor an implicit representation of the CSP constraints. Moreover, the robustness of each solution can be assessed independently of the assessment of other solutions.

3.2 What does r-robustness guarantee?

The more robust solution is, the more likely it will remain valid after changes in the constraints. The following conclusions can be obtained from (3): (i) A 1-robust solution is a solution that maintains its feasibility over the whole set of expected incidences, (ii) a 0-robust solution is a solution that becomes inconsistent with any expected incidence that may occur, and (iii) an r-robust solution is a solution that maintains its feasibility over (100*r) % of probabilistically pondered incidences. For instance, the solution (x1 = 4, x2 = 2) of the above example is

able to maintain robustness over 70 % of the expected likelihood incidences. Specically, this solution is robust against z1, z3 and z4, which have an accumulated probability density of 0.7.

4 Stability

Stability is an old concept that derives from astronomy and physics [22]. Loosely speaking, a solution (meaning an equilibrium state) of a dynamical system is said to be stable if small perturbations to the solution result in a new solution that stays close to the original solution. Perturbations can be viewed as small differences that occur in the actual state of the system [11]. Therefore, by applying this informal denition to CSPs, a solution is stable if small modications of the constraint set allow a new solution (new consistent variable assignment) that remains close to the original solution:

Sol(X, D, C) is stable (with respect zi, C Czi) iff

Sol(X, D, C Czi) : Sol(X, D, C)

= Sol(X, D, C Czi)

Denition 4 A solution S of a CSP is s-stable, with respect to an incidence zi, if there exist a new feasible solution S in the s-neighborhood of S.

123

Robustness, stability, recoverability, and reliability in CSPs 725

The neighborhood of solutions can be formally dened in terms of norms in the n-dimensional space [8]. Thus above denition can be detailed as follows.

Denition 5 A solution S = (x1 = v1, x2 = v2, ..., xn = vn) is s-stable if, given an

incidence zi, there is a solution S = (x1 = v 1, x2 = v 2, ..., xn = v n), such that: S S < s,

where . is some n-dimensional norm dened in the solution space to evaluate the difference

between S and S .

In relation to the implementation of n-dimensional norms, we have:

1. Metric domains, we can apply the Euclidean distance between S and S , with a optional weighted factor i for each assigned variable xi:

[radicaltp]

[radicalvertex]

i=1

[radicalbt] [summationdisplay] i(x i xi)2 (4)

but normalizing with the maximum distance between any two tuples in the space of solutions. Note that the domains {di} are nite in a CSP. Thus, the normalized relative

distance in a metric domain between S and S becomes:

S S z =

[radicalBig][summationtext]n

i=1 i(x i xi)2 [radicalBig][summationtext]n

i=1 i | di |2

(5)

Note that the similarity given in (5) between S and S may be very low if the two solutions S and S are very close in the n-dimensional space even though all the variables of S change their values. This n-dimensional norm measures the relative distance between S and S , such that S S z [0, 1] due to a change in the value of one or all variables.

2. Non-metric domains (like non-ordered sets of values), the Hamming distance (H) can be applied. This n-dimensional norm measures the number of variables that have different values in S and S . Therefore, the distance between S and S on non-metric domains can be dened as:

S S z =

ni=1 i H(x i, xi)

n (6)

where H(x i, xi) is equal to 0 iff x i = xi, and 1 otherwise. The expression is normalized

with respect to n, such that this criterion evaluates the relative number of variables that change their values and S S z [0, 1]. Note that this concept is related to the super-

solution concept given in [10].

These measures evaluate the closeness of solutions in the space of solutions. Therefore, given an incidence zi, the s-stability for a solution S quanties the distance to S of the closest feasible solution S in the n-dimensional space of the CSP, by applying expression 5 or 6 depending on metric or non-metric domains. In other words, we should determine how much the new solution S differs from the initial one S to address the incidence. A robust solution is a 0-stable solution.

The proposed measures of s-stability require nding a solution in the closest neighborhood of S, among the complete set of new feasible solutions, such that deviation with respect to the previous solutions S is minimized. Let us denote N(S, zi) as the value of S S for

the closest solution S to S, after the occurrence of zi:

N(S, zi) = minS S S (7)

Note that N(S, zi) = 0 iff F(S, zi) = 1 (i.e.,: S satises Czi).

123

726 F. Barber, M. A. Salido

According to denition 5, we can dene the s-stability (STA) of a solution (S) against a given set of perturbations Z with a probability P as:

s(S, Z, P) = STASZ,P =

[summationdisplay]

zi Z

pd(zi) N(S, zi) (8)

where P is the set of normalized probabilities (P = {pd(zi), zi Z}). STASZ varies from

0 to 1 in both cases, metric and non-metric CSPs. The lower its s-stability is, the more stable the solution is.

Obtaining stability of a CSP solution implies obtaining N(S, zi) for each zi Z, which

derives in a Constraint Satisfaction and Optimization Problem (CSOP) whose constraints are C Czi and whose optimality criteria is to minimize S S (Eq. 7). In general, solving

a CSOP is NP-hard. However, this computational cost can be reduced by searching for a solution S in the closest neighborhood of S. Note that the notion of distance between S and

S should take into account whether or not the domain is metric. Therefore, an incremental process can be dened (Algorithm 1 for metric domains and Algorithm 2 for non-metric domains). In Algorithm 1, each iteration k in the process has a cost (2 k )n, such that the

computational cost for obtaining stability of a solution can be decreased if a solution exists in the close neighborhood of S. In Algorithm 2, each iteration in the process has a cost n

[parenrightbig](di ). Thus, computational cost for obtaining stability of a solution can be decreased if a solution exists in the close neighborhood of S.

Algorithm 1 Incremental Stability Process for obtaining N(S, zi ) in metric domains.Let C S P =< X, C, D >, let S = (v1, v2, ..., vn) be a solution S of the CSP, and let be the granularity of

the search process.k=1;

NSz = 1;repeatif S , a solution to C S P =< X, C Czi , D >, where

D D: d j = {[v j k ], [v j + k ]} d j , j 1..n then

NSz = S S ;

else

k=k+1; end if until D [notsubseteql] D return NSz;

Algorithm 2 Incremental Stability Process for obtaining N(S, zi ) in non-metric domains.Let C S P =< X, C, D >, and let S = (v1, v2, ..., vn) be a solution S of the CSP.

=1;

NSz = n; repeatif S = (v

1, v

2, ..., v

n), a solution to CSP=< X, C Czi , D >, where

nj=1H(v j , v j ) = then

NSz = ; else

= + 1; end if until = n

return NSz;

123

Robustness, stability, recoverability, and reliability in CSPs 727

Table 1 Stability of some robust solutions {(5,3), (5,4)} and a non-robust solution (4,6)

Solution (x1, x2)

Robustness Stability

(5,3) Satises (6,4) Satises Satises Satises 0.9 0.14/50

(5,4) Satises (6,4) Satises Satises Satises 0.9 0.1/50

(4,6) (4,5) Satises (5,5) Satises (5,6) 0.4 0.7/50

4.1 Example

Let us apply the above denition of stability (8) to the previous example (Fig. 1) for the most and least robust solutions.

For instance, the stability of solution (4, 6), according to expression (8), is:

STA(4,6)Z =

0.15 1 + 0.25 2 + 0.2 1

52 + 52 =

0.750 (9)

Thus, Table 1, (x1 = 5, x2 = 4) is the most robust (0.9) and the most stable solution

(0.1/50) according to the given set of expected incidences.

4.2 What does s-stability guarantee?

Stability of a solution S represents the expected minimum normalized distance between S and a new feasible solution of the new problem after Z. The more stable the solution, the less need for change will be necessary to obtain a new solution after changes in the constraints. The following conclusions can be obtained from (Expression 8):

A solution S, with STASZ = 0, is a 1-robust solution. It is fully stable over the whole set

of expected incidences. A solution S of a non-metric CSP, with STASZ = n, requires changing the assignments of

the whole set of variables to become consistent against any expected incidence that may occur. A solution S of a metric CSP, with STASZ = 1, requires moving to the far extreme

point of the solution space to become consistent against any expected incidence that may occur. A solution S of a non-metric CSP, with STASZ = k, requires changing k variables, as

average, to become consistent over the whole set of probabilistically pondered incidences. A solution S of a metric CSP, with STASZ = k, requires moving to a distance (k

[radicalBig][summationtext]n

i=1 d2i), as average, to become consistent over the whole set of probabilistically

pondered incidences.

5 Temporal constraint satisfaction problems

A Temporal Constraint Satisfaction Problem (TCSP) is a subtype of CSPs, where variables represent temporal primitives (time points or temporal intervals), such that interpretation domain is the time, variable assignments are temporally ordered and solutions have a temporal interpretation [2,7]. This is the typical case of scheduling problems, where variables can be instantiated on the time line (see Fig. 2) so that they can be associated with starting or ending times of tasks (see Fig. 3).

Closest sol. with z1

Closest sol. with z2

Closest sol. with z3

Closest sol. with z4

Closest sol. with z5

123

728 F. Barber, M. A. Salido

Fig. 2 Recoverability of a solution in a TCSP

Besides robustness and stability concepts, in TCSP, not only is it important to know how different the new feasible solution S is from the original one S, given an incidence zi (i.e., stability), but it is also important to know (i) how long the new solution S differs from the initial solution S (recoverability), and (ii) how long the actual solution S can be maintained after the incidence (reliability). Therefore, two new properties appear in relation to the temporal stability or temporal robustness: recoverability and reliability.

An example of TCSP: a scheduling problem

Figure 3a shows a TCSP that represents a ow-shop scheduling problem with two jobs J1, J2, each of which has three activities (x1i, x2j , i, j = 1..3) and one resource that should

be shared by all activities. Each row corresponds to a job, and an activity (xi j) is represented as a rectangle whose length corresponds to its duration. This problem can be modeled as a TCSP, where variables represent time points (starting or ending times) of different activities (xi j.on, xi j.off). There exist constraints that refer to non-overlap and precedence constraints among activities. Moreover, it is known that x23 should be performed at least k-units after x22 (Constraint C2322). The rst solution (Fig. 3a) minimizes the makespan and it is considered

to be the optimal solution. The projection of variables xi j on time represents the optimal assignment of variables of the TCSP.

5.1 Recoverability

Recoverability refers to the ability to restore a system to the point at which a failure occurred. Despite proactive approaches, it is clear that robustness is not always completely guaranteed. Therefore, recovery strategies should be used once disturbing events occur to keep the feasibility of the pre-computed solution. Robustness and recoverability are closely related and, in some optimization frameworks, they have been unied into an integrated notion of recoverable robustness [13]. For TCSP, where solutions are projected over time, the recoverability of a solution can be measured by the required amount of time (t) (after an incidence zi occurs) to restore part of the initial solution (Fig. 2). Therefore, it must be taken into account that temporal variables, in a solution of a TCSP, are distributed over time, so we can dene that a t-recovered solution maintains the same assigned values in the variables from t after the incidence:

Solt(X, D, C Czi) Solt(X, D, C)

where Solt covers the set of variables from t after the incidence (Fig. 2). The objective of a recovery process is to minimize t. Likewise, since the variables of a TCSP are temporally

123

Robustness, stability, recoverability, and reliability in CSPs 729

Fig. 3 A scheduling problem: four solutions

ordered (i.e., they are instantiated over time), the objective of a recovery process is to minimize the set of variables, from time t (when the incidence occurs) to t + t that require changing

their values to obtain a new feasible solution.

123

730 F. Barber, M. A. Salido

Denition 6 A TCSP solution S is h-recoverable iff, at most h variables (consecutive variables after the incidence occurs) require changing their values to obtain a new feasible solution S .

Variables of a TCSP are instantiated over the time line, such that variables of a solution S = (x1 = v1, x2 = v2, ..., xn = vn) are temporally ordered. Thus, as corollary of Denition

6, in a h-recoverable solution S = (x1 = v1, x2 = v2, ..., xn = vn), given an incidence zi

that occurs in t (vk < t vk+1) the incidence affects S in the temporal interval [t, t + t],

such that the variables x1, ..., xk and xk+h+1, ..., xn can maintain their initial values, while the

variables in the interval [t, t + t] (xk+1, ..., xk+h) must change their values (v k+1, ..., v k+h)

(see Fig. 2). The initial solution is recovered after xk+h,that is after t + t.

Note that the denition of h-recoverability is similar to the denition of (h, 0)super

solutions where if h variables lose their assigned values, another solution can be found by reassigning a new value to these variables.

The only difference is that, in hrecoverability, the variables to be repaired are consecutive

over time, while, in (h,0)-super solutions, the variables to be repaired are not consecutive. From Denition /refd6, it can be concluded that 0 h-recoverability n. The lower

is h-recoverability, the more recoverable a solution is. A 0-recoverable solution S does not require changing any variable after incidence to maintain the feasibility of S (equivalent to 1-robust solution) An n-recoverable solution S does require changing all the variables after incidence. Thus, h-recoverability can be considered to be a temporal s-stability.

5.2 Reliability

In engineering, reliability is associated with the condence that a system will perform its intended function during a specied period of time under stated conditions, as well as under unexpected circumstances. Mathematically it can be expressed as:

R(t) =

[integraldisplay] t f (x)dx (10) where f (x) is the failure probability density function and t is the length of the period of time (which is assumed to start from time zero). There is always some chance for failure, but R(t) means that the system has a specied probability that it will operate without failure before time t.

In TCSP, variables of solution are distributed over time. Thus, a solution found initially may be invalid for variables that are related to a time greater than t after incidence. Thus, by applying the above concepts, we can assess that a TCSP solution is t-reliable, if given an incidence zi at time t, the solution remains valid until t + t (Fig. 4). Thus, the set of

variables that represents the solution of the problem from time t to t + t maintain their

assigned values:

Soltt(X, D, C Czi) Soltt(X, D, C)where Solt covers the set of variables from time t to t + t. The way to obtain a reliable

solution is to maximize t, or alternatively, to maximize the set of variables from time t, (when incidence occurs) to t + t) that can maintain their values (Fig. 4).

Similarly to recoverability, the reliability of a solution S can be dened in terms of the number of assignments in S that remains valid after the incidence occurs (i.e., they can take part of a solution of TCSPZ).

Denition 7 A TCSP solution S is u-reliable if, at least, u assignments of variables in S (consecutive variables after the incidence occurs) can take part of a solution of the TCSPZ.

123

Robustness, stability, recoverability, and reliability in CSPs 731

Fig. 4 Reliability of a solution in a TCSP

As corollary of Denition 7, in a u-reliable TCSP solution S = (x1 = v1, x2 =

v2, ..., xn = vn) given an incidence zi that affects the problem in t, where vk < t vk+1, the

assignments of variables (x1 = v1, x2 = v2, ..., xk = vk, xk+1 = vk+1, ..., xk+u = vk+u),

1 k + u n, can take part of a solution of TCSPZ, while the variables from t + t

(x k+u+1, ..., x n) must change their values (v k+u+1, ..., v n) (see Fig. 4). The initial solution is

maintained from xk to xk+u, that is from t to t + t.

As in the above case, from Denition 7, it can be concluded that 0 u-reliability n.

The greater the u-reliability is, the more reliable a solution is. A 0-reliable solution S cannot maintain values in any variable after incidence for maintaining feasibility of S. A n-reliable solution S can maintain the assigned values in all variables. Therefore, we can consider that u-reliability is a concept that is related to the temporary maintenance of robustness from time of occurrence. Moreover, a n-reliable solution is a 0-recoverable solution, which can also be considered to be a temporally 0-stable or 1-robust solution.

Note that h-recoverability and u-reliability of a solution S are not contradictory nor complementary concepts. If an incidence occurs at time t, (i) the initial solution S can be maintained feasible from t until t + u(u variables), and (ii) the initial solution S can be restored

from t + h (h variables), where u h. Of course, (h-recoverability + u-reliability) n. Recoverability and reliability in the example

With respect to the scheduling problem presented in Fig. 3, Fig. 3b shows a robust solution. To this end, some buffer times have been included between some activities to absorb incidences. For instance, if a resource is broken for a short time, (incidence in Fig. 3b), the solution is not affected by the incidence. Thus, all assignments to variables remain valid. Furthermore, this solution is also stable. If variables x21.off, x22.off, x12.off or x13.off are minimally delayed, the rest of the variables maintain the same values. Moreover, the typical trade-off between robustness and optimality can be observed in Fig. 3a/b.

Figure 3c shows a 3-recoverable solution for an incidence z: x21.off is delayed to x 21.off in time t. In this case, only 3 variables must change their values (x21.off, x22.on, x22.off), while assigned variables with assigned values greater than t + t, (x12.on, x12.off, x13.on, x13.off,

x23.on, x23.off), do not require to change their values. On the other hand, Fig. 3d shows a 4-reliability solution for an incidence z: x22.off is delayed to x 22.off in time t. In this case, the next 4 variables (x12.on, x12.off, x13.on, x13.off) do not change their values. The solution is maintained until t + t. However, activity x23 must satisfy C2322, such that x23.on and

further variables must change their values.

6 Generalizing concepts

In the previous sections, the concepts of robustness, stability, recoverability, and reliability have been dened by analyzing how a solution S absorbs or can be adapted to cope with

123

732 F. Barber, M. A. Salido

an incidence zi. These concepts can be generalized, such that we can assess the achievable levels of robustness, stability, recoverability, and reliability of solutions of a CSP for a given typology of incidences {zi, pd(zi)}, a desired level of optimality of solution, and a given

constrainedness of the CSP which is inherent to the problem. Thus:

Robustness guarantees that perturbations can be absorbed by the solution. Thus, robustness decreases as the level of incidences increases.

Stability guarantees that the consequences of perturbations can be minimized by the new solution. Thus, stability decreases as the level of the incidences increases.

A low-restricted CSP with a large solution space will usually allow more robust and stable solutions.

A more optimized solution will usually be more sensitive to changes in the environment. Optimal solutions are usually located at edges of solutions space where robustness is lowest. There exists a clear trade-off between robustness and optimality/quality [4].

These ideas introduce the main concepts to which robustness, stability, recoverability, and reliability of solutions in CSP are related and appear in many CSPs applications [1]. Figure 5 represents the existing relationship among robustness, stability, recoverability, and reliability of solutions with: (i) the constrainedness of CSPs (which is a problem-dependent feature);(ii) the incidence level (which is a feature of the problem and/or application scenario; and (iii) optimality of S (which is a feature of each solution). Thus, typology of expected incidences and their stochastic features, optimality of solutions, and constrainedness of problems are the main factors that limit the desired level of robustness, stability, recoverability, and reliability of solutions in CSPs. A more detailed model of robustness would allow us to parameterize the implicit relations presented in Fig. 5, by relating the concepts of robustness with the characteristics of the problems or their application scenarios.

The evaluation of the robustness, stability, recoverability, and reliability of a solution S can be viewed as a guarantee of the behavior of S with respect to the expected set of incidences Z. Moreover, recoverability and reliability can be considered as forms of partial robustness, where part of the solution remains valid. Likewise, the concepts and situations described in this section occur not only with TCSP, but more generally with dynamic CSP [5,9] and, particularly, with Planning and Scheduling problems modeled as CSP.

Fig. 5 Robustness and problem-related concepts

123

Robustness, stability, recoverability, and reliability in CSPs 733

7 Conclusions

While expressivity, efciency, and optimality have been the typical goals in the development of CSP techniques, there are robustness-related issues that have received less attention. However, robustness requirements have a clear relevance in dynamic environments (usually with incomplete or imprecise knowledge). This work aims to review the concepts of robustness, stability, recoverability, and reliability in dynamic Constraint Satisfaction Problems. This supposes an advance in the state of the art in constraint programming, and new models and techniques can be developed to achieve this properties in CSP solutions.

The general notion of robustness includes several different concepts. Despite the existence of several works on dynamic CSP, there is still no clear and common denition of robustness-related concepts. In this paper, these concepts have been characterized and formalized, such that they can be used, in a general way, to assess robustness-related features of solutions in CSPs.

In this paper, a denition and formalization of these concepts has been proposed, on the basis of their meaning in other areas of science, as well as on how they can be evaluated, and what it guarantees. They can be used, in a general way, to assess robustness-related features of solutions in CSPs. Particularly, the introduced concepts have been applied to simple problems, which allows us to contrast the differences between them, as well as, the different ways that a solution can react to incidences: it can be maintained, it can be adapted, it can be maintained during (or restored after) a given time. This different behavior becomes relevant when a CSP is applied to solve real-world problems in a dynamic and partially unknown world. From this point, other relevant issues remain open. Particularly, the design of efcient algorithms for obtaining robust, stable, recoverable, and reliable solutions is subject of relevant research lines.

Acknowledgments This work has been partially supported by the research project TIN2013-46511-C2-1 (MINECO, Spain). We would also thank the reviewers for their efforts and helpful comments.

References

1. Abril M, Barber F, Ingolotti L, Salido MA, Tormos P, Lova A (2008) An assessment of railway capacity. Transp Res Part E 44(5):774806

2. Barber F (2000) Reasoning on intervals and point-based disjunctive metric constraints in temporal contexts. J Artif Intell Res 12:3586

3. Bartak R, Salido MA (2011) Constraint satisfaction for planning and scheduling problems. Constraints 16(3):223227

4. Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52(1):35535. Climent L, Wallace R, Salido M, Barber F (2013) Modeling robustness in CSPS as weighted CSPS. In: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems CPAIOR 2013, pp 4460

6. Climent L, Wallace R, Salido M, Barber F (2014) Robustness and stability in constraint programming under dynamism and uncertainty. J Artif Intell Res 49(1):4978

7. Dechter R (1991) Temporal constraint network. Artif Intell 49:612958. Hazewinkel M (2002) Encyclopaedia of mathematics. Springer, New York9. Hebrard E (2007) Robust solutions for constraint satisfaction and optimisation under uncertainty. PhD thesis, University of New South Wales

10. Hebrard E, Hnich B, Walsh T (2004) Super solutions in constraint programming. In: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR-04), pp 157172

11. Jen E (2003) Stable or robust? Whats the difference? Complexity 8(3):121812. Kitano H (2007) Towards a theory of biological robustness. Mol Syst Biol 3(137)

123

734 F. Barber, M. A. Salido

13. Liebchen C, Lbbecke M, Mhring R, Stiller S (2009) The concept of recoverable robustness, linear programming recovery, and railway applications. In: LNCS, vol 5868

14. Papapetrou P, Kollios G, Sclaroff S, Gunopulos D (2009) Mining frequent arrangements of temporal intervals. Knowl Inf Syst 21:133171

15. Rizk A, Batt G, Fages F, Solima S (2009) A general computational method for robustness analysis with applications to synthetic gene networks. Bioinformatics 25(12):168179

16. Rossi F, van Beek P, Walsh T (2006) Handbook of constraint programming. Elsevier, New York17. Roy B (2010) Robustness in operational research and decision aiding: a multi-faceted issue. Eur J Oper Res 200:629638

18. Szathmary E (2006) A robust approach. Nature 439:192019. Verfaillie G, Schiex T (1994) Solution reuse in dynamic constraint satisfaction problems. In: Proceedings of the 12th national conference on articial intelligence (AAAI-94), pp 307312

20. Wallace R, Grimes D, Freuder E (2009) Solving dynamic constraint satisfaction problems by identifying stable features. In: Proceedings of international joint conferences on articial intelligence (IJCAI-09), pp 621627

21. Wang D, Tse Q, Zhou Y (2011) A decentralized search engine for dynamic web communities. Knowl Inf Syst 26(1):105125

22. Wiggins S (1990) Introduction to applied nonlinear dynamical systems and chaos. Springer, New York23. Zhou Y, Croft W (2008) Measuring ranked list robustness for query performance prediction. Knowl Inf Syst 16:155171

Federico Barber is Full Professor in the Department of Computer Science at Universitat Politcnica de Valncia, where he leads a research team in articial intelligence. He has worked on the development of temporal reasoning systems, Constraint Satisfaction Problems, planning and scheduling. He is the author of several articles, published in international journals and conferences. His research has produced several tools for solving real-world constrained optimization problems. He has participated in and led national and European research projects related to these areas, as well as he has led several technology transference projects to relevant companies. He is the current president of the IberoAmerican Society of Articial Intelligence (IBERAMIA) and member of several scientic committees and associations. More information can be found at: http://users.dsic.upv.es/~fbarber

Web End =http://users.dsic.upv.es/~fbarber .

Miguel A. Salido is Associated Professor in the Department of Computer Science at Technical University of Valencia. His expertise area is focused on constraint programming and its application to planning and scheduling problems. He is the author of more than 80 papers published in international journals and conferences. He is PC member of international conferences in the area: IJCAI, AAAI, ECAI, ICAPS. He has participated in several national and European research projects. More information can be found at: http://users.dsic.upv.es/~msalido/

Web End =http://users.dsic.upv.es/~msalido/ .

123

Word count: 7608

Show less

Springer-Verlag London 2015

Robustness, stability, recoverability, and reliability in constraint satisfaction problems

Content area

Abstract

Full text