Traditional logic-based belief revision research focuses on designing rules to constrain the behavior of revision operators. Frameworks have been proposed to characterize iterated revision rules, but they are often too loose, leading to multiple revision operators that all satisfy the rules under the same belief condition. In many practical applications, such as safety critical ones, it is important to specify a definite revision operator to enable agents to iteratively revise their beliefs in a deterministic way. In this paper, we propose a novel framework for iterated belief revision by characterizing belief information through preference relations. Semantically, both beliefs and new evidence are represented as belief algebras, which provide a rich and expressive foundation for belief revision. Building on traditional revision rules, we introduce additional postulates for revision with belief algebra, including an upper-bound constraint on the outcomes of revision. We prove that the revision result is uniquely determined given the current belief state and new evidence. Furthermore, to make the framework more useful in practice, we develop a particular algorithm for performing the proposed revision process. We argue that this approach may offer a more predictable and principled method for belief revision, making it suitable for real-world applications.

In this paper, we present a reinforcement learning approach for resolving inconsistencies in qualitative constraint networks ( QCN s). QCN s are typically used in constraint programming to represent and reason about intuitive spatial or temporal relations like x { is inside of ∨ overlaps } y . Naturally, QCN s are not immune to uncertainty, noise, or imperfect data that may be present in information, and thus, more often than not, they are hampered by inconsistencies. We propose a multi-armed bandit approach that defines a well-suited ordering of constraints for finding a maximal satisfiable subset of them. Specifically, our learning approach interacts with a solver, and after each trial a reward is returned to measure the performance of the selected action (constraint addition). The reward function is based on the reduction of the solution space of a consistent reconstruction of the input QCN . Experimental results with different bandit policies and various rewards that are obtained by our algorithm suggest that we can do better than the state of the art in terms of both effectiveness, viz., lower number of repairs obtained for an inconsistent QCN , and efficiency, viz., faster runtime.

People often use qualitative relations to describe locations or directional information, especially in written communication, such as ‘the restaurant is located at the southeast corner of the square’. However, when a large number of spatial entities are involved, qualitative relations alone are not intuitive enough for people to understand a spatial configuration. In fact, many applications, e.g. pertaining to sharing travel experiences, use sketch maps, i.e. maps focusing on the main features of an area whilst abstracting exact scale measurements, to help demonstrate abstract qualitative relations with more intuitive geometric points. Current approaches for generating point sketch maps from qualitative spatial relations require a high level of expertise, face inherent difficulties with efficiently processing large-scale data in bulk, and are vulnerable to inaccurate or conflicting information contained in qualitative data. To address these limitations, by incorporating machine learning techniques, we propose to translate the problem into an optimization problem of data reconstruction, enabling a novel end-to-end approach for generating point sketch maps from qualitative directional relations in bulk. Experiments on real-world datasets show that the proposed approach has very high accuracy and is robust even with a large portion of inaccurate or incomplete information.

Inconsistency handling is a fundamental problem in knowledge representation and reasoning. In this paper, we study this problem in the context of qualitative spatio-temporal reasoning, a framework for reasoning about space and time in a symbolic, human-like manner, by following an approach similar to that used for defining paraconsistent logics; paraconsistency allows deriving informative conclusions from inconsistent knowledge bases by mainly avoiding the principle of explosion. Inspired by paraconsistent logics, such as Priest’s logic LPm, we introduce the notion of paraconsistent scenario (i.e., a qualitative solution), which can be seen as a scenario that allows a conjunction of base relations between two variables, e.g., x precedes ∧ follows y. Further, we present several interesting theoretical properties that concern paraconsistent scenarios, including computational complexity results, and describe two distinct approaches for computing paraconsistent scenarios and solving other related problems. Moreover, we provide implementations of our two methods for computing paraconsistent scenarios and experimentally evaluate them using different strategies/metrics. Finally, we show that our paraconsistent scenario notion allows us to adapt to qualitative reasoning one of the well-known inconsistency measures employed in the propositional case, namely, contension measure.

Decomposition can be a fundamental process for dealing with inconsistency in different domains. Among other things, it allows us to capture potential contexts, identify conflicting factors, restore consistency, and measure inconsistency. The aim of this paper is to explore the process of decomposition in qualitative spatial and temporal reasoning. We first study a problem that consists in decomposing the original inconsistent constraint network into the fewest possible consistent subnetworks (components) that share a given part. After establishing several interesting theoretical properties, such as providing bounds on the number of components in a decomposition, as well as computational complexity results, we propose two methods for solving this problem. The first method is based on a SAT encoding, while the second one corresponds to a greedy constraint-based algorithm, a variant of which involves the use of spanning trees to reduce the number of oracle calls. Secondly, we consider a version of the previous decomposition problem by focusing on maximizing the similarity between the decomposition components; the similarity in this context is represented by the common constraints among components. We then adapt our methods to solve this new problem. Thirdly, we propose two inconsistency measures that are based on our decomposition framework and show that they satisfy several desired properties. Finally, we provide implementations of our decomposition methods and perform an experimental evaluation.

