R4-[LogoSpace] - Tools

GQR: A Generic Qualitative Reasoner

GQR (Generic Qualitative Reasoner) is a solver for binary qualitative constraint networks. GQR takes a calculus description and one or more constraint networks as input, and tries to solve the networks using path consistency and backtracking [1,2,3,4].

In contrast to other qualitative reasoners, it offers reasoning services for different calculi. These services are not hard-coded into the program. Both spatial calculi, e.g., RCC-5 and RCC-8, and temporal ones, like Allen's interval algebra, are supported. New logics can be added to the system using a simple text format; no programming is necessary. GQR is currently one of the best reasoning systems for qualitative calculi [5].

The program is designed and implemented with genericity and extensibility in mind, while remaining efficient and scalable. It supports calculi of arbitrary finite size (number of base relations). Developers can work with different data structures and heuristics, and new ones can be easily added to the object-oriented framework.

[1] Zeno Gantner, Matthias Westphal, Stefan Wölfl. GQR - A Fast Reasoner for Binary Qualitative Constraint Calculi, Proceedings of the AAAI'08 Workshop on Spatial and Temporal Reasoning, 2008. pdf
[2] Matthias Westphal, Stefan Wölfl, Zeno Gantner. GQR: A Fast Solver for Binary Qualitative Constraint Networks, AAAI Spring Symposium on Benchmarking of Qualitative Spatial and Temporal Reasoning Systems, 2009. pdf
[3] Matthias Westphal, Stefan Wölfl, Jason Jingshi Li. Restarts and Nogood Recording in Qualitative Constraint-based Reasoning, Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), 2010. pdf
[4] Matthias Westphal, Julien Hué. Nogoods in Qualitative Constraint-based Reasoning, KI 2012: Advances in Artificial Intelligence (KI 2012), 2012. pdf
[5] Matthias Westphal, Stefan Wölfl. Qualitative CSP, finite CSP, and SAT: Comparing methods for qualitative constraint-based reasoning, Proceedings of the 21th International Joint Conference on Artificial Intelligence (IJCAI 2009), 2009. pdf

Download

GQR is available under the GNU General Public License Version 2 or (at your option) any later version.
Download package: gqr-1500.tar.bz2

Run "./configure" and "make" to setup and compile GQR. The GQR binary will be located at "./_build_/default/gqr/gqr". See the included ReadMe.txt for more details (in particular for compilation errors on MacOS).

Changelog

Changes since release 1418:

  • Major code refactoring
  • Search with nogoods and restarts
  • Speed and scalability improvement

 

Changes since release 1417:

  • Ability to compile GQR into a C library (based on the GObject framework)
  • Minor bugfixes for gcc-4.5, data search path, memory leaks, unit tests and waf

 

Changes since release 1298:

  • Compute the splitting of relations into tractable relations on startup (no precomputed cover files)
  • New heap-based queue that supports decrease-key operations used in weighted algebraic closure
  • Remove std::tr1 dependency; GQR now ships with a HashSet class

 

Changes since release 1200:

  • Multiple relation data types precompiled in binary
  • Use trailing-like history to reduce memory consumption within search
  • Fix bug in weighted a-closure and enable weighted a-closure by default

 

Changes since release 1137:

  • reduce memory consumption within the path consistency algorithm
  • new precomputation architecture for calculi operations (improves constraint propagation speed)

 

Changes since release 1089:

  • GCC 4.4.1 compile fix
  • minor search space reduction in 2-way branching DFS with dynamic edge selection

 

Changes since release 729:

  • switched to subcommand commandline structure (subversion style)
  • support for combinations of binary constraint calculi
  • correctly handle calculi whose base relations are non-serial
  • speedup for weighted path consistency scheme
  • more edge ordering heuristics
  • dynamic edge ordering heuristics
  • new default heuristic (dynamic) "weight over learned weights" (a variant of "domain over weighted degree")
  • value ordering according to weight of relations
  • support for eligible edges (Condotta et al.)
  • support for MINCSP calculation

 

Changes since version 20102006:

  • now uses waf as build system
  • added support for x86-64 CPUs (should also work on other 64 bit systems)
  • new class RelationFixedBitset to represent relations as binary vectors
  • added the cardinal directions calculus (cd)
  • introduced some variable ordering heuristics to the backtracking search
  • removed GUI code and Python bindings (will come back in the future)
  • fixed composition table of the occlusion calculus
  • fixed the cover files of the RCC-8 subclasses
  • lots of bugfixes

 

 

All releases

This is the complete list of previously released versions. These are mainly for reference. New users should download the most recent version.

ReleaseDate
gqr-1500.tar.bz217.09.2012
gqr-1418.tar.bz211.10.2011
gqr-1417.tar.bz203.05.2011
gqr-1298.tar.bz225.05.2010
gqr-1200.tar.bz202.02.2010
gqr-1137.tar.bz227.12.2009
gqr-1089.tar.bz215.06.2009
gqr-729.tar.bz207.07.2008
generic-csp-solving-20102006.tar.gz20.10.2006
generic-csp-solving-21072006.tar.gz21.07.2006