ASA: A conceptual design-support system

Pergamon PIhS0952-1976(96)00080-2

EngngApplic. Artif lntell. Vol. 10, No. 1, pp. 99-111, 1997 © 1997 Elsevier Science Ltd Printed in Great Britain. All rights reserved 0952-1976/97 $17.00 + 0.00

Contributed Paper

ASA: A Conceptual Design-Support System ALBERTO GIRETTI University of Ancona, Italy LUCA SPALAZZI University of Ancona, Italy (Received June 1995; in revised form September 1996) This paper proposes a computational architecture for conceptual design support that integrates typical CAD editing activities with symbolic information processing. The architecture is composed of a knowledge representation server and a variational CAD system. The knowledge-representation server is based on a terminological language which is expressive enough to represent the knowledge involved in a design process, and to support the typical inferences used in a case-based design-support system. The knowledgerepresentation server contains both episodic knowledge, stored as cases in a long-term memory, and general domain knowledge. It supports the usual strategies of case-based design-support systems as case retrieval and case adaptation. The variational CAD environment processes the geometric information. The variational approach to the geometric representation of domain elements separates the metric aspects from the topological aspects of design artefacts. As a consequence, inferences on topology can be performed at a symbolic level, obtaining an increased integration between geometric and symbolic knowledge. The system is part of the ASA project, under development at the University of Ancona. © 1997 Elsevier Science Ltd. All rights reserved

Keywords: Case-based reasoning, terminological languages, CAD, conceptual design, knowledge representation.

design is usually considered as an exploration task, i.e. it involves both the transformation of the initial requirements and the synthesis of the final device. Design is a task that operates on many different representations of the complex real world. Each world model captures only some partial aspects of the reality. Thus the different kinds of knowledge involved in the design process must be integrated (e.g. geometric knowledge, functional and/or behavioural models, past design experience, design process knowledge like histories, failures, etc.). Knowledge integration is quite common in the human practice. As a matter of fact, designers unconsciously integrate many different kinds of knowledge through the propagation of inference effects from one domain to others. For example, during the definition of a house lay-out, i.e. a purely geometric disposition of building elements, an architectural designer frequently makes inferences about lighting and/or thermal aspects, and propagates the effects to the geometrical disposition (mostly as additional constraints). The design activity is usually based on past experience, especially when the problem domain is not completely

1. INTRODUCTION Conceptual design is a human activity which benefits from the application of computer-aided design techniques. In the last decade, there has been an evolution of computer-aided design systems from drafting, calculation and simulation utilities, towards systems that are able to support the conceptual phase of the design processes (Eastman, 1991; Gero, 1993; Haber and Karghenas, 1994). Systems supporting some aspects of conceptual design have been built according to different paradigms, such as task analysis, design prototypes, case-based reasoning, etc. (Yu and Adeli, 1991; Aouad et al., 1994; Chandrasekaran, 1990; Gero, 1990; Maher et al., 1995). The experience gained in conceptual design support has highlighted some issues: • Design cannot be reduced only to a problem-solving task, at least in the sense adopted in the AI community. In fact, design has the further complexity that the requirements (i.e. goals) usually change during the process itself. Thus, Correspondence should be sent to: Luca Spalazzi, Istituto di Informatica, University of Ancona, via Brecce Blanche, 60131 Ancona, Italy [E-mail: [email protected]].

99

I00

ALBERTO GIRETTI and LUCA SPALAZZI: ASA