The concept of prime implicant is a fundamental tool in Boolean algebra, which is used in Boolean circuit design and, recently, in explainable AI. This study investigates an analogous concept in qualitative spatial and temporal reasoning, called prime scenario. Specifically, we define a prime scenario of a qualitative constraint network (QCN) as a minimal set of decisions that can uniquely determine solutions of this QCN. We propose in this paper a collection of algorithms designed to address various problems related to prime scenarios. The first three algorithms aim to generate a prime scenario from a scenario of a QCN. The main idea consists in using path consistency to identify the constraints that can be ignored to generate a prime scenario. The next two algorithms focus on generating a set of prime scenarios that cover all the scenarios of the original QCN: The first algorithm examines every branch of the search tree, while the second is based on the use of a SAT encoding. Our last algorithm is concerned with computing a minimum-size prime scenario by using a MaxSAT encoding built from countermodels of the original QCN. We show that this algorithm is particularly useful for measuring the robustness of a QCN. Finally, a preliminary experimental evaluation is performed with instances of Allen’s Interval Algebra to assess the efficiency of our algorithms and, hence, also the difficulty of the newly introduced problems here.

Dealing with inconsistency is a central problem in AI, due to the fact that inconsistency can arise for many reasons in real-world applications, such as context dependency, multi-source information, vagueness, noisy data, etc. Among the approaches that are involved in inconsistency handling, we can mention argumentation, non-monotonic reasoning, and paraconsistency, e.g., see [Philippe Besnard and Anthony Hunter, 2008; Gerhard Brewka et al., 1997; Koji Tanaka et al., 2013]. In the work of [Yakoub Salhi and Michael Sioutis, 2023], we are interested in dealing with inconsistency in the context of Qualitative Spatio-Temporal Reasoning (QSTR) [Ligozat, 2013]. QSTR is an AI framework that aims to mimic, natural, human-like representation and reasoning regarding space and time. This framework is applied to a variety of domains, such as qualitative case-based reasoning and learning [Thiago Pedro Donadon Homem et al., 2020] and visual sensemaking [Jakob Suchan et al., 2021]; the interested reader is referred to [Michael Sioutis and Diedrich Wolter, 2021] for a recent survey. Motivation. In [Yakoub Salhi and Michael Sioutis, 2023], we study the decomposition of an inconsistent constraint network into consistent subnetworks under, possible, mandatory constraints. To illustrate the interest of such a decomposition, we provide a simple example described in Figure 1. The QCN depicted in the top part of the figure corresponds to a description of an inconsistent plan. Further, we assume that the constraint Task A {before} Task B is mandatory. To handle inconsistency, this plan can be transformed into a decomposition of two consistent plans, depicted in the bottom part of the figure; this decomposition can be used, e.g., to capture the fact that Task C must be performed twice. More generally, network decomposition can be involved in inconsistency handling in several ways: it can be used to identify potential contexts that explain the presence of inconsistent information; it can also be used to restore consistency through a compromise between the components of a decomposition, e.g., by using belief merging [Jean-François Condotta et al., 2010]; in addition, QCN decomposition can be used as the basis for defining inconsistency measures. Contributions. We summarize the contributions of [Yakoub Salhi and Michael Sioutis, 2023] as follows. First, we propose a theoretical study of a problem that consists in decomposing an inconsistent QCN into a bounded number of consistent QCNs that may satisfy a specified part in the original QCN; intuitively, the required common part corresponds to the constraints that are considered necessary, if any. To this end, we provide upper bounds for the minimum number of components in a decomposition as well as computational complexity results. Secondly, we provide two methods for solving our decomposition problem. The first method corresponds to a greedy constraint-based algorithm, a variant of which involves the use of spanning trees; the basic idea of this variant is that any acyclic constraint graph in QSTR is consistent, and such a graph can be used as a starting point for building consistent components. The second method corresponds to a SAT-based encoding; every model of this encoding is used to construct a valid decomposition. Thirdly, we consider two optimization versions of the initial decomposition problem that focus on minimizing the number of components and maximizing the similarity between components, respectively. The similarity between two QCNs is quantified by the number of common non-universal constraints; the interest in maximizing the similarity lies mainly in the fact that it reduces the number of constraints that allow each component to be distinguished from the rest. Of course, our previous methods are adapted to tackle these optimization versions, too. Additionally, we introduce two inconsistency measures based on QCN decomposition, which can be seen as counterparts of measures for propositional KBs introduced in [Matthias Thimm, 2016; Meriem Ammoura et al., 2017], and show that they satisfy several desired properties in the literature. Finally, we provide implementations of our methods for computing decompositions and experimentally evaluate them using different metrics.

