A-System: Problem Solving through Abduction

1 Introduction

Over the last two decades it has become clear that abduction can play a central role in addressing a variety of problems in Artificial Intelligence. These problems include diagnosis [Poole et al., 1987; Console et al., 1996], planning [Missiaen et al., 1995; Kakas et al., 2000; Shanahan, 2000] knowledge assimilation and belief revision, [Inoue and Sakama, 1995; Pagnucco, 1996] multi-agent coordination,[Ciampolini et al., 2000; Kowalski and Sadri, 1999] and knowledge intensive learning [Muggleton, 2000; Mooney, 2000].

The essential feature of this abductive approach to problem solving is the fact that it allows the application problems to be formalized directly in their high-level declarative representation. A close link therefore emerges between declarative problem solving in AI and the logical reasoning of abduction. However, despite this variety of applications for abduction and its potential benefits it has not been easy to develop general systems for abduction that are computationally effective for problems of practical size and complexity.

This paper presents a new system, called the BT-System, that supports abductive reasoning within the framework of Abductive Logic Programming (ALP) [Kakas et al., 1998; Denecker and Kakas, 2000]. In this framework problems are

Bert Van Nuffelen and Marc Denecker

Dep. of Computer Science K.U.Leuven Celestijnenlaan 200A B-3000 Leuven, Belgium CUbertv, marcdCV@cs.kuleuven.ac.be

represented in a high-level declarative way with logic programming rules and classical first-order sentences (integrity constraints). Our work aims to examine the possibility of developing ALP into a declarative problem solving framework, suitable for a variety of AI problems, that is computationally viable for problems of practical scale.

A principled implementation of the BT-System is developed based on a hybrid computational model that formalizes the abductive search for a solution in terms of two interleaving processes: the logical reduction of the high-level representation of the problem and lower-level constraint solving. The abductive search is linked tightly to the construction of an associated constraint store.

To validate our approach we have carried out a set of "proof of principle" experiments with an initial implementation of the system that aim to test (a) the general underlying computational behaviour of the BT-System on different domains and (b) the flexibility of the framework to incorporate additional problem specific knowledge in a modular and computationally enhancing way. In particular, some of these experiments are designed to test the extend to which the high-level representation of problems can be computationally improved via extra domain knowledge added to it. The experiments considered include constraint satisfaction problems and standard AI Planning Systems Competition problems.

The BT-System has been developed as a follow up of two earlier ALP systems, the ACLP system [Kakas et al., 2000] and SLDNFAC [Denecker and Schreye, 1998], bringing together features from these two systems. The main development in the design of the BT-System over these previous systems is the fact that the non-determinism in the abductive computation is now made explicit allowing the possibility of implementing this as a form of parameterized heuristic search coupled with a process of deterministic propagation of the state of computation. The BT-System is available from www.cs.kuleuven.ac.be/AOdtai/kt.

2 Declarative Programming with Abduction

Declarative Problem Solving with a high-level representation of the problem at hand is closely related to abduction. The reason for this stems from the fact that in a declarative representation where one describes the expert knowledge on the problem domain rather than some method for its solution often, the task of solving the problems consists in filling the missing information from this representation pertaining to the goal at hand. Typically, in a logical framework of representation the solution consists in finding the extension of some predicate(s) which are incompletely specified in the representation. The high-level theory describing the problem is then extended to a new one such that the problem goal is satisfied.

Computing such extensions of the theory representing our problem is an abductive task. Indeed, abduction as a problem solving method assumes that the general data structure for the solution to a problem (or solution carrier) is at the predicate level and hence that a solution is described in the same terms and level as the problem itself.

A framework for problem solving with abduction therefore needs to be expressing enough to allow high-level declarative representations of complex problems with missing or incomplete information. At the same time for such a framework to have a practical value it should provide ways of improving the computational effectiveness of this high-level representation for any particular problem. One such framework that combines representational expressiveness and computational flexibility is that of Abductive Constraint Logic Programming (ACLP) a framework that integrates together Abductive Logic Programming (ALP) with methods from Constraint Logic Programming (CLP). The A-system is developed within this framework. Let us briefly review the underlying framework of ALP.

