Efficiently Enforcing Path Consistency on Qualitative Constraint Networks by Use of Abstraction

1 Introduction

Qualitative Spatial and Temporal Reasoning (QSTR) is a major field of study in Artificial Intelligence, and Knowledge Representation & Reasoning in particular. This field has received a lot of attention over the past decades, as it extends to a plethora of areas and domains that include ambient intelligence, dynamic GIS, cognitive robotics, and spatiotemporal design [Bhatt et al., 2011]. QSTR abstracts from numerical quantities of space and time by using qualitative descriptions instead (e.g., precedes, contains, is left of ), thus providing a concise framework that allows for rather inexpensive reasoning about entities located in space and time.

The problem of representing and reasoning about qualitative information can be modeled as a qualitative constraint network (QCN), i.e., a network of constraints corresponding to qualitative spatial or temporal relations between spatial or temporal variables respectively, using a qualitative constraint language. A qualitative constraint language involves constraints defined over a finite set of binary relations, called base relations (or atoms) [Ligozat and Renz, 2004].

The fundamental reasoning problems associated with a given QCN N are the problems of satisfiability checking, minimal labeling (or deductive closure), and redundancy (or entailment) [Renz and Nebel, 2007]. In particular, the satisfiability checking problem is the problem of deciding if there exists a spatial or temporal valuation of the variables of N that satisfies its constraints, such a valuation being called a solution of N, the minimal labeling problem is the problem of finding the strongest implied constraints of N, and the redundancy problem is the problem of determining if a given constraint is entailed by N (that constraint being called redundant, as its removal does not change the solution set of the QCN). In general, for most qualitative constraint languages the satisfiability checking problem is NP-complete. Further, the redundancy problem, the minimal labeling problem, and the satisfiability checking problem are equivalent under polynomial Turing reductions [Golumbic and Shamir, 1993].

The vast amount, if not all, of the published works that study the aforementioned reasoning problems, use partial ⋄-consistency as a means to define practical algorithms for efficiently tackling them [Amaneddine et al., 2013; Sioutis et al., 2015; 2016b; Li et al., 2015; Renz and Nebel, 2001; Nebel, 1997]. Given a QCN N and a graph G, partial ⋄-consistency with respect to G, denoted by ⋄G-consistency, entails (weak) consistency for all triples of variables in N that correspond to three-vertex cycles (triangles) in G. We note that if G is complete, ⋄G-consistency becomes identical to ⋄-consistency [Renz and Ligozat, 2005]. Hence, ⋄-consistency is a special case of ⋄G-consistency. In fact, earlier works have relied solely on ⋄-consistency; it was not until the introduction of chordal (or triangulated) graphs in QSTR, due to some generalized theoretical results of [Huang, 2012], that researchers started restricting ⋄-consistency to a triangulation of the constraint graph of an input QCN and benefiting from better complexity properties.

Currently, and to the best of our knowledge, the fastest algorithm for enforcing partial ⋄-consistency, which is presented in [Long et al., 2016], is complete only for certain subsets of the set of allowed relations that can occur in a QCN. This fact significantly limits its practicality for arbitrary QCNs. Further, since those subsets define subclasses of relations that are in general smaller than the classes of relations for which partial ⋄-consistency is able to decide satisfiability, the algorithm of [Long et al., 2016] is able to tackle fewer QCNs in comparison with a generic algorithm for enforcing partial ⋄-consistency. To ameliorate this issue, we exploit the notion of abstraction for QCNs, which is an idea adopted from concepts of abstract interpretation [Cousot and Cousot, 1992]. In particular, a QCN is typically abstracted by relaxing some of its constraints in order to satisfy some property (if possible); in our case, we aim to abstract a given QCN is such a way that all of its constraints involve relations for which the algorithm of [Long et al., 2016] is complete. This should allow us to harvest as much of the performance gains of that algorithm as possible for an arbitrary QCN N, as we can use the algorithm to enforce partial ⋄-consistency on a proper abstraction of N very fast, and then incrementally apply appropriate constraint propagations on its output QCN to achieve partial ⋄-consistency pertaining to the original QCN N. Specifically, we make the following contributions: (i) we provide an efficient and generic algorithm for enforcing partial ⋄-consistency that exploits the notion of abstraction for QCNs and makes full use of the algorithm of [Long et al., 2016], (ii) we prove the correctness of our approach by utilizing certain properties of partial ⋄-consistency, such as idempotence and monotonicity, and (iii) we experimentally validate the usefulness and efficiency of our method against the state-of-the-art generic algorithm for enforcing partial ⋄-consistency of [Chmeiss and Condotta, 2011].

