The QAT project

The aim of the QAT project (Qualitative Algebras Toolkit) is to provide tools and libraries for the qualitative algebras manipulated in the context of the qualitative spatial and temporal reasoning. More particularly, this site provides :

a set of XML files containing the definitions of several qualitative algebras,
a library written in Java allowing to manipulate qualitative algebras and qualitative networks defined on these algebras,
a benchmark containing a set of qualitative CSPs.

Representing and reasoning about spatial and temporal information is an important task in many applications, such as in geographical information system (GIS), knowledge representation, robot navigation, scheduling and pattern recognition, temporal and spatial planning, archeology and genetics,... Qualitative spatial and temporal reasoning aims to describe a qualitative relationships between spatial and temporal reasoning.

In the literature, A number of qualitative constraint calculi have been developed in the past two decades (Interval Algebra, Point Algebra, Cyclic Point Algebra, INDU, RCC5, RCC8, ...). The Temporal or spatial information about the configuration of a specific set of entities can be represented using a particular kind of constraint networks called qualitative constraint networks, or QCNs for short. A QCN consists of a set of variables, a set of possible values for each variable (its domain) and a set of constraints defining the allowed tuples of values for the variables (a special case of discrete CSP). For QCN case, the domain of each variable is infinite, so you must find efficient methods to deal such problem.

QAT (for Qualitative Algebra Toolkit) is a open java constraint programming library developed at CRIL-CNRS. at the university of Artois. QAT aims to provide open and generic tools for defining and manipulating qualitative algebras and qualitative networks based on these algebras. While programs proposed in the literature for using qualitative formalisms are ad hoc implementations for a specific algebra and for specific solving methods, the QAT allows the user to define arbitrary qualitative algebra (including non-binary algebra, the product Cartesian of two or more defined algebras for example) by using a simple XML file.

We represent a QCN instance by a simple XML file. file containing the information about the instance (variables number, constraints, ...).

To compare the efficiency of different QCN algorithms, some few random QCN models have been widely used experimentally to generate benchmark instances in the past decade. To overcome the trivial asymptotic insolubility of such models, because the lack of benchmarks instances we first propose an alternative random QCN models to generate benchmarks instances for any used algebra.

last update: 15 jan. 2006.