A recent way to formalize ALP is to view this as a special case of ID-logic [Denecker, 2000], a logic extending classical logic with inductive definitions. Let a language of predicates, , be given consisting of three disjoint types of predicates: (i)  BW the defined predicates, (ii) BT the open or abducible predicates and (iii) BV the constraint predicates. Then a theory in ALP is defined as follows.

Definition 2.1 An abductive theory is a triple B4BNBTBN
BVB5 where:

• AF  is a constraint logic program where only defined predicates appearing in the head of these rules.
• AF BT is a set of ground abducible atoms over open predicates.
• AF
  BV is a set of first order formulae over , called integrity constraints.

The representation of an application problem in an abductive theory B4BNBTBN
BVB5 splits, in this view of ALP in terms of ID-logic, into two parts. The set of rules in  represents the expert's strong definitional knowledge of the problem, i.e. knowledge which fully determines one or a group of predicates, the defined predicates, in terms of other open predicates. Each rule represents a case in which the defined predicate in the head will be true; the program is an exhaustive enumeration of the cases. The open or abducible predicates have no definition. But some general information about themmay be available indirectly through the expert's weaker assertional knowledge of the problem. This is represented by the theory
BV of integrity constraints. The set BT enumerates all the possible missing "values" for the open predicates. Abductive solutions are build from BT giving a ground (partial) definition of these open predicates.

The constraint predicates are defined, as in CLP, by an underlying constraint theory which is independent of any particular abductive theory B4BNBTBN
BVB5. We will assume that the constraint theory is a finite domain theory that also includes equality over logical terms. The formal details of this are beyond the scope of this paper.

In ALP the abductive problem task is defined as follows.

Definition 2.2 Given an abductive theory B4BNBTBN CCB5 and some query , consisting of a conjunction of literals over , an abductive solution (or explanation) for is a set A1 AIBTof ground abducible atoms together with an answer substitution AI such that  CJ A1 is consistent and:

• AF  CJA1 CYBP BKB4AIB4 B5B5
• AF  CJA1 CYBP
  BVBM

This definition is generic in that it defines the notion of an abductive solution in terms of any given semantics of standard (constraint) Logic Programming (LP). Each particular choice of semantics defines its own entailment relation CYBP and hence its own notion of what is an abductive solution. In the context of ID-logic, its inductive definition semantics essentially coincides with the well-founded model semantics [Gelder et al., 1991] for LP when this is a two valued model 1 . In the rest of this paper we will be adopting this well-founded model semantics for LP for the development of our BT-System.

A computed abductive solution A1 therefore gives a ground definition of the open predicates which in turn through the logic program,  CJ A1, extends this to the defined predicates.

As an example of an abductive theory we give below a part of the theory representing a planning domain. In this, CSD6CXDACT DACTCWCXCRD0CT, is the only open predicate, BO, AK, BIBP are constraint predicates and all others are defined predicates. The predicates DACTCWCXCRD0CT, D0D3CRCPD8CXD3D2 and D8CXD1CT are simple predicates defining the finite domain of variables, e.g. using CLP notation DACTCWCXCRD0CTB4CC D6D9CRCZB5 BM A0CC D6D9CRCZ CXD2 BDBMBMBDBC for a problemwhere we have ten trucks.