2 Preliminaries

A (binary) qualitative spatial or temporal constraint language, is based on a finite set B of jointly exhaustive and pairwise disjoint relations defined over an infinite domain D, which is called the set of base relations [Ligozat and Renz, 2004]. The base relations of a particular qualitative constraint language can be used to represent the definite knowledge between any two of its entities with respect to the level of granularity provided by the domain D. The set B contains the identity relation Id, and is closed under the converse operation (-1 ). Indefinite knowledge can be specified by a union of possible base relations, and is represented by the set containing them. Hence, 2B represents the total set of relations. The set 2B is equipped with the usual set-theoretic operations of union and intersection, the converse operation, and the weak composition operation denoted by the symbol ⋄ [Ligozat and Renz, 2004]. For all r ∈ 2B , we have that r-1 = ⋃{b-1 | b ∈ r}. The weak composition (⋄) of two base relations b, b′ ∈ B is defined as the smallest (i.e., strongest) relation r ∈ 2B that includes b ◦ b′ , or, 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′ } is the (true) composition of b and b′ . For all r, r′ ∈ 2B , we have that r ⋄ r′ = ⋃{b ⋄ b′ | b ∈ r, b′ ∈ r′ }.

As an example, the Region Connection Calculus (RCC) is a first-order theory for representing and reasoning about mereotopological information [Randell et al., 1992]. The domain D of RCC comprises all possible non-empty regular subsets of some topological space. These subsets do not have to be internally connected and do not have a particular dimension, but are commonly required to be regular closed [Renz, 2002]. Simply put, a subset X of a topological space is regular closed in that space, if X equals the closure of its interior. The base relations of RCC are the following ones: disconnected (DC), externally connected (EC), equal (EQ), partially overlapping (PO), tangential proper part (TPP), tangential proper part inverse (TPPi), nontangential proper part (NTPP), and non-tangential proper part inverse (NTPPi). These eight base relations form the RCC-8 constraint language. Relation EQ is the identity relation Id of RCC-8. Other notable and well known qualitative spatial and temporal constraint languages include Point Algebra [Vilain and Kautz, 1986], Cardinal Direction Calculus [Ligozat, 1998; Frank, 1991], Interval Algebra [Allen, 1983], and Block Algebra [Balbiani et al., 2002].

The weak composition operation ⋄, the converse operation -1 , the union operation ∪, the complement operation ∁ , and the total set of relations 2B along with the identity relation Id of a qualitative constraint language, form an algebraic structure (2B , Id, ⋄,-1 ,∁ , ∪) that can correspond to a relation algebra in the sense of Tarski [Tarski, 1941].

Proposition 1 ([Dylla et al., 2013]). The languages of Point Algebra, Cardinal Direction Calculus, Interval Algebra, Block Algebra, and RCC-8 are each a relation algebra with the algebraic structure (2B , Id, ⋄, -1 , ∁ , ∪).

In what follows, for a qualitative constraint language that is a relation algebra with the algebraic structure (2B , Id, ⋄, -1 , ∁ , ∪), we will simply use the term relation algebra, as the algebraic structure will always be of the same format.

The problem of representing and reasoning about qualitative information can be modeled as a qualitative constraint network (QCN), 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; 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 of RCC-8 is shown in Figure 1. In particular, the QCN comprises the set of variables {x, y, z} and the constraints C(x, y) = C(y, z) = C(z, x) = {EC}; for simplicity, converse relations as well as Id loops are not mentioned or shown in the figure.

