ABDUCTION FOR DESIGN
Hideaki Takeda

This paper describes a logical design process model and in particular abduction in it. We
present our model of design processes that consists of abduction, deduction, circumscription, meta-level inference, and multi-world mechanism. In this model, design is a processof re ning descriptions of design objects. Abduction generates object descriptions as ahypothesis, deduction examines validity of the object descriptions proposed by abduction, circumscription maintains knowledge used in abduction and deduction by resolving inconsistency, meta-level inference provides knowledge for abduction, and multi-world
mechanism represents evolution of the object descriptions. Since abduction is crucial partto realize synthesis in design, we clarify the role of abduction in design and develop an
abductive inference for design. Here we de ne abduction as a process making integrated
hypotheses and theories to explain the given facts. It means that (i) not only hypotheses but also theory to explain facts with hypotheses are important part of explanation,and that (ii) integration should be kept both in hypotheses and in theories. To achieve
above features of abduction in a knowledge-based framework, we introduce a segment of
explanatory coherence and superposition of proposition. The former shows connectivity of
explanations and the latter realizes integration of hypotheses. Since abduction contributes
to integration of knowledge, the framework based on abduction gives an answer to deal
with variety of knowledge in CAD systems.

1. Introduction

Recently CAD systems are largely used in industries, and there is no doubtthat CAD systems contribute to increasing design quality and decreasing
designers' routine work like drafting. Although current CAD systems, inwhich geometric modeling is centered, have been developed rapidly and usedwidely, the next generation CAD systems, which can support designers fromthe beginning of design, remain obscure in their concept and realization.
This is mainly because of lack of formal theory for design that can explicate
design and also serve as foundation to realize design activities in computers.
The purpose of this paper is to propose a model of design that is
not only descriptive but also computable (Finger and Dixon, 1989). In
order to establish such a model, we adopt logic as the basic framework, and model design processes as logical reasoning. We have proposed the framework to model design processes in which design is modeled as abduction, deduction, circumscription, and meta-level inference(Takeda, Tomiyama and Yoshikawa, 1992; Takeda, Veerkamp, Tomiyama
and Yoshikawa, 1990; Takeda, Tomiyama, Yoshikawa and Veerkamp, 1990).
In this paper, we focus on abduction in this model. Abduction is crucial partto realize synthesis in design. We clarify the role of abduction in design anddevelop an abductive inference for design.
In the next section, we will discuss our design process model which includes various types of inferences in the logical framework. After we will

2
HIDEAKI TAKEDA
discuss characters of abduction in Section 3, then we will show how suchcharacters can be realized as a knowledge-based inference in Section 4. We
will demonstrate how this inference works in design by using the design
simulator that we implemented to evaluate the design process model in Section 5. We will discuss future directions for this research in Section 6, thensummarize the paper in Section 7.

2. Logical Design Process Modeling2.1. The Logical Framework for Design