DACTCWCXCRD0CT CPD8B4CC D6D9CRCZBN D3CRBN CC B5 BM A0 CXD2CXD8 DACTCWCXCRD0CT CPD8B4CCD6D9CRCZBN D3CRB5BN BMCRD0CXD4D4CTCS DACTCWCXCRD0CT CPD8B4CC D6D9CRCZBN D3CRBN BCBN CC B5 2 BM DACTCWCXCRD0CT CPD8B4CC D6D9CRCZBN D3CRBN CC B5 BM A0 CSD6CXDACT DACTCWCXCRD0CTB4CCD6D9CRCZBN D3CRBNBXB5BN BX BO CCBN BMCRD0CXD4D4CTCS DACTCWCXCRD0CT CPD8B4CC D6D9CRCZBN D3CRBN BXBN CC B5BM CRD0CXD4D4CTCS DACTCWCXCRD0CT CPD8B4CC D6D9CRCZBN D3CRBDBN BXBN CC B5 BM A0 CSD6CXDACT DACTCWCXCRD0CTB4CCD6D9CRCZBN D3CRBEBNBVB5BN D3CRBE BIBP D3CRBDBN BX AK BVBN BV BO CCBM D4D6CTCR DACTCWCXCRD0CTB4CCD6D9CRCZBN D3CRBN CCB5 BM A0 DACTCWCXCRD0CTB4CC D6D9CRCZB5BN D0D3CRCPD8CXD3D2B4D3CRB5BN D8CXD1CTB4CC B5BN D4CTD8D6D3D0 CXD2B4CCD6D9CRCZBN CCB5BM BKCC D6CRBN D3CRBN CC BM CSD6CXDACT DACTCWCXCRD0CTB4CCD6CRBN D3CRBN CCB5AX D4D6CTCR DACTCWCXCRD0CTB4CCD6CRBND3CRBN CCB5BM

1 The formal details of this are beyond the scope of this paper.

The initial state of the problem is given by a set of facts in the logic program  including statements of the form CXD2CXD8 DACTCWCXCRD0CT CPD8B4CCD6D9CRCZBN D3CRB5, e.g. CXD2CXD8 DACTCWCXCRD0CT CPD8B4D8D6D9CRCZBDBN CRCXD8DDBD BDB5BM

3 BT-System and Abductive Search

The computation of an abductive solution in the BT-System can be seen as a process of reduction of the query, , to a set of abducible hypotheses on the open predicates together with an associated constraint store BV CB of constraints over the general finite domain constraint theory supported by the particular ALP framework. This is similar to the computation of CLP with two important differences.

First the reduction involves through the hypotheses also a reduction of the integrity constraints
BV. Effectively, when a new abductive hypothesis is made the integrity constraints need to be re-evaluated to remain true. This satisfaction of the
BV can result in new constraints for the constraint store BV CB and possibly new goals at the same level as the original query. The second difference with CLP is the way that the constraint store BV CB is used in this reduction. As we will see in the next subsection, this is not merely a passive store of constraints to be evaluated at the end of the reduction but it is used actively during the reduction to affect the search. For example, it enables reductions to be pruned early by setting new constraints in BV CB provided that this remains satisfiable.

3.1 Abductive Inference in the BT-System

The logical reduction of a query in the BT-System can be defined as a derivation for through a rewriting process between states. We give here in brief the formal details of this.

A computational restriction on the form of the integrity constraints,
BV, of an abductive theory B4BN BTBN
BVB5 is imposed in the BT-System. These sentences must be (or should be transformed to classically equivalent sentences) of the form: BKBMB4D0 BD BN BM BM BM BN D0 D2 B5 where each D0 CX is a literal. Such an integrity constraint will also be called a denial or a negative goal and will be denoted by AW D0 BD BN BM BM BM BN D0 D2 . Also to simplify the presentation, we assume that each rule in  is of the form D4B4CGB5 AW BUCJCGBNCG CX CL where all variables are (implicitly) universally quantified, referred to as free variables, and BUCJCGBN CH CL is a conjunction of literals with free variables CG occurring in the head and CH occurring only in the body. Rules are therefore in homogeneous form where no non-variable term can appear in their head e.g. a rule D4B4CRB5 AW D5B4CH B5 will be written equivalently as D4B4CGB5 AW CG BP CRBN D5B4CH B5.

A state CB of the derivation consists of two types of elements: a set of literals (possibly with free variables), called positive goals, and a set of denials, called negative goals, of the form BKCGBM AW BYCJCGBN CH CL where BYCJCGBN CH CL is a conjunction of literals and CH are free variables. A1B4CBB5 denotes the set of abducible atoms in CB, i.e. positive goal atoms whose predicate is an open predicate and BVB4CBB5 denotes the set of positive constraint atoms in CB. A derivation for starts with an initial state consisting of the literals of the query as positive goals and all the denials in
BV as negative goals. The rewriting derivation proceeds by selecting a literal in a goal of CB and applying a suitable inference rule yielding a new state. The main inference rules are given by the following rewrite rules (different elements of CB are separated by ";"):