modelled in a closed form. Experience provides designers with the appropriate guidelines in order to avoid mistakes previously made, to find solutions more efficiently, and to preview solutions. Thus, designers spend part of their time thinking about existing design experience and reviewing the literature, instead of starting from scratch. This involves the designer's ability to recall pieces of past successful designs, and to insert them into a new context according to considerations performed in different domains. Design-support systems (Adeli and Hawkins, 1991; Barber et al., 1992; Berraris and Watson, 1994; Kolodner, 1991) are built with the aim of assisting the designer in the management of extensive and complex knowledge, and of providing some autonomous problem-solving abilities that are usually applied to limited and well-understood domains. Knowledge integration, reuse of past experience and design choice repercussions are the problems usually faced by such support. For example, knowledge integration requires a computational model that is able to represent every kind of processed knowledge uniformly (i.e. by using the same schema). Thus, knowledge integration strongly suggests the use of formal knowledge-representation languages. The reuse of past experience has been addressed by several authors using different approaches (Adeli and Yu, 1995; Kolodner, 1991). This issue plays a central role, especially in case-based reasoning (Kolodner, 1993). Case-based design support (Barber et al., 1992; Kolodner, 1991; Pearce et al., 1992) is the application of case-based reasoning to design support. The main processing cycle of a case-based design system can be summarised in the following phases: problem assessment, key definition, case retrieval, case adaptation, solution evaluation, solution storing, or, in case of failure, failure explanation, failure storing and solution repair. A complete explanation of the above phases and of the issues involved is outside the scope of this paper; the interested reader can find further information in (Kolodner, 1993). The requirement for knowledge integration in a casebased support system is specialised as the integration of episodic knowledge (cases) with general domain knowledge (domain models) (Goel, 1991; Bhatta et al., 1994). Tight integration of general domain knowledge with specific situation knowledge is the main issue involved in the construction of effective reasoning systems in complex, real-world situations. "If we put the two (case based reasoning and model based reasoning) together, letting each provide what it specialises in, we will be able to build robust reasoning systems that can both reason efficiently about generalised situations and cover idiosyncrasies of atypical ones" (Kolodner, 1993, p. 96). A good example of the integration of multiple types of knowledge and reasoning is given in (Goel and Chandrasekaran, 1992). This paper proposes a computational architecture for conceptual design support, called the Architectural Symbolic Assistant (ASA) (Giretti et al., 1994; De Grassi et al., 1996). ASA integrates a case-based reasoning system with several domain models in order to produce a case-based

design-support system. The case-based reasoner adopts a terminological language for knowledge representation. The terminological language has been defined in order to capture the structural properties of the represented knowledge. The resulting knowledge structure uniformly represents both episodic knowledge, stored as cases in a long-term memory, and general domain knowledge. The main topic of this work is the analysis of the application of the formal knowledgerepresentation schema (i.e. the terminological system) to the construction of a case-based design system. Section 2 gives some formal aspects of the knowledge representation, and Section 3 the related basic algorithms. Section 4 describes the architecture of the system. The system inferences, with some examples, are given in Section 5. Finally, Section 6 draws some conclusions.

2. KNOWLEDGE REPRESENTATION Basically, the knowledge involved in a design process can be classified into static knowledge, which describes declarative theories of the application domain, and design task knowledge, which combines design goals with basic inference procedures. The following sections introduce the formalisms used in ASA for the representation of both domain and task knowledge.

2.1. Domain knowledge representation language-ASACL The basic assumption for the description of the application domain is that it is possible to structure the knowledge according to both generalisation/specialisation and part-of relationships. Therefore, the knowledge-representation schema follows the line of the structured knowledge representation (e.g. semantic networks and frames); in particular it reflects many aspects of terminological and feature languages (Plaza, 1995; Schaerf, 1994). On the KLONE line (Brachman and Schmolze, 1985), the basic knowledge-representation object is called a concept. Essentially a concept is a structured description of a meaningful aspect of the application domain; it may be a design element or a domain relationship. So a concept asserts the relevant conditions for the identification of the element or a relationship in a domain status. Indirectly, a concept also projects a classification on the application domain. The syntax and semantics of the ASA Concept Language (ASACL) are outlined below. 2.1.1. Definition 2.1 (ASACL syntax) Let ASA concept names, host concept names, attribute names, function names, and host individual names be distinct sets of symbols. Then concept and attribute terms

are inductively defined as follows: Base: • Every ASA concept name is an ASA concept term • Every host concept name is a host concept term • Every attribute name is an attribute term

ALBERTO GIRETTI and LUCA SPALAZZI: ASA

101

Step: Let C be a concept term. Let D, D~. . . . . D~ be ASA concept terms. Let A, A~. . . . . Ak be attribute terms. Let h~. . . . . h, be host individual names. Let k~, k2 be numbers. Let n be a non negative integer. Let R be a function name. Then:

the set of all domain individuals, then the interpretation of a concept name is a subset of A and the interpretation of an attribute name is a subset of ell × At. Thus the semantics of A S A C L can be formally defined as follows.

• • • • • •

2.1.2. Definition 2.2 (ASACL semantics)

HOST-THING NUMBER SYMBOL STRING (ONE-OF hi "" h,) (RANGE kl k2)

