Qualitative reasoning formalisms facilitate the representation and interpretation of information involving complex entities. We use in this paper qualitative spatial and temporal reasoning to introduce novel data mining tasks, which consist in extracting knowledge from quantitative databases that are trans-formed into collections of qualitative relation networks (QRNs). After describing our qualitative data mining framework, we first propose an Apriori-like algorithm that exploits monotonicity and QRN consistency for pruning the search space: the validity of a pattern candidate depends on the supports of the larger patterns that include it and on its consistency. We then introduce an encoding of our data mining tasks into the well-known problem of frequent itemset mining. We finally show the feasibility of our approach by providing preliminary experimental results using real-world datasets about the movements of football players during matches.

Defeasible Linear Temporal Logic is a defeasible temporal formalism for representing and verifying exception-tolerant systems. It is based on Linear Temporal Logic (LTL) and builds on the preferential approach of Kraus et al. for non-monotonic reasoning, which allows us to formalize and reason with exceptions. In this paper, we tackle the satisfiability checking problem for defeasible LTL. One of the methods for satisfiability checking in LTL is the one-pass tree shaped analytic tableau proposed by Reynolds. We adapt his tableau to defeasible LTL by integrating the preferential semantics to the method. The novelty of this work is in showing how the preferential semantics works in a tableau method for defeasible linear temporal logic. We introduce a sound and complete tableau method for a fragment that can serve as the basis for further exploring tableau methods for this logic.

Linear Temporal Logic (LTL) has found extensive applications in Computer Science and Artificial Intelligence, notably as a formal framework for representing and verifying computer systems that vary over time. Non-monotonic reasoning, on the other hand, allows us to formalize and reason with exceptions and the dynamics of information. The goal of this paper is therefore to enrich temporal formalisms with non-monotonic reasoning features. We do so by investigating a preferential semantics for defeasible LTL along the lines of that extensively studied by Kraus et al. in the propositional case and recently extended to modal and description logics. The main contribution of the paper is a decidability result for a meaningful fragment of preferential LTL that can serve as the basis for further exploration of defeasibility in temporal formalisms.

Accurate and quick treatment of patients is the most important aim of the health care systems, especially at emergency departments (ED), as such departments are dealing with life and death situations on a daily basis. Nevertheless, the patients scheduling problem (PSP) is often very difficult to solve in practice particularly by applying manual approaches. To this end, the target of this paper is to study the PSP in ED. We propose a hybrid ILS/VND algorithm that aims to minimize the total waiting time of patient’s. After generating the initial solution using the "Triage - First in First out" (TFF) heuristic, the solution is further improved by employing a VND algorithm. The proposed VND involves four neighborhood structures in order to disrupt the actual solution and provide a better exploration of the search space. The obtained results show that the hybrid ILS/VND algorithm is computationally effective and provides high-quality solutions.

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α.

Health organizations are complex to manage due to their dynamic processes and distributed hospital organization. It is therefore necessary for healthcare institutions to focus on this issue to deal with patients’ requirements. Preparing a schedule for patients in the emergency department is a complex task, which requires taking into account numerous rules, related to various aspects: respect the triage process (emergency degrees of patients), respect the availability of resources, etc. In this paper, we present a mixed integer linear programming (MILP) approach to facilitate this task. The objective is to minimize the total waiting time of patient’s in the emergency department. We consider simultaneously four patients’ process: registration and triage, consultation, treatment and hospitalization. The model is characterized by the availability of both human (triage staff, physician, nurse) and material resources (bed) in each process through the stay of patient in the ED except for triage and registration which does not require a bed. To solve this model, we used the commercial solver IBM ILOG CPLEX Optimization Studio. The program has been tested on a set of instances. Numerical results show that the proposed approach can significantly improve the efficiency of emergency department by reducing the total waiting time of patients.

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.

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.

Various formalisms for representing and reasoning about temporal information with qualitative constraints have been studied in the past three decades. The most known are definitely the Point Algebra (PA) and the Interval Algebra (IA) proposed by Allen. In this paper, for both calculi, we study a particular problem that we call minimal consistency problem (MinCons). Given a temporal qualitative constraint network (TQCN) and a positive integer k, this problem consists in deciding whether or not this TQCN admits a solution using at most k distinct points on the line. On the one hand, we prove that this problem is NP-complete for both PA and IA, in the general case. On the other hand, we show that for TQCNs defined on the convex relations, MinCons is polynomial. For these TQCNs, we give a polynomial method allowing to obtain compact scenarios.