In this paper, we deal with inconsistency resolution in qualitative constraint networks (QCN). This type of networks allows one to represent and reason about spatial or temporal information in a natural, human-like manner, e.g., by expressing relations of the form x {is north of ∨ is east of} y. On the other hand, inconsistency resolution involves maximizing the amount of information that is consistent in a knowledge base; in the context of QCNs, this translates to maximizing the number of constraints that can be satisfied, via obtaining a qualitative solution (scenario) of the QCN that ignores/violates as few of the original constraints as possible. To this end, we present two novel approaches: a greedy constraint-based and an optimal Partial MaxSAT-based one, with a focus on the former due to its simplicity. Specifically, the greedy technique consists in adding the constraints of a QCN to a new, initially empty network, one by one, all the while filtering out the ones that fail the satisfiability check. What makes or breaks this technique is the ordering in which the constraints will be processed to saturate the empty QCN, and for that purpose we use many different strategies to form a portfolio-style implementation. The Partial MaxSAT-based approach is powered by Horn theory-based maximal tractable subsets of relations. Finally, we compare the greedy approach with the optimal one, commenting on the trade-off between obtaining repairs that are optimal and obtaining repairs in a manner that is fast, and make our source code available for anyone to use.

In this paper, we present an online (incremental) algorithm for checking the satisfiability of qualitative spatio-temporal data, with direct implications to other fundamental knowledge representation and reasoning problems for such data, like the problems of deductive closure and redundancy removal. In particular, qualitative data come in the form of human-like, symbolic, descriptions such as "region x contains or overlaps region y", which are abundant in the Web of Data. Our approach is also able to maintain, to some extent, any sparse graph structure that may be inherent in the data, i.e., it acts parsimoniously and only tries to infer new information when needed for soundness and completeness. To this end, we complement our practical algorithm with certain theoretical results to assert its correctness and efficiency. A subsequent evaluation with publicly available large-scale real-world and random datasets against the state of the art, shows the interest and promise of our method.

Qualitative Constraint Networks (QCNs) comprise a Symbolic AI framework for representing and reasoning about spatial and temporal information via the use of disjunctive natural relations, e.g., a constraint can be of the form "Task A is scheduled after or during Task C". In this short paper, we make a comparison and evaluation with respect to prominent QCN-tackling heuristics in the literature, and reveal that there exists a trade-off between fast and robust solving of QCNs for a dataset of Allen’s Interval Algebra instances.

Qualitative Spatial & Temporal Reasoning (QSTR) is a major field of study in Symbolic AI that deals with the representation and reasoning of spatio- temporal information in an abstract, human-like manner. We survey the current status of QSTR from a viewpoint of reasoning approaches, and identify certain future challenges that we think that, once overcome, will allow the field to meet the demands of and adapt to real-world, dynamic, and time-critical applications of highly active areas such as machine learning and data mining.

We introduce and study a notion of robustness in Qualitative Constraint Networks (QCNs), which are typically used to represent and reason about abstract spatial and temporal information. In particular, given a QCN, we are interested in obtaining a robust qualitative solution, or, a robust scenario of it, which is a satisfiable scenario that has a higher perturbation tolerance than any other, or, in other words, a satisfiable scenario that has more chances than any other to remain valid after it is altered. This challenging problem requires to consider the entire set of satisfiable scenarios of a QCN, whose size is usually exponential in the number of constraints of that QCN; however, we present a first algorithm that is able to compute a robust scenario of a QCN using linear space in the number of constraints. Preliminary results with a dataset from the job-shop scheduling domain, and a standard one, show the interest of our approach and highlight the fact that not all solutions are created equal.

