On the Utility of Neighbourhood Singleton-Style Consistencies for Qualitative Constraint-Based Spatial and Temporal Reasoning
Full text
On the Utility of Neighbourhood Singleton-Style Consistencies for Qualitative Constraint-Based Spatial and Temporal Reasoning Michael Sioutis1 Department of Computer Science, Aalto University, Espoo, Finland https://msioutis.gitlab.io/ mic[email protected] Anastasia Paparrizou CRIL CNRS UMR 8188, Artois University, Lens, France http://www.cril.univ-artois.fr/~paparrizou/ [email protected] Tomi Janhunen Department of Computer Science, Aalto University, Espoo, Finland Tampere University, Tampere, Finland https://users.ics.aalto.fi/ttj/ tomi.janh[email protected] Abstract A singleton-style consistency is a local consistency that verifies if each base relation (atom) of each constraint of a qualitative constraint network ( QCN ) can serve as a support with respect to the closure of that network under a (naturally) weaker local consistency. This local consistency is essential for tackling fundamental reasoning problems associated with QCN s, such as the satisfiability checking or the minimal labeling problem, but can suffer from redundant constraint checks, especially when those checks occur far from where the pruning usually takes place. In this paper, we propose singletonstyle consistencies that are applied just on the neighbourhood of a singleton-checked constraint instead of the whole network. We make a theoretical comparison with existing consistencies and consequently prove some properties of the new ones. In addition, we propose algorithms to enforce our consistencies, as well as parsimonious variants thereof, that are more efficient in practice than the state of the art. We make an experimental evaluation with random and structured QCN s of Interval Algebra in the phase transition region to demonstrate the potential of our approach. 2012 ACM Subject Classification Theory of computation → Constraint and logic programming; Computing methodologies → Temporal reasoning; Computing methodologies → Spatial and physical reasoning Keywords and phrases Qualitative constraints, spatial and temporal reasoning, singleton-style consistencies, neighbourhood, minimal labeling problem Digital Object Identifier 10.4230/LIPIcs.TIME.2019.14 1 Introduction Qualitative Spatial and Temporal Reasoning (QSTR) is a Symbolic AI approach that deals with the fundamental cognitive concepts of space and time in a qualitative, human-like, manner [ 28 , 16 ]. For instance, in natural language one uses 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. QSTR provides a concise framework that allows for rather inexpensive reasoning about entities located in 1Corresponding author ©Michael Sioutis, Anastasia Paparrizou, and Tomi Janhunen; licensed under Creative Commons License CC-BY 26th International Symposium on Temporal Representation and Reasoning (TIME 2019). Editors: Johann Gamper, Sophie Pinchinat, and Guido Sciavicco; Article No. 14; pp. 14:1–14:17 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
14:2 Neighbourhood Singleton-Style Consistencies for QSTR space and time and, hence, further boosts research and applications to a plethora of areas and domains that include, but are not limited to, dynamic GIS [ 7 ], cognitive robotics [ 18 ], deep learning [ 25 ], and qualitative model generation from video [ 15 ]. The interested reader may look into a more comprehensive review of the emerging applications, the trends, and the future directions of QSTR in [6]. The problem of representing and reasoning about qualitative spatial or temporal information can be modeled as a qualitative constraint network ( QCN ), i.e., a network of qualitative constraints corresponding to spatial or temporal relations between spatial or temporal variables respectively. Two fundamental reasoning problems associated with a given QCN N are the problems of satisfiability checking and minimal labeling (or deductive closure) [ 37 ]. In particular, the satisfiability checking problem is about deciding if there exists a valuation of the variables of N that satisfies its constraints, and the minimal labeling problem concerns finding the strongest implied constraints and consequently obtaining its minimal sub-network. In general, for most well-known spatio-temporal calculi the satisfiability checking problem is NP -hard [ 17 ]. Further, the minimal labeling problem is polynomial-time Turing reducible to the satisfiability checking problem [20]. Motivation In this paper, we focus mostly on the minimal labeling problem, which, since its introduction in 1974 by Montanari [ 31 ], has been studied in the domain of both CSP s [ 21 , 46 ] and QCN s [ 19 , 30 ]. As noted in [ 21 ], a minimal network is a quite useful knowledge compilation, since it allows one to answer a number of queries in polynomial time that would otherwise be NP -hard; indeed, in the context of QSTR, for instance, one could exploit minimality of a QCN to immediately deduce whether a task A could be scheduled before a task B , or an object X could be placed on top of an object Y . Difficult problems such as the minimal labeling problem and alike are, in general, either approximated by the use of local consistencies [ 46 ] or even solved by the aid of such consistencies [ 2 ]. Among the local consistencies introduced in the literature, we study singleton-style consistencies in the aforementioned context, which are consistencies that entail support for each base relation (atom) of the constraints of a QCN with respect to the closure of that network under a weaker local consistency (typically G-consistency [ 10 , 35 ]). Specifically, we investigate how these consistencies behave when the underlying weaker local consistency that they build upon is restricted to the neighbourhood of a singleton-checked constraint. As noted in [ 47 ], neighbourhood-based restrictions can hit the sweet spot between effectiveness and efficiency in singleton-style consistencies for CSP s; therefore, it is imperative that we introduce and study such restrictions in the context of QCN s as well, and consequently provide a foundation for further work in understanding this kind of network structures, which have received much attention over the past years [16]. Contributions Our contributions are fourfold and are described as follows: (i) we enrich the family of consistencies for QCN s by proposing singleton-style consistencies that are applied just on the neighbourhood of the singleton-checked constraint instead of the entire network; (ii) we theoretically obtain a strength-based hierarchy among existing consistencies for QCNs and the novel ones; (iii) we present algorithms to enforce the proposed consistencies for QCN s, as well as parsimonious variants thereof;
M. Sioutis, A. Paparrizou, and T. Janhunen 14:3 precedes meets overlaps starts during finishes equals p pi m mi o oi s si d di f fi eq x y y y y y y y x x x x x x Figure 1 The base relations of IA;·idenotes the converse of ·. (iv) we make an experimental evaluation with random and structured QCN s of Interval Algebra to measure and compare the performance of all considered algorithms, especially in terms of how fast and how well they can independently approximate the minimal sub-network of a QCN. The rest of the paper is organized as follows. In Section 2 we give some preliminaries on qualitative spatial and temporal reasoning. Next, in Section 3 we overview some known state-of-the-art local consistencies for QCN s. Then, in Section 4 we introduce, formally define, and thoroughly study the proposed neighbourhood-based consistencies for QCN s, and present the algorithms for enforcing these consistencies, as well as parsimonious variants thereof. In Section 5 we evaluate our approach with random and structured QCN s of Interval Algebra and comment on the outcome; one finding is that neighbourhood-focused singleton-style algorithms are ∼30 %faster in the phase transition region than the standard algorithms. Finally, in Section 6 we draw some conclusive remarks and give directions for future work. 2 Preliminaries A binary qualitative spatial or temporal constraint language, is based on a finite set Bof jointly exhaustive and pairwise disjoint relations, called the set of base relations [ 29 ], that is defined over an infinite domain D. 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 Bcontains 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, 2 B represents the total set of relations. The set 2 B is equipped with the usual set-theoretic TIME 2019
14:4 Neighbourhood Singleton-Style Consistencies for QSTR x1x2 x3 x4 {p, m} B {d, s, si} {oi} {oi, m} {pi, eq} (a) A satisfiable QCN N. x1 x2 x3 x4 (b) A solution σof N. Figure 2 Figurative examples of QCN terminology using IA. operations of union and intersection, the converse operation, and the weak composition operation denoted by the symbol [ 29 ]. For all r∈ 2 B , we have that r−1 = S{b−1|b∈r} . The weak composition ( )of two base relations b, b0∈ Bis defined as the smallest (i.e., strongest) relation r∈ 2 B that includes b◦b0 , or, formally, bb0={b00 ∈ B |b00∩ ( b◦b0 ) 6 = ∅} , where b◦b0={ ( x, y ) ∈ D × D | ∃z∈Dsuch that ( x, z ) ∈b∧ ( z, y ) ∈b0} is the (true) composition of band b0. For all r, r0∈2B, we have that rr0=S{bb0|b∈r, b0∈r0}. As an illustration, consider the well-known qualitative temporal constraint language of Interval Algebra ( IA ), introduced by Allen [ 1 ]. IA considers time intervals (as temporal entities) and the set of base relations B= {eq , p , pi , m , mi , o , oi , s , si , d , di , f , fi} to encode knowledge about the temporal relations between intervals on the timeline, as depicted in Figure 1. Specifically, each base relation represents a particular ordering of the four endpoints of two intervals on the timeline, and eq is the identity relation Id. Notably, most of the well-known and well-studied qualitative constraint languages, such as Interval Algebra [ 1 ] and RCC8 [ 34 ], are in fact relation algebras [ 17 ]. In what follows, we restrict ourselves to such calculi in order to facilitate discussion of the consistencies and of the algorithms for enforcing them. The problem of representing and reasoning about qualitative spatial or temporal information can be modeled as a qualitative constraint network, defined in the following manner: IDefinition 1. Aqualitative 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, v0)=(C(v0, v))−1for all v, v0∈V, where SB=D×D. An example of a QCN of IA is shown in Figure 2a; for clarity, converse relations as well as Id loops are not mentioned or shown in the figure. IDefinition 2. Let N= (V, C)be a QCN, then: asolution of N is a mapping σ : V→ Dsuch that ∀ ( u, v ) ∈V×V , ∃b∈C ( u, v )such that (σ(u), σ(v)) ∈b(see Figure 2b); Nis satisfiable iff it admits a solution; asubQCN N0 of N , denoted by N0⊆ N , is a QCN ( V, C0 )such that C0 ( u, v ) ⊆C ( u, v ) ∀u, v ∈V; if in addition ∃u, v ∈Vsuch that C0(u, v)⊂C(u, v), then N0⊂ N ; a base relation b∈C ( v, v0 )with v, v0∈V is feasible (resp. unfeasible) in N iff there exists (resp. there does not exist) a solution σ : V→ Dof N such that ( σ ( v ) , σ ( v0 )) ∈b ; Nis minimal iff ∀v, v0∈Vand ∀b∈C(v, v0),bis a feasible base relation in N;
M. Sioutis, A. Paparrizou, and T. Janhunen 14:5 the constraint graph of N , denoted by G( N ), is the graph ( V, E )where {u, v} ∈ E iff C(u, v)6=Band u6=v; Nis the empty QCN on V, denoted by ⊥V, iff C(u, v) = ∅for all u, v ∈V. Let us further introduce the following operation that substitutes C ( v, v0 )with r∈ 2 B in a given QCN: given a QCN N = ( V, C )and v, v0∈V , we define that N[v,v0]/r with r∈ 2 B yields the QCN N0 = ( V, C0 )defined by C0 ( v, v0 ) = r , C0 ( v0, v ) = r−1 and C0 ( u, u0 ) = C ( u, u0 ) ∀ ( u, u0 ) ∈ (V×V)\ {(v, v0),(v0, v)}. 3 State-of-the-art Consistencies We view a consistency φ G , where φ is some operation (such as the weak composition operation) and G a graph, as a predicate on QCN s, i.e., a function that receives an input QCN and returns true or false depending on whether φ G holds on that QCN or not respectively. In what follows, given some operation φ (such as the weak composition operation) and a graph G , the unique ⊆ -maximal φ G -consistent subQCN of N is called the closure of N under the consistency φ Gand is denoted by φ G(N). We recall the definition of G-consistency , which is a basic and widely used local consistency for reasoning with QCNs. IDefinition 3. Given a QCN N = ( V, C )and a graph G = ( V0, E ), where V0⊆V , N is said to be G-consistent iff ∀{vi, vj},{vi, vk},{vk, vj} ∈ E we have that C ( vi, vj ) ⊆ C(vi, vk)C(vk, vj). Intuitively, G-consistency entails consistency for all triples of variables of a QCN that correspond to triangles of a given graph G . If G is the complete graph on the variables of a given QCN , then G-consistency becomes identical to -consistency [ 35 ], and, hence, -consistency can be seen as a special case of G-consistency. In [ 39 ] the authors build upon G-consistency and propose a local consistency in the context of qualitative constraint-based reasoning that serves as the counterpart of directional path consistency in traditional constraint programming [ 14 ] or quantitative temporal reasoning [ 13 ], and is mainly distinguished by the fact that the involved consistency notions are tailored to handle infinite domains and qualitative relations. This local consistency is called ←− G - consistency and, in particular, it entails consistency for all ordered triples of variables of a QCN that correspond to triangles of a given graph G ; this ordering can be specified by a bijection between the set of the variables of a QCN and a set of integers, and can be chosen randomly or via an algorithm or heuristic. We recall the formal definition of that consistency as follows: IDefinition 4. Given a QCN N = ( V, C ), an ordering ( α−1 (0), α−1 (1), . . . , α−1 ( n− 1)) of V defined by a bijection α : V→ { 0 , 1 , . . . , n − 1 } , and a graph G = ( V0, E ), where V0⊆V , N is said to be ←− G -consistent iff ∀vi, vj, vk∈V such that {vi, vj},{vi, vk},{vk, vj} ∈ E and α(vi), α(vj)< α(vk)we have that C(vi, vj)⊆C(vi, vk)C(vk, vj). Since ←− G -consistency is basically G-consistency restricted to some ordering of the triples of variables of a given QCN , it is expected that it will perform worse than G-consistency in terms of tackling the satisfiability checking or the minimal labeling problem of that QCN , in the general case. However, that behaviour of ←− G -consistency in the context of the aforementioned reasoning problems for arbitrary QCN s has yet to be investigated (cf. [ 40 ]), and we shall use this work as an opportunity to do so (see Section 5). TIME 2019
14:6 Neighbourhood Singleton-Style Consistencies for QSTR We continue with the presentation of some state-of-the-art singleton-style consistencies. Given a graph G = ( V0, E ), where V0⊆V , a QCN N = ( V, C )is ◆ G-consistent iff for every pair of variables {v, v0} ∈ E and every base relation b∈C ( v, v0 ), after instantiating C ( v, v0 ) with {b} as the singleton and applying G-consistency on N , the revised constraint C ( v, v0 )is always supported by {b}. Formally, ◆ G-consistency of a QCN is defined as follows: IDefinition 5. Given a QCN N = ( V, C )and a graph G = ( V0, E ), where V0⊆V , N is said to be ◆ G-consistent iff N is G-consistent and ∀{v, v0} ∈ E and ∀b∈C ( v, v0 )we have that C0(v, v0) = {b}, where (V, C0) = G(N[v,v0]/{b}). If G is the complete graph on the variables of a given QCN , we can easily verify that ◆ G-consistency corresponds to B -consistency of the family of f -consistencies studied in [ 11 ]. Interestingly, ◆ G-consistency for QCN s can also be seen as a counterpart of singleton arc consistency (SAC) [12] for CSPs. Finally, in [ 42 ] the authors define a local consistency that is more restrictive than any of the practical 2 local consistencies known to date for QCN s, called collective ◆ G-consistency , or ◆∪ G-consistency for short. This singleton-style consistency is inspired by k -partitioning consistency for CSPs [5]. We recall the formal definition of that consistency as follows: IDefinition 6. Given a QCN N = ( V, C )and a graph G = ( V0, E ), where V0⊆V , N is said to be ◆∪ G-consistent iff N is ◆ G-consistent and ∀{v, v0} ∈ E , ∀b∈C ( v, v0 ), and ∀{u, u0} ∈ E we have that ∃b0∈C(u, u0)such that b∈C0(v, v0), where (V, C0) = G(N[u,u0]/{b0}). This underlying filtering condition of ◆∪ G-consistency is based on relation partitioning combined with G-consistency , and allows for improved pruning capability over ◆ G-consistency [ 42 ]. 4 Neighbourhood Singleton-style Consistencies In this section we propose and study a variety of singleton-style consistencies that are applied just on the neighbourhood of the singleton-checked constraint instead of the whole network. Before doing so, let us first formally introduce a preorder in order to compare the pruning (or inference) capability of different consistencies. Let φ G and ψ G be two consistencies defined by some operations φ and ψ respectively and a graph G . Then, φ G is stronger than ψ G iff whenever φ G holds on a QCN N with respect to a graph G , ψ G also holds on N with respect to G , and φ G is strictly stronger than ψ G iff φ G is stronger than ψ G and there exists at least one QCN N and a graph G such that ψ G holds on N with respect to G , but φ G does not hold on N with respect to G . (The terms weaker and strictly weaker can be defined likewise.) Finally, φ G and ψ G are incomparable iff there exist QCN s N and N0 such that φ G is strictly stronger than ψ G with respect to N and some graph G , and φ G is strictly weaker than ψ G with respect to N0and some graph G(we note that the graph Gcan be different in the two cases). In general, standard singleton-style consistencies can make a lot of redundant checks, which consequently can slow down their efficacy. It has been observed in the domain of CSP s that the majority of constraint revisions occur close to the relation that is being singleton checked, and rarely too far from it [ 47 ]. For that purpose, constraint programming researchers have proposed weaker singleton-style consistencies that localize propagation to the neighbourhood of the variable at hand [ 47 , 33 ]. Neighbourhood singleton-style consistencies for CSP s, despite being strictly weaker than SAC [ 12 ] in general, can produce almost as much 2 Clearly, in special cases notions like k -consistency can be defined and exploited theoretically [ 9 ], but these can be hardly implemented efficiently and are therefore not suitable for applications.
M. Sioutis, A. Paparrizou, and T. Janhunen 14:7 x1x2 x3x4 x5 {di, m} {m, si} {o} {pi, p, si, f} {d} {d, o} {eq, d, fi} {d, di} B B Figure 3 Given the QCN N = ( V, C )above and the graph G that results by removing the edge {x1, x5} from the complete graph on V , we have that N is neighbourhood ◆∪ G-consistent (and neighbourhood ◆ G-consistent), but not ◆ G-consistent (or ◆∪ G-consistent). filtering as SAC with substantially less cost on many problems [ 33 ]. In what follows, we define two neighbourhood singleton-style consistencies for QCNs , and then we proceed to present algorithms and parsimonious variants thereof for applying these consistencies efficiently. In order to define the new consistencies, we first need to define what exactly is meant by “neighbourhood of a relation” in the context of QCN s. Informally, given a QCN N and a graph G , the neighbourhood of a relation in N comprises all the triangles that involve the corresponding edge in G , and all the edges among the vertices of those triangles as well. Noting that in a given graph G = ( V, E ), for each u∈V the set of adjacent vertices of u , denoted by adj ( u ), is the set {w| {u, w} ∈ E} , we can formally define the neighbourhood of a relation of a QCN as follows: IDefinition 7. Given a QCN N = ( V, C ), a graph G = ( V0, E ), where V0⊆V , and two variables v, v0∈V such that {v, v0} ∈ E , the neighbourhood of C ( v, v0 ), denoted by GN(vv0) , is the induced subgraph G[S], where S= (adj(v)∩adj(v0)) ∪ {v, v0}. As an example, consider the QCN and its accompanying graph shown in Figure 3. The neighbourhood of C(x1, x3)is the induced subgraph of the set of vertices {x1, x2, x3, x4}. With the aforementioned definition in mind, we can define the notion of neighbourhood ◆ G-consistency as follows: IDefinition 8. Given a QCN N = ( V, C )and a graph G = ( V0, E ), where V0⊆V , N is said to be neighbourhood ◆ G-consistent , or N ◆ G-consistent for short, iff N is G-consistent and ∀{v, v0} ∈ E and ∀b∈C ( v, v0 )we have that C0 ( v, v0 ) = {b} , where ( V, C0 ) = GN(vv0)(N[v,v0]/{b}). Similarly, we can define the notion of neighbourhood ◆∪ G-consistency as follows: IDefinition 9. Given a QCN N = ( V, C )and a graph G = ( V0, E ), where V0⊆V , N is said to be neighbourhood ◆∪ G-consistent , or N ◆∪ G-consistent for short, iff N is N ◆ G-consistent and ∀{v, v0} ∈ E , ∀b∈C ( v, v0 ), and ∀{u, u0} ∈ E we have that ∃b0∈C ( u, u0 )such that b∈C0(v, v0), where (V, C0) = GN(vv0)(N[u,u0]/{b0}). TIME 2019
14:8 Neighbourhood Singleton-Style Consistencies for QSTR The reader can note that Definitions 8 and 9 mirror Definitions 5 and 6 respectively, the difference being that the closure under G-consistency is restricted to the neighbourhood of the constraint at hand. We recall the following result from [ 42 ] in our effort here to build a strength-based hierarchy among all discussed consistencies: IProposition 1 ([ 42 ]) . We have that ◆∪ G-consistency is strictly stronger than ◆ G-consistency . In the sequel, Figure 3 will be crucial in proving the results that follow. IProposition 2. We have that ◆∪ G-consistency is strictly stronger than N◆∪ G-consistency. Proof. Consider the QCN along with its accompanying graph depicted in Figure 3. As noted in its caption the QCN is N ◆∪ G-consistent and N ◆ G-consistent , but not ◆ G-consistent or ◆∪ G-consistent . Specifically, in order for the QCN to become ◆ G-consistent and ◆∪ G-consistent , the base relation mi needs to be removed from C(x2, x5). In addition, by the definitions of ◆∪ G-consistency and N ◆∪ G-consistency , we have that every ◆∪ G-consistent QCN is N ◆∪ G-consistent . Specifically, given a QCN N and two graphs G and G0 such that G⊆G0 , it holds that if N is G-consistent then Nis G0-consistent. J Following the same line of reasoning as that of the proof of Proposition 2, we assert the next result: IProposition 3. We have that ◆ G-consistency is strictly stronger than N◆ G-consistency. We proceed with presenting the next result: IProposition 4. We have that N◆∪ G-consistency is strictly stronger than N◆ G-consistency. Proof. Consider the QCN along with its accompanying graph depicted in Figure 3in [ 42 ]. It is the case that the QCN is N ◆ G-consistent , but not N ◆∪ G-consistent . Additionally, by definition of N◆∪ G-consistency, we have that every N◆∪ G-consistent QCN is N◆ G-consistent. J We continue with another result as follows: IProposition 5. We have that N◆∪ G-consistency is incomparable to ◆ G-consistency. Proof. Consider again the QCN along with its accompanying graph depicted in Figure 3 in [ 42 ]. It is the case that the QCN is ◆ G-consistent , but not N ◆∪ G-consistent . On the other hand, as noted also in the proof of Proposition 2, the QCN of Figure 3 here is N ◆∪ G-consistent , but not ◆ G-consistent, with respect to its accompanying graph. J From Propositions 2 and 4 (or 1 and 3) we obtain the following result: ICorollary 1. We have that ◆∪ G-consistency is strictly stronger than N◆ G-consistency. Finally, to complete our strentgh-based hierarchy we close off with some results that involve the non-singleton-style consistencies G-consistency and ←− G-consistency. IProposition 6. We have that N◆ G-consistency is strictly stronger than G-consistency. Proof. Consider the QCN depicted in Figure 14 in [ 36 ], which was used to prove that - consistency cannot decide the minimality of a QCN in general. It is the case that the QCN is G-consistent , but not N ◆ G-consistent , with respect to the complete graph on the set of variables of that QCN . Notably, applying N ◆ G-consistency on that QCN makes it minimal. Additionally, by definition of N ◆ G-consistency , we have that every N ◆ G-consistent QCN is G-consistent. J
M. Sioutis, A. Paparrizou, and T. Janhunen 14:9 ◆∪ G N◆∪ G ◆ G N◆ G G ←− G Figure 4 A strength-based hierarchy of consistencies for QCN s; an arrow denotes the (transitive) strictly stronger relationship and a dotted line the (symmetric) incomparable relationship. Algorithm 1 PSWC∪ N(N, G). in : AQCN N= (V, C), and a graph G= (V0⊆V, E). out : A sub-QCN of N. 1begin 2N ← G(N); 3Q←list(E); 4while Q6=∅do 5{v, v0} ← Q.pop(); 6(V, C0)← ⊥V; 7foreach b∈C(v, v0)do 8(V, C0)←(V, C0)∪ GN(vv0)(N[v,v0]/{b}); 9if (V, C0)⊂ N then 10 flag ←False; 11 foreach {u, u0} ∈ Edo 12 if C0(u, u0)⊂C(u, u0)then 13 C(u, u0)←C0(u, u0); 14 C(u0, u)←C0(u0, u); 15 flag ←True; 16 if flag then Q←list(E); 17 return N; From Propositions 1, 2, 3, 4, and 6 we obtain the following result: ICorollary 2. We have that each of the consistencies of ◆∪ G-consistency ,N ◆∪ G-consistency , ◆ G-consistency, and N◆ G-consistency is strictly stronger than G-consistency. From [40] we have the following result: IProposition 7 ([ 40 ]) . We have that G-consistency is strictly stronger than ←− G -consistency. From Corollary 2 and Proposition 7 we obtain the following last result: ICorollary 3. We have that each of the consistencies of ◆∪ G-consistency ,N ◆∪ G-consistency , ◆ G-consistency, N◆ G-consistency, and G-consistency is strictly stronger than ←− G-consistency. A visual representation of the established strength-based hierarchy of consistencies is shown in Figure 4. TIME 2019
14:16 Neighbourhood Singleton-Style Consistencies for QSTR References 1 James F. Allen. Maintaining Knowledge about Temporal Intervals. Commun. ACM, 26:832–843, 1983. 2 Nouhad Amaneddine, Jean-François Condotta, and Michael Sioutis. Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints. In IJCAI, 2013. 3 Amine Balafrej, Christian Bessiere, El-Houssine Bouyakhf, and Gilles Trombettoni. Adaptive Singleton-Based Consistencies. In AAAI, 2014. 4 Albert-László Barabási and Réka Albert. Emergence of Scaling in Random Networks. Science, 286:509–512, 1999. 5 Hachemi Bennaceur and Mohamed-Salah Affane. Partition-k-AC: An Efficient Filtering Technique Combining Domain Partition and Arc Consistency. In CP, 2001. 6 Mehul Bhatt, Hans Guesgen, Stefan Wölfl, and Shyamanta Hazarika. Qualitative Spatial and Temporal Reasoning: Emerging Applications, Trends, and Directions. Spatial Cognition & Computation, 11:1–14, 2011. 7 Mehul Bhatt and Jan Oliver Wallgrün. Geospatial Narratives and Their Spatio-Temporal Dynamics: Commonsense Reasoning for High-Level Analyses in Geographic Information Systems. ISPRS Int. J. Geo-Information, 3:166–205, 2014. 8 Manuel Bodirsky, Peter Jonsson, Barnaby Martin, and Antoine Mottet. Classification Transfer for Qualitative Reasoning Problems. In IJCAI, 2018. 9 Manuel Bodirsky and Stefan Wölfl. RCC8 is polynomial on networks of bounded treewidth. In IJCAI, 2011. 10 Assef Chmeiss and Jean-François Condotta. Consistency of Triangulated Temporal Qualitative Constraint Networks. In ICTAI, 2011. 11 Jean-François Condotta and Christophe Lecoutre. A Class of f -Consistencies for Qualitative Constraint Networks. In KR, 2010. 12 Romuald Debruyne and Christian Bessière. Some Practicable Filtering Techniques for the Constraint Satisfaction Problem. In IJCAI, 1997. 13 Rina Dechter, Itay Meiri, and Judea Pearl. Temporal Constraint Networks. Artif. Intell., 49:61–95, 1991. 14 Rina Dechter and Judea Pearl. Network-Based Heuristics for Constraint-Satisfaction Problems. Artif. Intell., 34:1–38, 1987. 15 Krishna Sandeep Reddy Dubba, Anthony G. Cohn, David C. Hogg, Mehul Bhatt, and Frank Dylla. Learning Relational Event Models from Video. J. Artif. Intell. Res., 53:41–90, 2015. 16 Frank Dylla, Jae Hee Lee, Till Mossakowski, Thomas Schneider, André van Delden, Jasper van de Ven, and Diedrich Wolter. A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties. ACM Comput. Surv., 50:7:1–7:39, 2017. 17 Frank Dylla, Till Mossakowski, Thomas Schneider, and Diedrich Wolter. Algebraic Properties of Qualitative Spatio-Temporal Calculi. In COSIT, 2013. 18 Frank Dylla and Jan Oliver Wallgrün. Qualitative Spatial Reasoning with Conceptual Neighborhoods for Agent Control. J. Intell. Robotic Syst., 48:55–78, 2007. 19 Alfonso Gerevini and Alessandro Saetti. Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure. Artif. Intell., 175:556–585, 2011. 20 Martin Charles Golumbic and Ron Shamir. Complexity and Algorithms for Reasoning about Time: A Graph-Theoretic Approach. J. ACM, 40:1108–1133, 1993. 21 Georg Gottlob. On minimal constraint networks. Artif. Intell., 191-192:42–60, 2012. 22 Jinbo Huang. Compactness and Its Implications for Qualitative Spatial and Temporal Reasoning. In KR, 2012. 23 Jinbo Huang, Jason Jingshi Li, and Jochen Renz. Decomposition and tractability in qualitative spatial and temporal reasoning. Artif. Intell., 195:140–164, 2013. 24 Peter Jonsson and Victor Lagerkvist. Why are CSPs Based on Partition Schemes Computationally Hard? In MFCS, 2018.
M. Sioutis, A. Paparrizou, and T. Janhunen 14:17 25 Nikhil Krishnaswamy, Scott Friedman, and James Pustejovsky. Combining Deep Learning and Qualitative Spatial Reasoning to Learn Complex Structures from Sparse Examples with Noise. In AAAI, 2019. 26 Olivier Lhomme. Quick Shaving. In AAAI, 2005. 27 Jason Jingshi Li, Jinbo Huang, and Jochen Renz. A divide-and-conquer approach for solving interval algebra networks. In IJCAI, 2009. 28 Gérard Ligozat. Qualitative Spatial and Temporal Reasoning. Wiley, 2013. 29 Gérard Ligozat and Jochen Renz. What Is a Qualitative Calculus? A General Framework. In PRICAI, 2004. 30 Weiming Liu and Sanjiang Li. Solving Minimal Constraint Networks in Qualitative Spatial and Temporal Reasoning. In CP, 2012. 31 Ugo Montanari. Networks of constraints: Fundamental properties and applications to picture processing. Inf. Sci., 7:95–132, 1974. 32 Bernhard Nebel. Solving Hard Qualitative Temporal Reasoning Problems: Evaluating the Efficiency of Using the ORD-Horn Class. Constraints, 1:175–190, 1997. 33 Anastasia Paparrizou and Kostas Stergiou. On Neighborhood Singleton Consistencies. In IJCAI, 2017. 34 David A. Randell, Zhan Cui, and Anthony Cohn. A Spatial Logic Based on Regions & Connection. In KR, 1992. 35 Jochen Renz and Gérard Ligozat. Weak Composition for Qualitative Spatial and Temporal Reasoning. In CP, 2005. 36 Jochen Renz and Bernhard Nebel. On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus. Artif. Intell., 108:69–123, 1999. 37 Jochen Renz and Bernhard Nebel. Qualitative Spatial Reasoning Using Constraint Calculi. In Handbook of Spatial Logics, pages 161–215. Springer, 2007. 38 Michael Sioutis, Jean-François Condotta, and Manolis Koubarakis. An Efficient Approach for Tackling Large Real World Qualitative Spatial Networks. Int. J. Artif. Intell. Tools, 25:1–33, 2016. 39 Michael Sioutis, Zhiguo Long, and Sanjiang Li. Efficiently Reasoning about Qualitative Constraints through Variable Elimination. In SETN, 2016. 40 Michael Sioutis, Zhiguo Long, and Sanjiang Li. Leveraging Variable Elimination for Efficiently Reasoning about Qualitative Constraints. Int. J. Artif. Intell. Tools, 27:1860001, 2018. 41 Michael Sioutis, Anastasia Paparrizou, and Jean-François Condotta. A Lazy Algorithm to Efficiently Approximate Singleton Path Consistency for Qualitative Constraint Networks. In ICTAI, 2017. 42 Michael Sioutis, Anastasia Paparrizou, and Jean-François Condotta. Collective Singleton-Based Consistency for Qualitative Constraint Networks. In TIME, 2017. 43 Michael Sioutis, Anastasia Paparrizou, and Jean-François Condotta. Collective SingletonBased Consistency for Qualitative Constraint Networks: Theory and Practice. Theor. Comput. Sci, 2019. In press. 44 Michael Sioutis, Yakoub Salhi, and Jean-François Condotta. Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning. Knowl. Eng. Rev., 32:e4, 2016. 45 Robert E. Tarjan and Mihalis Yannakakis. Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM J. Comput., 13:566–579, 1984. 46 Peter van Beek and Rina Dechter. On the Minimality and Decomposability of Row-Convex Constraint Networks. J. ACM, 42:543–561, 1995. 47 Richard J. Wallace. Neighbourhood SAC: Extensions and new algorithms. AI Commun., 29:249–268, 2016. TIME 2019