• AF D4B4D8B5 B5 BU CX CJD8CL if D4 is a defined predicate and D4B4CGB5 AW BU CX CJCGCL a rule.
• AF D4B4D8B5 B5 D8 BP D7 if D4 is an open predicate and D4B4D7B5 BE CB.
• AF BMBTB5AWBT.
• AF BKCGBM AW D4B4D8B5BN B5 BY BD BN BMBMBMBN BY D2 (D4 a defined predicate) where BY CX BP BKCG BC BNCG CX BM AW BU CX CJD8BNCG CX CLBN for each rule D4B4CH B5 AWBU CX CJCH BNCG CX CL, (CG BC AI CG).
• AF BKCGBM AW D4B4D8B5BN B5 BKCGBM AW D4B4D8B5BN BN BY BD BN BMBMBMBN BY D2 (D4 an open predicate) where BY CX BP BKCG BC BM AW D8 BP D7BN for each D4B4D7 CX B5 an abduced atom in CB, (CG BC AI CG).
• AF BKCGBM AW BVBN B5 BMBVBN if BV is a constraint atom without universally quantified variables.
• AF BKCGBM AWBVBN B5BVBN BKCGBM AW BN if BV is a constraint atom without universally quantified variables.
• AF BKCGBM AW BMBTBN B5 BT if BT does not contain universally quantified variables.

A successful derivation terminates with a state CB such that:

1. CB contains positive goals only of the form of abducible atoms or constraint atoms,
2. negative goals in CB are denials containing some open atom D4B4D8B5 which has already been selected and resolved with each abduced atom D4B4D7B5 BE CB, and
3. the constraint store BVB4CBB5 of CB is satisfiable.

Otherwise, the derivation flounders when universally quantified variables appear in the selected literal in a denial. If the derivation does not succeed or flounder then it fails. Note that negation as failure in  is simply re-written (via the 3rd rule) to a denial of the positive atom.

Let CB be the final state of a successful derivation. Then any substitution AI that assigns a ground term to each free variable of CB and which satisfies the constraint store BVB4CBB5 is called a solution substitution of CB. Such a substitution always exists since BVB4CBB5 is satisfiable for a successful derivation.

Theorem 3.1 Let B4BNBTBN
BVB5 be an abductive theory s.t.  CYBP
BV, a query, CB the final state of a successful derivation for and AI a solution substitution of CB. Then the pair AIB4A1B4CBB5B5 and AI is an abductive solution of .

3.2 Abductive Search

The search for an abductive solution in the BT-System based on the above proof theory, depends very closely on the computed constraint store. Typically, the abducible hypotheses made during the computation are non-ground atoms whose variables are restricted by the constraints in the associated constraint store of the computation. This constraint store plays a central role not only in carrying (together with the abducibles) the solution but also in controlling the abductive search.

In many respects the computation can be viewed as a process of constructing a constraint store from the high-level specification and query of the abductive theory as any decision that we take, e.g. which abducible to introduce or how to satisfy an integrity constraint, extends differently the current constraint store. Hence we can turn things around and use the constraint store to guide the decisions that we make in this abductive search.

The overall pattern of the abductive computation in the BT-System is as follows:

1. Deterministic Propagation of +ve and -ve Goals
2. Suspend and Evaluate Choices
3. (a) Quasi-consistency of -ve Goals
4. (b) Evaluate Choices on +ve goals
5. Global set of Choices: new +ve Goals, BZ D2CTDB
6. If BZ D2CTDB non-empty then Return to (1)
7. Otherwise, Exit and Ground Solution.

The computation starts with a phase of deterministic propagation where all of the current goals that have only one possible rewriting are reduced until no such goals are left in the resulting state of the computation. The purpose of this phase is two-fold: (a) to expose and collect all the choice points in the current state of the computation and (b) to propagate the construction of the constraint store with all new constraints that are necessarily imposed under the choices made so far in the previous iteration steps. The updated constraint store is checked for satisfiability during this phase as it grows. This can have a significant effect on the computation as it enables us to detect early the ensuing failure of the choices made prior to this before committing to other choices.

