# on_robustness_in_qualitative_constraint_networks__6ba38d9d.pdf On Robustness in Qualitative Constraint Networks Michael Sioutis1 , Zhiguo Long2 , Tomi Janhunen3 1Otto-Friedrich-University Bamberg, WIAI, Bamberg, Germany 2Southwest Jiaotong University, SIST & IAI, Chengdu, China 3Tampere University, ICT, Tampere, Finland michail.sioutis@uni-bamberg.de, zhiguolong@swjtu.edu.cn, tomi.janhunen@tuni.fi We introduce and study a notion of robustness in Qualitative Constraint Networks (QCNs), which are typically used to represent and reason about abstract spatial and temporal information. In particular, given a QCN, we are interested in obtaining a robust qualitative solution, or, a robust scenario of it, which is a satisfiable scenario that has a higher perturbation tolerance than any other, or, in other words, a satisfiable scenario that has more chances than any other to remain valid after it is altered. This challenging problem requires to consider the entire set of satisfiable scenarios of a QCN, whose size is usually exponential in the number of constraints of that QCN; however, we present a first algorithm that is able to compute a robust scenario of a QCN using linear space in the number of constraints. Preliminary results with a dataset from the job-shop scheduling domain, and a standard one, show the interest of our approach and highlight the fact that not all solutions are created equal. 1 Introduction Qualitative Spatial and Temporal Reasoning (QSTR) is a major field of study in AI, and in particular in KR&R, that deals with the fundamental cognitive concepts of space and time in an abstract manner, via simple qualitative constraint languages [Ligozat, 2013; Dylla et al., 2017]. For instance, in natural language one uses qualitative expressions such as inside, before, and north of to spatially or temporally relate one object with another object or oneself, without resorting to providing quantitative information about these entities. Thus, QSTR provides a concise framework for rather inexpensive spatio-temporal reasoning and, hence, further boosts research to a plethora of application areas and domains, such as cognitive robotics [Dylla and Wallgr un, 2007], deep learning [Krishnaswamy et al., 2019], ambient intelligence [Bhatt et al., 2009], visual explanation [Suchan et al., 2018] and sensemaking [Suchan et al., 2019], semantic question-answering [Suchan and Bhatt, 2016], qualitative Partially supported by Academy of Finland (#327352), National Natural Science Foundation of China (61806170), and Fundamental Research Funds for the Central Universities (2682018CX25). Task A Task C before after before Figure 1: A QCN in simplified form, ? denotes all possibilities simulation [Cui et al., 1992], and spatio-temporal data mining [Moskovitch and Shahar, 2015; Kostakis and Papapetrou, 2017; Kostakis et al., 2017]. Qualitative spatial or temporal information can be modeled as a Qualitative Constraint Network (QCN), which is defined as a network where the vertices correspond to spatial or temporal entities, and the arcs are labeled with qualitative spatial or temporal relations respectively. For instance x y can be a temporal QCN over Z. Given a QCN N, the literature is particularly interested in its satisfiability problem, which is the problem of deciding if there exists a spatial or temporal interpretation of the variables of N that satisfies its constraints, such an interpretation being called a solution of N. For instance, x = 0 y = 1 is one of the (infinitely many) solutions of the aforementioned QCN, and x < y is the corresponding qualitative solution (satisfiable scenario) that concisely represents all the cases where x is assigned a lesser value than y. In general, for many widely adopted qualitative calculi the satisfiability problem is NP-complete [Dylla et al., 2013]. Motivation Let us consider the QCN of Figure 1, which, for the sake of our example, encodes the following scheduling problem: A factory produces a product that requires three tasks A, B, and C to be performed. Task B must be done before Task C, and Task A should take place either before or after B. As there might be unpredictable incidents concerning resource availability (e.g., power outage), how should the factory schedule production so that it may be least disturbed? In this case, if we choose the atom before as the preferred relation between Task A and Task B, then the only possible relation between Task A and Task C is before. However, if we place Task A after Task B, then we maintain the whole range of possibilities between Task A and Task C (e.g., before, during, after, or equals). In that way, whatever the change in the relation between Task A and Task C, any satisfiable scenario that places Task A after Task B, being more robust in comparison, will be able to maintain its satisfiability. In a sense, a Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20) robust scenario can be viewed as a satisfiable scenario of better quality than the rest, and as a proactive measure that limits as much as possible the need for successive repairs. Thus, it is an important notion in the context of uncertain and dynamic environments, such as real-life configurations. Related work Robustness in the context of problem solving can probably be traced back to the introduction of search techniques for problem solving itself, as ever since there were ways to obtain solutions for a given problem, there was also a need to be able to differentiate between those solutions on some (usually robustness-related) basis; see for example [Ginsberg et al., 1998], and [Verfaillie and Jussien, 2005] and the references therein. Robustness has been studied quite extensively in the field of traditional constraint programming over the past years [Climent, 2015; Climent et al., 2014; Climent et al., 2010; Barber and Salido, 2015]. We note that in the aforementioned works notions related to robustness, such as stability, are studied as well, but these go beyond the scope of this paper. Briefly put, a solution is stable, if in the event of a change that invalidates it, it can be repaired with a minimum number of revisions, whereas a robust solution is more likely to remain valid after the change occurs; the distinction is subtle, but clear. To the best of our knowledge, robustness has not been studied at all in the context of infinite-domain CSPs, i.e., QCNs. Indeed, since a QCN has infinitely many solutions, as it is defined over an infinite domain such as space or time, comparing one solution against all others is an impossible task. Therefore, it is necessary to operate on a higher, symbolic, level and focus on qualitative solutions, i.e., satisfiable scenarios, instead. This suggests that the techniques that are used for CSPs cannot be readily applied to QCNs. (In support of the aforementioned statement, see also [Westphal and W olfl, 2009] for a comparison of various techniques for tackling QCNs.) Contributions In this paper, (i) we introduce and study a notion of robustness in QCNs, and formally define the robustness problem and a robust scenario of a QCN, (ii) we present a first algorithm that is able to compute a robust scenario of a QCN using linear space in the number of constraints of that QCN, and that is modular in the sense that any state-of-the-art tool that is able to enumerate/generate satisfiable scenarios of a QCN can be employed during its execution, and (iii) we make a preliminary experimentation with a dataset from the job-shop scheduling domain, and a standard one, to assess the differences that exist between the scenarios of a given QCN. 2 Preliminaries A binary qualitative constraint language is based on a finite set B of jointly exhaustive and pairwise disjoint relations, called the set of base relations (atoms), that is defined over an infinite domain D [Ligozat and Renz, 2004]. These base relations represent definite knowledge between two entities with respect to the level of granularity provided by the domain D; indefinite knowledge can be specified by a union of possible base relations, and is represented by the set containing them. The set B contains the identity relation Id, and is closed under the converse operation ( 1). The entire set of relations 2B is equipped with the set-theoretic operations of union B {d, s, fi} {oi} {oi, m} (a) A QCN N {d} {d} {oi} {oi} (b) A satisfiable scenario S of N Figure 2: Examples of QCN terminology using Interval Algebra; symbols p, e, m, o, d, s, and f correspond to the base relations precedes, equals, meets, overlaps, during, starts, and finishes respectively, with i denoting the converse of and intersection, the converse operation, and the weak composition operation denoted by [Ligozat and Renz, 2004]. The weak composition ( ) of two base relations b, b B is the smallest relation r 2B that includes b b ; formally, b b ={b B : b (b b ) = }, where b b ={(x, y) D D : z D such that (x, z) b (z, y) b }. Finally, for all r 2B, r 1 = S{b 1 : b r}, and for all r, r 2B, r r = S{b b : b r, b r }. As an illustration, consider the well known qualitative temporal constraint language of Interval Algebra [Allen, 1983]. Its domain is defined to be the set of intervals on Q, i.e., D = {x = (x , x+) Q Q : x < x+}. Then, each base relation can be defined by appropriately constraining the endpoints of two intervals, which yields a total of 13 base relations comprising the set B = {e, p, pi, m, mi, o, oi, s, si, d, di, f, fi}, as detailed in Figure 2. For example, d, viz., during, is defined as d = {(x, y) D D : x > y and x+ < y+}. The identity relation Id of Interval Algebra is e, and its converse, i.e., e 1, is defined to be again e. The interested reader may find a detailed survey of qualitative spatial and temporal calculi in [Dylla et al., 2017]. The problem of representing and reasoning about qualitative spatial or temporal information can be tackled (among other ways) via the use of a Qualitative Constraint Network, defined in the following manner: Definition 1. A qualitative constraint network (QCN) is a tuple (V, C) where: V = {v1, . . . , vn} is a non-empty finite set of variables, each representing an entity of an infinite domain D; and C is a mapping C : V V 2B such that C(v, v) = {Id} for all v V and C(v, v ) = C(v , v) 1 for all v, v V . An example of a QCN is shown in Figure 2a; for clarity, neither converse relations nor Id loops are mentioned or shown in the figure, but they are part of any QCN. Definition 2. Let N = (V, C) be a QCN, then: a solution of N is a mapping σ : V D such that v, v V , b C(v, v ) such that (σ(v), σ(v )) b; N is satisfiable iff it admits a solution; N is trivially inconsistent, denoted by N, iff v, v V such that C(v, v ) = ; N is the empty QCN on V , denoted by V , iff C(v, v ) = for all v, v V such that v = v ; Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20) a sub-QCN N of N, denoted by N N, is a QCN (V, C ) such that C (v, v ) C(v, v ) v, v V ; N is atomic iff v, v V , C(v, v ) = {b} with b B; a scenario S of N is an atomic sub-QCN of N; the size of N, denoted by |N|, is |{(v, v ) : v, v V v < v }|. In what follows, given some operation φ (such as the weak composition operation ), the unique -maximal φconsistent sub-QCN of N is called the closure of N under φ-consistency and is denoted by φ(N). We recall the definition of -consistency, which is a basic and widely used local consistency for reasoning with QCNs. Definition 3. Given a QCN N = (V, C), N is -consistent iff v, v , v V , C(v, v ) C(v, v ) C(v , v ). In the sequel, given a QCN N of some calculus, we assume that (N) always exists and that it is computable in polynomial time in |N|, and that -consistency decides the satisfiability of atomic QCNs. These assumptions hold for many widely adopted qualitative calculi [Dylla et al., 2013]; however, there do exist calculi (and new ones may arise) where the assumptions may not hold (e.g., [Hirsch, 1999]). 3 Robustness in QCNs In this section, we introduce and study a notion of robustness in QCNs, and formally define related terms such as the robustness problem and a robust scenario of a QCN. Generally, robustness can be defined as the ability of a system to resist change without adapting its initial stable configuration [Wieland and Wallenburg, 2012]. In our context, we are interested in a satisfiable scenario of a QCN (see Figure 2b) with the ability to retain its satisfiability more than any other in the case where some of its constraints are changed. In other words, we are interested in obtaining a satisfiable scenario of a QCN that has more chances than any other to remain valid (satisfiable) after it is altered. We call such a scenario a robust scenario, a scenario with the maximum ability of resisting and avoiding unsatisfiability. Therefore, a robust scenario can be seen as a proactive measure that limits as much as possible the need for successive repairs, and hence can play an important role in environments that are prone to perturbation and unexpected change, such as real-life configurations. Definition 4. (Perturbation) Given a QCN N and a scenario S of N, we say that S is perturbed iff one or more of its constraints change, resulting in a different scenario S of N. Before moving on to the main definitions of this section, we first introduce the operator #same Cons, which allows measuring the number of constraints that are the same respectively between two atomic QCNs over the same set of variables. More formally, given two atomic QCNs N = (V, C) and N = (V, C ), #same Cons(N, N ) = |{(v, v ) : v, v V v < v C(v, v ) = C (v, v )}|. We note that the condition v < v is used because C(v, v ) and C(v , v) concern a same constraint, since C(v, v ) = C(v , v) 1 for any QCN N = (V, C) and v, v V , and because C(v, v) = {Id} for any QCN N = (V, C) and v V . In what follows, the set of scenarios of N will be denoted by [N] and the set of satisfiable scenarios of N by [[N]]. Clearly, for any given QCN N it holds that [[N]] [N]. Next, we define a similarity measure to be able to assess how similar an atomic QCN N is on average to a set of atomic QCNs M (that may or may not include N). Definition 5. (Similarity Measure) Given an atomic QCN N and a set M of atomic QCNs over the same set of variables, the similarity measure of N with respect to M, denoted by similarity(N, M), is defined to be: similarity(N, M) = N M #same Cons(N, N )/|N | In other words, the similarity function with N and M as its parameters, measures the common constraints on average between N and each of the QCNs in M. Note that, for any given atomic QCN N and set M of atomic QCNs over the same set of variables, we have that: similarity(N, M) [0, 1] Thereby, it is possible to use the similarity measure for atomic QCNs of different size. Now, we define the notion of a robust scenario of a QCN. Definition 6. (Robust Scenario) Given a QCN N, a scenario S of N is said to be robust iff we have that: S arg max S [[N ]] similarity(S , [[N]]) Intuitively, a robust scenario of a QCN N has the largest number of common constraints on average with each satisfiable scenario of N. To be in line with our claims in this paper, we assume that the following statistical property holds: Property 1. Given a QCN N, the probability that a scenario S of N remains satisfiable once it is perturbed, is a monotonically increasing function of similarity(S, [[N]]). Thus, a robust scenario of a QCN N is one that is more likely to fall within the set [[N]] when perturbed and, consequently, one that is more likely to withstand that perturbation. Example 1. Let us view again the simplified QCN of Figure 1, and let us interpret it now as a QCN N of Interval Algebra (which has 13 base relations); so, before after becomes {p, pi}, before becomes {p}, and ? becomes B. A robust scenario S of N can be defined by labeling the arc between Task A and Task B with {pi}, and the arc between Task A and Task C with {p}. Then, S produces a similarity measure of around 0.7 when compared against the entire set [[N]] of 14 satisfiable scenarios of the QCN, which is the highest theoretically possible measure (as the measure is upper bounded by |N |+(|N | 1) (|[[N ]]| 1) |[[N ]]| |N | , i.e., S must differ from any other scenario of [[N]] by at least one constraint). By contrast, a feeble scenario of N, when arg max is replaced by arg min in Definition 6, can be obtained by labeling the arc between Task A and Task B with {p}, and the arc between Task A and Task C with {p} (now the only possible option). This scenario produces a similarity measure of around 0.4. The definition of the robustness problem of a QCN is straightforward. Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20) Definition 7. (Robustness Problem) Given a QCN N, the robustness problem is finding a robust scenario S of N. The robustness problem is an optimization problem; the related decision problem can be defined as follows: Definition 8. (k-Robustness Problem) Given a QCN N and a rational number k [0, 1], the k-robustness problem is checking the existence of a scenario S of N such that S is satisfiable and we have that: similarity(S, [[N]]) k We have the following complexity result: Proposition 1. Given a qualitative calculus Q for which the satisfiability problem is NP-complete, the k-robustness problem for Q is NP-hard. Proof. We can solve the k-robustness problem of a given QCN N of Q by choosing k = 0 and determining if N is satisfiable. Hence, the k-robustness problem for Q is NP-hard as the satisfiability problem for Q is NP-hard. Next, we formally define the notion of a maximum scenario of a QCN, which is not necessarily satisfiable: Definition 9. (Maximum Scenario) Given a QCN N, a scenario S of N is said to be maximum iff we have that: S arg max S [N ] similarity(S , [[N]]) On its own, a maximum scenario of a given QCN can serve as a practical upper bound of the similarity measure that we can achieve. However, as [[N]] [N], the following implied result (the detailed practical importance of which is unveiled in the next section) allows us to directly obtain a robust scenario of a QCN through a maximum scenario of it: Proposition 2. Given a QCN N, a maximum scenario S of N is also a robust scenario of N iff S is satisfiable. Finally, we end this section with the following result: Proposition 3. Given a QCN N, a robust or maximum scenario of N is not unique in general. Proof. Let us consider the QCN N = (V, C) that is defined by the variables v and v and the constraint C(v, v ) = {p, pi}. Each of its two scenarios is maximal and robust. 4 Algorithm for Robust Scenarios of QCNs In this section, we present a first algorithm for obtaining a robust scenario of a QCN. Before doing so, let us briefly describe a naive algorithm for carrying out this task. Given a QCN N, a naive algorithm would compute the set [[N]] of satisfiable scenarios of N, and would then compare each one of those scenarios against all other. This would require O(|[[N]]|2 |N| + |B||N| α(N)) time and O(|N| |[[N]]| + β(N)) space, where α(N) and β(N) would be the time and space needed respectively for obtaining a satisfiable scenario of N. The algorithm that we present in what follows is able to carry out the same task using O(|[[N]]| |N|+|B||N | α(N)) Algorithm 1: Robust Scen(N, Oracle) in : A satisfiable QCN N = (V, C), and a generator Oracle that iterates [[N]]. out : A robust scenario of N. 3 foreach v, v V : v < v do 4 ν[(v, v )] dict(); 5 foreach b B do 6 ν[(v, v )][b] 0; 7 foreach (V, C ) Oracle(N) do 8 foreach v, v V : v < v do 9 extract b from C (v, v ) = {b}; 10 ν[(v, v )][b] ν[(v, v )][b] + 1; 11 Smaximum = (V, C ) V ; 12 foreach v, v V : v < v do 13 countmax 0 ; 14 foreach b B do 15 if ν[(v, v )][b] > countmax then 16 countmax ν[(v, v )][b]; 17 brelmax b; 18 C (v, v ) {brelmax}; 19 C (v , v) {brelmax} 1; 20 if (Smaximum) then return Smaximum ; 21 summax 0; 22 foreach (V, C ) Oracle(N) do 24 foreach v, v V : v < v do 25 extract b from C (v, v ) = {b}; 26 sum sum + ν[(v, v )][b]; 27 if sum > summax then 28 summax sum; 29 Srobust (V, C ); 30 return Srobust; Algorithm 2: Gen Scen(N) in : A QCN N = (V, C). out : A satisfiable scenario of N, or V . 3 if N then return V ; 4 if N is atomic then yield N; return; 5 foreach v, v V : v < v do 6 if |C(v, v )| > 1 then break; 7 foreach b C(v, v ) do 8 C(v, v ) {b}; 9 C(v , v) {b} 1; 10 foreach S Gen Scen(N) do 11 if S = V then yield S ; 12 return V ; time and O(|N| + β(N)) space. In the end, we show that the space complexity can be as low as O(|N|), i.e., linear in |N|. Let us come back to our algorithm, called Robust Scen and presented in Algorithm 1. Robust Scen first initializes a Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20) counter to store the number of occurrences of each base relation for each constraint over the set of all satisfiable scenarios of a given QCN N. Then, it calculates a maximum scenario of N by choosing the most frequent base relation for each constraint. If this maximum scenario is satisfiable, then it returns it, as it is also a robust scenario of N by Proposition 2; otherwise, it proceeds to obtain a robust scenario of N by calculating the similarity between a satisfiable scenario of N and [[N]], via the efficient use of the aforementioned counter. We note that to obtain a space complexity of as low as O(|N|), the set [[N]] needs to be recalculated.1 This makes Proposition 2 of particular practical importance, as this recalculation may be avoided by simply checking if the obtained maximum scenario of N is satisfiable; such a check takes polynomial time in |N| (see Section 2). Finally, Robust Scen receives as input a generator too, viz., Oracle, that iterates [[N]]; such a generator is presented in Algorithm 2. Simply put, a generator is a function that can stop midway (via the execution of the yield operator) and then continue from where it stopped. Theorem 1. Given a satisfiable QCN N and a generator Oracle that iterates [[N]], Algorithm 1 returns a robust scenario of N using O(|[[N]]| |N| + |B||N| α(N)) time and O(|N|+β(N)) space, where α(N) and β(N) is the time and space needed respectively for the used generator to obtain a satisfiable scenario of N. Proof. First, we prove that the output of the algorithm is a robust scenario of N. In lines 11 19, a scenario Smaximum = (V, C ) is constructed in such a way that v, v V the constraint C (v, v ) is defined by a base relation b such that: b arg max b B |{(V, C) [[N]] : C(v, v ) = {b}}| This implies that: Smaximum arg max S [N ] S [[N ]] #same Cons(S, S ) And finally by Definition 5 we obtain that: Smaximum arg max S [N ] similarity(S, [[N]]) Therefore, by Definition 9, Smaximum is a maximum scenario of N. In line 20, Smaximum is returned if it is satisfiable; hence, by Proposition 2 a robust scenario of N is returned. In lines 21 29, a scenario Srobust is chosen such that: Srobust arg max (V,C) [[N ]] v,v V :v