Definition 2. Let N = (V,C) be a QCN, then: a solution of N is a mapping σ : V → D such that ∀(u, v) ∈ V × V , ∃b ∈ C(u, v) such that (σ(u), σ(v)) ∈ b; N is satisfiable iff it admits a solution; a QCN is equivalent to N iff it admits the same set of solutions as N; a sub-QCN N ′ of N, denoted by N ′ ⊆ N, is a QCN (V, C ′ ) such that C ′ (u, v) ⊆ C(u, v) ∀u, v ∈ V ; the constraint graph of N is the graph (V,E) where {u, v} ∈ E iff C(u, v) ̸= B and u ̸= v; and N is trivially inconsistent iff ∃u, v ∈ V such that C(u, v) = ∅.

We recall the following definition of ⋄G-consistency, which, as noted in the introduction, is the basic local consistency used in the literature for solving fundamental reasoning problems of QCNs, such as the satisfiability checking problem.

Definition 3. Given a QCN N = (V,C) and a graph G = (V,E), N is ⋄G-consistent iff ∀{vi, vj}, {vi, vk}, {vk, vj} ∈ E we have that C(vi, vj) ⊆ C(vi, vk) ⋄ C(vk, vj).

It is routine to formally prove the following properties of ⋄G-consistency, which we will use in the sequel, as they naturally derive from respective properties of ⋄-consistency:

Property 1. Let N = (V,C) be a QCN and G = (V,E) a graph. Then, the following properties hold:

• ⋄G(N) ⊆ N (viz., the ⋄G-closure of N) is the largest (w.r.t. ⊆) ⋄G-consistent sub-QCN of N (Dominance);
• ⋄G(⋄G(N)) = ⋄G(N) (Idempotence);
• ⋄G(N) is equivalent to N (Equivalence);
• if N ′ ⊆N then ⋄G(N ′ ) ⊆ ⋄G(N) (Monotonicity).

Definition 4. A subclass of relations is a subset A ⊆ 2B that contains the singleton relations of 2B and is closed under converse, intersection, and weak composition.

We note again that if G is complete, ⋄G-consistency becomes identical to ⋄-consistency [Renz and Ligozat, 2005], and, hence, ⋄-consistency is a special case of ⋄G-consistency.

Given a relation r of 2B and a subclass A ⊆ 2B containing B, A(r) denotes the smallest relation of A that includes r.

Definition 5. Given a QCN N = (V,C), a graph G = (V,E), and a subclass A ⊆ 2B containing B, the abstraction of N w.r.t. to A and G, denoted by AG(N), is the QCN (V, C ′ ) where C ′ (v, v′ ) = A(C(v, v′ )) ∀{v, v′ } ∈ E.

As an example, Figure 2 illustrates the abstraction of a QCN of RCC-8 w.r.t. to the subclass that results from the closure of the base relations of RCC-8 under converse, intersection, and weak composition (which, in addition, contains B) and the complete graph on its set of variables.

Given three relations r, r′ , r′′ ∈ 2B , we say that weak composition distributes over intersection if we have that r ⋄ (r′ ∩ r′′ ) = (r ⋄ r′ ) ∩ (r ⋄ r′′ ) and (r′ ∩ r′′ ) ⋄ r = (r′ ⋄ r) ∩ (r′′ ⋄ r).

Definition 6. A subclass A is distributive iff weak composition distributes over non-empty intersection ∀r, r′ , r′′ ∈ A.

Distributive subclasses of relations containing the universal relation B are defined for all of the qualitative constraint languages mentioned in Proposition 1 [Long and Li, 2015].

3 ⋄G-Consistency by Use of Abstraction

The main idea behind our approach, is to benefit as much as possible from the performance characteristics of the algorithm for enforcing partial ⋄-consistency of [Long et al.,

2016], when given an arbitrary QCN N. As noted in the introduction, that algorithm is complete only for certain subsets of 2B . Those subsets essentially define subclasses of relations that are distributive (see Definition 6). Hence, to be able to make full use of the algorithm of [Long et al., 2016], we utilize an abstraction of N with respect to some distributive subclass of relations, feed that abstraction to the algorithm, compare its output QCN N ′ with our initial QCN N and properly update N ′ , and finally employ a generic algorithm for enforcing partial ⋄-consistency to incrementally apply appropriate constraint propagations on the updated QCN N ′ and achieve partial ⋄-consistency pertaining to the original QCN N .

