The Experts below are selected from a list of 5442 Experts worldwide ranked by ideXlab platform
Abdul Sattar - One of the best experts on this subject based on the ideXlab platform.
-
a local search approach to modelling and solving Interval Algebra problems
Journal of Logic and Computation, 2004Co-Authors: John Thornton, Matthew Beaumont, Abdul Sattar, Michael J MaherAbstract:Local search techniques have attracted considerable interest in the artificial intelligence community since the development of GSAT and the min-conflicts heuristic for solving propositional satisfiability (SAT) problems and binary constraint satisfaction problems (CSPs) respectively. Newer techniques, such as the discrete Langrangian method (DLM), have significantly improved on GSAT and can also be applied to general constraint satisfaction and optimization. However, local search has yet to be successfully employed in solving temporal constraint satisfaction problems (TCSPs). This paper argues that current formalisms for representing TCSPs are inappropriate for a local search approach, and proposes an alternative CSP-based end-point ordering model for temporal reasoning. The paper looks at modelling and solving problems formulated using Allen's Interval Algebra (IA) and proposes a new constraint weighting algorithm derived from DLM. Using a set of randomly generated IA problems, it is shown that local search outperforms existing consistency-enforcing algorithms on those problems that the existing techniques find most difficult.
-
indu an Interval and duration network
Australian Joint Conference on Artificial Intelligence, 1999Co-Authors: Arun K Pujari, Vijaya G Kumari, Abdul SattarAbstract:The significance of representing duration information along with the qualitative information of the time Intervals is well argued in the literature. A new framework INVU (Interval and DUration) network consisting of 25 basic relations, is proposed here. INDU cam handle qualitative information of time Interval and duration in one single structure. It inherits many interesting properties of Allen's Interval Algebra (of 13 basic relations) but it also exhibits severed interesting additional features. We present several representations of INDU (ORD-clause, Geometric and Lattice) and chatracterise its tractable subclasses such as the Convex and Pre-convex classes. The important contribution of the current study is to show that for the tractable subclasses (Convex as well as Pre-convex) 4-consistency is necessary to guarantee global consistency of INDU-network.
-
indu an Interval duration network
Australasian Joint Conference on Artificial Intelligence, 1999Co-Authors: Abdul Sattar, Arun K Pujari, Vijaya G KumariAbstract:The significance of representing duration information along with the qualitative information of the time Intervals is well argued in the literature. A new framework INDu (Interval and DUration) network consisting of 25 basic relations, is proposed here. INDu can handle qualitative information of time Interval and duration in one single structure. It inherits many interesting properties of Allen’s Interval Algebra (of 13 basic relations) but it also exhibits severed interesting additional features. We present several representations of INDu (ORD-clause, Geometric and Lattice) and characterise its tractable subclasses such as the Convex and Pre-convex classes. The important contribution of the current study is to show that for the tractable subclasses (Convex as well as Pre-convex) 4-consistency is necessary to guarantee global consistency of INDu-network.
Karen R. Strung - One of the best experts on this subject based on the ideXlab platform.
-
c Algebras of minimal dynamical systems of the product of a cantor set and an odd dimensional sphere
Journal of Functional Analysis, 2015Co-Authors: Karen R. StrungAbstract:Abstract Let β : S n → S n , for n = 2 k + 1 , k ≥ 1 , be one of the known examples of a nonuniquely ergodic minimal diffeomorphism of an odd dimensional sphere. For every such minimal dynamical system ( S n , β ) there is a Cantor minimal system ( X , α ) such that the corresponding product system ( X × S n , α × β ) is minimal and the resulting crossed product C ⁎ -Algebra C ( X × S n ) ⋊ α × β Z is tracially approximately an Interval Algebra (TAI). This entails classification for such C ⁎ -Algebras. Moreover, the minimal Cantor system ( X , α ) is such that each tracial state on C ( X × S n ) ⋊ α × β Z induces the same state on the K 0 -group and such that the embedding of C ( S n ) ⋊ β Z into C ( X × S n ) ⋊ α × β Z preserves the tracial state space. This implies C ( S n ) ⋊ β Z is TAI after tensoring with the universal UHF Algebra, which in turn shows that the C ⁎ -Algebras of these examples of minimal diffeomorphisms of odd dimensional spheres are classified by their tracial state spaces.
-
C*-Algebras of minimal dynamical systems of the product of a Cantor set and an odd dimensional sphere
arXiv: Operator Algebras, 2014Co-Authors: Karen R. StrungAbstract:Let \beta : S^n \to S^n, for n = 2k + 1, k \geq 1, be one of the known examples of a non-uniquely ergodic minimal diffeomorphism of an odd dimensional sphere. For every such minimal dynamical system (S^n, \beta) there is a Cantor minimal system (X, \alpha) such that the corresponding product system (X x S^n, \alpha x \beta) is minimal and the resulting crossed product C*-Algebra C(X x S^n) \rtimes_{\alpha x \beta} \mathbb{Z} is tracially approximately an Interval Algebra (TAI). This entails classification for such C*-Algebras. Moreover, the minimal Cantor system (X, \alpha) is such that each tracial state on C(X x S^n) \rtimes_{\beta} \mathbb{Z} induces the same state on the K_0-group and such that the embedding of C(S^n) \rtimes_{\beta} \mathbb{Z} into C(X x S^n) \rtimes_{\alpha x \beta} \mathbb{Z} preserves the tracial state space. This implies C(S^n) \rtimes_{\beta} \mathbb{Z} is TAI after tensoring with the universal UHF Algebra, which in turn shows that the C*-Algebras of these examples of minimal diffeomorphisms of odd dimensional spheres are classified by their tracial state spaces.
Sioutis Michael - One of the best experts on this subject based on the ideXlab platform.
-
Allen’s Interval Algebra Makes the Difference
2021Co-Authors: Janhunen Tomi, Sioutis MichaelAbstract:Allen’s Interval Algebra constitutes a framework for reasoning about temporal information in a qualitative manner. In particular, it uses Intervals, i.e., pairs of endpoints, on the timeline to represent entities corresponding to actions, events, or tasks, and binary relations such as precedes and overlaps to encode the possible configurations between those entities. Allen’s calculus has found its way in many academic and industrial applications that involve, most commonly, planning and scheduling, temporal databases, and healthcare. In this paper, we present a novel encoding of Interval Algebra using answer-set programming (ASP) extended by difference constraints, i.e., the fragment abbreviated as ASP(DL), and demonstrate its performance via a preliminary experimental evaluation. Although our ASP encoding is presented in the case of Allen’s calculus for the sake of clarity, we suggest that analogous encodings can be devised for other point-based calculi, too.Peer reviewe
-
Collective singleton-based consistency for qualitative constraint networks: Theory and practice
'Elsevier BV', 2020Co-Authors: Sioutis Michael, Paparrizou Anastasia, Condotta Jean-françoisAbstract:Avaa tiedosto embargolla sitten kun julkaisu ilmestyy.Partial singleton weak path-consistency, or partial (Figure presented.)-consistency for short, is essential for tackling challenging fundamental reasoning problems associated with qualitative constraints networks. Briefly put, partial (Figure presented.)-consistency ensures that each base relation of each of the constraints of a qualitative constraint network can define a singleton relation in its corresponding partially weakly path-consistent, or partially ⋄-consistent for short, subnetwork. In this paper, we propose a stronger local consistency that couples (Figure presented.)-consistency with the idea of collectively deleting certain unfeasible base relations by exploiting singleton checks. We then propose an algorithm for enforcing this new consistency and a lazy variant of that algorithm for approximating the new consistency that, given a qualitative constraint network, both outperform the respective algorithm for enforcing partial (Figure presented.)-consistency in that network. With respect to the lazyalgorithmic variant in particular, we show that it runs up to 5 times faster than our original exhaustive algorithm whilst exhibiting very similar pruning capability. We formally prove certain properties of our new local consistency and our algorithms, and motivate their usefulness through demonstrative examples and a thorough experimental evaluation with random qualitative constraint networks of the Interval Algebra and the Region Connection Calculus from the phase transition region of two different generation models. Finally, we provide evidence of the crucial role of the new consistency in tackling the minimal labeling problem of a qualitative constraint network, which is the problem of finding the strongest implied constraints of that network.Peer reviewe
-
On Neighbourhood Singleton-style Consistencies for Qualitative Spatial and Temporal Reasoning
'Elsevier BV', 2020Co-Authors: Sioutis Michael, Paparrizou Anastasia, Janhunen TomiAbstract:International audienceGiven a qualitative constraint network (QCN), a singleton-style consistency focuses on each base relation (atom) of a constraint separately, rather than the entire constraint altogether. This local consistency is essential for tackling fundamental reasoning problems associated with QCNs, such as minimal labeling, but can suffer from redundant constraint checks, especially when 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. Further, 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. An experimental evaluation with random and structured QCNs of Allen’s Interval Algebra in the phase transition region demonstrates the potential of our approach
-
Dynamic Branching in Qualitative Constraint Networks via Counting Local Models
LIPIcs - Leibniz International Proceedings in Informatics. 27th International Symposium on Temporal Representation and Reasoning (TIME 2020), 2020Co-Authors: Sioutis Michael, Wolter DiedrichAbstract: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
-
On the Utility of Neighbourhood Singleton-Style Consistencies for Qualitative Constraint-Based Spatial and Temporal Reasoning.
HAL CCSD, 2019Co-Authors: Sioutis Michael, Paparrizou Anastasia, Janhunen TomiAbstract:International audienceA 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
Jochen Renz - One of the best experts on this subject based on the ideXlab platform.
-
decomposition and tractability in qualitative spatial and temporal reasoning
Artificial Intelligence, 2013Co-Authors: Jinbo Huang, Jochen RenzAbstract:Constraint networks in qualitative spatial and temporal reasoning (QSTR) typically feature variables defined on infinite domains. Mainstream algorithms for deciding network consistency are based on searching for network refinements whose consistency is known to be tractable, either directly or by using a SAT solver. Consequently, these algorithms treat all networks effectively as complete graphs, and are not directly amenable to complexity bounds based on network structure, such as measured by treewidth, that are well known in the finite-domain case. The present paper makes two major contributions, spanning both theory and practice. First, we identify a sufficient condition under which consistency can be decided in polynomial time for networks of bounded treewidth in QSTR, and show that this condition is satisfied by a range of calculi including the Interval Algebra, Rectangle Algebra, Block Algebra, RCC8, and RCC5. Second, we apply the techniques used in establishing these results to a SAT encoding of QSTR, and obtain a new, more compact encoding which is also guaranteed to be solvable in polynomial time for networks of bounded treewidth, and which leads to a significant advance of the state of the art in solving the hardest benchmark problems.
-
a divide and conquer approach for solving Interval Algebra networks
International Joint Conference on Artificial Intelligence, 2009Co-Authors: Jinbo Huang, Jochen RenzAbstract:Deciding consistency of constraint networks is a fundamental problem in qualitative spatial and temporal reasoning. In this paper we introduce a divide-and-conquer method that recursively partitions a given problem into smaller sub-problems in deciding consistency. We identify a key theoretical property of a qualitative calculus that ensures the soundness and completeness of this method, and show that it is satisfied by the Interval Algebra (IA) and the Point Algebra (PA). We develop a new encoding scheme for IA networks based on a combination of our divide-and-conquer method with an existing encoding of IA networks into SAT. We empirically show that our new encoding scheme scales to much larger problems and exhibits a consistent and significant improvement in efficiency over state-of-the-art solvers on the most difficult instances.
-
maximal tractable fragments of the region connection calculus a complete analysis
International Joint Conference on Artificial Intelligence, 1999Co-Authors: Jochen RenzAbstract:We present a general method for proving tractability of reasoning over disjunctions of jointly exhaustive and pairwise disjoint relations. Examples of these kinds of relations are Allen's temporal Interval relations and their spatial counterpart, the R.CC8 relations by Randell, Cui, and Colin. Applying this method does not require detailed knowledge about the considered relations; instead, it is rather sufficient to have a subset of the considered set of relations for which path-consistency is known to decide consistency. Using this method, we give a complete classification of tractability of reasoning over RCC8 by identifying two large new maximal tractable subsets and show that these two subsets together with H∞, the already known maximal tractable subset, are the only such sets for RCC8 that contain all base relations. We also apply our method to Allen's Interval Algebra and derive the known maximal tractable subset.
Arun K Pujari - One of the best experts on this subject based on the ideXlab platform.
-
indu an Interval and duration network
Australian Joint Conference on Artificial Intelligence, 1999Co-Authors: Arun K Pujari, Vijaya G Kumari, Abdul SattarAbstract:The significance of representing duration information along with the qualitative information of the time Intervals is well argued in the literature. A new framework INVU (Interval and DUration) network consisting of 25 basic relations, is proposed here. INDU cam handle qualitative information of time Interval and duration in one single structure. It inherits many interesting properties of Allen's Interval Algebra (of 13 basic relations) but it also exhibits severed interesting additional features. We present several representations of INDU (ORD-clause, Geometric and Lattice) and chatracterise its tractable subclasses such as the Convex and Pre-convex classes. The important contribution of the current study is to show that for the tractable subclasses (Convex as well as Pre-convex) 4-consistency is necessary to guarantee global consistency of INDU-network.
-
indu an Interval duration network
Australasian Joint Conference on Artificial Intelligence, 1999Co-Authors: Abdul Sattar, Arun K Pujari, Vijaya G KumariAbstract:The significance of representing duration information along with the qualitative information of the time Intervals is well argued in the literature. A new framework INDu (Interval and DUration) network consisting of 25 basic relations, is proposed here. INDu can handle qualitative information of time Interval and duration in one single structure. It inherits many interesting properties of Allen’s Interval Algebra (of 13 basic relations) but it also exhibits severed interesting additional features. We present several representations of INDu (ORD-clause, Geometric and Lattice) and characterise its tractable subclasses such as the Convex and Pre-convex classes. The important contribution of the current study is to show that for the tractable subclasses (Convex as well as Pre-convex) 4-consistency is necessary to guarantee global consistency of INDu-network.
