Abstract
We discuss a research roadmap for going beyond the state of the art in qualitative spatial and temporal reasoning (QSTR). Simply put, QSTR is a major field of study in Artificial Intelligence that abstracts from numerical quantities of space and time by using qualitative descriptions instead (e.g., precedes, contains, is left of); thus, it provides a concise framework that allows for rather inexpensive reasoning about entities located in space or time. Applications of QSTR can be found in a plethora of areas and domains such as smart environments, intelligent vehicles, and unmanned aircraft systems. Our discussion involves researching novel local consistencies in the aforementioned discipline, defining dynamic algorithms pertaining to these consistencies that can allow for efficient reasoning over changing spatio-temporal information, and leveraging the structures of the locally consistent related problems with regard to novel decomposability and theoretical tractability properties. Ultimately, we argue for pushing the envelope in QSTR via defining tools for tackling dynamic variants of the fundamental reasoning problems in this discipline, i.e., problems stated in terms of changing input data. Indeed, time is a continuous flow and spatial objects can change (e.g., in shape, size, or structure) as time passes; therefore, it is pertinent to be able to efficiently reason about dynamic spatio-temporal data. Finally, these tools are to be integrated into the larger context of highly active areas such as neuro-symbolic learning and reasoning, planning, data mining, and robotic applications. Our final goal is to inspire further discussion in the community about constraint-based QSTR in general, and the possible lines of future research that we outline here in particular.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Background and Motivation
Qualitative Spatial and Temporal Reasoning (QSTR) is a major field of study in Artificial Intelligence, and in particular in Knowledge Representation and Reasoning, that deals with the fundamental cognitive concepts of space and time in an abstract, qualitative, manner, and ranges from theoretical computer science, mathematics, and logic to practical algorithms and applications [58]. In a sense, this approach is in line with the qualitative abstractions of spatial and temporal aspects of the common-sense background knowledge on which the human perspective of physical reality is based. 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. More formally, QSTR restricts the vocabulary of rich mathematical theories that deal with spatial and temporal entities to simple qualitative constraint languages. Thus, QSTR provides a concise framework that allows for rather inexpensive reasoning about entities located in 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 [12], cognitive robotics [37], deep learning [54], spatio-temporal design [88], qualitative model generation from video [34], ambient intelligence [8, 77], visual explanation [91] and sensemaking [90], semantic question-answering [89], qualitative simulation [26], and spatio-temporal data mining [52, 53, 65]. The interested reader may look into a more comprehensive review of the emerging applications, the trends, and the future directions of QSTR in [9, 43]. In addition, a detailed survey of qualitative spatial and temporal calculi appears in [35].
As an illustration, the first constraint language to deal with time in a qualitative manner was proposed by Allen in [2], called Interval Algebra. Allen wanted to define a framework for reasoning about time in the context of natural language processing that would be reliable and efficient enough for reasoning about temporal information in a qualitative manner. In particular, Interval Algebra uses intervals on the timeline to represent entities corresponding to actions, events, or tasks. Interval Algebra has become one of the most well-known qualitative constraint languages, due to its use for representing and reasoning about temporal information in various applications. Specifically, typical applications of Interval Algebra involve planning and scheduling [3, 4, 33, 66, 68], natural language processing [32, 86], temporal databases [20, 85], multimedia databases [60], molecular biology [42] (e.g., arrangement of DNA segments/intervals along a linear chain involves particular temporal-like problems [7]), and workflow [62].
As another illustration, inspired by the success of Interval Algebra, Randell et al. developed the Region Connection Calculus (\(\mathsf {RCC}\)) in [70], which studies the different relations that can be defined between regions in some topological space; these relations are based on the primitive relation of connection. For example, the relation disconnected between two regions x and y suggests that none of the points of region x connects with a point of region y, and vice versa. Two fragments of \(\mathsf {RCC}\), namely, \(\mathsf {RCC}\)-8 and \(\mathsf {RCC}\)-5 (a sublanguage of \(\mathsf {RCC}\)-8 where no significance is attached to boundaries of regions), have been used in several real-life applications. In particular, Bouzy in [16] used \(\mathsf {RCC}\)-8 in programming the Go game, Lattner et al. in [55] used \(\mathsf {RCC}\)-5 to set up assistance systems in intelligent vehicles, Heintz et al. in [44] used \(\mathsf {RCC}\)-8 in the domain of autonomous unmanned aircraft systems (UAS), and Randell et al. in [71] used a particular discrete domain counterpart of \(\mathsf {RCC}\)-8 (called discrete meterotopology) to correct segmentation errors for images of hematoxylin and eosin (H&E)-stained human carcinoma cell line cultures. Other typical applications of \(\mathsf {RCC}\) involve robot navigation [38, 39, 74], computer vision [87], and natural language processing [50, 51].
Real-world problems involving spatio-temporal information are rarely stated in the form of fixed input data. Since time is a continuous flow, it is natural that spatial objects may change (e.g., in shape, size, or structure) as time passes; in some cases, even new objects may manifest themselves as time passes [11]. Consider the case of tree shadows as an example, which are known to cause unnecessary or overly cautious braking in self-driving vehicles that could pose crash risks in heavy traffic.Footnote 1 This problem is due to the fact that the machine learning techniques that are used in the vehicles often confuse shadows with some kind of obstacle (cf. [1] where shadows are classified as water). Therefore, it is necessary to be able to ameliorate the performance of these techniques with just-in-time qualitative spatio-temporal reasoning, which will act as a referee upon the output of the classifier. In this particular example, we can use the spatial and temporal properties related to the context at hand (e.g., height of the tree, date and time, weather, and topology) to deduce that a tall tree that is connected to the road casts a shadow in a given day that overlaps the road.
1.1 Contribution
In this paper, we are concerned with constraint-based frameworks for Qualitative Spatial and Temporal Reasoning (QSTR) [35, 73], and specifically with frameworks that concern local consistencies, reasoning algorithms, and decomposability and theoretical tractability properties for the fundamental reasoning problems associated with this research area (to be detailed in the next section).
In what follows, we begin our contribution by describing a research roadmap for going beyond the state of the art in QSTR in the aforementioned context, and emphasize the need of having tools for tackling dynamic variants of foundational reasoning tasks, such as the satisfiability checking of spatial and temporal formulas. Further, we briefly describe how such tools could find use in highly active areas such as neuro-symbolic learning and reasoning, planning, data mining, and robotic applications. As an example, classical verification is not applicable to neural network-based components, but only runtime verification can be applied [92]; so, given a spatio-temporal model describing a computational system, its working environment, and interactions between the computational system and the working environment, runtime verification is applied to check whether actions proposed by the computational system are admissible with respect to the model. The pertinence of the roadmap is established by overviewing the state of the art in constraint-based QSTR, and bringing forward certain shortcomings that have to do with the static nature of the related approaches and/or their inability to combinedly exploit both the semantics of the relations and the graph structures of the constraint networks that appear in QSTR.
As per the subtitle of this paper, the ultimate goal is to inspire further discussion in the community about constraint-based QSTR in general, and the possible lines of future research that we outline here in particular.
2 Purpose and Aims
On a concrete technical level, within the discussed roadmap we propose to research novel local consistencies for Qualitative Spatial and Temporal Reasoning (QSTR), with an emphasis on defining dynamic algorithms pertaining to these consistencies (such as constraint propagators) that can allow for efficient and flexible handling of changing spatio-temporal information by means of real-time computing and just-in-time inference. Notably, the state of the art in QSTR lacks such dynamic algorithms (more to follow in Sects. 3 and 4) and, hence, falls short of being practical for highly active applications [77]. In addition, we suggest to exploit the structures of spatio-temporal problems upon which the new consistencies are to be applied, with regard to obtaining new decomposability and theoretical tractability properties in particular.
Long-term ambition. On a broader level, we motivate the need to showcase the impact of the focused technical work by reaching out to and seeking to integrate it into areas that can provably benefit from just-in-time qualitative spatio-temporal reasoning.
In particural, we can mention the area of neuro-symbolic learning and reasoning, which seeks to integrate principles from connectionist learning and logical, symbolic, reasoning [27].Footnote 2 The need for qualitative spatio-temporal reasoning in that context has been demonstrated recently by the IJCAI Workshop on Learning and Reasoning: Principles and Applications to Everyday Spatial and Temporal Knowledge,Footnote 3 but also in recent related works [1, 54].
Another relevant area involves spatio-temporal planning, i.e., planning that will take into account the physical location of a system or a system component in the environment over time. An example of how qualitative spatio-temporal reasoning is applicable in that area was already provided in Sect. 1, viz., the case of the self-driving vehicle reasoning about shadows, but the overall importance of reasoning about space and time in planning is also demonstrated by recent research projects in the AI community.Footnote 4
Further, the aforementioned areas naturally extend to robotic applications, as a next-generation robot would ideally perform spatio-temporally enhanced neuro-symbolic learning and reasoning to make sense of the heterogeneous input that it receives, and spatio-temporal planning to be able to efficiently carry out its tasks.
Finally, another application area is that of spatio-temporal data mining (cf. [52, 53] where temporal relations are taken into account). Let us consider a sensorized environment, such as a hospital. As sensory events are triggered, new spatial and temporal relations occur that have to be taken into account and integrated into a spatio-temporal knowledge base. In addition, these spatial or temporal relations might be repetitive and, hence, constitute a pattern, or might be entirely new and, hence, potentially break a pattern. In either case, spatio-temporal patterns must be identified in order to be accounted for and assess whether some critical condition is met (e.g., gradual loss of spatial orientation of a patient over time). Due to its conciseness, the proposed qualitative approach may facilitate spatio-temporal pattern recognition algorithms and additionally enable such recognition at run time.
In what follows, we will go into the underlying fundamental reasoning problems and technical research directions that are associated with the goal of just-in-time qualitative spatio-temporal reasoning that we discuss in this paper, and that will serve as the platform for accomplishing the ambition of broadening the scope of qualitative spatio-temporal reasoning to the highly active international contexts mentioned earlier.
2.1 Preliminaries
To facilitate discussion, we first recall the notion of a qualitative calculus, which is a constraint language that is used to represent and reason about qualitative information, and is based on a finite set \({\mathsf {B}}\) of jointly exhaustive and pairwise disjoint binary relations defined over an infinite domain \({\mathsf {D}}\) (such as a topological space or the real line), called the set of atoms [59]. Furthermore, this set contains the identity atom \(\mathsf {Id}\), and is closed under the converse operation [59]. A subset of \({\mathsf {B}}\) (item of \({2^{\mathsf {B}}}\)) denotes a relation encoding possible atoms, only one of which may hold between two entities. Hence, \(2^{{\mathsf {B}}}\) represents the total set of spatial or temporal relations.
As an illustration, consider the well-known qualitative temporal constraint language of Interval Algebra, introduced by Allen in [2]. The domain \({\mathsf {D}}\) of Interval Algebra is defined to be the set of intervals on the line of rational numbers, i.e., \({\mathsf {D}}\) \(=\) \(\{x=(x^-, x^+) \in \mathbb {Q}\times \mathbb {Q}~|~x^-<x^+\}\). Each base relation can be defined by appropriately constraining the endpoints of the two intervals at hand, which yields a total of 13 base relations comprising the set \({\mathsf {B}}=\{e\), p, pi, m, mi, o, oi, s, si, d, di, f, \(fi\}\); these symbols are explained in the caption of Fig. 1. For example, d, viz., during, is defined as d \(=\) \(\{(x,y)\in {{\mathsf {D}}\times {{\mathsf {D}}}}~|~x^->y^-~\text {and}~x^+<y^+\}\).
Qualitative spatial or temporal information of a qualitative calculus can be typically modeled as a Qualitative Constraint Network (\(\mathsf {QCN}\)), which is defined as follows:
Definition 1
A qualitative constraint network (\(\mathsf {QCN}\)) is a tuple (V, C) where:
-
V \(=\) \(\{v_1,\) \(\ldots ,\) \(v_n\}\) is a non-empty finite set of variables, each representing an entity of an infinite domain \({\mathsf {D}}\);
-
and C is a mapping \(C:V\times {V}\rightarrow {2^{\mathsf {B}}}\) such that \(C(v,v) = \{\mathsf {Id}\}\) for all \(v \in V\), and \(C(v,v^\prime )=(C(v^\prime ,v))^{-1}\) for all \(v,v^\prime \in V\).
An example of a \(\mathsf {QCN}\) is shown in Fig. 1a (e.g., interval \(x_1\) can either precede or meet interval \(x_2\)); for simplicity, self-loops corresponding to relation \(\{\mathsf {Id}\}\), and converse relations, are not depicted.
2.2 Fundamental Reasoning Tasks
Given a \(\mathsf {QCN}\) \(\mathcal {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 \(\mathcal {N}\) that satisfies its constraints, such an interpretation being called a solution of \(\mathcal {N}\) (an example of a solution for a \(\mathsf {QCN}\) of Interval Algebra is shown in Fig. 1b). Other fundamental reasoning problems include the minimal labelling (or deductive closure) problem and the redundancy problem [73]. The minimal labelling problem is the problem of finding the strongest implied constraints of \(\mathcal {N}\), i.e., finding the atoms in each constraint that are present in a scenario (or satisfiable atomic refinement) of \(\mathcal {N}\) (see Fig. 1c for the notion of a scenario), and the redundancy problem is the problem of determining if a given constraint in \(\mathcal {N}\) is entailed by the rest of \(\mathcal {N}\) (that constraint being called redundant, as its removal does not change the solution set of the \(\mathsf {QCN}\)). In general, for most widely adopted qualitative constraint languages the satisfiability problem is \(\mathcal {NP}\)-complete [36]. Further, the redundancy problem, the minimal labelling problem, and the satisfiability problem are equivalent under polynomial Turing reductions [42]. Finally, a variant of the satisfiability problem that concerns an over-constrained \(\mathsf {QCN}\), is the problem of obtaining a spatial or temporal configuration that maximizes the number of satisfied constraints in that \(\mathsf {QCN}\); this problem is called the \(\mathsf {MAX}\)-\(\mathsf {QCN}\) problem and was recently introduced in [22]. The motivation behind studying the \(\mathsf {MAX}\)-\(\mathsf {QCN}\) problem lies in the fact that representing spatial or temporal information may inevitably lead to inconsistencies due to, for example, human error or contradictory data of different sources.
2.3 Technical Research Directions
Coming back to the discussion about the purpose and the ambition of the proposed roadmap, we argue for pushing the envelope in QSTR by providing novel and efficient methods for tackling the aforementioned fundamental reasoning problems, but also—and most importantly—for tackling dynamic variants thereof, i.e., problems stated in terms of changing input data. To this end, we propose to:
-
theoretically and experimentally explore new local consistencies for \(\mathsf {QCN}\)s and, in particular, local consistencies that rely mainly upon singleton checks, i.e., constraint checks involving a temporary assignment of a singleton relation (defined by an atom) to the constraint at hand (for example, all the constraints in Fig. 1c are defined by singleton relations), and that utilize the neighbourhood of the constrained variables to propagate themselves, similarly to ongoing research in traditional constraint programming (which considers finite domains and, hence, different propagation techniques) [67, 95];
-
define efficient algorithms pertaining to the novel consistencies, emphasizing on their dynamicity, which will enable these algorithms to be readily available for time-critical applications and dynamic systems that are subject to uncertainty and perturbation of the input data; furthermore, as existing state-of-the-art algorithms for enforcing or utilizing (e.g., for search) current local consistencies are static in nature (see [61, 76, 78, 80,81,82]), i.e., they operate on fixed input data (this will be stressed again in more detail in Sect. 4), it is imperative to provide dynamic variants of those algorithms as well and, consequently, fill this research void, which has occurred due to rapid advances over the past few years missing out on that aspect;
-
leverage the structure of the constraint graphs of the studied \(\mathsf {QCN}\)s in an effort to obtain new decomposability and theoretical tractability properties; specifically, do research on structural and microstructural in particular (a concept that is yet to be studied in the context of infinite domains, cf. [23, 47]) properties for \(\mathsf {QCN}\)s, similar to backbones and backdoors [64, 97] or broken triangles [24] in traditional constraint programming for example, that could allow for exploiting even further the use of tree decompositions in QSTR [46, 84] and enable parallelization in a fruitful manner as a consequence (cf. [84]).
In summary, the aim on a concrete technical level is to theoretically establish new techniques to efficiently handle qualitative spatial and temporal information in a dynamic setting, but also to develop readily available tools for putting these techniques into practice in the way that was described in the discussion about the long-term ambition earlier. The consisely aforementioned research directions are to be viewed alongside and compared with the state of the art, discussed in Sect. 3, the significance and the scientific novelty that they bring along, discussed in Sect. 4, and the foreseen extensions to other disciplines, presented in Sect. 5.
2.4 Theory and method
In order for the goals that were specified earlier to be reached, in what follows we describe the related theory and methods that should be considered for carrying out the roadmap and achieving its objectives.
Regarding the theory, most of it can be drawn directly from the field of Qualitative Spatial and Temporal Reasoning [35, 58], which is concerned with symbolic knowledge representation over infinite domains; however, it is important to stress here that the—very pertinent—model-theoretic aspect of QSTR should be leveraged in order to boost research [14]. In particular, and as it is pointed out in [14], research in qualitative constraint-based reasoning has concurrently been performed within the AI community and the theoretical computer science (TCS) community for many years, but, unfortunately, collaboration and cross-fertilisation between the communities have been rare. This has led to a number of serious problems such as diverging terminology, rediscoveries of known results, and an ignorance of available methods and concepts. Regarding the methodology, constraint-based methods are to be used to structure the frameworks and describe the proposed techniques, since this paradigm is of course the focus of this paper but has also been shown to give rise to highly efficient reasoning techniques [73], and logic-based methods are to be employed to prove the soundness and completeness of the related contributions. Regarding constraint-based methods in particular, a first immediate step would be to look into counting-based techniques to devise strategies for the choice of atoms, or sub-relations, in the new algorithms [69]. Specifically, as currently the selection of atoms, or sub-relations, either during search or in a method for enforcing some local consistency is based on static weights [96, Section 5] (e.g., in Interval Algebra the atom e is assigned a static weight of, say, 1, to state that it is more restrictive than other atoms, for example, atom o, which is assigned another static weight of, say, 4 [93, Figure 9]), the constraints in which a given atom participates should be exploited from a local model counting perspective. For instance, given a \(\mathsf {QCN}\) (V, C) and a constraint C(i, j) with i, \(j \in V\), one could count how many times a given atom b \(\in \) C(i, j) participates in the local “models” (viz., local scenarios) of each triangle that involves variables i, j, and \(k \in V\) when \(i \not = k\) and \(k \not = j\); then, depending on how aggressive or flexible the reasoning mechanism needs to be, the appropriate atom can be chosen. Further down the line, it would be interesting to couple such methodologies with other paradigms, such as answer set programming (some discussion follows in Sect. 5).
3 State of the Art
In the context of Qualitative Spatial and Temporal Reasoning (QSTR), and with regard to local consistencies and algorithms for enforcing them in particular, the state of the art has been established by the main author and close collaborators in the published works of [61, 76, 78, 80,81,82].Footnote 5 We will briefly go over these key references in what follows.
In [76, 80] the authors propose a new local consistency (at that time) in the context of qualitative constraint-based reasoning that serves as the counterpart of directional path consistency in traditional constraint programming [31] or quantitative temporal reasoning [30], 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 directional partial closure under weak composition and is denoted by \(^{\overleftarrow{\diamond }}_{G}\)-consistency. In particular, \(^{\overleftarrow{\diamond }}_{G}\)-consistency entails consistency for all ordered triples of variables of a \(\mathsf {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 \(\mathsf {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 in what follows.
Definition 2
A \(\mathsf {QCN}\) \(\mathcal {N}= (V,C)\) is \(^{\overleftarrow{\diamond }}_{G}\)-consistent with respect to a graph \(G=(V,E)\) and an ordering \((\alpha ^{-1}(0)\),\(\alpha ^{-1}(1)\),\(\ldots \),\(\alpha ^{-1}(n-1))\) defined by a bijection \(\alpha \) : V \(\rightarrow \) \(\{0,1,\ldots ,n-1\}\) iff for all \(v_i,v_j,v_k\in V\) such that \(\{v_k,v_i\},\{v_k,v_j\}\), \(\{v_i,v_j\}\) \(\in \) E and \(\alpha (v_i),\alpha (v_j) < \alpha (v_k)\) we have that \(C(v_i,v_j)\) \(\subseteq \) \(C(v_i,v_k)\) \(\diamond \) \(C(v_k,v_j)\), where symbol \(\diamond \) denotes the weak composition operation [59].
The authors then proceed to prove that \(^{\overleftarrow{\diamond }}_{G}\)-consistency solves the satisfiability problem for a certain subset of qualitative relations, called a distributive class of relations. This work is further extended in [81] to include more theoretical and practical results concerning other fundamental reasoning problems as well, such as the problem of scenario extraction from a satisfiable \(\mathsf {QCN}\) (where a scenario is defined to be a satisfiable atomic refined \(\mathsf {QCN}\), see also Fig. 1c).
Then, in [61] the authors show how \(^{\overleftarrow{\diamond }}_{G}\)-consistency can be used to efficiently achieve \(^\diamond _{G}\text{-consistency }\) for a given \(\mathsf {QCN}\) that is defined over a distributive class of relations, which is a stronger local consistency with implications in the problems of minimal labelling and redundancy. Specifically, \(^\diamond _{G}\text{-consistency }\) can be seen as \(^{\overleftarrow{\diamond }}_{G}\)-consistency where the notion of ordered triples of variables is not taken into account, i.e., \(^\diamond _{G}\text{-consistency }\) entails consistency for all triples of variables of a \(\mathsf {QCN}\) that correspond to triangles of a given graph G. We recall the formal definition of that consistency in what follows.
Definition 3
A \(\mathsf {QCN}\) \({\mathcal N}=(V,C)\) is \(^\diamond _{G}\text{-consistent }\) with respect to a graph G \(=\) (V, E) iff \(\forall \{v_i,v_j\},\) \(\{v_i,v_k\}, \{v_k,v_j\} \in E\) we have that \(C(v_i,v_j) \subseteq C(v_i,v_k) \diamond C(v_k,v_j)\).
In [78] the authors build upon the work of [61] and demonstrate how \(^{\overleftarrow{\diamond }}_{G}\)-consistency can be used to efficiently achieve \(^\diamond _{G}\text{-consistency }\) for any given \(\mathsf {QCN}\) and not just for a \(\mathsf {QCN}\) defined over a distributive class of relations. To this end, they exploit the notion of abstraction for \(\mathsf {QCN}\)s, which is an idea adopted from concepts of abstract interpretation [25]. In particular, a \(\mathsf {QCN}\) is typically abstracted by relaxing some of its constraints in order to satisfy some defined property.
Finally, in [82] the authors define a singleton check-based local consistency that is strictly stronger than any of the local consistencies known to date, called collective partial singleton check-based closure under weak composition and denoted by . This new singleton-style consistency is inspired by k-partitioning consistency for constraint satisfaction problems (\(\mathsf {CSP}\)s) [6]. We recall the formal definition of that consistency in what follows.
Definition 4
A \(\mathsf {QCN}\) \({\mathcal N}=(V,C)\) is with respect to a graph G \(=\) (V, E) iff \(\forall \{v,v^\prime \} \in E\), \(\forall b \in C(v,v^\prime )\), and \(\forall \{u,u^\prime \}\in E\) we have that \(\exists b^\prime \in C(u,u^\prime )\) such that \(b \in C^\prime (v,v^\prime )\), where \((V,C^\prime ) = {^\diamond _{G}}({\mathcal N}_{[u,u^\prime ]/\{b^\prime \}})\), and where \({^\diamond _{G}}(\varvec{\cdot })\) is the closure of \(\varvec{\cdot }\) under \(^\diamond _{G}\text{-consistency }\).
A motivating example of the application of is shown in Fig. 2. As noted in [82] this local consistency can be essential for approximating satisfiability of \(\mathsf {QCN}\)s and can play a crucial role in tackling the minimal labelling problem of a \(\mathsf {QCN}\) in particular, as it is both strictly stronger and more efficient to enforce than the consistency that had been utilized until that time to tackle the aforementioned problems, viz., [5] (which can be seen as a counterpart for \(\mathsf {QCN}\)s of singleton arc consistency [29] for \(\mathsf {CSP}\)s in traditional constraint programming). Notably, the exact behaviour of in the context of those problems has been thoroughly experimentally studied in [83].
As it was stressed earlier, and will be stressed again later on, the state-of-the-art algorithms for enforcing or utilizing (e.g., for search) the aforementioned consistencies are designed to operate on fixed input data and lack any dynamicity. However, there has been a recent effort in defining decremental algorithms for some special cases of point-based calculi, viz., Point Algebra and the ORD-Horn sub-calculus of Interval Algebra, in regard to the satisfiability problem in particular [15]; it should be noted that we propose to have dynamic algorithms that will be generic, i.e., not dependent on the characteristics of the domain of a given qualitative constraint language, but rather on its algebraic properties.
Definition 5
Let \(\mathcal {N} = (V,C)\) be a \(\mathsf {QCN}\), then a partitioning of \(\mathcal {N}\) is a \(\mathsf {QCN}\) \(\mathcal {N}_p\) \(=\) \((\{\mathcal {N}_1,\ldots ,\mathcal {N}_n\}\), \(C_p)\), where variables \(\mathcal {N}_1,\ldots ,\mathcal {N}_n\) correspond to \(\mathsf {QCN}\)s \((V_1,C_1)\), \(\ldots \), \((V_n,C_n)\) respectively, such that:
-
\(V_i \subseteq V\) for every \(i \in \{1,\ldots ,n\}\).
-
\(V = \bigcup ^n_{i=1} V_i\) and \(V_i,\ldots ,V_n\) are pairwise disjoint.
-
For every \(u,v \in V\), we have that \(C_i(u,v) = C(u,v)\) for some \(i \in \{1,\ldots ,n\}\), or \(u \in V_i\), \(v \in V_j\), and \(C_p(\mathcal {N}_i,\mathcal {N}_j) \subseteq C(u,v)\) for some \(i,j \in \{1,\ldots ,n\}\) with \(i\ne {j}\).
-
\(\mathcal {N}_p\) is satisfiable.
With regard to structural properties of the constraint graphs of the studied \(\mathsf {QCN}\)s that can be leveraged to boost efficiency of the reasoning process, to the best of our knowledge there does not exist any practical published research besides the works that utilize tree decompositions for \(\mathsf {QCN}\)s [46, 84]. The exploitation of tree decomposition became possible due to some generalized theoretical results of [45], which in turn build upon results relating to concrete domains for description logics; in particular, in [63] the authors identify the property of \(\omega \)-admissibility, which includes a patchwork property that grants satisfiability of a complete \(\mathsf {QCN}\), given that the \(\mathsf {QCN}\) can be decomposed into overlapping sub-\(\mathsf {QCN}\)s (patches) that are individually satisfiable and agree on their overlap. While the paper shows \(\omega \)-admissibility to hold for \(\mathsf {RCC}\)-8 and Allen’s Interval Algebra, the property does not hold for several other constraint languages. In a first step towards parallelization, Sioutis et al. in [84] go as far as identifying the biconnected components of the constraint graph of a given \(\mathsf {QCN}\) in order to acquire a particular tree decomposition where the nodes (corresponding to partitions of the original \(\mathsf {QCN}\)) can be solved independently of one another, in parallel. However, this approach is almost entirely graph-based and does not take into account the semantics of the relations of a \(\mathsf {QCN}\) (or, to be exact, it only exploits the fact that the identity relation can relate a spatial or temporal entity with itself, which is usually always the case for \(\mathsf {QCN}\)s). On the other hand, a purely relation-based decomposition technique appears in [19], where a \(\mathsf {QCN}\) is partitioned into smaller \(\mathsf {QCN}\)s based on a calculus-dependent set of partitioning relations, see Definition 5. Given a \(\mathsf {QCN}\) \(\mathcal {N} = (V,C)\), a partitioning \(\mathcal {N}_p\) \(=\) \((\{\mathcal {N}_1,\ldots ,\mathcal {N}_n\},C_p)\) of \(\mathcal {N}\) partitions the set of variables V of \(\mathcal {N}\) into exactly n sets, each of which is associated with a distinct node of \(\mathcal {N}_p\). Whenever two variables of \(\mathcal {N}\) reside in different nodes of \(\mathcal {N}_p\), the relation holding between the two nodes of \(\mathcal {N}_p\) is a subset of the relation holding between the two variables of \(\mathcal {N}\). In a sense, each node of \(\mathcal {N}_p\) forms a \(\mathsf {QCN}\) that has a subset of the set of variables of \(\mathcal {N}\) as its set of variables, and original relations between variables of \(\mathcal {N}\) as its set of relations. It was proven in [19] that if the set of relations of \(\mathcal {N}_p\) is sufficiently restricted, then the original network \(\mathcal {N}\) is satisfiable exactly when all the \(\mathsf {QCN}\)s \(\mathcal {N}_1\), \(\ldots \), \(\mathcal {N}_n\) that correspond to the nodes of \(\mathcal {N}_p\) are individually satisfiable. The relations of a given qualitative constraint language that satisfy this condition are called partitioning relations. For example, the set of relations \(\{\{DC\},\{PO\},\{DC,PO\}\}\) for \(\mathsf {RCC}\)-8 is a set of partitioning relations. Although the aforementioned technique is very elegant in its conception, it was noted in [19] that useful candidates of this kind of decomposition can be difficult to identify, especially when the size of the set of partitioning relations is small (as is the case with Interval Algebra and \(\mathsf {RCC}\)-8), thus deeming the technique impractical for efficient reasoning with qualitative constraint languages.
4 Significance and Scientific Novelty
The significance and scientific novelty of the proposed research roadmap can already be drawn from the various applications of Qualitative Spatial and Temporal Reasoning (QSTR) detailed in Sect. 1 and the research directions described in Sect. 2. Specifically, by now the reader should be able to assert that QSTR is an active application area within Artificial Intelligence (AI), spanning several decades of research, and that fundamental scientific advances in that discipline are well adopted and appreciated by the research community. Nevertheless, in this section we delve into the particulars of the proposed technical research directions to pinpoint exactly how the proposal can move forward and innovate the current research frontier.
With regard to the direction concerning local consistencies that rely upon singleton checks, we suggest to build upon the state-of-the-art local consistency of , presented in Sect. 3, and define weaker variants of it, thus enriching the family of consistencies for \(\mathsf {QCN}\)s. Specifically, the weaker variants could restrict singleton checks to the neighbourhood of the constraint in question. Early experiments in that direction have shown really promising results for constraint satisfaction problems (\(\mathsf {CSP}\)s) in traditional constraint programming [67, 95], which is due to the fact that constraint revisions tend to propagate themselves to just neighbouring constraints. In that respect, it would be interesting to seek a balance between the strong theoretical properties that offers, viz., that it is strictly stronger than any of the local consistencies known to date and can hence remove more unfeasible atoms in a given \(\mathsf {QCN}\) than those consistencies (see [82, Section 4]), and the efficiency that should characterize algorithms for enforcing weaker variants of it. In particular, it will be interesting to investigate how good of an approximation certain variants of can achieve in terms of pruning capability and consequent implications in the problems of satisfiability, minimal labelling, redundancy, and \(\mathsf {MAX}\)-\(\mathsf {QCN}\).
Studying local consistencies by itself makes for a solid line of research, but, all things considered, in the end a local consistency is only as good as the algorithm that enforces it. This brings us to the second research direction, that of defining efficient algorithms pertaining to the new local consistencies with an emphasis on their dynamicity. As a first step, for the state-of-the-art algorithm that enforces [82, Section 5], we propose to explore queuing strategies such that the singleton checks are applied in a more fruitful manner. In particular, it would make sense to prioritize certain singleton checks that are more likely to eliminate atoms anywhere in the network at hand, because this could unveil certain inconsistencies faster, but also lead to fewer constraint checks overall. Such strategies have been used to much success in the case of \(^\diamond _{G}\text{-consistency }\) [72, 93]. These queuing strategies could be employed for the algorithms that are to be designed to enforce the discussed weaker variants of as well. Furthermore, dynamic algorithms could be developed to accommodate real-time computing and just-in-time inference for efficient and flexible handling of incrementally (orx decrementally) available spatial and temporal information. For instance, let us consider the problem of qualitative spatio-temporal stream reasoning, i.e., the problem of incremental spatio-temporal reasoning over streams of information, studied in [28, 44]. This is an essential problem as, with the amount of data that is continuously produced, AI applications such as robotic systems are often tasked with reasoning about incrementally available information, and drawing relevant conclusions over such data flows and reacting to new situations with minimal delays is important. In both of those works, viz., [28, 44], the authors present approaches that rely upon the incremental functionality of the state-of-the-art algorithm at that time for enforcing \(^\diamond _{G}\text{-consistency }\), which is described in [40, Section 3]. Although there have have developed much more efficient algorithms for enforcing \(^\diamond _{G}\text{-consistency }\) in a given \(\mathsf {QCN}\) [61, 78] (see also the discussion in Sect. 3), such incremental functionality is not available in these algorithms for they are designed to operate on fixed input data; this is also the case for the state-of-the-art algorithms for enforcing or utilizing (e.g., for search) the rest of the consistencies detailed in Sect. 3, viz., \(^{\overleftarrow{\diamond }}_{G}\)-consistency and [76, 80,81,82]. Thus, obtaining dynamic variants of those algorithms is a critical task that needs to be resolved. This contribution will enable the community to tackle the dynamic variants of the fundamental reasoning tasks discussed in Sect. 2.
With respect to the third research direction, which involves the exploration of the structure of the constraint graphs of the studied \(\mathsf {QCN}\)s in an effort to obtain new decomposability and theoretical tractability properties, we could make the reasonable argument that too little has been done over the past years, as discussed in the previous section. Therefore, the field is open to lay new foundations in accordance with the purpose and aims detailed in Sect. 2. Specifically, we argue for prioritizing approaches that can be readily put into practice and adapted to dynamic settings, and that will involve a combination of both graph-based and relation-based techniques.
5 Relation to Other Disciplines
In this section we describe how Qualitative Spatial and Temporal Reasoning (QSTR) relates to other disciplines that are worth exploring.
5.1 Traditional Constraint Programming
As noted in Sect. 2, a qualitative constraint network (\(\mathsf {QCN}\)) is most efficiently modeled as an infinite-domain variant of a constraint satisfaction problem instance through the use of a set of jointly exhaustive and pairwise disjoint binary relations defined over some infinite domain [59]; this set is called a partition scheme, and it is therefore not unusual at all to view \(\mathsf {QCN}\)s as \(\mathsf {CSP}\) instances based on partition schemes [48]. However, a \(\mathsf {QCN}\) can even be encoded as a finite-domain constraint satisfaction problem instance [17, 21]. In particular, given a qualitative constraint network (V, C), where \(|V| = n\), we can obtain a constraint satisfaction problem instance as follows. Let X denote the set of variables containing a variable \(x_{ij}\) for each pair of variables \(v_i,v_j \in V\) with \(1 \le i < j \le n\). Then, our instance has the form \((X,{\mathsf {B}},DCon\cup {TCon})\), where DCon is the set of domain constraints \(\{(x_{ij},C(i,j))~|~1\le {i}<{j}\le {n}\}\) and TCon the set of ternary constraints \(\{((x_{ij},x_{ik},x_{kj}),R_\diamond )~|~1\le {i}<{j}<{k}\le {n}\}\) with \(R_\diamond = \{(b,b^\prime ,b^{\prime \prime }) \in {\mathsf {B}}^3~|~b\in {b^\prime \diamond {b^{\prime \prime }}}\}\). Namely, DCon restricts the values of a variable \(x_{ij}\) to the base relations of the corresponding qualitative constraint C(i, j) and TCon encodes all the consistent paths of length 2 that can exist in the network. The resulting finite-domain network has \(\frac{n(n-1)}{2}\) variables and \(\left( {\begin{array}{c}n\\ 3\end{array}}\right) \) ternary constraints. A solution of this finite instance corresponds to a scenario of a \(\mathsf {QCN}\), and vice versa [21]. The main disadvantage of this approach is that we are not able to make use of certain tractable subsets of qualitative relations. This can seriously impact the performance of satisfiability checking for qualitative constraint languages that heavily rely upon those subsets, such as \(\mathsf {RCC}\)-8 and Interval Algebra. However, for large-sized qualitative constraint languages (viz., where the partition scheme comprises hundreds of atoms) for which no tractable subsets are known, a finite-domain constraint satisfaction problem encoding can provide a considerable performance gain [96]. Nevertheless, in light of the strong relation that exists between qualitative and traditional constraint programming, it has often been the case that research in one paradigm inspired research in the other paradigm, and the other way around. For example, with respect to our own published research, the use of chordal graphs in \(\mathsf {CSP}\)s [13] influenced the use of them in QSTR as well [79], and the exploitation of a variable elimination property in QSTR [81] led to a similar contribution for \(\mathsf {CSP}\)s [49]; similar examples are available throughout the literature for the interested reader.
5.2 Answer Set Programming
Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily \(\mathcal {NP}\)-hard) search problems, and is based on the stable model (answer set) semantics of logic programming [57]. The elegance of this paradigm attracted various researchers in the QSTR community over the past years, who wanted to provide a declarative framework capable of representing and reasoning about high-level, qualitative spatio-temporal knowledge about the world [18, 56] (see also [10] in that regard). Recently, some researchers went even further and used answer set programming modulo theories (ASPMT), a framework of tight integration of answer set programming (ASP) and satisfiability modulo theories (SMT), to enhance QSTR with quantitative reasoning capabilities [75, 94]. Unfortunately, answer set programming does not scale well for \(\mathsf {QCN}\)s, at least with respect to the problem of satisfiability and when compared against native QSTR reasoners, as it is reported in [18, 56]. However, if we draw inspiration from the advances in the SAT community with respect to QSTR, where due to the usual blow-up and the lack of scalability in SAT-based encodings for \(\mathsf {QCN}\)s the researchers switched to collaborative approaches between SAT-based encodings and native QSTR model checkers [41], we can envision a similar collaborative approach between ASP tools and QSTR reasoners as well. In particular, with respect to the minimal labelling problem, we could think of an ASP tool providing stable models (scenarios) of an under-abstraction of a given \(\mathsf {QCN}\) (in other words, a \(\mathsf {QCN}\) that is typically easier to tackle due to restructuring its solution space) and letting a QSTR model checker act as a referee to accept or reject a scenario. By closing the loop, as in [41], and obtaining back-and-forth reasoning in a lazy setting, one could then, for instance, translate the decision of the QSTR model checker into useful information for the ASP tool (e.g., send back a no-good in the form of an illegal condition) and enhance its performance.
6 Conclusion
In this paper we discussed a research roadmap of what we think the next steps should be to go beyond the state of the art in Qualitative Spatial and Temporal Reasoning (QSTR). We made the case for researching novel local consistencies in the aforementioned discipline, defining dynamic algorithms pertaining to these consistencies that can allow for efficient reasoning over changing spatio-temporal information, and leveraging the structures of the locally consistent related problems with regard to novel decomposability and theoretical tractability properties. Ultimately, we argued for pushing the envelope in QSTR via defining tools for tackling dynamic variants of the fundamental reasoning problems in this discipline, i.e., problems stated in terms of changing input data, as it is very often and naturally the case that real-world problems are stated in terms of evolving spatio-temporal information. Therefore, it is pertinent to be able to reason just-in-time about dynamic spatio-temporal data. Finally, we described a long-term ambition of integrating the novel tools into the larger context of highly active areas such as neuro-symbolic learning and reasoning, planning, data mining, and robotic applications. Ultimately, we would like to inspire further discussion in the community about constraint-based QSTR in general, and the possible lines of future research that we outline here in particular.
Change history
30 September 2021
A Correction to this paper has been published: https://doi.org/10.1007/s13218-021-00742-6
Notes
Obviously, research in QSTR extends much further back in time and is not only concerned with constraint-based frameworks, but, to the best of our knowledge, this statement, which refers to the state of the art in local consistencies and algorithms for applying them on qualitative constraint networks, is accurate.
References
Alirezaie M, Längkvist M, Sioutis M, Loutfi A (2018) A symbolic approach for explaining errors in image classification tasks. In: IJCAI workshop on learning and reasoning: principles and applications to everyday spatial and temporal knowledge
Allen JF (1983) Maintaining knowledge about temporal intervals. Commun ACM 26:832–843
Allen JF (1991) Planning as temporal reasoning. In: KR
Allen JF, Koomen JAGM (1983) Planning using a temporal world model. In: IJCAI
Amaneddine N, Condotta J-F, Sioutis M (2013) Efficient approach to solve the minimal labeling problem of temporal and spatial qualitative constraints. In: IJCAI
Bennaceur H, Affane M-S (2001) Partition-k-AC: an efficient filtering technique combining domain partition and arc consistency. In: CP
Benzer S (1959) On the topology of the genetic fine structure. Proc Natl Acad Sci USA 45:1607–1620
Bhatt M, Dylla F, Hois J (2009) Spatio-terminological inference for the design of ambient environments. In: COSIT
Bhatt M, Guesgen H, Wölfl S, Hazarika S (2011) Qualitative spatial and temporal reasoning: emerging applications, trends, and directions. Spatial Cognit Comput 11:1–14
Bhatt M, Lee JH, Schultz Carl PL (2011) CLP(QS): a declarative spatial reasoning framework. In: COSIT
Bhatt M, Loke SW (2008) Modelling dynamic spatial systems in the situation calculus. Spatial Cognit Comput 8:86–130
Bhatt M, Wallgrün JO (2014) Geospatial narratives and their spatio-temporal dynamics: commonsense reasoning for high-level analyses in geographic information systems. ISPRS Int J Geo-Inf 3:166–205
Bliek C, Sam-Haroud D (1999) Path consistency on triangulated constraint graphs. In: IJCAI
Bodirsky M, Jonsson P (2017) A model-theoretic view on qualitative constraint reasoning. J Artif Intell Res 58:339–385
Bono M, Gerevini AEo (2018) Decremental consistency checking of temporal constraints: algorithms for the point algebra and the ord-horn class. In: CP
Bouzy B (2001) Les concepts spatiaux dans la programmation du go. Revue d’Intelligence Artificielle 15:143–172
Brand S (2004) Relation variables in qualitative spatial reasoning. In: KI
Brenton C, Faber W, Batsakis S (2016) Answer set programming for qualitative spatio-temporal reasoning: methods and experiments. In: ICLP
Broxvall M (2002) Constraint satisfaction on infinite domains: composing domains and decomposing constraints. In: KR
Chen CX, Zaniolo C (1998) Universal temporal data languages. In: DDLP
Condotta J-F, Dalmeida D, Lecoutre C, Sais L (2006) From qualitative to discrete constraint networks. In: KI Workshop on Qualitative Constraint Calculi
Condotta J-F, Mensi A, Nouaouri I, Sioutis M, Said LB (2015) A practical approach for maximizing satisfiability in qualitative spatial and temporal constraint networks. In: ICTAI
Cooper MC, Jégou P, Terrioux C (2015) A microstructure-based family of tractable classes for CSPs. In: CP
Cooper MC, Mouelhi A, Terrioux C, Zanuttini B (2016) On broken triangles. In: IJCAI
Cousot P, Cousot R (1992) Abstract interpretation frameworks. J Log. Comput 2:511–547
Cui Z, Cohn AG, Randell DA (1992) Qualitative simulation based on a logical formalism of space and time. In: AAAI
d’Avila Garcez Artur S., Besold Tarek R, De Raedt Luc, Földiak Peter, Hitzler Pascal, Icard Thomas, Kühnberger Kai-Uwe, Lamb Luís C, Miikkulainen Riisto, Silver Daniel L (2015) Neural-Symbolic Learning and Reasoning: Contributions and Challenges. In AAAI Spring Symposium on Knowledge Representation and Reasoning: Integrating Symbolic and Neural Approaches.
de Leng Daniel, Heintz Fredrik (2016) Qualitative Spatio-Temporal Stream Reasoning with Unobservable Intertemporal Spatial Relations Using Landmarks. In AAAI
Debruyne Romuald, Bessière Christian (1997) Some Practicable Filtering Techniques for the Constraint Satisfaction Problem. In IJCAI
Dechter R, Meiri I, Pearl J (1991) Temporal Constraint Networks. Artif Intell 49:61–95
Dechter R, Pearl J (1987) Network-Based Heuristics for Constraint-Satisfaction Problems. Artif Intell 34:1–38
Denis Pascal, Muller Philippe (2011) Predicting Globally-Coherent Temporal Structures from Texts via Endpoint Inference and Graph Decomposition. In IJCAI
Dorn J (1995) Dependable Reactive Event-Oriented Planning. Data Knowl Eng 16:27–49
Dubba KSR, Cohn AG, Hogg DC, Bhatt M, Dylla F (2015) Learning Relational Event Models from Video. J Artif Intell Res 53:41–90
Dylla F, Lee JH, Mossakowski T, Schneider T, van Delden A, van de Ven J, Wolter D (2017) A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties. ACM Comput Surv 50:7:1–7:39
Dylla Frank, Mossakowski Till, Schneider Thomas, Wolter Diedrich (2013) Algebraic Properties of Qualitative Spatio-temporal Calculi. In COSIT
Dylla F, Wallgrün JO (2007) Qualitative Spatial Reasoning with Conceptual Neighborhoods for Agent Control. J. Intell. Robotic Syst. 48:55–78
Falomir Z, Cabedo LM, Castelló V, Abril LG (2013) Qualitative distances and qualitative image descriptions for representing indoor scenes in robotics. Pattern Recognit. Lett. 34:731–743
Fenelon V, Santos PE, Dee HM, Cozman FG (2013) Reasoning about shadows in a mobile robot environment. Appl. Intell. 38:553–565
Gerevini A (2005) Incremental qualitative temporal reasoning: Algorithms for the Point Algebra and the ORD-Horn class. Artif Intell 166:37–80
Glorian Gael, Lagniez Jean-Marie, Montmirail Valentin, Sioutis Michael (2018) An incremental sat-based approach to reason efficiently on qualitative constraint networks. In CP
Golumbic MC, Shamir R (1993) Complexity and Algorithms for Reasoning about Time: A Graph-Theoretic Approach. J ACM 40:1108–1133
Hazarika SM (2012) Qualitative Spatio-Temporal Representation and Reasoning: Trends and Future Directions. Igi Global
Heintz Fredrik, de Leng Daniel (2014) Spatio-Temporal Stream Reasoning with Incomplete Spatial Information. In ECAI
Huang Jinbo (2012) Compactness and its implications for qualitative spatial and temporal reasoning. In KR
Huang J, Li JJ, Renz J (2013) Decomposition and tractability in qualitative spatial and temporal reasoning. Artif Intell 195:140–164
Jégou Philippe (1993) Decomposition of Domains Based on the Micro-Structure of Finite Constraint-Satisfaction Problems. In Richard Fikes and Wendy G. Lehnert, editors, AAAI
Jonsson Peter, Lagerkvist Victor (2018) Why are CSPs Based on Partition Schemes Computationally Hard? In MFCS
Kong S, Li S, Sioutis M (2018) Exploring Directional Path-Consistency for Solving Constraint Networks. Comput. J. 61:1338–1350
Kordjamshidi Parisa, Hois Joana, van Otterlo Martijn, Moens Marie-Francine (2011) Machine learning for interpretation of spatial natural language in terms of QSR. In COSIT (Extended abstract)
Kordjamshidi P, Moens M-F (2015) Global machine learning for spatial ontology population. J. Web Sem. 30:3–21
Kostakis O, Papapetrou P (2017) On searching and indexing sequences of temporal intervals. Data Min. Knowl. Discov. 31:809–850
Kostakis O, Tatti N, Gionis A (2017) Discovering recurring activity in temporal networks. Data Min. Knowl. Discov. 31:1840–1871
Krishnaswamy Nikhil, Friedman Scott, Pustejovsky James (2020) Combining Deep Learning and Qualitative Spatial Reasoning to Learn Complex Structures from Sparse Examples with Noise. In AAAI, 2019.
Lattner Andreas D, Timm Ingo J, Lorenz Martin, Herzog Otthein (2005) Knowledge-based risk assessment for intelligent vehicles. In KIMAS
Li Jason Jingshi (2012) Qualitative Spatial and Temporal Reasoning with Answer Set Programming. In ICTAI
Lifschitz Vladimir (2008) What Is Answer Set Programming? In AAAI
Ligozat Gérard (2011) Qualitative Spatial and Temporal Reasoning. Iste Series. Wiley
Ligozat Gérard, Renz Jochen (2004) What Is a Qualitative Calculus? A General Framework. In PRICAI
Little TDC, Ghafoor A (1993) Interval-Based Conceptual Models for Time-Dependent Multimedia Data. IEEE Trans Knowl Data Eng 5:551–563
Long Zhiguo, Sioutis Michael, Li Sanjiang (2016) Efficient Path Consistency Algorithm for Large Qualitative Constraint Networks. In IJCAI
Lu Ruopeng, Sadiq Shazia Wasim, Padmanabhan Vineet, Governatori Guido (2006) Using a temporal constraint network for business process execution. In ADC
Lutz C, Milićič M (2007) A Tableau Algorithm for Description Logics with Concrete Domains and General TBoxes. J. Autom. Reason. 38:227–259
Monasson R, Zecchina R, Kirkpatrick S, Selman B, Troyansky L (1999) Determining computational complexity from characteristic ’phase transitions’. Nature 400:133–137
Moskovitch R, Shahar Y (2015) Classification of multivariate time series via temporal abstraction and time intervals mining. Knowl Inf Syst 45:35–74
Mudrová Lenka, Hawes Nick (2015) Task scheduling for mobile robots using interval algebra. In ICRA
Paparrizou Anastasia, Stergiou Kostas (2017) On Neighborhood Singleton Consistencies. In IJCAI
Pelavin Richard N, Allen James F (1987) A Model for Concurrent Actions Having Temporal Extent. In AAAI
Pesant G, Quimper C-G, Zanarini A (2012) Counting-Based Search: Branching Heuristics for Constraint Satisfaction Problems. J Artif Intell Res 43:173–210
Randell David A, Cui Zhan, Cohn Anthony (1992) A Spatial Logic Based on Regions and Connection. In KR
Randell DA, Galton A, Fouad S, Mehanna H, Landini G (2017) Mereotopological Correction of Segmentation Errors in Histological Imaging. J. Imaging 3:63
Renz J, Nebel B (2001) Efficient Methods for Qualitative Spatial Reasoning. J Artif Intell Res 15:289–318
Renz Jochen, Nebel Bernhard (2007) Qualitative Spatial Reasoning Using Constraint Calculi. In Handbook of Spatial Logics, pages 161–215
Rost Pascal, Hotz Lothar, von Riegen Stephanie (2012) Supporting Mobile Robot’s Tasks through Qualitative Spatial Reasoning. In ICINCO
Schultz Carl PL, Bhatt Mehul, Suchan Jakob, Walega Przemyslaw Andrzej (2018) Answer Set Programming Modulo ’Space-Time’. In RuleML+RR
Sioutis Michael (2017) Algorithmic Contributions to Qualitative Constraint-based Spatial and Temporal Reasoning. PhD thesis, Université d’Artois
Sioutis Michael, Alirezaie Marjan, Renoux Jennifer, Loutfi Amy (2017) Towards a Synergy of Qualitative Spatio-Temporal Reasoning and Smart Environments for Assisting the Elderly at Home. In IJCAI Workshop on Qualitative Reasoning
Sioutis Michael, Condotta Jean-François (2017) Efficiently Enforcing Path Consistency on Qualitative Constraint Networks by Use of Abstraction. In IJCAI
Sioutis M, Condotta J-F, Koubarakis M (2016) An Efficient Approach for Tackling Large Real World Qualitative Spatial Networks. Int J Artif Intell Tools 25:1–33
Sioutis Michael, Long Zhiguo, Li Sanjiang (2016) Efficiently Reasoning about Qualitative Constraints through Variable Elimination. In SETN
Sioutis M, Long Z, Li S (2018) Leveraging Variable Elimination for Efficiently Reasoning about Qualitative Constraints. Int J Artif Intell Tools 27:1860001
Sioutis Michael, Paparrizou Anastasia, Condotta Jean-François (2017) Collective Singleton-Based Consistency for Qualitative Constraint Networks. In TIME
Sioutis M, Paparrizou A, Condotta J-F (2019) Collective singleton-based consistency for qualitative constraint networks: Theory and practice. Theor. Comput. Sci. 797:17–41
Sioutis M, Salhi Y, Condotta J-F (2017) Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning. Knowl. Eng. Rev. 32:e4
Snodgrass RT (1987) The Temporal Query Language TQuel. ACM Trans. Database Syst. 12:247–298
Song Fei, Cohen Robin (1988) The Interpretation of Temporal Relations in Narrative. In IJCAI
Sridhar Muralikrishna, Cohn Anthony G, Hogg David C (2011) From Video to RCC8: Exploiting a Distance Based Semantics to Stabilise the Interpretation of Mereotopological Relations. In COSIT
Story Philip A, Worboys Michael F (1995) A Design Support Environment for Spatio-Temporal Database Applications. In COSIT
Suchan Jakob, Bhatt Mehul (2016) Semantic Question-Answering with Video and Eye-Tracking Data: AI Foundations for Human Visual Perception Driven Cognitive Film Studies. In IJCAI
Suchan Jakob, Bhatt Mehul, Varadarajan Srikrishna (2019) Out of Sight But Not Out of Mind: An Answer Set Programming Based Online Abduction Framework for Visual Sensemaking in Autonomous Driving. In IJCAI
Suchan Jakob, Bhatt Mehul, Walega Przemyslaw Andrzej, Schultz Carl PL (2018) Visual Explanation by High-Level Abduction: On Answer-Set Programming Driven Reasoning About Moving Objects. In AAAI
Taylor Brian J, Darrah Marjorie A, Moats Christina D (2003) Verification and validation of neural networks: a sampling of research in progress. In Intelligent Computing: Theory and Applications
van Beek P, Manchak DW (1996) The design and experimental analysis of algorithms for temporal reasoning. J Artif Intell Res 4:1–18
Walega PA, Schultz CPL, Bhatt M (2017) Non-monotonic spatial reasoning with answer set programming modulo theories. TPLP 17:205–225
Wallace RJ (2016) Neighbourhood SAC: Extensions and new algorithms. AI Commun. 29:249–268
Westphal Matthias, Wölfl Stefan (2009) Qualitative CSP, Finite CSP, and SAT: Comparing Methods for Qualitative Constraint-based Reasoning. In IJCAI
Williams Ryan, Gomes Carla P, Selman Bart (2003) Backdoors To Typical Case Complexity. In IJCAI
Acknowledgements
We would like to thank Professor Tomi Janhunen and Doctoral Researcher Neziha Akalin for their valuable feedback.
Funding
Open Access funding enabled and organized by Projekt DEAL.
Author information
Authors and Affiliations
Corresponding author
Additional information
The original online version of this article was revised due to a retrospective Open Access order.
Taking place at the time when it is needed, at run time, and not in advance.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Sioutis, M. Just-In-Time Constraint-Based Inference for Qualitative Spatial and Temporal Reasoning. Künstl Intell 34, 259–270 (2020). https://doi.org/10.1007/s13218-020-00652-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13218-020-00652-z