The A S A C L semantics is defined relative to an interpretation L An interpretation I consists of a domain, A, and an interpretation function (.)1. A is divided into two disjoint sets: AA and A n. The interpretation function is recursively defined as follows:

are host concept terms; • ASA-THING • (And D l D2 "'" Dk) • (All A C)

• (RVM Aj A2) • (Test R A l A 2 ... A,) are concept terms; • • • •

THING BOTTOM host concept terms A S A concept terms

are concept terms; • (A I " " A . )

is an attribute term. Roughly speaking, a concept term represents a set of domain individuals. An attribute term is a map among individuals. The term (A~ ... A,,) represents a function composition. T H I N G is a concept representing the whole domain. B O T T O M represents the empty set. The host concepts represent basic data types of the host language (LISP in this case). As a consequence, N U M B E R and ( R A N G E kl kz) represent the set of numbers and an interval respectively. S Y M B O L and ( O N E - O F h~ ... h,,) represent all the symbols and a subset of symbols, respectively. Finally, S T R I N G denotes the set of host strings. The other concepts are used to represent the domain knowledge. (And CI Cz "'" Ck) is the concept sharing the features of Cl C2 "'" Ck, i.e. it is the intersection among the sets of individuals denoted by C1 C2 "'" Ck. (All A C) is a concept with an attribute A filled by instances belonging to C. (RVM A~ A2) denotes the set of individuals where the contents of the A~ and A2 attributes are equal. In practice, A S A C L revealed the utility of attaching a procedure to test whether an individual belongs to a concept. The procedural attachment is represented by the concept (Test R A~ A2 "'" A.). The practice also revealed a useful and recurrent term combination, that is called Rule. It is useful to represent structural relationships among domain elements. (Rule R C (An A21) "'" (A~, Az,,)) is a concept whose attributes An, ..., AI, share respectively the same fillers of the attributes Az~, ..., A2, that belong to a concept C (the structural rule). (Rule R C (An Azl) "'" (AI,, A2,)) is equivalent to (And (All R C) (RVM An (Azj R)) "'" (RVM AI, , (Az, R))). The semantics of A S A C L are inductively defined on the semantics of concept names and attribute names. Let el be

Base: Let H be a host concept name. Let E be an ASA concept name. Let A be an attribute name. Let h, h~. . . . . h, be host individual names. Let k~, k2 be numbers. Let R be a function name. Then: (1) hIeAH (2) THING i: = AA (3) ASA-THING/: = AA (4) HOST-THING/: =A n (5) BO'ITOMI: =0 (6) EICAA (7) HICAn (8) N U M B E R I C A n (9) SYMBOLICAH (10) STRINGICAn (11) (ONE-OF hi "" h , ) l : = { h / . . . . . h,/} (12) (RANGE kl k:)1: = {xl x e N U M B E R 1, x>kl, xi C2) if the set of individuals denoted by C/includes the set denoted by (?2.

102

ALBERTO GIRETTI and LUCA SPALAZZI: ASA

2.1.3. Definition 2.3 (subsumption) Let CI, C2 be concept terms. Then C~ subsumes C2(CL>-C2) w.r.t. I iff C~tDC~. The subsumption relationship captures the generalisation/ specialisation relationship that can be stated between two concepts.

2.2. Task knowledge representation language Design is basically a purposeful activity, in which many strategies are applied in order to accomplish a design goal. The application of a strategy in a design domain produces a transformation of the current state into a new one. Task knowledge is the knowledge related to the representation of goals, strategies and transformations. The ASA Planning Language (ASAPL) is the representation language of goals and strategies, and is based on the basic notion of primitive action. A primitive action is an immediately executable action, i.e. a basic transformation of the domain state. It transforms a set of instances (individuals) into a new one. Any planning expression represents a strategy in terms of (sub-)goals and primitive actions. Strategies are expressed by means of the ASA Planning Language as follows:

2.2.1. Definition 2.3 (ASA planning language--ASAPL) Given the set of concept terms and two disjoint alphabets of symbols, primitive actions and goals; the set of planning expressions is inductively defined as the smallest set such that: if P, P~ . . . . . Pk are planning expressions and C is a concept term, then: • • • • • • • • •