All the choice points exposed by this deterministic phase are suspended and a new process of their evaluation begins. This explicit handling of the non-determinism in the computation allows the use of a parameterized form of heuristic search where a variety of different types of heuristics can be used. There are essentially two types of choices in the computation. These are (1) a choice of which rule from the program to use in rewriting a positive goal (cf. first and second rewrite rule) and (2) a choice of which way to satisfy a denial (cf. last three rewrite rules).

The choice points of the second type are considered in a phase called quasi-consistency 3 where we try to satisfy all the denials in the current state together if possible without the introduction of new positive goals. Choices result in a new possible constraint store, that we can compute by a subsidiary phase of deterministic propagation. The "quality" of this ensuing constraint store under various criteria, e.g. tightness of its finite domain variables or minimal change in the current constraint store, forms a possible heuristic criterion. A second criterion concerns the number and complexity of the new positive goals, that a choice would produce. For example, preferring new goals which are deterministic or which introduce new abducibles whose associated denials would have a simple form are different possibilities that we are currently exploring here in the implementation of the BT-System.

3 This name reflects the fact that at this stage of the computation the satisfaction of the integrity constraint denials is in general contingent on a set of new goals.

After the phase of quasi-consistency the computation examines the other choice points left suspended, namely positive goals which are non-deterministic, and again it can apply a form of heuristic evaluation to choose amongst the different possibilities. Once a global decision is taken on all these choice points the computation either returns to the top to repeat the process, when the choice leads to new positive goals, or otherwise, it terminates successfully by labeling the constraint store and thus grounding the abductive solution.

This global approach, of the BT-System to choice making where it tries to cover together as many choice points as possible results in more informed decisions leading to less backtracking and thus to a better computational performance. It also facilitates the use of heuristics by helping to parameterize them and make them available at the top level.

An important parameter of the computation is the degree to which the constraint store is examined for its satisfiability (and other quality measures) during its construction. One possibility is to do a full check of the whole store at each point where this grows. But this can be costly as a large part of this maybe unnecessary. On the other hand an incomplete check may result in the late (after several choices) recognition of the inconsistency of the constraint store. An intermediate possibility is to localizing the check to the latest addition to the store, i.e to the variables of the current constraints and other variables connected to these by constraints already in the store. This induces a form of dynamic partition of the constraint store into connected components that reflects, to a certain extend, the high-level structure of the problem and query at hand and could help minimize the computation required to check the satisfiability of the store.

4 Experiments with the A-System

A number of different experiments have been carried out to test the underlying general computational behaviour of (an initial implementation of) the BT-System and how this can be affected by extending the high-level representation of problems with additional information.

The current version of the system is implemented as a meta-program on top of Sicstus Prolog 3.8.5 and uses its finite domain constraint solver. It is developed as an experimentation tool to test different datastructures and strategies. Currently a form of indexing on the abducibles and constraints is used in the datastructures. With respect to the parameters of the abductive search presented in the previous section the current version implements only a very basic form of heuristics. In particular, the methods used for checking the satisfiability of the constraint store during its construction are simple.

A first set of experiments consists of problems whose specification can be reduced to a finite domain constraint store in one phase of reduction. Such problems include standard constraint satisfaction problems, e.g. N-Queens, Graph Coloring and Scheduling problems. The aim here was to confirm that the execution will be deterministic and to compare the execution time with that of solving the problem directly in CLP to see the overhead cost of the reduction of the high-level representation of the problem. The tables below show a sample of these experiments for the N-Queens problem and a graph coloring problem. For the graph coloring experiment a set of 4-colorable planar graphs were constructed. The run times are split into the time needed to find an abductive solution and the subsequent time needed to ground this by the CLP labeling. All experiments reported in this paper are done on a Linux machine (800 Mhz) with 512 MB of memory.

Graph Coloring

Although the reduction of the whole specification is done in one step (no backtracking occurs over the abductive solution) in both experiments the construction time (abductive solution) increases clearly with the size. So the metainterpreter is some orders slower than the Prolog below, which is used in a CLP-program to set up the constraints.