An algorithm that follows the aforementioned steps is presented in Algorithm 1, called PWC� (which stands for partial closure under weak composition by use of abstraction), where subroutine DPWC+ in line 3 (which stands for directional partial closure under weak composition plus) corresponds to a generalized version of the algorithm of [Long et al., 2016] and subroutine PWC in line 14 (which stands for partial closure under weak composition) is the state-of-the-art generic algorithm for enforcing partial ⋄-consistency of [Chmeiss and Condotta, 2011]. As opposed to the original algorithm of [Long et al., 2016], its generalized version, viz., algorithm DPWC+, restricts consistency checks to constraints corresponding to edges of a given input graph G. Algorithm DPWC+, as well as its subroutine, algorithmDPWC, are presented in Algorithms 2 and 3 respectively. For completeness, algorithm PWC is presented in Algorithm 4. With respect to algorithm DPWC+, we can prove the following result:

Proposition 2 (cf. [Long et al., 2016]). Given a not trivially inconsistent QCN N = (V,C) defined over a distributive subclass of relations of a relation algebra, a chordal graph G = (V,E), and a bijection α : V → {0, 1, . . . , |V | - 1} such that (α-1 (|V |-1),α-1 (|V |-2),. . .,α-1 (0)) is a perfect elimination ordering of G, algorithm DPWC+ returns (True, ⋄G(N)) if ⋄G(N) is not trivially inconsistent, and (False, N ′ )

Algorithm 2: DPWC+(N , G, α)

in : AQCNN = (V,C), a graph G = (V,E), and a bijection α : V → {0, 1, . . . , |V | - 1}. out : True or False, and a sub-QCN of N. 1 begin 2 (decision, N ) ← DPWC(N , G, α); 3 if decision = False then 4 return (False, N ); 5 for x from 1 to |V | - 1 do 6 v ← α-1 (x); 7 foreach v′ ∈ V | {v′ , v} ∈ E ∧ α(v′ ) < α(v) do 8 adj ←{v′′ ∈ V | {v′′ , v}, {v′ , v′′ } ∈ E ∧ 9 α(v′′ ) < α(v)}; 10 C(v, v′ ) ← ⋂v′′∈adj C(v, v′′ ) ⋄ C(v′′ , v′ ); 11 C(v′ , v) ← (C(v, v′ ))-1 ; 12 return (True, N );

Algorithm 3: DPWC(N , G, α)

in : AQCNN = (V,C), a graph G = (V,E), and a bijection α : V → {0, 1, . . . , |V | - 1}. out : True or False, and a sub-QCN of N. 1 begin 2 for x from |V | - 1 to 1 do 3 v ← α-1 (x); 4 adj ←{v′ ∈ V | {v′ , v} ∈ E ∧α(v′ ) < α(v)}; 5 foreach v′ , v′′ ∈ adj | {v′ , v′′ } ∈ E ∧ 6 α(v′ ) < α(v′′ ) do 7 r ← C(v′ , v′′ ) ∩ (C(v′ , v) ⋄ C(v, v′′ )); 8 if r = ∅ then return (False, N); 9 if r ⊂ C(v′ , v′′ ) then 10 C(v′ , v′′ ) ← r; 11 C(v′′ , v′ ) ← r-1 ; 12 return (True, N );

with N ′ ⊆ N otherwise.