We introduce and evaluate dynamic branching strategies for solving Qualitative Constraint Networks (QCNs), which are networks that are mostly used to represent and reason about spatial and temporal information via the use of simple qualitative relations, e.g., a constraint can be "Task A is scheduled after or during Task C". In qualitative constraint-based reasoning, the state-of-the-art approach to tackle a given QCN consists in employing a backtracking algorithm, where the branching decisions during search are governed by the restrictiveness of the possible relations for a given constraint (e.g., after can be more restrictive than during). In the literature, that restrictiveness is defined a priori by means of static weights that are precomputed and associated with the relations of a given calculus, without any regard to the particulars of a given network instance of that calculus, such as its structure. In this paper, we address this limitation by proposing heuristics that dynamically associate a weight with a relation, based on the count of local models (or local scenarios) that the relation is involved with in a given QCN; these models are local in that they focus on triples of variables instead of the entire QCN. Therefore, our approach is adaptive and seeks to make branching decisions that preserve most of the solutions by determining what proportion of local solutions agree with that decision. Experimental results with a random and a structured dataset of QCNs of Interval Algebra show that it is possible to achieve up to 5 times better performance for structured instances, whilst maintaining non-negligible gains of around 20% for random ones.

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 QCNs, 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 singleton-style 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 QCNs of Interval Algebra in the phase transition region to demonstrate the potential of our approach.

Among the local consistency techniques used for solving constraint networks, path-consistency (PC) has received a great deal of attention. However, enforcing PC is computationally expensive and sometimes even unnecessary. Directional path-consistency (DPC) is a weaker notion of PC that considers a given variable ordering and can thus be enforced more efficiently than PC. This paper shows that DPC (the DPC enforcing algorithm of Dechter and Pearl) decides the constraint satisfaction problem (CSP) of a constraint language if it is complete and has the variable elimination property (VEP). However, we also show that no complete VEP constraint language can have a domain with more than 2 values. We then present a simple variant of the DPC algorithm, called DPC*, and show that the CSP of a constraint language can be decided by DPC* if it is closed under a majority operation. In fact, DPC* is sufficient for guaranteeing backtrack-free search for such constraint networks. Examples of majority-closed constraint classes include the classes of connected row-convex (CRC) constraints and tree-preserving constraints, which have found applications in various domains, such as scene labeling, temporal reasoning, geometric reasoning, and logical filtering. Our experimental evaluations show that DPC* significantly outperforms the state-of-the-art algorithms for solving majority-closed constraints.

Partial singleton (weak) path consistency, or partial -consistency, for a qualitative constraint network, ensures that the process of instantiating any constraint of that network with any of its base relations b and enforcing partial (weak) path consistency, or partial -consistency, in the updated network, yields a partially -consistent subnetwork where the respective constraint is still defined by b. This local consistency is essential for helping to decide the satisfiability of challenging qualitative constraint networks and has been shown to play a crucial role in tackling more demanding problems associated with a given qualitative constraint network, such as the problem of minimal labeling. One of the main downsides to using partial -consistency, is that it is computationally expensive to enforce in a given qualitative constraint network, as, despite being a local consistency in principle, it retains a global scope of the network at hand. In this paper, we propose a lazy algorithm that restricts the singleton checks associated with partial -consistency to constraints that are likely to lead to the removal of a base relation upon their propagation. A key feature of this algorithm is that it collectively eliminates certain unfeasible base relations by exploiting singleton checks. Further, we show that the closure that is obtained by our algorithm is incomparable to the one that is entailed by partial -consistency and non-unique in general. We demonstrate the efficiency of our algorithm via an experimental evaluation with random Interval Algebra networks from the phase transition region of two separate models and, moreover, show that it can exhibit very similar pruning capability for such networks to the one of an algorithm for enforcing partial -consistency.

Partial closure under weak composition, or partial weak path-consistency for short, is essential for tackling fundamental reasoning problems associated with qualitative constraint networks, such as the satisfiability checking problem, and therefore it is crucial to be able to enforce it as fast as possible. To this end, we propose a new algorithm, called PWCα, for efficiently enforcing partial weak path-consistency on qualitative constraint networks, that exploits the notion of abstraction for qualitative constraint networks, utilizes certain properties of partial weak path-consistency,and adapts the functionalities of some state-of-the-art algorithms to its design. It is worth noting that, as opposed to a related approach in the recent literature, algorithm PWCα is complete for arbitrary qualitative constraint networks. The evaluation that we conducted with qualitative constraint networks of the Region Connection Calculus against a competing state-of-the-art generic algorithm for enforcing partial weak path-consistency, demonstrates the usefulness and efficiency of algorithm PWCα.

Partial singleton closure under weak composition, or partial singleton (weak) path-consistency for short, is essential for approximating satisfiability of qualitative constraints networks. Briefly put, partial singleton path-consistency ensures that each base relation of each of the constraints of a qualitative constraint network can define a singleton relation in the corresponding partial closure of that network under weak composition, or in its corresponding partially (weak) path-consistent subnetwork for short. In particular, partial singleton path-consistency has been shown to play a crucial role in tackling the minimal labeling problem of a qualitative constraint network, which is the problem of finding the strongest implied constraints of that network. In this paper, we propose a stronger local consistency that couples partial singleton path-consistency with the idea of collectively deleting certain unfeasible base relations by exploiting singleton checks. We then propose an efficient algorithm for enforcing this consistency that, given a qualitative constraint network, performs fewer constraint checks than the respective algorithm for enforcing partial singleton path-consistency in that network. We formally prove certain properties of our new local consistency, and motivate its usefulness through demonstrative examples and a preliminary experimental evaluation with qualitative constraint networks of Interval Algebra.

