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.
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.
Release | Date |
gqr-1500.tar.bz2 | 17.09.2012 |
gqr-1418.tar.bz2 | 11.10.2011 |
gqr-1417.tar.bz2 | 03.05.2011 |
gqr-1298.tar.bz2 | 25.05.2010 |
gqr-1200.tar.bz2 | 02.02.2010 |
gqr-1137.tar.bz2 | 27.12.2009 |
gqr-1089.tar.bz2 | 15.06.2009 |
gqr-729.tar.bz2 | 07.07.2008 |
generic-csp-solving-20102006.tar.gz | 20.10.2006 |
generic-csp-solving-21072006.tar.gz | 21.07.2006 |