As shown in [Long et al., 2016], algorithm DPWC+ (at least in its original and more particular version as it appears in that work) exhibits outstanding performance in comparison with algorithm PWC for enforcing partial ⋄-consistency on QCNs defined over a distributive subclass of relations. Due to space constraints, it is not possible to detail the functionality of that algorithm; however, it should suffice to say that it utilizes partial ←-⋄ -consistency as its core local consistency [Sioutis et al., 2016a], which is enforced by algorithm DPWC, and exploits unique properties of distributive subclasses of relations to achieve partial ⋄-consistency in a given QCN defined over such a subclass. In summary, partial ←-⋄ -consistency is partial ⋄-consistency restricted (directionally) to a variable ordering α of the considered QCN. On the other hand, algorithm PWC is both efficient and complete for enforcing partial ⋄-consistency on arbitrary QCNs. With respect to algorithm PWC, we recall the following result:

Proposition 3 ([Chmeiss and Condotta, 2011]). Given a not trivially inconsistent QCN N = (V,C) of a relation alge-

Algorithm 4: PWC(N , G, e ← ∅)

in : AQCNN = (V,C), a graph G = (V,E), and optionally a set e such that e ⊆ E. out : True or False, and a sub-QCN of N. 1 begin 2 Q← (e if e ̸= ∅ else E); 3 while Q ̸= ∅ do 4 {v, v′ } ← Q.pop(); 5 foreach v′′ ∈ V | {v, v′′ }, {v′ , v′′ } ∈ E do 6 r ← C(v, v′′ ) ∩ (C(v, v′ ) ⋄ C(v′ , v′′ )); 7 if r = ∅ then return (False, N); 8 if r ⊂ C(v, v′′ ) then 9 C(v, v′′ ) ← r; 10 C(v′′ , v) ← r-1 ; 11 Q ← Q ∪ {{v, v′′ }}; 12 r ← C(v′′ , v′ ) ∩ (C(v′′ , v) ⋄ C(v, v′ )); 13 if r = ∅ then return (False, N); 14 if r ⊂ C(v′′ , v′ ) then 15 C(v′′ , v′ ) ← r; 16 C(v′ , v′′ ) ← r-1 ; 17 Q ← Q ∪ {{v′′ , v′ }}; 18 return (True, N );

bra, and a graph G = (V, E), algorithm PWC returns (True, ⋄G(N)) if ⋄G(N) is not trivially inconsistent, and (False, N ′ ) with N ′ ⊆ N otherwise.

Having presented the structure and the core components of algorithm PWC� , we obtain the following lemma to be used for establishing the correctness of our algorithm in the sequel:

Lemma 1. Let N ′ = (V, C ′ ) and N = (V, C) be two QCNs such that N ⊆ N ′ . Then, we have that ⋄G(N) ⊆ ⋄G(N ′ ) ∩ N .

Proof. As N ⊆ N ′ , by monotonicity of ⋄G-consistency we have that ⋄G(N) ⊆ ⋄G(N ′ ). Moreover, since it also holds that ⋄G(N) ⊆N, it follows that ⋄G(N) ⊆ ⋄G(N ′ ) ∩N.

The following result states that algorithm PWC� is complete for enforcing partial ⋄-consistency on arbitrary QCNs:

Theorem 1. Given a not trivially inconsistent QCN N = (V,C) of a relation algebra, a distributive subclass of relations A of that relation algebra, a chordal graph G = (V,E), and a bijection α : V → {0, 1, . . . , |V | - 1} such that (α-1 (|V | - 1),α-1 (|V | - 2),. . .,α-1 (0)) is a perfect elimination ordering of G, algorithm PWC� returns (True, ⋄G(N)) if ⋄G(N) is not trivially inconsistent, and (False, N ′ ) with N ′ ⊆ N otherwise.