In order to describe design processes in the logical framework, we should clarify what we should represent in logic. Although many factors are complexly
related to design, we use three factors which are prerequisite to describe
design processes. These factors are required speci cations, design solutions(design objects), and knowledge. And we interpret design as logical inference
among them.
It may seem natural to take the deductive framework to describe design
processes in logic. In this approach, we can formalize design as follows;
S [ K ` Ds

where S , K , and Ds are sets of formulae that denote required speci cations,knowledge used in design, and design solutions, respectively. Here solutions
are derived from speci cations and knowledge as the results of deduction.
In short, this approach adopts the \design is deduction" paradigm.
Many works which explain design or design processes in logic are basedon this framework in principle. For example, Treur (1991), and Dietterichand Ullman (1987) took this approach, and we also took it in Ref. (Takeda,
Tomiyama and Yoshikawa, 1990).
This \design as deduction" approach may be suitable for routine design,
but it cannot o er a sucient framework for other more exible and complicated design. Although solutions and knowledge are always incomplete indesign, it requires solid and absolute knowledge and solutions.
Then we can use the second framework | the abductive framework. In
this case, speci cations can be derived from design solutions and knowledge.
Ds [ K ` S:

Here design is abduction with knowledge and speci cations.
Coyne (1988) and RESIDUE system (Finger and Genesereth, 1985) standfor this approach for design formalization.
Knowledge represented in this framework is knowledge about objects
themselves, i.e., knowledge about object properties and behaviors, because
formulae in this framework should be prepared to deduce properties and3

ABDUCTION FOR DESIGN

Meta Level Inference

Deduction

Ka

C

O

Ka: Knowledge on actions
Conditionsof object level

Object Level Inference
Circumscription

Ko

Operations to object level(deduction, abduction,
circumscription, etc)

Deduction

Ds

P

Abduction
Ds: Descirptions of objects
P: Descriptions of properties and behaviors of objects
Ko: Knowledge on objects

Fig. 1. The logical design process model

behaviors of objects from descriptions of objects themselves. It is more desirable than knowledge representation in the deductive framework whereknowledge is about how to design.
Furthermore solutions the abductive inference can generate are, by de nition, not de nite solutions but feasible solutions.
Therefore, we adopt the abductive framework as the framework of thelogical formalization of design.
2.2. The Logical Inference Model for Design Processes

The inference model we propose is illustrated in Figure 1. We de ne thedesign process model as a logical inference model.
Here there are two levels in the model, one is the object level and theother is the action level. The object level contains descriptions of design
objects (design solution) Ds, knowledge about objects Ko, and descriptionsof object properties and behaviors P . P can include required speci cations.

4

HIDEAKI TAKEDA

The basic design process is interpreted by iteration of abduction anddeduction that evolve design objects and their properties and behaviors,and circumscription is invoked to resolve inconsistency.
The action level contains knowledge about actions (knowledge about how
to design) Ka, and the meta-level inference is performed to proceed design byspecifying inferences in the object level and operating directly the contentsof Ds, Ko, and P .
Changing of design objects (Ds) is managed by the multi-world mechanism based on a type of modal logic. Every state of design objects in design
processes corresponds to a possible world in modal logic so as to manage
multiple solutions and operations to design processes themselves.
2.2.1. Iteration of Abduction and Deduction as the Basic Process

We regard a design process as an evolutionary process, that is, the design
objects are re ned in step-wise manner. We call each state of step-wise
re nement as a design state. In each state, the following three types of descriptions hold; The rst one is descriptions of the current design solution
which is denoted by Ds. It consists of identi ers of design objects which
are components of the current design solution, and properties and relations
which are necessary to identify the objects. The second one is descriptionsof properties and behaviors of the current design solution, P . It consists ofall kinds of properties and behaviors that the current design solution has.
Required speci cations are included in P . The third one is knowledge thatis available at the current state, Ko. These descriptions are kept consistent
to satisfy the following formula;Ds [ Ko ` P:

Given design knowledge Ko and the required properties P as the speci cations, the designer tries to nd a candidate by abduction, hence, thecurrent descriptions of the design objects are formed. Then deduction is
performed to obtain all the properties of the current solution with respect
to the current available knowledge. It is performed (i) to see what properties the solution has and (ii) to see whether the solution does not contradict
with the given speci cations and knowledge. Then again abduction is performed to evolve the solution more | new descriptions for the next state areformed. If the solution does not satisfy the speci cations or can not evolve
any more, the designer either tries an alternative solution or modi es thedesign knowledge and the speci cations.
This iteration of abduction and deduction continues until the descriptionsof the objects become fully detailed ones that are suitable to hand the next
process (e.g., manufacturing) or reach a situation where no more evolutions
are possible.

ABDUCTION FOR DESIGN

5

2.2.2. Circumscription for Resolution of Inconsistency

Inconsistency in design has not only negative e ects in design but also positive ones. Most cases of inconsistency in design does not mean that knowledge has wrong information essentially, but that knowledge is used in awrong manner. Knowledge is used beyond situations where it is expected
to be used. But it is not impossible to describe all applicable situations inadvance, because it is the nature of knowledge in design that boundary of
applicability is vague.
Here we assume that inconsistency comes from such incompleteness of theknowledge description. Then resolution of inconsistency is to nd implicit
descriptions of knowledge which restrict applicability of knowledge. One
solution to accomplish this process is circumscription (Lifschitz, 1985; McCarthy, 1980).
Circumscription is a type of commonsense reasoning and has been developed to deal with exceptions. In circumscription, exceptions for given contexts can be determined by minimizing logical extensions of the predicates
which represent abnormality with keeping the whole context consistent. Hereabnormality is the implicit description of each piece of knowledge.
When abduction is performed with the modi ed knowledge by circumscription, we can obtain di erent results from before. Thus use of circumscription not only solves inconsistency but also helps design to proceed moreby modifying knowledge.
2.2.3. Meta-level Inference for Actions

We de ned the basic design process as iteration of abduction and deduction
on descriptions of objects, knowledge about objects, and descriptions of object properties and behaviors. We also introduced circumscription to resolveinconsistency.
Although they explain what the designer can do with given knowledge andspeci cations, they can not deal with change of knowledge or speci cations
because such actions require change of axioms or theorems of the logicalsystem and therefore it is out of a logic system.
In order to solve this problem, we introduce a meta-level inference architecture. Metal-level inference architectures for reasoning are suggested bymany researchers. For example, Weyhrauch (1980) proposed FOL which is ameta-level reasoning system based on rst-order logic. Usually the relation
between axioms and theorems in the object-level logical system corresponds
to the atomic formula in the meta-level logical system. In our approach, what
the meta-level system treats as its atomic formula is the relation among descriptions of objects, available knowledge about objects, and descriptions ofobject properties and behaviors in the object-level system. We can represent

6this as follows;

HIDEAKI TAKEDA

Ds [ Ko `LO P , `LM design(Ds; Ko; P ):where `LO and `LM denote derivativeness in the object-level system and in
the meta-level system respectively.
The current condition of the three elements in the object level systems isconstantly reported to the meta-level system, and the results of inference inthe meta-level system are re ected to the object-level system. The re ectionis the change of the condition of the object level system, i.e., either speci cation of the next inference or modi cation of the contents of the threeelements in the object-level system.
Knowledge about how to design can be described as formula in the metalevel system. For example, a rule \if you are designing a certain object g ,you should use knowledge base Kg " can be described as follows;
design(Ds; K; P ) ^ g 2 Ds ! design (Ds; K [ Kg ; P )We can thus describe knowledge like design rules and design procedures inthis level.
02.2.4. Multi-worlds for Representation of Changing

Each element of the object level system (descriptions of objects, available
knowledge about objects, and descriptions of object properties and behaviors) is changed dynamically by either the object-level inference or the metalevel inference. We introduce the multi-world mechanism based on modal
logic to manage this changing.
Since a designer accumulates her or his decisions as the design solution
in step-wise re nement processes, it is crucial to distinguish what is alreadydetermined from what is not determined yet. It is suitable to represent suchsituations by partial semantics. Therefore we can use data logic to represent
them. Data logic (Landman, 1986; Veltman, 1981) is intuitively a version ofmodal logic based on partial semantics. There are three truth values, i.e.,t, f, and u. The third value can be interpreted as undecided . Among thesevalues, a partial-order w is de ned where t w u and f w u are hold. In
this logic, we can access the other possible worlds from a certain possible
world, if the value of every proportion in the world is not lower than thatin the original world with respect to partial-order w. This means that thenext world is more determined one than the current world. The truth value
u is thus expected to fall into either t or f at last.
Since changing of descriptions of object properties and behaviors (logically it means a set of derivable formulae) is monotonic, we can use possible
worlds and accessibility to represent design states and their relations.

7
In this formalization, if a designer obtains two new di erent object descriptions from a single solution, two possible worlds are created as descendants of the current possible world. Revision and retraction of the design
solution means backtracking to the desirable world (the latest world which
does not contradict with the new object descriptions) and creating a newworld as its descendant.
ABDUCTION FOR DESIGN

3. Characters of Abduction in Design

We have presented our model of design processes that consists of abduction,
deduction, circumscription, meta-level inference, and multi-world mechanism. Abduction is crucial part of this model, because it should represent
synthesis in design. Abduction generates object descriptions as a hypothesis, while other types of reasoning assist this process. Deduction examines
validity of the object descriptions proposed by abduction, circumscription
maintains knowledge used in abduction and deduction by resolving inconsistency, meta-level inference provides knowledge for abduction, and multiworld mechanism represents evolution of the object descriptions.
Although we have shown the function of abduction in design, we havenot discussed mechanism how abduction should be performed. We discuss
nature of abduction in design in this section, and then discuss the mechanism
to involve such nature of abduction as an inference in the next section.
3.1. Abduction in Computer Science

C.S. Peirce introduced abduction as the third kind of reasoning in logic inaddition to deduction and induction.
One of important characters of abduction he argued is that direction ofinference in abduction is opposite to that in deduction. For example, hedemonstrated abduction as follows (Peirce, 1935);
The surprising fact C is observed,
But if A were true, C would be a matter of course;
Hence, there is reason to suspect that A is true.
Many logical formalizations for abductive reasoning have been proposed
recently, including Levesque (1989), Poole (1988), Cox and Pietrzykowski(1986), and Finger and Genesereth (1985), but their de nitions for abduction are basically similar, i.e., abduction for an observation O with a theory
T is to nd a hypothesis A which consists of (ground instances of) possible
hypotheses and satis es both A [ T ` O and A [ T is consistent. This de nition is logically sound and suitable to represent the character of abduction
mentioned above.
Unfortunately, this de nition of abduction fails to capture another important character of abduction. Abduction is ampliative reasoning, while

8
HIDEAKI TAKEDA
deduction is merely explicative reasoning. In ampliative inference the conclusion introduces new ideas into our store of knowledge, but it it does notfollow from the premises with necessity (Fann, 1970). In explicative inference the conclusion explicates what is stated in the premises and follows
form the premises necessarily.
Hypotheses generated by the above de nition are de nitely all what can
deduce the given observation with the given theory, and ampliativity is realized just by enumeration of multiple hypotheses.
This clear and de nite abduction is unattractive in design because of complexity and quantity of object structures and knowledge. Since it translates
ampliative ability of abduction into enumeration of multiple hypotheses, itwould generate an enormous number of hypotheses. We need the other way
to interpret ampliative ability of abduction.
The problem lies in the following two issues. One issue is that they put
abduction into a traditional problem solving scheme. It should include not
only problem solving but also problem formation to some extent. Althoughabduction may generate hypotheses by using reasoning like reversed deduction , it does not imply that the whole process of abduction is such reasoning.
The other issue is lack of structures in hypotheses and the background theory. They assume simple and uniform structures that hide crucial problems
in abduction like composition of hypotheses.
In the following discussion, a problem given to abduction to solve is called
an observation. It represents facts in the target world and it is what weshould nd explanation for. Knowledge which is used to nd explanation iscall a background theory. A hypothesis is an idea conjectured by abduction.
Then we will discuss what kind of characters are needed for abduction indesign.
3.2. Explanation = Hypothesis + Theory

When a set of facts is given as an observation, abduction is to make hypotheses that explain the given facts with a background theory. It is important
to show not only proposed hypotheses but also how the background theory is used to explain the facts. One of the requirements that the proposed
hypotheses should satisfy is to show that they can deduce the given facts.
In this deduction, at least the background theory that is used in abduction
should be included in the axiom.
But there are no reasons that the background theory used in abduction
is identical to the whole background theory that exists before abduction. It
is natural to assume that the background theory used in abduction can beextracted from the whole background theory. We call this used backgroundtheory an explanatory theory. Then abduction is to make a hypothesis andan explanatory theory of which combination can explain the given facts.

9
The content of explanatory theories need not be created newly. To create new rules or laws is another abduction problem in a higher level. An
explanatory theory consists of formulae that are selected from the existingbackground theory.
ABDUCTION FOR DESIGN

3.3. Integration of Explanations

As we mentioned, the rst requirement for hypotheses is to derive the observation with the background theory. But it is not sucient to restrict
generation and selection of hypotheses, and some criteria are proposed as
methods, for example, speci city (Pople, 1973) and creditability (Hobbs,
Stickel, Martin and Edwards, 1988).
In this paper, we use integration of explanations for criteria for generating
and selecting explanations, It means how parts of explanation are integrated
together as an explanation, and this criteria is thus to ensure that an explanation is valid to explain observation as a whole. Integration of explanations
has two meanings; One is coherence of explanations that is integration of theway how they explain the observation. It represents plausibility of hypotheses as explanation. We will discuss this problem in Section 4.3. The otheris integration of hypotheses that is how parts of a hypothesis are integrated
together. It represents plausibility of hypotheses themselves. It is related tothe problem how abduction can yield new ideas. We clarify it in the next
subsection.
3.4. Creation of New Ideas

Creation of new ideas in abduction can be realized as new combinationsof propositions in hypotheses. Even if every proposition in a hypothesis iswell-known, combination of these propositions can express a new idea if it
is a new and meaningful combination. Therefore, it is crucial for abduction
to provide meaningful combinations in a hypothesis.
In order to obtain meaningful combinations, members of a hypothesis
should be related to each other. A set of irrelevant propositions does notcarry any new ideas as a hypothesis. Integration of hypotheses to yield new
ideas is therefore to conglomerate propositions which are able to carry newideas.
In design, an important relationship among propositions is sharing ofentities. Combination of propositions in a hypothesis is more important indesign if they share entities, because it forms a description of an object.
Integration of hypotheses in design is, so far, to form conglomerate of
information around entities. More propositions share entities in a hypothesis,
more integrated it is to be able to carry new ideas.

10

HIDEAKI TAKEDAThis problems is signi cant when an explanation needs new entities. Since
each proposition in a hypothesis is proposed as explanation of some propositions in the observation, it can have its own new entities if the explanation
requires entities which are di erent from entities in the observation.
If di erent propositions in the hypothesis can share such newly required
entities, we can obtain a more integrated hypothesis. It means to identify
entities which are introduced independently and therefore have di erent
properties. We call identi cation of di erent entities superposition . It is afusion of di erent concepts and such fusion can produce a new concept. In
abduction this process is performed in order to obtain integrated hypotheses.
We will discuss how to realize it in Section 4.2.
3.5. Abduction as Problem Formation

Abduction can work not only to solve problems but also to generate information to de ne problems.
Since design consists of a lot of ill-de ned problems, it is dicult in design
to de ne space for solution and domain of knowledge (heuristics) for eachproblem in advance. In such domains, abduction can serve to de ne spacefor solution and extent of knowledge to solve the problem preliminarily.
As we have shown in the design process model, abduction in design isused iteratively and develops hypotheses gradually. Each abduction stops its
inference by using some criteria, and generates hypotheses and explanatory
theories gathered from the background theory. Since each hypothesis is not
so de nite, it does not indicate that the hypothesis is a solution exactly,
but that there would exist a solution around the hypothesis. Thus we canuse it as preliminary de nition of space for solution. An explanatory theory
also indicates preliminary de nition of knowledge. Because the explanatory
theory is collected just to explain the observation, it is not all information we
can solve the problem. But at least it is related and maybe needed to solve
the problem. It serves, therefore, the rst de nition of extent of knowledge.
After we obtain preliminary de nitions of space for solution and extent
of knowledge, we can use more de nite methods like deduction.
Furthermore characters of abduction we have explained can generate
other information to de ne problems. We will discuss how these types of
information can be used in a knowledge-based inference in Section 4.4.

4. Formalization of Abduction as a Knowledge-based Inference
We have discussed general characters of abduction in design in the previous
section. In this section we focus on how to realize abduction in the current
knowledge-based framework.

11
Here we provide a rst-order language L, and explanatory hypotheses,
observations, and background theory are written in the rst-order predicate
language. We can de ne abduction as follows;
DEFINITION 1. Explanation.
ABDUCTION FOR DESIGN

An explanation of an observation O with a background theory K0 is hA; K i,
a tuple of an explanatory hypothesis A and an explanatory theory K which
satisfy the following conditions;0 K  K0 ,0 K [ A is consistent,
0 K 6j= O,
0 A [ K j= O, and0 there are no E  A [ K that strati es E j= O.

We can say that a hypothesis A explains an observation O by an explanatory theory K . In this paper, we restrict both observations and hypotheses
to ground formulae, i.e., no variables are appeared in them. Furthermore
observations are given as a set of literals (atomic formulae or negation of
atomic formulae).
This de nition may seem identical to the de nition in Section 3.1, but
an explanation is not a hypothesis but combination of a hypothesis and an
explanatory theory, and the whole background theory is not required to use
in abduction. But we have not de ned how an explanatory theory is takenfrom the background theory, and what an explanatory hypothesis consistsof.
Under this de nition, we then de ne structures of a background theory
and hypotheses to realize integration of explanation.
4.1. Structure in Theory

When designers design even a single object, they usually use various kinds ofknowledge which come from some di erent backgrounds. They can manage
to combine and use such kinds of knowledge which sometimes seem to beinconsistent to each other. It is important for design to deal with such variety
of knowledge.
Instead of assuming a single background theory, we here assume a setof background theories, i.e., the background theory is divided into separate
aspect theories each of which has its own perspective of description. The
perspective of an aspect theory is how to represent phenomena or concepts
as propositions in laws or rules. It is de nition of vocabulary for the aspect.
Furthermore we assume clusters of knowledge in an aspect theory. We
often use some part of an aspect theory instead of the whole aspect theory.
A cluster of knowledge is a unit to handle aspect theories. An aspect theory
consists of a set of clusters.

12

HIDEAKI TAKEDA

We can de ne aspect theories as follows;
DEFINITION 2. Aspect.

An aspect Ai consists of vocabulary Vi , an aspect theory Ki , and clustering of
knowledge KCi = fkcji g. The aspect theory is a set of formulae written withS
the vocabulary, and divided into knowledge clusters, i.e., KCi = j 23C kcji
where 3 is a set of identi ers for knowledge clusters.

We need knowledge to connect di erent aspect theories in order to usethem together. We call it an inter-aspect theory. Since di erent aspect theories may represent the same phenomena or concepts di erently, the interaspect theory holds relations among such representations. Then we can dene the background theory.
DEFINITION 3. Background theory.

The background theory K0 is union of aspect theories Ki and the inter-aspect
theory KI , i.e.,

KU =

[

K i [ KI ;i 3where 3 is a set of aspect identi ers.
2

Then an explanatory theory can be de ned as collection of clusters ofknowledge to explain the given observation (see Figure 2).
DEFINITION 4. Explanatory theory.

An explanatory theory K for the background theory K0 is union of knowledge
clusters taken from aspect theories in the background theory.

Of course this de nition satis es K  K0 .
4.2. Superposition in Hypotheses

Then we can also divide an explanatory hypothesis as follows;
A = AT H [ AI
Here, AT H is the derivative hypothesis that can be derived from the backgroundStheory and the observation. AT H is a set of formulae with vocabulary
V0 = i 3 Vi . AI is the connective hypothesis that integrates members ofthe derivative hypothesis (see Figure 2). A derivative hypothesis AT H alone
can satisfy derivativeness of the observation O, i.e.,
ATH [ K0 j= O:
Since the hypothesis is generated from combination of di erent aspect
theories, it may be merely a set of hypotheses each of which is generated
from an aspect theory. To ensure integration of the hypothesis, we need
the connective hypothesis which combines parts of the derivative hypothesis
together. We realize this connective hypothesis as superposition of entities.
2

ABDUCTION FOR DESIGN

13
Knowledgecluster

Vocabulary

Aspect theory

Aspect1
derivative
hypothesis

hyopothesis

connective
hypothesis

Aspect2

derivative
hypothesis

Explanatory theory

Observation

Fig. 2. Hypothesis and explanatory theory
4.2.1. Instantiation of Entities

An observation is a description about entities, and a hypothesis is anotherdescription about entities appeared in the observation. But in synthesis one
should consider not only entities presented in the observation, but also otherentities needed to solve the given problem. We can call these entities instantiated entities.
Introduction of new entities should be careful because it changes thedegree of integration of explanation. It is one of important criteria to create
and evaluate hypotheses.
Suppose a = ha1; :::; ai i a tuple of constants appeared in the observation,i = hi1 ; :::; ij i a tuple of instantiated constants appeared in the hypothesis
A, and x = hx1 ; :::; xi i a tuple of variables.
Suppose that there are no constants in the explanatory theory.
We can get A(x) by substituting each constant in A, A(x) itself can explain
the observation too, i.e.,
8xA(x) [ K j= O:
Since we need hypotheses of ground formulae, we nd a substitution  to all
variables in A(x) so that A(x) = A (Lloyd, 1984).
We can also represent O as O(y) a where a = fa1=y1; :::; ai=yi g is a
substitution. Then,
8xA(x) [ K j= 8yO(y):Since the observation is given as O(y) a not as O(y), terms which satisfy every predicate in O should be restricted to constants used in the substitution

14
HIDEAKI TAKEDA
a . It means that A(x) [ K [ O should be minimal with respect to each predicate in O. Minimality with respect to a predicate is that the extension of
the predicate (a set of tuples which satisfy the predicate) is minimal (Davis,
1980). The extension of a predicate in O for A(x) [ K [ O should be thesame to the extension for O. This restriction can nd a substitution a for
A(x). Abductive procedures with the resolution principle can nd this substitution. But still A(x)a can have free variables. Then these free variablesin A(x)a are assigned either to instantiated constants or to constants in O.
Here s stands for a substitution from variables to variables, i for a substitution from variables to instantiated constants. Then A = A(x)si a . srepresents identi cation between di erent terms, i.e., the way which entities
in hypotheses should be identi ed.
For example, suppose
f is alive(x) ^ has(x; y) ^ wing(y) ^ is feather(y) ! bird(x);has(x; y ) ^ wing(y ) ^ is big(y ) ! fly(x)g
as K and fbird(a); fly(a)g as O. If there are no ideas to identify entities,
both
A1 = f is alive(a); has(a; b); wing(b); is feather(b); has(a; c);wing(c); is big(c)gand
A2 = fis alive(a); has(a; b); wing (b); is feather(b); is big(b)g
can be hypotheses. The former seems redundant, but both hypotheses areminimal because A1 6 A2 and A1 6 A2 . The di erence is the way how to
introduce entities in hypotheses.
4.2.2. Minimality of Entities in Explanation

One of criteria to integrate hypotheses is minimality of entities. Domain circumscription (McCarthy, 1980) can be used to achieve minimality of entities
in explanations. Domain circumscription nds models that have minimal domains to hold given formulae. In this case A(x)a ^ K ^ O(a) is a formula
to circumscribe. But using domain circumscription without any restrictions
will make undesirable results. For the above example, we can get
fis alive(a); has(a; a); wing(a); is feather(a); is big(a)g
as a hypothesis with domain circumscription. This hypothesis seems unnatural, because we have knowledge about what kind of entities can be uni ed
or not. In this case, entities which can satisfy wing(x) and bird(x) should

15
be di erent, while entities which can satisfy wing(x) can be uni ed to eachother1.
Superposition is identi cation between entities, but it is speci ed by two
propositions which have entities to be identi ed.
Although it is impossible to describe all possible uni able entity relationsin knowledge2, we can postulate at least consistency of aspect theories. Relations among predicates in an aspect are all what are written in the aspect
theory. If two proposition have predicates in the same aspect, they are notallowed to identify unless these predicates are the same.
SupposeK1 = fis alive(x) ^ has(x; y) ^ wing(y) ^ is feather(y) ! bird(x)g
K2 = fpart(x; y) ^ lift force device(y) ! fly(x)g
K = K 1 [ K2
O = bird(a) ^ fly(a)where K1 and K2 are aspect theories. We can get a hypothesis
A = f is alive(a); has(a; b); wing (b); is feather(b); part(a; c);lift force device(c)g:
If we assume superposition
fhas(x; y); part(x; y)gandfwing(x); lift force device(x)g;then the hypothesis is
A = f is alive(a); has(a; b); part(a; b); wing (b); is feather(b);lift force device(b)g:
Notice such superposition is also a hypothesis, and validity of the superposition is examined by deduction and further abduction from the wholeor part of the hypothesis A . In particular, part of the hypothesis which
includes identi ed entities is important in further abduction and deductionin order to realize how the superposition is feasible. In this example, it isfwing(b); is feather(b); lift force device(b)g.
1
It is not a matter of course. If there are more than two entities which
satisfy the same predicate, each of such predicates can be related to di erent
entities.
2
It is the frame problem to enumerate all combinations among predicates(McCarthy and Hayes, 1969).
ABDUCTION FOR DESIGN

0

0

16

HIDEAKI TAKEDA

4.3. Explanatory coherence

Ng and Mooney (1990) proposed explanatory coherence as the primary measure to evaluate the quality of an explanation. Explanatory coherence computes the degree of connectivity of a hypothesis as follows;
XC=

1 i j l

Ni;j

  

Nl(l 0 1)=2

where l is the total number of the observation, N is the total number ofnodes in the proof graph, and Ni;j is the number of distinct nodes nk in the
proof graph such that there is a sequence of directed edges from nk to ni
and also nk to nj where ni and nj are elements of the observation.
This quantity may be useful to compare some tightly connected hypotheses, but we need a more qualitative scale to evaluate coherence of explanations where connectivity is not so tight, and nding connectivity of explanation itself is one of purposes of abduction.
Here we introduce a coherent segment of explanation to evaluate explanations.
DEFINITION 5. When an explanation hA; K i for an observation O is given,a partial explanation hA(O ); K (O )i for the observation O  O is de ned
000

as follows;
A(O0 ) and K (O0 ) are both minimal sets of formulae that satisfy A(O0 ) 
A, K (O0 )  K and A(O0 ) [ K (O0 ) j= O0 .

In case of multiple partial explanations, we denote A(O )[i] and K (O )[i].
DEFINITION 6. Given an explanation hA; K i forS O, O1  O and O2  O
areconnected to each other if and only if i;j (A(O1 )[i] \ A(O2 )[j ]) [S (directly
K (O )[i] \ K (O )[j ]) is non empty. This set is called \direct connection
0

0

1
2
i;j
of explanation between O1 and O2 ".

Direct connection of an explanation corresponds there exists nk for speci ed
ni and nj in Ng and Mooney's de nition.
DEFINITION 7. Given an explanation hA; K i for O, O1  O and O2  O

are indirectly connected to each other if O1 and O2 are directly connected toeach other or there is O3  O that is indirectly connected to both O1 andO2 .

DEFINITION 8. Given an explanation hA; K i for O, if every element ofO  O is indirectly connected to other element in O , and any element in
O 0 O is not indirectly connected to element in O , hA(O ); K (O ); O i is a000

coherent segment of explanation.

0

0

0

0

17
If the number of coherent segments for an explanation is 1, the whole explanation is connected. If the number is more than 1, the explanation includes
some explanations that are not related to each other. This coherent segments
are calculated by tracing dependency of members of hypotheses.
ABDUCTION FOR DESIGN

4.4. Information for Next Inferences

Abduction can generate useful results for next inferences.
As discussed, an explanation consists of not only a hypothesis but also an
explanatory theory. Furthermore we can obtain superposition of propositions
to identify entities, and coherent segments of the explanation.
These types of information are used by two di erent ways, i.e., for successive inference steps, and for inferences to solve similar problems.
Explanatory theories and explanatory coherence are useful for successive
inferences. An explanatory theory is a primary theory for deduction thatis used to con rm the hypothesis proposed by abduction, i.e., deduction
should use at least this theory. And it is also a reference theory for the
next abduction. Clusters of knowledge in an explanatory theory are mostplausible candidate theories for the next abduction.
Explanatory coherence helps us to determine the extent of next problems. If there are some coherence segments, it seems reasonable to divide
the current problem. Even if there is only one coherent segment, we canform sub problems by direct or indirect connections among members in theobservation and the hypothesis.
Explanatory theories and superposition of propositions are useful to solve
similar problems. The sets of clusters that are used in abduction are examples of adherence among knowledge. And superposition of propositions is
also examples of connections among predicates in di erent aspect theories.
By gathering such information, we can develop the inter-aspect theory, or
add more descriptions in meta-level knowledge (see Section 2.2.3).

5. Design simulation
We have been developed a prototype system called design simulator to evaluate our inference model discussed in Section 2 and Section 4. This system
has two purposes. One to show computability of the proposed model, andthe other is to show adaptability to actual design processes. Figure 3 is theoutline of the design simulator and Figure 4 is a snapshot of the system. Thissystem is implemented in Lucid/Allegro Common Lisp, CLX (Common Lisp
X interface), and X11 on Decstation/Sparcstation.
We show how abduction can explain designers' processes by using a simple example taken from protocols in design experiments (Takeda, Hamada,

18

HIDEAKI TAKEDA

Design Simulator
Multi-world
Management
SystemAction-level Inference System
Knowledge-baseon actions

changeof worlds

conditions

operations

justifications

ATMS

Object-level Inference System
abduction
deduction
justifications
circumscription
workspace
Ds

P

Ko

Fig. 3. The architecture of the design simulator

Fig. 4. A snapshot of the design simulator

Knolwedge-baseon objects

aspects

ABDUCTION FOR DESIGN
19
Tomiyama and Yoshikawa, 1990)3 . We interpret this design session as aninference by knowledge. We pick up pieces of protocol (verbal protocol andgures), and represent them as logical formulae. Inference procedures inthe system has been described in Ref. (Takeda, Tomiyama, Yoshikawa and
Veerkamp, 1990).
This session is an interactive process, i.e., every time the system nishes
one step of its inference, it shows results and possible actions to do next,
and then the user speci es one of them.
In this session, we assume ve aspects, i.e., scale aspect, exterior-design
aspect, support-motion aspect, translate-motion aspect, and manufacturing
aspect. These aspects have rules that are representation of designers' knowledge in this design session.
The speci cation is to design a scale. It means to design an object thatcan support and measure given weight (see Figure 5(a)).
Then designers suggest a structure of typical scales(see Figure 5(b)).
Revered lines are newly added members of the hypothesis.
Since \(support sc1 w) (measure sc1 w) (weight w) (quantity
100kg w) (move d w sc1) (displacement d) (quantity 5mm d)" havenot been abduced yet and other members of the hypothesis are connectedto each other at this moment, there are eight coherent segments. Then they
abduce \(support sc1 w)"and get a hypothesis using the following rule;(support *s *w) <(upper-frame *u)(has *s *u)(base-frame *b)(has *s *b)(slide-guide *sl)(connected *sl *u)(connected *sl *b)(pickup *pk)(has *pk *sc)(stopper *st)(connected *st *u)(connected *st *b))This rule introduces \(stopper st14)" and \(slide-guide sl11)', andalso makes these propositions connect to the segment which includes\(upper-frame u3)" and \(base-frame b1)". Thus the number of coherent segments is decreased. Using the exterior-design aspect, they get a new
hypothesis as design descriptions shown in Figure 5(c).
Furthermore they decide to connect the plastic cover and the upper baseby screws. \(connected dp15 ub17)" is abduced to \(screw z18)(fixed
z18 ub17)(fixed z18 dp15)" by a rule in manufacturing aspect, Thenthey notice these screws can be used as the stopper of the vertical movement. They identify \(screw z18)" and \(stopper st14)". Figure 4 is a3This example is taken from other experiments that we used in Ref.
(Takeda, Veerkamp, Tomiyama and Yoshikawa, 1990). According to names
in Ref. (Takeda, Hamada, Tomiyama and Yoshikawa, 1990), we use experiment No. I{1 in this paper, while we used No. I{3 in Ref. (Takeda, Veerkamp,
Tomiyama and Yoshikawa, 1990).

20
HIDEAKI TAKEDA
snapshot of the design simulator when superposition of propositions is asked
to users. Using some other rules, they can get a hypothesis shown in Figure5(d). In this hypothesis, revered lines are descriptions of the entity whichshould play two roles in this design. One problem they should solve next is
to develop and examine descriptions of this entity.

(a)

(b)

(c)

(d)

Fig. 5. Changing of descriptions of design objects

6. Abduction as Fundamental Reasoning in Future CAD

It is important for future CAD systems to keep integration of knowledge.
Nowaday we have been putting models and knowledge from various backgrounds in computer in order to support design. But there are no uni ed
methods to integrate them. Since design is not archived with a single model,
but various perspectives should be taken into account, integration of various
models and knowledge is crucial to realize future CAD systems.
Furthermore future CAD systems should have not only ability of exchang-

21
ing information in various models to each other, but also ability of guiding
use of various models. That is, static and dynamic integration of models are
required.
Methodology to exchange information among models tends to deal with
objects and aspects ontologically, while integrated use of models in design
tends to deal with objects and aspects teleologically. If every relation amongmodels be clear enough, there would be no reason to be teleological. Since
we could not expect such a situation in design, designers assume relations
under their purpose. Then such relations are very vulnerable and should be
examined by experiment and manufacturing. But if it turns out that they
are true and useful relations, then they can be included into ontologicalknowledge.
As an approach to model integration, Tomiyama, Kiriyama, Takeda andXue (1989) proposed the concept of metamodel for a new modeling framework for design objects. The metamodel is used as (1) as a central modelingmechanism to integrate models, (2) as a mechanism for modeling physicalphenomena, and (3) as a tool for describing evolving design objects. Eachmodel in CAD systems is connected only through metamodel where physical phenomena as concepts are used to describe objects. They also proposeda metamodel system based on qualitative physics (Xue, Takeda, Kiriyama,
Tomiyama and Yoshikawa, 1991). Here qualitative physics plays an interaspect theory among models.
The metamodel based on qualitative physics can provide basic and common connections among aspect models, but it is not appropriate to represent and describe integration generated in design processes. Integration of
aspects di ers in every design, and furthermore it is also the goal of design
because objects should be represented as integration of aspects. Abduction
we discussed here is an approach to realize to create such integration.
Abduction can support designers to achieve dynamic integration ofknowledge. As mentioned in Section 4.4, both explanatory theories and superposed propositions represent dynamic integration of knowledge. An explanatory theory is an example of combination of knowledge. Superposed
propositions is also an example how descriptions in di erent aspects can be
related to each other. Accumulation of these examples in successful design
processes shows how knowledge is used in design processes. This information
is useful to re-organize knowledge-bases and aspects as well as to create new
relationship among di erent aspects.
Thus corporation of two types of integration of knowledge could make
CAD systems more exible and more designer-oriented.
ABDUCTION FOR DESIGN22

HIDEAKI TAKEDA

7. Conclusion

In this paper, we explained the logical framework for design processes inwhich iteration of abduction and deduction is main process to proceed design. Since abduction is a key inference in this framework, we investigatedabduction in design, and proposed an abductive inference for design.
Unlike other de nition of abduction, we assumed variety of backgroundtheory, and de ned abduction as reasoning to integrate theories to obtain
explanation. It means that abduction serves not only to obtain hypotheses,
but also to propose integration of background theory. We also demonstrated
how this abductive inference works in design processes.
Since integration of knowledge is a key issue for future CAD systems,
this framework gives an answer to deal with variety of knowledge in CAD
systems.

Acknowledgements

The author would like to thank Prof. yvind Bjrke for his advice and support. The author would also like to thank Prof. Hiroyuki Yoshikawa andProf. Tetsuo Tomiyama of the University of Tokyo. The motivation andbackground material were developed while the author was in the Universityof Tokyo. The help provided by all former colleagues is gratefully acknowledged.

References

Cox, P. and Pietrzykowski, T.: 1986, Causes for events: their computation and applications,Lecture Notes in Computer Science 230, Springer-Verlag, Berlin, pp. 608{621.
Coyne, R.: 1988, Logic Models of Design, Pitman Publishing, London.
Davis, M.: 1980, Notes on the mathematics of non-monotonic reasoning, Ariti cal Intelligence.
Dietterich, T. and Ullman, D.: 1987, FORLOG: A logic-based architecture for design, Rep.
no. 86-30-8, Computer Science Department, Oregon State University.
Fann, K.: 1970, Peirce's Theory of Abduction, Martinus Nijho , The Hague, The Netherlands.
Finger, J. and Genesereth, M.: 1985, RESIDUE: A deductive approach to design synthesis,
Technical report stan-cs-85-1035, Stanford University.
Finger, S. and Dixon, J.: 1989, A review of research in mechanical engineering design. part
I: descriptive, prescriptive, and computer-based models of design processes, Research
in Engineering Design 1(1), 51{67.
Hobbs, J., Stickel, M., Martin, P. and Edwards, D.: 1988, Interpretation as abduction,
Proceedings of 26th Annual Meeting of the Association for Computational Linguistics,
Bu alo, NY, pp. 95{103.
Landman, F.: 1986, Towards a Theory of Information: the Status of Partial Objects in
Semantics, Foris, Dordrecht.
Levesque, H.: 1989, A knowledge-level account of abduction, Proceedings IJCAI-89, Detroit, pp. 1061{1067.

ABDUCTION FOR DESIGN

23

Lifschitz, V.: 1985, Computing circumscription, Proceedings IJCAI-85, Los Angles, CA,
pp. 121{127.
Lloyd, J.: 1984, Foundations of Logic Programming, Springer-Verlag, Berlin.
McCarthy, J.: 1980, Circumscription | a form of non-monotonic reasoning, Arti cialIntelligence 13, 27{39.
McCarthy, J. and Hayes, P.: 1969, Some philosophical problems from the standpoint ofarti cial intelligence, Machine Intelligence 4, 463{502.
Ng, H. and Mooney, R.: 1990, On the role of coherence in abductive explanation, Proceedings AAAI-90, pp. 337{342.
Peirce, C.: 1935, Collected Papers of Charles Sanders Peirce, Vol. 5, Harvard University
Press, Cambridge, MA.
Poole, D.: 1988, A logical framework for default reasoning, Arti cial Intelligence 36, 27{47.
Pople, Jr., H. E.: 1973, On the mechanization of abductive logic, Proceedings IJCAI-73,
Stanford, CA, pp. 147{152.
Takeda, H., Hamada, S., Tomiyama, T. and Yoshikawa, H.: 1990, A cognitive approach of
the analysis of design processes, Design Theory and Methodology { DTM '90 {, The
American Society of Mechanical Engineers (ASME), pp. 153{160.
Takeda, H., Tomiyama, T. and Yoshikawa, H.: 1990, A logical formalization of design processes for intelligent CAD systems, in H. Yoshikawa and T. Holden (eds), Intelligent
CAD, II, North-Holland, Amsterdam, pp. 325{336.
Takeda, H., Tomiyama, T. and Yoshikawa, H.: 1992, A logical and computerable framework for reasoning in design, in D. Taylor and L. Stau er (eds), Design Theory andMethodology { DTM '92 {, The American Society of Mechanical Engineers (ASME),
pp. 167{174.
Takeda, H., Tomiyama, T., Yoshikawa, H. and Veerkamp, P.: 1990, Modeling design processes, Technical Report CS-R9059, Centre for Mathematics and Computer Science(CWI), Amsterdam, The Netherlands.
Takeda, H., Veerkamp, P., Tomiyama, T. and Yoshikawa, H.: 1990, Modeling design processes, AI Magazine 11(4), 37{48.
Tomiyama, T., Kiriyama, T., Takeda, H. and Xue, D.: 1989, Metamodel: A key to intelligent CAD systems, Research in Engineering Design 1, 19{34.
Treur, J.: 1991, A logical framework for design processes, in P. ten Hagen and P. Veerkamp(eds), Intelligent CAD Systems III | Practical Experience and Evaluation, SpringerVerlag, Berlin.
Veltman, F.: 1981, Data semantics, in J.A.G.Groenendijk, T. Janssen and M.B.J.Stokhof(eds), Formal methods in the study of language, Mathematisch Centrum, Amsterdam,
pp. 541{565.
Weyhrauch, R.: 1980, Prolegomena to a theory of mechanized formal reasoning, Arti cialIntelligence 13, 133{170.
Xue, D., Takeda, H., Kiriyama, T., Tomiyama, T. and Yoshikawa, H.: 1991, An intelligent integrated interactive CAD | a preliminary report, Proceedings of the IFIP 5.2
Working Conference on Intelligent Computer Aided Design, Ohio, USA.