Another set of experiments was carried out on planning problems. These are non-deterministic problems where the abductive computation and search of the BT-System can be tested. We selected from the latest AIPS2000 planning competition two domains: blocks world and logistics. The next table shows the performance of the system on the blocks world domain. For this experiment we used a specification with one action move(X,Y,T), which denotes moving a block X onto Y at time T.

The second considered domain is that of logistics. For this domain a specification with functors and the general event calculus is used. Futhermore the specification is two layered: the top layer is a compact high level description of the logistics domain. The lower level actions (from the original AIPS strips description) are derived from the high level ones. The first table below shows the performance of the BT-System on problems where the system has been used to compute only high-level abstract plans. The length of the plans are given by the final time when the goal is achieved (first number in the column) and the number of abduced actions describing the actual plan. A blank entry indicates that the system was unable to find a solution within a given time limit.

The results for the low level plans are presented in a second table. These plans are computed in a separated phase using as input the previous computed high level plans. This step expands the high level plans in number of time points and

actions.

High level solutions

Low level solutions

Some of the problems took a while to return a solution. Because the finite domain solver is incomplete, the BT-System may go on with a branch although the constraint store is already unsatisfiable (see the marked entries in the above tables). We tried different satisfiability checks but none of them was overall successful. A parameter in such a check is the domain size of the variables (see the last column of the table of the high level plans): by decreasing the maximal number of time points the satisfiability check fails faster when the constraint store is insatisfiable. As consequence some problems could be solved in a reasonable time. Currently, we are investigating how we can improve this satisfiablity check.

Compared to previous experiments with SLDNFAC and ACLP, the BT-System is more reliable and more robust to changes in the order of execution of the query. However because the constraint solver is incomplete it still possible to have one derivation of BT-System failing to find a solution and another one finding it immediately. Another main difference of the BT-System with these previous systems is its separation of search and inference. This allows easy experimentation with several strategies and different degrees of deterministic propagation.

5 RelatedWork and Conclusions

There are several other abductive systems for ALP that have recently been developed. Different methods have been used e.g. bottom up computation [Iwayama and Satoh, 2000], tabling [Alferes et al., 1999] and rewriting rules with the completion [Fung and Kowalski, 1997; Kowalski et al., 1998]. The BT-System with its two earlier ALP systems, the ACLP system and SLDNFAC, is to our knowledge the first abductive system that has paid particular attention to the computational aspects of abduction using constraint solving extensively to control the abductive search and enhance its computational behaviour.

On a more abstract level our work is related to Answer Set Programming(ASP) [Gelfond and Lifschitz, 1991]. Strong connections have been established [Satoh and Iwayama, 1991] between ALP and ASP. At the level of semantics these two frameworks are for a large class of theories (ASP admits only a special type of integrity constraints) equivalent.

At the level of computation our construction of an abductive solution in the BT-System corresponds to the generation of a model in ASP but there are some significant differences in the respective computational models. It is therefore instructive to develop systematic experiments to compare systems from these two approaches to declarative problem solving.

The abductive search in the BT-System can be parametrized in a variety of ways to reflect the type of cooperation with constraint solver and the heuristics that are used. An important future development of the system is to structure further this parametric space and to study howmore techniques from constraint programming and advanced heuristic search can be incorporated in order to improve the general computational behaviour of the framework on a variety of problems. In particular, we can study how recent heuristic methods for planning [Bonet and Geffner, 1999] can be generalized to the abductive computation of the BT-System.

This general improvement of the underlying computational efficiency of the ALP framework, or indeed of any other declarative problem solving framework, is clearly limited as we are aiming to use the framework on a general variety of problems. A complementary line of development of the BT-System and its associated ALP framework concerns the study of how to provide a programming environment where the user has the facility to incrementally refine her/his high-level representation of the problem in a modular way. A general methodology for declarative problem solving with abduction is emerging where the ALP modeling environment provides the possibility for extra problem specific (declarative or control) knowledge to be included that would enhance its computational performance.