Proof. Let N ′ = AG(N). Clearly, N ⊆ N ′ . As N ′ is defined over a distributed subclass of relations, by Proposition 2 we have that, in line 3 of algorithm PWC� , algorithm DPWC+ returns (False, N ′′ ) with N ′′ ⊆ N ′ if ⋄G(N ′ ) is trivially inconsistent, and (True, ⋄G(N ′ )) otherwise. By monotonicity of ⋄G-consistency we have that ⋄G(N) ⊆ ⋄G(N ′ ). Thus, algorithm PWC� in line 5 returns (False, N) only if ⋄G(N) is trivially inconsistent. Assuming that ⋄G(N ′ ) is not trivially inconsistent and the algorithm continues its execution, the operation ⋄G(N ′ ) ∩ N is performed in lines 7-13 of algorithm PWC� . By Lemma 1 we have that ⋄G(N) ⊆ ⋄G(N ′ ) ∩ N. Hence, if ⋄G(N ′ ) ∩ N defines a trivially inconsistent QCN, then ⋄G(N) is trivially inconsistent. Therefore, algorithm PWC� in line 9 returns (False, N) only if ⋄G(N) is trivially inconsistent. Let M = ⋄G(N ′ ) ∩ N, and further assume that M is not trivially inconsistent and the algorithm continues its execution. M is a not trivially inconsistent QCN that results by tightening some of the constraints of ⋄G(N ′ ). Note also that M⊆ N ; hence, by monotonicity of ⋄G-consistency we have that ⋄G(M) ⊆ ⋄G(N). In addition, as we have already established that ⋄G(N) ⊆M, by monotonicity of ⋄G-consistency we have that ⋄G(⋄G(N)) ⊆ ⋄G(M), and by idempotence of ⋄G-consistency it follows that ⋄G(N) ⊆ ⋄G(M). Consequently, we have that ⋄G(N) = ⋄G(M). Now, by utilizing the incremental functionality of algorithm PWC, we need only feed the algorithm with the QCNM, the graph G, and the set of edges that correspond to the tightened constraints of ⋄G(N ′ ) in order to obtain ⋄G(M) (see [Gerevini, 2005, Section 3]). Thus, by Proposition 3 we have that, in line 14 of algorithm PWC� , algorithm PWC returns (True, ⋄G(M)) if ⋄G(M) is not trivially inconsistent, and (False, M′ ) withM′ ⊆M otherwise. Since ⋄G(N) = ⋄G(M), we deduce that algorithm PWC� returns (True, ⋄G(N)) if ⋄G(N) is not trivially inconsistent, and (False, N ′′ ) with N ′′ ⊆ N otherwise.

Regarding time complexity, given a QCN N = (V, C) and a graph G = (V,E) with a maximum vertex degree ∆, algorithm PWC� runs in O(max{∆2 |V |,∆|E||B|}) time, as the run-times of DPWC+ and PWC are O(∆2 |V |) [Long et al., 2016] and O(∆|E||B|) [Chmeiss and Condotta, 2011] respectively. In terms of the number of triangles t in G, and assuming that |V | + |E| ∈ O(t), algorithm PWC� runs in O(t|B|) time. However, depending on the percentage of distributive relations that are in the given QCN N and the quality of the abstraction that is obtained with respect to a given distributive subclass of relations, algorithm DPWC+ (employed in line 3 of algorithm PWC� ) may diminish that run-time in practice, as it runs in O(t) time [Long et al., 2016], which is independent of the size of the set of base relations B. We will explore the aforementioned implication by means of a thorough experimental evaluation in the following section.

4 Experimental Evaluation

We evaluated the performance of an implementation of algorithm PWC� , against an implementation of the state-ofthe-art generic algorithm for enforcing partial ⋄-consistency PWC, with a varied dataset of arbitrary QCNs of RCC-8.

Technical Specifications. The evaluation was carried out on a computer with an Intel Core i7-2820QM processor (which has a frequency of 2.30 GHz per CPU core), 8 GB of RAM, and the Trusty Tahr x86 64 OS (Ubuntu Linux). All algorithms were coded in Python and run using the standard CPython 2.7 interpreter. Only one CPU core was used.