Every primitive action is a planning expression. Every goal is a planning expression. (And P~ Pz "'" P~) is a planning expression. (Or Pi Pz "'" Pk) is a planning expression. (Sub P~ Pz) is a planning expression. (Inelass P C) is a planning expression. (Seq P~ Pz "'" P~,) is a planning expression. (Orelse P~ Pz) is a planning expression. (Iffail Pm Pz P3) is a planning expression.

And, Or, Sub and Inclass are called algebraic operators. Roughly speaking, the effects of (And P~ Pz "'" Pk) and (Or Pm Pz "'" Pk) are the intersection and union respectively of the effects of each strategy P~. (Sub P~ Pz) represents the effects of P~ minus the effects of P2. Seq, Orelse and Iffail are called control structures to handle failures (see Giunchiglia et al., 1994). The effects of (Seq Pt P2) are the effects of P2 applied to the effects of Pv When P~ fails (i.e. the final set of individuals is empty) the overall action fails too. (Orelse P~ P2) denotes the effects of Pi when it does not fail; otherwise the effects of P2- Similarly, (Iffail P~ P, P3) denotes the effects of the sequence P~, P3 when P~ does not fail; otherwise the effects of P> The semantics of planning expressions is inductively defined on the base of the semantics of goals and primitive actions and the starting situation (i.e. the initial set of individuals). Let XJC_AA be the set of all instances reachable by plans; the semantics of a goal G or a primitive action A is the set of all the

transitions

from

A J C X J X X y and

an

individual

to

another

one,

i.e.

GJCXJ X X ~.

2.2.2. Definition 2.4 (semantics of ASAPL) The semantics of ASAPL is defined relative to an interpretation J. The interpretation J consists of a domain XJCA, a starting situation SC_X J, and an interpretation function (.)s s. The interpretation function is recursively defined as follows: Base: Let A be a primitive action. Let G be a goal. Let A J and G J be the semantics of A and G respectively. Then

• GsJ:={(a,b)l a~SA(a,b)EG J} • AsS: = {(a,b)l a ~ SA(a,b) ~_AI}. Step: Let P, P~ . . . . . P k be planning expressions. Let C be a concept term. Then • (And PI P2)Js:= (a,b)l a ~ S A (a,b ) E P ~s U PJsAb ~ im( PJ~s)if) im( P ~s)

• (Or Pi P2)~: = { (a,b )la e S A (a,b ) E PJ~sU P ~sAb E im( Pf ~)U im( P ~s) } • (Sub Pj P2)~: =

{ (a,b)Fa E SA(a,b) E PJlsA(a,b) ¢£PJs) } •

(Inclass P

C ) ss: =

{ (a,b)la ~ SA(a,b) E PJsAb ~ C j } • (Seq PiP2)Ss:= {(Co,C2)lc0~ SA 3c I.(co,cl) ~ PJsA(C.,C2) E (P2) J,,~o } • (Orelse PI P2)~ :=

{ P~s i f P { s = O P{s otherwise • (Iffail PI P2 P3)Ss:=

{ P~s

(Seq Pl P3)~

if P{s=O otherwise.

The language is interpreted by a planner that builds the related plan and applies the plan to the initial set of individuals.

3. ELEMENTARY TASKS 3.1. Subsumption Subsumption is one of the main reasoning services offered by a concept-based system. Terminological languages allow the subsumption relationship to be computed (i.e. defined semantically) using the structure of the concept definition (which is essentially syntactic). The computational complexity of the subsumption algorithm depends on the expressive power of the defined language. An overview is given in Schaerf (1994). The algorithm for the computation of the subsumption relationship in A S A C L is a

ALBERTO GIRETTI and LUCA SPALAZZI: ASA straightforward extension of Borgida and Patel-Schneider (1994). The algorithm is sound but not complete: for any pair of concepts C and D, when the algorithm returns that D subsumes C (D-->C), this guarantees that D I ~ C ~ holds, but the converse is not true. A simplified version of the algorithm is given below. 3.1.1. Algorithm 3.1 (subsumption) Subsumes (D,C): D>--C holds if one of the following conditions is verified:

(1) (2) (3) (4) (5)

C is BOTTOM. D is THING. D is HOST-THING and C is a host concept term. D is NUMBER and C is NUMBER or (RANGE kl k2). D is SYMBOL and C is SYMBOL or (ONE-OF hj ... h,,). (6) D and C are both STRING. (7) D is (RANGE kl k2) and C is (RANGE k3 k4) and kl