An Abductive Constraint System
news and changes
last update: may 2010
Context
The Asystem is a part from a larger project within the Knowledge Representation and Reasoning subgroup in the DTAI reasearch group at the departement of Computerscience, KULeuven.
In that research we investigate the whole process of knowledge engineering: from the high level logical representation (development of the language ID-Logic), through building efficient solvers for (subsets of) that language, e.g. the Asystem, and applying that framework in a number of (large) experiments: repairing inconsistent databases, development of a departemental duties system, AI planning, etc...
In the process of solving of many declarative formulated realworld problems abductive reasoning appears naturally.
For example, abduction has been studied in problem domains such as diagnosis, planning, knowledge assimilation and multi agent coordination.
Despite this variety of applications for abduction and its potential benefits it has not been easy to develop general systems that support abduction which are computationally effective for problems of practical size and complexity.
The Asystem project's main goal is to investigate these issues.
In the past (around the early 90's) several systems have been designed based on different reasoning schema's.
The Asystem merges ideas from three systems: SLDNFA [Denecker and De Schreye], IFF [Fung] and ACLP [Kakas], in a more efficient way.
Basically, it formulates the inference rules of SLDNFA in the form of state rewrite rules as done by the IFF procedure.
The original rules of SLDNFA are extended with rules that handle (finite domain) constraint expressions as proposed by ACLP.
Internally, at the level of implementation, the Asystem uses a similar scheme as finite domain constraint solvers: it will evaluate all deterministic information before it makes a non-deterministic choice.
When all non-determinitic choices are successfully evaluated and all the constraint stores are consistent, a solution is found.
The constraint stores that are constructed during a run, participate actively in the search, i.e. the current state of an constraint store may invoke new derivations or backtracking.
This is achieved by implementing for each constraint domain, that are equational reaoning on Herbrand terms and finite domain constraint expressions, handles that monitor the state of an expression w.r.t. the current constraint store.
These handles take in the Asystem the form of reification.
Since Sicstus Prolog (nor any other Prolog system) comes with a predefined module for equational reasoning on Herbrand terms, the Asystem comes with a novel equality solver for Herbrand terms which supports reification.
Also the Asystem contains a layer on top of the finite domain constraint solver that will provide a similar functionality for general finite domain expressions.
The Asystem is joint work by the following people:
The system
The system's name origin
The name stands for An Abductive System, obviously because it underlying reasoning process is abduction. Moreover it is just one of the systems for knowledge represenation and abductive reasoning.
System Requirements
Which Prolog?
Asystem is written as a meta reasoner in Sicstus Prolog.
We recommend to use at least Sicstus Prolog 3.10.1.
If not available, make sure that the version is older than 3.8.5, because earlier versions of 3.8.x serie have a buggy clp(fd) library.
Recent experiments with the Asystem have uncovered an bug in Sicstus Prolog 3.11.2, which exists in all ealier versions, that might lead to unsound behaviour of the Asystem.
Sicstus Prolog might remove unintented attributes from the variables.
This is notified to the maintainers of Sicstus Prolog and should be solved in the next release.
Which Operating System
Pricipally, the prolog code is OS independent. However the Asystem does some filehandling which use OS (= linux) specific commands.
Also some libraries were (are) not available on the Windows OS, e.g. the timeout module.
This module is not part of the core implementation, but might be triggered by some parameter settings.
In general requires the windows version of the Asystem more validation.
Porting to another Prolog?
In principle it is easy to port to another Prolog.
The main requirements for the Prolog are that it has an interface to a CLP finite domain solver, supports coroutining, and is able to define the type of the variables (by for example attributes).
System Releases
(This software is no longer maintained)
Documentation and applications
Publications and related work
Related Publications
- B. Van Nuffelen, Abductive constraint logic programming: implementation and applications, Ph.D. Thesis, Department of Computer Science, K.U.Leuven, Leuven, Belgium, June, 2004, 315+xxii pages
- A. Kakas, B. Van Nuffelen, and M. Denecker, A-system : Problem solving through abduction , Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (B. Nebel, ed.), vol. 1, Morgan Kaufmann Publishers, Inc, 2001, pp. 591-596.
- B. Van Nuffelen, and A. Kakas, A-system : Programming with abduction, Logic Programming and Nonmonotonic Reasoning, LPNMR 2001, Proceedings (T. Eiter, W. Faber and M. Truszczynski, eds.), LNAI, vol. 2173, Springer Verlag, 2001, pp. 393-396.
- O. Arieli, B. Van Nuffelen, M. Denecker, and M. Bruynooghe, Coherent composition of distributed knowledge-bases through abduction, Logic for Programming, Artificial Intelligence, and Reasoning, 8th International Conference, LPAR 2001, Havana, Cuba, December 3-7, 2001, Proceedings (R. Nieuwenhuis and A. Voronkov, eds.), Lecture Notes in Computer Science, vol. 2250, Springer, 2001, pp. 620-635.
Related Systems
Related systems are sModels and DLV. These systems are based on stable model semantics and focus on the same type of problem domains as we are able to solve.
These systems work in two phases: first grounding the problem (hence they require that the problem can be grounded finitely) and the search for a solution in this ground problem space.