Datasets and Measures. We considered random scale-free RCC-8 networks generated by the BA(n, m) model [Barabasi and Albert, 1999], the use of which in qualitative constraintbased reasoning is well motivated in [Sioutis et al., 2016b], and random (unstructured) RCC-8 networks generated by the A(n, d, l) model [Renz and Nebel, 2001], which has been traditionally employed over the past decades in the literature. Each of the aforementioned models was enriched with a parameter rd that allowed us to specify the percentage of distributive relations we would like to have in our RCC-8 networks. In particular, we used the enriched BA(n,m, rd) model to create random scale-free RCC-8 constraints graphs of order n, with a preferential attachment value m, and with rd% of distributive relations, and the enriched A(n, d, l, rd) model to create random RCC-8 constraint graphs of order n, with an average vertex degree d, with an average size of relation per constraint l (which defaults to |B|/2 for model BA(n,m, rd)), and with rd% of distributive relations. We generated a total of 400 RCC-8 networks; more specifically, we considered 10 satisfiable and 10 unsatisfiable RCC-8 networks for each of the models BA(n = 10 000, m = 2, rd) and A(n = 1000, d = 10.0, l = 4.0, rd), and for all values of rd ranging from 0% to 90% with a step of 10%. Regarding distributive relations in particular, we considered the distributive subclass D64 8 of RCC-8 [Li et al., 2015] as our selection pool and as an input to algorithm PWC� . Satisfiability or otherwise of our networks was guaranteed by the generic qualitative constraint-based reasoner GQR [Gantner et al., 2008; Westphal et al., 2009]. Finally, the maximum cardinality search algorithm [Tarjan and Yannakakis, 1984] was used to obtain a variable elimination ordering α of a given QCN N for PWC� , and a triangulation G of the constraint graph of N based on α for both PWC� and PWC. We note that, with respect to our evaluation, any perfect elimination orderings and, hence, any respective chordal graphs would have been adequate, as they would have affected all involved algorithms proportionally and would not have qualitatively distorted the obtained results. An overview of the use of chordal graphs in the QSTR literature is presented in [Sioutis et al., 2016c].

Our evaluation involved two measures, which we describe as follows. The first measure considers the number of constraint checks performed by an algorithm for enforcing partial ⋄-consistency. Given a QCN N = (V, C) and three variables vi, vk, vj ∈ V , a constraint check occurs when we compute the relation r = C(vi, vj) ∩ (C(vi, vk) ⋄ C(vk, vj)) and check if r ⊂ C(vi, vj), so that we can propagate its constrainedness if that condition is satisfied. The second measure concerns the CPU time and is strongly correlated with the first one, as the run-time of any proper implementation of an algorithm for enforcing partial ⋄-consistency should rely mainly on the number of constraint checks performed.

Results. The experimental results for random RCC-8 networks of models BA(n, m, rd) and A(n, d, l, rd) are presented in Tables 1a and 1b respectively, where a fraction xy denotes that an approach required x seconds of CPU time and performed y constraint checks on average per dataset of networks during its operation. Regarding satisfiable networks, despite a rather sluggish performance of PWC� when 0% of distributive relations were considered, in terms of being around 20% slower on average than PWC, it caught up fast, at around 20% of distributive relations, and constantly outperformed PWC from that point on, being nearly 80% faster on average than PWC when 90% of distributive relations were considered. The same trend held true, more or less, for unsatisfiable networks, with the addition that the minimum time for refuting unsatisfiable networks for PWC� was often significantly less than that of PWC, which is explained by the fact that PWC� may generally detect certain inconsistencies at an earlier stage (see lines 5 and 9 in Algorithm 1).

Table 1: Evaluation of the performance of algorithms PWC and PWC �

5 Conclusion and FutureWork

Partial ⋄-consistency is an essential local consistency for tackling fundamental reasoning problems associated with qualitative constraint networks (QCNs), such as the problems of satisfiability checking, minimal labeling, and redundancy.

We proposed a new algorithm for efficiently applying partial ⋄-consistency on arbitrary QCNs, that exploits the notion of abstraction for QCNs, utilizes certain properties of partial ⋄-consistency, and adapts the functionalities of some state-of-the-art algorithms to its design. The evaluation that we conducted with QCNs of the Region Connection Calculus showed the usefulness and efficiency of our method. For future work, we would like to obtain a variation of our algorithm for efficiently enforcing singleton partial ⋄-consistency (i.e., partial ◆-consistency [Amaneddine et al., 2013]) on arbitrary QCNs, which is an important local consistency for solving the minimal labeling problem, in particular, of QCNs.