In this paper, we introduce for the qualitative constraint networks (QCNs) a new consistency: the partial weak composition consistency. The partial weak composition consistency, similarly to the partial path-consistency, considers triangles of a graph and corresponds to the weak composition consistency restricted to these triangles. We show that for the pre-convex QCNs of the Interval Algebra (IA), the partial weak composition consistency with respect to a triangulation of the graph of constraints is sufficient to decide the consistency problem. From this result, we propose an algorithm allowing to solve QCNs of IA. The experiments that we have conducted show the interest of this algorithm to solve the consistency problem of the QCNs of IA.

A common way to decide the consistency problem of a qualitative constraint network (QCN) is to encode it as a boolean formula in order to benefit from the efficiency of SAT solvers. In recent works, a decomposition method of QCNs have been proposed to reduce the amount of boolean formulae. In this paper, we first show that the decompositions used can be expressed by particular tree decompositions. Furthermore, for some classes of relations, we prove that the consistency problem of a QCN can be decided by applying the method of the closure by weak composition on the clusters of a tree decomposition. This result allows us to extend the approach recently proposed to tree decompositions of QCNs.

This paper is centered on the problem of merging (possibly conflicting) information coming from different sources. Though this problem has attracted much attention in propositional settings, propositional languages remain typically not expressive enough for a number of applications, especially when spatial information must be dealt with. In order to fill the gap, we consider a (limited) first-order logical setting, expressive enough for representing and reasoning about information modeled as half-spaces from metric affine spaces. In this setting, we define a family of distance-based majority merging operators which includes the propositional majority operator ΔdH,Σ. We identify a subclass of interpretations of our representation language for which the result of the merging process can be computed and expressed as a formula.

We address the problem of merging qualitative constraints networks (QCNs). We point out a merging algorithm which computes a consistent QCN representing a global view of the input set of (possibly conflicting) QCNs. This algorithm is generic in the sense that it does not depend on a specific qualitative formalism. The efficiency of our method comes from the fact that it merges locally the constraints of the input QCNs bearing on the same pairs of variables. We define several constraint merging operators in a way to ensure that the induced QCNs merging operator satisfies some expected properties from a logical standpoint.

In this paper we consider the consistency problem of temporal or spatial qualitive constraint networks. A new encoding making it possible to represent and solve this problem in the framework of the prepositional logic is proposed. The definition of this encoding presupposes the existence of a particular order on the basic relations of the qualitative calculus such as that of the conceptual lattice of the interval algebra of Allen.

In this paper, we consider quantitative temporal or spatial constraint networks whose constraints evolve over time in an ultimately periodic fashion. These constraint networks are an extension of STPs (simple temporal problems). We study some properties of these new types of constraint networks. We also propose a constraint propagation algorithm. We show that this algorithm decides the consistency problem in some particular cases

Temporal and spatial reasoning is a central task for numerous applications in many areas of artificial intelligence. For this task, numerous formalisms using the qualitative approach have been proposed. Clearly, these formalisms share a common algebraic structure. In this paper we propose and study a general definition of such formalisms by considering calculi based on basic relations of an arbitrary arity. We also describe the QAT (the qualitative algebra toolkit), a JAVA constraint programming library allowing to handle constraint networks based on those qualitative calculi

We consider qualitative temporal or spatial constraint networks whose constraints evolve over time in an ultimately periodic fashion: after an initial stretch of time, a fixed pattern of constraints (over an interval) is reproduced indefinitely. We propose a local propagation algorithm which is polynomial, and we show that it decides the consistency problem in some particular cases. We also show that the general problem of consistency for such networks is in PSPACE

In this paper, we further investigate the consistency problem for the qualitative temporal calculus INDU introduced by A. K. Pujari et al. (1999). We prove the intractability of the consistency problem for the subset of preconvex relations. On the other hand, we show the tractability of strongly preconvex relations. Furthermore, we also define another interesting set of relations for which the consistency problem can be decided by a method similar to the usual path-consistency method.

In this paper we define the notion of a block algebra, which is based upon a spatial application of Allen's interval algebra. In the p‐dimensional Euclidean space, where p ≥ 1, we consider only blocks whose sides are parallel to the axes of some orthogonal basis. The block algebra consists of a set of relations (the block relations) together with the fundamental operations of composition, converse and intersection. The 13p basic relations of this algebra constitute the exhaustive list of the relations possibly holding between two blocks. We are interested in the problem of testing the consistency of a set of spatial constraints between blocks, i.e. a block network. The consistency question for block networks is NP‐complete. We first extend the notions of convexity and preconvexity to the block algebra. Similarly to the interval algebra case, convexity leads to a tractable set whereas, contrary to the interval algebra case, preconvexity leads to an intractable set. Nevertheless we characterize a tractable subset of the preconvex relations: the strongly preconvex relations. Moreover we show that strong preconvexity and ORD‐Horn representability are the same.