The Simple Temporal Problem (STP) has been widely used in various applications to schedule tasks. For dynamical systems, scheduling needs to be efficient and flexible to handle uncertainty and perturbation. To this end, modern approaches usually encode the temporal information as an STP instance. This representation contains redundant information, which can not only take a significant amount of storage space, but also make scheduling inefficient due to the non-concise representation. In this paper, we investigate the problem of simplifying an STP instance by removing redundant information. We show that such a simplification can result in a unique minimal representation without loss of temporal information, and present an efficient algorithm to achieve this task. Evaluation on a large benchmark dataset of STP exhibits a significant reduction in redundant information for the involved instances.

We introduce and study the problem of obtaining a spatial or temporal configuration that maximizes the number of constraints satisfied in a qualitative constraint network (QCN). We call this problem the MAX-QCN problem and prove that it is NP-hard for most of the qualitative calculi. We also propose a complete generic branch and bound algorithm for solving the MAX-QCN problem. This algorithm builds on techniques used in the literature for solving the consistency checking problem and the minimal labeling problem of a given QCN. In particular, we make use of a tractable subclass of relations, a chordal graph provided by a triangulation of the input QCN, and the partial weak composition as a filtering method. The experimentation that we have conducted with QCNs from the Interval Algebra and the Region Connection Calculus shows the interest of our proposed algorithm.

We improve the state-of-the-art method for the compression of web and other similar graphs by introducing an elegant technique which further exploits the clustering properties observed in these graphs. The analysis and experimental evaluation of our method shows that it outperforms the currently best method of Boldi et al. by achieving a better compression ratio and retrieval time. Our method exhibits vast improvements on certain families of graphs, such as social networks, by taking advantage of their compressibility characteristics, and ensures that the compression ratio will not worsen for any graph, since it easily falls back to the state-of-the-art method.

There has been interest in recent literature in tackling very large real world qualitative spatial networks, primarily because of the real datasets that have been, and are to be, offered by the Semantic Web community and scale up to millions of nodes. The proposed techniques for tackling such large networks employ the following two approaches for retaining the sparseness of their underlying graphs and reasoning with them: (i) graph triangulation and sparse matrix implementation, and (ii) graph partitioning and parallelization. Regarding the latter approach, an implementation has been offered recently, presented in [AAAI, 2014]. However, although the implementation looks promising and with space for improvement, an improper use of competing solvers in the evaluation process resulted in the wrong conclusion that it is able to provide fast consistency for very large qualitative spatial networks with respect to the state-of-the-art. In this paper, we review the two aforementioned approaches and provide new results that are different to the results presented in [AAAI, 2014] by properly re-evaluating them with the benchmark dataset of that paper. Thus, we establish a clear view on the state-of-the-art solutions for reasoning with large real world qualitative spatial networks efficiently, which is the main result of this paper.

We consider chordal RCC-8 networks and show that we can check their consistency by enforcing partial path consistency with weak composition. We prove this by using the fact that RCC-8 networks with relations from the maximal tractable subsets H8, C8, and Q8of RCC-8 have the patchwork property. The use of partial path consistency has important practical consequences that we demonstrate with the implementation of the new reasoner PyRCC∇, which is developed by extending the state of the art reasoner PyRCC8. Given an RCC-8 network with only tractable RCC-8 relations, we show that it can be solved very efficiently with PyRCC∇ by making its underlying constraint graph chordal and running path consistency on this sparse graph instead of the completion of the given network. In the same way, partial path consistency can be used as the consistency checking step in backtracking algorithms for networks with arbitrary RCC-8 relations resulting in very improved pruning for sparse networks while incurring a penalty for dense networks.

TELEIOS is a recent European project that addresses the need for scalable access to petabytes of Earth Observation data and the discovery and exploitation of knowledge that is hidden in them. TELEIOS builds on scientific database technologies (array databases, SciQL, data vaults) and Semantic Web technologies (stRDF and stSPARQL) implemented on top of a state of the art column store database system (MonetDB). We demonstrate a first prototype of the TELEIOS Virtual Earth Observatory (VEO) architecture, using a forest fire monitoring application as example.