Key Centre of Design ComputingDepartment of Architectural and Design ScienceThe University of Sydney NSW 2006 Australiae-mail: {john, kaz}@arch.usyd.edu.au

Abstract. We propose an exploration model of design based on the extension of the space of design behaviours using analogy. The analogy is drawn on the basis of structure similarity or structure and behaviour similarity between source and target designs. New behaviours are introduced from the source design. This paper describes such a process and discusses its significance for creative design.

One way to describe a design process is through a structure-behaviour-function (S-B-F) framework (Gero, 1990). Each design here is represented as a triplet of points in three different spaces, which represent three levels of abstraction: the structure space, S which describes the elements and their relationships in an artefact (list of design variables); the behaviour space B of derived properties of the artefact (list of performance or criteria variables) and the function space F which defines the artefact’s teleology. Essentially, structure space includes all the variables whose values can be directly decided upon and measured from the artefact (or its computational model) and behaviour space includes all the variables whose values are important to the quality of design and which cannot be measured directly from a model of the artefact but should be computed using only variables whose values can be `measured' in structure space. The union of these three spaces produces the state space of a design problem D=SÈ BÈ F, Figure 1. A model of design based on this framework includes also knowledge which is necessary to support mappings between S, B and F, ranges of variables, constraints, etc. Ranges of variables and constraints define a feasible subset of D: DÌ D which contains all feasible designs and where search for the best or an appropriate design is to be conducted. Correspondingly, the feasible subsets of three subspaces are: SÌ S, BÌ B and FÌ F . The design state space D represents a conceptual view of designing.

Routine design processes in this framework are characterised by a fixed D and D and are represented by a search process in a well-defined, fixed and bounded (although in some case countably infinite) space S which is governed by a set of criteria defined by components of B (Gero, 1996). In other words, the space of all possible designs S is given and the goal is to choose which one of them has the best values of the set of given behaviours B. This space of design alternatives S is defined (known) a priori before the designing process is started and remains the same throughout this process. The set of desired behaviours required from an artefact is also chosen a priori before the designing process is started and remains unchanged throughout this process. The constancy of the spaces S and B simply means that a complete set of design variables is chosen a priori and what is left to be done by the designer is to choose an appropriate set of values for these variables. In this model routine designing is viewed essentially as an optimisation or constraint satisfaction problem with search state space S and multi-criterion objective defined by B.

It is widely accepted that one way creative designing processes differs from routine designing processes is that the search processes are augmented by exploration processes during which a new design state space is created (Gero, 1996). Usually this new state space is not created from scratch but rather by modification of the current space: D t D^m . By definition this modification always includes the addition of new areas to the state space, Figure 2. Gero (1990), argued that if the new modified D^m still is a subset of the same initial S and therefore can be reduced to changes in ranges of existing design variables and does not require introduction of additional variables then a search in such D^m corresponds to an innovative design process. If the replacement of D with D^m does require adding some new design variables — new dimensions to S (that is, S ^m Ë S) only then is there a creative design process. This approach allows us to model a creative design process as sequence of periods when a temporarily fixed S is searched followed by periods when S is replaced with a modified S^m The block-schema of an algorithm where search and exploration stages are executed cyclically is shown in Figure 3. One can view this approach as an attempt to model a creative design problem as a sequence of routine design problems.

Gero (1996) suggested that five fundamental processes can be used as computational engines to produce a new S^m - emergence, combination, mutation, first principles and analogy. In this paper we will use analogy. Although any of the three components spaces S, B and F can be changed when S is replaced with S^m the majority of the creative design models so far proposed deal with the changes to a structure state space S only and leave the B and F spaces unchanged. They yield a search in a changing space of possible designs S (that is, search accompanied by introduction of new structure variables) governed by the same fixed set of behaviours B. In this paper we describe a design approach which is driven by the requirement to modify the behaviour state B t B^m produced by the introduction of new dimensions to B. This approach is a particular case of a general approach, shown in Figure 3. Its exploration stage always includes the replacement of B by a higher dimensioned B^m and sometimes a consequential replacement of S by a higher dimensioned S^m, Figure 4. Since B^mË B this is a model of a creative and not an innovative design process. Essentially, this means that the criteria which are used to evaluate designs are changed during designing. Those criteria changes may or may not require a change in the corresponding structure space.

Analogy is accepted as one important process in modelling creative designing. Basically if one tries to solve some problem (called a target problem) using analogy he/she looks for some other problem which is somehow similar to the target problem (called a source problem) and whose solution is known and then attempts to construct a solution to the target problem by adapting a solution from the source problem (transformational analogy) or using a successful problem solving process from source problem (derivational analogy). Many formalisation of analogy processes has been developed, see for example Carbonell (1986), French (1995), Keane (1988), Mitchell (1993), and Prieditis (1988).

1. matching and retrieval stage: the similarity of each design from an archive and the target design is evaluated; the design with the highest degree of similarity D_S(i) : (for which SIM(D_T,D_S(i))=max_kSIM(D_T,D_S(k)), where SIM(*,*) is a real function which measures a degree of similarity (matching) between its parameter spaces, D_S(i) is the i-th source design state space, D_T is the target design state space) is retrieved for further processing;
2. mapping and transformation stage: D^m=t (D_TÈ M(D_S (i))). Here M is a mapping operation and t is a transformation operator. Mapping adds some design variables from D_S (i) into D_T and then t transforms the result of this operation into a modified design space D^m .
3. knowledge construction stage: first, the knowledge from the target design state space is passed to the modified design state space; then the analysis of the D^m is carried out to determine if any the relationships in it are not supported by its current knowledge ; if some are not then additional parts of knowledge from the source state space are identified and added to the current knowledge of the modified design state space. We use standard realisations of this knowledge construction step (see for example Qian and Gero, 1996).

Depending on which subspace of D is used to match the source and target designs and which is used to construct the new D^m the analogy-based design process could belong to one of three following types:

1. A similarity between structure spaces D_S and D_T is used to match and retrieve a source design, the similarity function is defined as SIM(S_T,S_S) . Then parts of S_S are used to modify S_T by mapping S_S on to it and then transforming its result : S^m=t (S_TÈ M(S_S )). B_T and F_T become B^m and F^m without change. Then the analysis of S^m is used as a guide for the knowledge construction process by adding the necessary knowledge components from the source design to the knowledge in the target design. The operations of this algorithm is shown in Figure 5.
2. A similarity between behaviour spaces B_S and B_T is used to match and retrieve a source design , the similarity function is defined as SIM(B_T,B_S), where B_T and B_S are behaviour component-spaces of D_T and D_S correspondingly. The structure space S_T is used to modify the structure space of the target design by mapping S_S onto it and transforming the result of this operation: S^m=t (S_TÈ M(S_S)). B_T and F_T become B^m and F^m without change. Then the analysis of S^m is used as a guide for any knowledge construction process by adding the required knowledge components from the source design to the knowledge from the target design. The operations of this algorithm are shown in Figure 6.
3. A surface similarity between structure spaces is used to match and retrieve a source design, the similarity function is defined as SIM(S_T,S_S). The mapping and transformation steps here may consist of one or two stages, depending on the S_T, and S_S chosen. During stage 1 parts of B_S are used to modify B_T by mapping B_S on it and transforming the result of this operation : B^m=t (B_TÈ M(B_S )). Then an analysis is carried out (using the knowledge from both target and source designs) to determine if S_T contains all the variables on which the behaviours from B^m depend. If it does, then S_T and F_T become S^m and F^m without change. Otherwise stage 2 of the algorithm is executed, during which these missing variables are identified in S_S and are mapped onto S_T : S^m=t ₁(S_TÈ M₁(S_S)). Then follows the stage of the knowledge construction induced by S^m and B^m . The operations of this algorithm are shown in Figure 7. Note that if stage 2 is not executed then the algorithm does not add any new dimensions to S_S . The resulting transformation S_S-tS^m is shown in Figure 4(b). If stage 2 is executed then the algorithm always adds new dimensions to S_S. The resulting transformation S_StS^m is shown in Figure 4(c).

Many computational models of a design process which apply various realisations of this type of analogical reasoning have been developed (see for example Goldschmith (1994), Navinchandra (1991) and Qian and Gero (1996)). The majority of them can be classified as belonging to either type A or type B of the above-described classification. As a rule they draw the analogy on the basis of structure or behaviour similarity between source and target design state spaces and then use the source problem’s structure to construct a modified structure space for the target problem. In terms of Figure 3, their exploration steps include modification of structure space S (jointly with corresponding knowledge) only and leave B and F spaces unchanged. That is, they are attempting to change the current problem's (the target problem’s) structure space S by injecting parts and features (new structure design variables) from S_S into S or by replacing S with an adapted S_S. The set of criteria which evaluate designs remain constant in such algorithms.

In constructing a computational model of creative design processes the assumption that similarity in behaviour of two design problems may lead to useful additional structure features for the target design or that the similarity in structure may cause further structure similarities to be useful (on which the above-mentioned works are based) seems no more valid than the assumption that similarity in structure between two designs may cause some behaviours from one to be useful for the other. Designers may well draw an analogy on the basis of structure or structure and behaviour similarity and then try to apply behaviours from designs which have been matched. In this paper we present a computational approach of type C which, unlike the other analogy-based design processes, follows this strategy. Here again it is assumed that a design state space for the current design is given and a design state space of the source designs (not necessarily from the same domain) is retrieved and has structure or structure and behaviour spaces similar to the corresponding spaces of the current (target) design. Then the system tries to bring across a part of the source design into the target. Here this part consists of some of the behaviours which are present in a source but not present in the target design. It is also possible that some of the current behaviours from B_T are then discarded. Essentially this means that a source design is found which has a similar structure space and then some of its criteria are transferred to the target. If these new criteria (behavioural components) are expressible in terms of the target structure space variables (in another words, if the model of the target design has enough to support these new behaviours) then all that is required here is knowledge that is necessary to express these new behaviours. Hence in this case only the behaviour space B is changed but S stays the same, Figure 4(b). In many cases, the additional behaviours which are brought into the design cannot be expressed in terms of the variables of the target structure state space. Then stage 2 of the algorithm shown in Figure 7 should be used which yields a modification of the structure space which is shown in Figure 4(c).

In order to make this operation meaningful the usefulness of the added behaviours needs to be evaluated. We do not consider this problem fully here. We only note that a necessary condition for these behaviours to be useful is the requirement that they be able to discriminate between designs in the design space. In other words, one should be able to generate points in the structure space which have various values of these new behaviours. If the structures are not able to provide distinguishable values of the new behaviour variables then, prima facie, these new behaviours cannot be useful. Another requirement is that if an introduction of new behaviours into the design leads to an introduction of some additional structure variables into it then the designs with the resulting structure should be able to achieve at least a Pareto performance with respect to the old behaviours as designs with old structures. That is, an analogy of type C should not cause a decline in the behaviours which are already present in the design. If it does reduce existing behaviours but the added behaviours turn out to be useful then it is likely, that a modified structure produced by stage 2 of type C algorithm needs further modification.

We assume that the design state space is represented using design prototype P (Gero, 1990)

K_c = computational knowledge,

K_r = relational knowledge,

K_q = qualitative knowledge,

that structure has three types of design variables: (1) elements (components) of structure {e} depicted in Figure 8 with rectangles; (2) attributes (describe properties of elements) {a} depicted in Figure 8 with ovals and (3) relations (describe relationship between elements 1,…,n) {r(1,…,n)}, depicted in Figure 8 with crosses. Filled ovals denote exogenous attributes. The rest of the exogenous variables are not shown in Figure 8 and are kept in a separate unstructured section of a design prototype. Hexagons denote behaviours. Connecting lines denote the connections (relationships) between corresponding entities and thus represent of relational knowledge K_r.

SIM(S_T,S_S)= SIM(P_T,P_S)= { max N_m } / N(P_T,P_S), (1)

where N_m is double the maximal total number of matching pairs of elements in prototypes P_T and P_S (maximal means that from many possible lists of matching pairs of elements from P_T and P_S one list should be chosen for which N_m is maximal ) and N(P_T,P_S) is the total number of structure elements in both these prototypes. Note that in this formula as well as in all similar formulas in this paper, relative numbers could be substituted with absolute numbers.

Two structure elements in two design prototypes are defined as matching if sufficient number of their attributes and relations match. Two attributes which could design variables or exogenous variables or two relations are defined as matching if their labels match (that is, their labels match as character strings). These heuristic definitions seem to correspond the intuitive picture of surface structure similarity but should not be considered unique or universally applicable.

Let us give these definitions more formally. Consider two structure elements {e₁} from P_T and {e₂} from P_S . Element {e₁} has k attributes {a₁(1),…a_k(1)} and l relations {r₁(1,..),…r_l(1,..)} associated with it. Similarly, element {e₂} has p attributes {a₁(2),…a_p(2)} and q relations {r₁(2,..),…r_q(2,..)} associated with it. We define that two structure elements {e₁} and {e₂} match if the following condition holds

NS(e₁,e₂)= N(a(1),a(2))/(k+p) + N(r(1),r(2))/(l+q) > e, (2)

where e >0 is the threshold which should be chosen experimentally; N(a(1),a(2)) is the doubled number of pairs of attributes of {e₁} and {e₂} whose labels match label {a(1)}w label{a(2)}; N(r(1),r(2)) is the doubled number of pairs of relations which depend on {e₁} and {e₂} and whose labels match label{r(1)}w label{r(2)}. Note, that the maximal value of NS(e₁,e₂) is 2, therefore e is not greater than 2.

In terms of structure + behaviour graphs of two design prototypes the problem of computing SIM(P_T,P_S) takes the form of finding such partial mapping between these two graphs that the maximal possible number of rectangles are connected with solid arrows (which depict matching structure elements), Figure 9. Here two rectangles could be connected if a sufficient number of their attributes and relations are matched and thus are connected with dashed lines in Figure 9. Function SIM basically gives the ratio of the number of rectangles connected with the solid arrows to the total number of rectangles in both graphs.

In the general case when one calculates the SIM function and generates corresponding lists of matching elements, matching attributes and matching relations combinatorial explosion may occur. We suggest the use of a sub-optimal greedy heuristic algorithm to ensure tractable performance. This algorithm includes two greedy searches on two levels: one which computes NS(e₁,e₂) and builds a list of matching attributes and a list of matching relations (that is, when it draws dashed arrows between ovals and crosses which are one branch way from rectangles e₁, and e₂); and the other when it uses the NS(e₁,e₂) found to build a list of matching elements (that is, to draw solid lines between rectangles). Both searches are greedy in a sense that they do not produce the most complete (optimal) set of matches because they build their set of matches from the first match they encounter. This structure matching algorithm is shown in Appendix A.

The computation of the similarity function SIM(P_T,P_S) for two design prototypes P_T,P_S automatically yields the following hierarchical structure of matching entities: a list of matching structure elements {E}=({e_T(i₁), e_S(j₂),},…, ({e_T(i_N), e_S(j_N),}) . Each pair from that list has two sub-lists associated with it: attributes {A}= ({a(1),a(2)},…, {a(1),a(2)}), relations {R}=({r (1),r(2)},…,{r(1),r (2)}). This is an analytical representation of the matches that are shown in Figure 9 with the dashed and solid arrows.

3. EVALUATION OF BEHAVIOUR SIMILARITY

In practice, it is far more beneficial to retrieve all the source P_S(i) with a sufficiently high level of similarity to the target: SIM(P_T,P_S(i)) > a max _jSIM(P_T,P_S(j)),

---

where 0 < a <1 is a constant which should be chosen experimentally and maximisation is done over all prototypes in an archive. The retrieved set of {P_S(i)}, i=1,…,d which all have structures that are highly similar to the structure of the target design, can then be ranked by the degree of similarity SB(P_T,P_S)=SB(B_T,B_S), between their behaviour spaces and the behaviours of the target problem. SB(B_T,B_S) is defined as the fraction of the maximal number of behaviours in P_T which have matches in the source P_S to the total number of its behaviours. The match of two behaviours is denoted by the double dashed arrow between two hexagons in Figure 10. The value of SB(B_T,B_S) is simply the doubled total number of these arrows between their structure + behaviour graphs. The sources with different values of SB and SIM correspond to different design situations and require different computational strategies. This question will be considered in the next section.

Again we propose to compute SB(B_T,B_S) in a greedy fashion. The corresponding algorithm is shown in Appendix B. It computes the value of SB(B_T,B_S) and generates the list of matching behaviours {BB}.

4. CHOOSING A SOURCE ON THE BASIS OF STRUCTURE AND BEHAVIOUR SIMILARITY

• The retrieval process proceeds in two stages. During the first stage a set of sources with high structure similarity with the target is retrieved from the archive. During the second stage the source which has the given degrees of behaviour — behaviour similarity is filtered out of this set and used for further processing. Since the high degree of structure-structure matching is fundamentally important for the validity of the proposed algorithm - the higher the similarity between S_s and S_t the likelier is that the replacement of D with D^m will be productive. Once a set of source design prototypes have been identified and retrieved their behaviours are matched. If the two behaviour spaces match completely then no new behaviours can be found since the source design prototypes contain no behaviours which are not already in the target. If there are no matches between the two behaviour spaces then it is unlikely that the behaviours of the source are going to satisfactorily augment those in the target. The most useful sources are likely to be those where there is considerable overlap in behaviours with the target but not a complete overlap. Therefore the best performance should be expected from the source which has high value of SIM and a reasonably high value of SB functions. The best actual choice of SB function’s values is domain or even problem dependent and can be found experimentally.
• It is clear that one should try to minimize the size of the source structure which has to be passed to the target, because transplantation of structure is a difficult and potentially dangerous operation — it could damage or destroy the coherence of the target’s structure as well as viability of structure-behaviour connections in the target which is difficult and computationally expensive to fix.

The most desirable case is when all the structures in source and target are matched and all the source behaviours except a few are matched with target behaviours, SIM(P_T,,P_S)=1 and SB(P_T,P_S) d1. It is equally likely here that the passing of any of these unmatched behaviours to the target will be productive so one should try all of them. On the other hand one should expect that this operation will not require any structure space expansions (stage 1 of the Type C algorithm should be sufficient). This is probably the most favorable case to apply the proposed approach.

• Let us consider a case when source and target structures as well as source and structure behaviours do not match completely . Assume the source has two unmatched behaviours b₁, that depends on the structure elements which have matches in target, and b₂, that depends on the structure elements which have no matches in target . It is clear that the passing of b₁ to the target will not require the transplantation of new structure elements to it but passing of b₂ will require that. Therefore if there is no any particular external reason to expect b₂ to be productive in the target, one should use b₁ rather than b₂ to extend the behaviours in target. The new set of behaviours should be examined (using knowledge from the prototype) , to make sure that it does not contain obsolete behaviours. If they do then they should be deleted from the modified problem.

• Once the decision which source to use is taken, the set of candidate-behaviours is created by filtering all the behaviours which are in the {BB} list of matching behaviours, out of the set of behaviours of the source problem: {B_c}={B_s}-{BB}. In graphical form this corresponds to making a list of all the hexagons from the source graph , which do not have dashed double arrow pointed on them, to the target graph, Figure 10.

Once the decision about which behaviour b from the list of candidates {B_c}, should be passed to the target is taken, the process of its ``transplantation" together with everything in the source structure which supports this behaviour is executed. In order to determine what does support that task a list of elements on which it depends is retrieved from the description of the source problem and {E} the list of matching elements is used to substitute the elements from the source problem with the corresponding matching elements from the target problem. Finally, one checks if the new behaviour still depends on any of the elements of the source problem. If it does not then the step 2 of passing new structures from source to target problems is not required and the knowledge construction stage begins. Otherwise the elements of the source design on which new behaviour depends and which have not been substituted with the matching elements of the target design are added to the set of elements of the target design, together with all the attributes and relations which are connected to these elements. Since relations could depend on a number of elements, for each relation which is added to the target design, its list of elements is also pulled up, scanned for the elements of the source problem, which are on the list of matches {E}, and these elements are substituted with those matches. The elements of the source design which have not been replaced with the target matches are again added to the set structure elements of the target design, etc., Figure 10. Graphically, this process consists of copying a hexagon which does not have a double dashed arrow pointing to it from the source structure+behaviour graph to the target; copying all branches that are attached to it. If the copied branch has some entity (attribute and/or relation ) attached to it, then either this branch gets attached to the matching entity in the target or this entity is copied into the target, then all the branches attached to it are copied, etc. This process yields a complete self-contained and self-referential modified graph of the target design which contains the new behaviour and the minimal number of attributes and relations that are needed to support it.

1. Examples

Let us consider a few illustrative examples of using this approach. Our archive of design spaces contains two design prototypes. One is of a VLSI design problem (Zimmerman, 1997) where a board has to be designed to produce a layout of a given set of elementary units (which assumed to have rectangular shapes) on it. The behaviours here include the total length of net wiring, the area of the board, the total dead space on the board and the heat behaviour (essentially, the condition of temperature stability of the board). The second is of a disposable napkin and/or handkerchief design problem. Here a napkin and/or handkerchief has to be designed. The behaviours here include the foldability, absorption, weight, cost (specific per 1 usage), hyper-allergenity and disposability. Design prototypes for all our examples are shown in Appendix D. We chose a high threshold value e=0.5 in the condition of structure element’s matching (2).

4.1 DESIGNING BUILDING FLOOR-PLAN LAYOUT

Let us consider the facility layout planning problem where a given set of rectangular departments with given areas and given aspect ratios have to be placed into a given building (Mellet, et al, 1997). The distance-based measure of the net amount of traffic flow in the building (we denote it as travel load) is used as a behaviour, jointly with dead area. Following the above-described action plan first the degree of similarity between this target and the first design prototype in the archive (VLSI) is calculated using the algorithm described in Appendix D. It turns out to be the highest possible, ie SIM(P_T,,P_S)=1. It corresponds to the following list of matching elements {E}=({e_1T , e_1S}, {e_2T , e_2S},{e_3T , e_3S}), their respective degrees of similarity are NS(e_1T , e_1S )=2, NS(e_2T,e_2S )=1.55, NS(e_3T,e_3S )=1.55 (remember that the maximal possible value of NS is 2) and the corresponding matching is shown in Figure 11. The degree of similarity of this target and the napkin design prototype is SIM(P_T,,P_S)=0 (there are no matching elements, the maximal value of NS(e_T,e_S)=0.5 for any structure elements in target and source is well below the chosen threshold 1.5). Since VLSI is the only design prototype in our archive which has sufficiently similar structure to the target’s structure, the system choses VLSI design as the source design. The behaviour similarity between VLSI and facility layout prototypes SB(B_T,B_S)=0.33 because there is only one matching pair of behaviour {BB}=({b_1S,b_1T }), Figure 11. This leaves two behaviour-candidates b₂ and b₃. But the source’s b₂ is actually similar to the target’s b₂ - they both are distance-based and belong to the same taxonomic tree. Therefore we are left with only one behaviour candidate b₃ to be added to the set of target’s behaviours. In order to support it, new attribute a₅ - analogous of the source’s attribute a₅ - is added to the lists of attributes of the structure elements e₂ and e₃. Note, that since physical laws which govern heat transfer processes in buildings and in VLSI are different, the knowledge constructed by copying the knowledge from VLSI design prototype needs to be replaced by the domain specific knowledge.

The new behaviour derived for the facility layout problem by analogy with VLSI design, b₃ — heat transfer, does not require the introduction of new structure variables, only new attributes of existing variables. It has the capacity potentially to differentiate between a variaty of layouts and as a consequence provides a pressure to produce designs which would not have been produced previously

4.2 DESIGN OF A NAPPY (DIAPER)

The target problem here is a problem of designing a nappy. Since disposable napkin and handkerchief had been invented much earlier than disposable nappy it is possible that the first disposable nappy may have been designed using this type of reasoning. Again first the degree of structure similarity between the target and each prototype in the archive are computed. It turns out that there is no similarity in structure (at least according to our definition of structure similarity) between this target and the VLSI design, SIM(P_T,P_S)=0. In other words no matching elements are found, the maximal degree of matching between any structure elements of the target and any structure element of the source is NS(e_T,e_S )=0.5. The degree of similarity of this target and disposable napkin design prototype is SIM(P_T,,P_S)=0.5. The corresponding list of matching elements is {E}=({e_1T,e_1S}) and NS(e_1T,e_1S)=2, Figure 12. Because the target’s structure possesses enought similarity to the napkin’s structure and no similarity to the VLSI structure, our system chooses the napkin design as the source problem. The behaviour similarity between napkin and nappy prototypes is SB(B_T,B_S)=1.66. Two source’s behaviours, that do not have matches among target behavious, make the list of behaviour-candidates for transplantation: {B_c }=(b₁, b₆}. But b₁ (foldability) is similar to the b₁ (wearability ) of the target problem. Hence, it is unlikely that its addition to the target will be productive and it is rejected from the list of candidates. Because not all the elements on which source’s behaviour b₆ depends have matches among elements of target’s b₆ , the adding of b₆ to the list of target’s behaviours does require adding new structure elements (2 new layer) with their corresponding attributes to the target design. This new behaviour can not be supported simply by replacing the ranges of the source’s variables with the target’s ranges of their matches.

---

Note, that adding disposability to the range of the target’s behaviours makes one of its initial behaviours obsolete and it should be dropped from the list modified target’s behaviours.
2. Discussion.

Gero, J.S.:1990, Design prototypes: a knowledge representation schema for design, AI Magazine, 11(4): 26-36.

1. (initialisation) Set structures S_S and S_T unmarked. Marking means that each entity in a structure is given additional logical variable which can take two values .false. if the entity is unmarked and .true. if it is marked. Create empty list of matching structure elements.
2. Repeat the following cycle until all the elements in one of the structures S_S and S_T are marked.
1. Take unmarked structure element e₁ from the target prototype .
1. Take unmarked structure element e₂(k) from the target prototype and compute function NS(e₁,e₂(k)) .
2. Repeat step 1 for all unmarked e₂(k) .
2. Find e₂ (i) for which NS(e₁,e₂(i))=max_kNS(e₁, e₂ (k)).
3. Add the pair {e₁, e₂ (k)} to the list of matching structure elements. Create a sub-list of matching attributes and relations for {e₁, e₂ (k)} by copying from the corresponding list produced during computation of NS (see the description of the algorithm which computes NS in the next section).
4. Mark e₁ and e₂ (k) and all their attributes.
3. Compute N(P_T,,P_S) by counting as the number N of pairs (e₁,e₂) in the final list of matching structure elements and multiplying it on 2.

Function NS(e₁,e₂(k)) is calculated also sub-optimally in a greedy fashion. We assume that the element e₂(k)) has p attributes {a₁(k),…a_p(k)} and q relations {r₁(k),…r_q(k)} associated with it. The corresponding algorithm has the following structure:

1. (initialisation ) Create two empty lists of matching attributes and relations. All the attributes and relations, connected to e₁ and e₂(k) are unmarked by design (see above).
2. Take unmarked attribute a₁ of the element e₁.
1. Set counter i=1.
2. Take attribute a_i(k) . If it is unmarked then
1. Compare the label of a₁ with the label of a_i(k).
2. If they match (label{a₁}w label{a_i(k)}) then
1. Add the pair {a₁,a_i(k)} to the list of matching attributes.
2. Mark a₁ and a_i(k) .
3. Go to step III.
3. Sep i=i+1.
4. If i <= p repeat steps II.B-II.D.
5. Mark a₁.
3. Repeat steps II until all the attributes of e₁ are marked.
4. Compute N(a(1),a(2)) as the doubled length of the list of matched attributes.
5. Take unmarked relation r₁ of the element e₁.
1. Set the counter i=1.
2. Take relation r_i(k) . If it is unmarked then
1. Compare the label of r₁ with the label of r_i(k).
2. If they match (label{r₁}w label{r_i(k)}), then
1. Add the pair {r₁,r_i(k)} to the list of matching relations.
2. Mark r₁ and r_i(k).
3. Go to step VI.

C. If i=q mark r₁.

3. Set i=i+1.
4. If i <=q repeat steps IV.B-IV.D.
6. Repeat step V until all the relations of e₁ are marked.
7. N(r(1),r(k)) is computing as the double length of the list of matched relations;
8. NS(e₁,e₂(k)) is computed as the sum of N(a(1),a(2)) and N(r(1),r(2)) . If NS(e₁,e₂) < e then we set NS(e₁,e₂)=0.

The computation of SB(B_T,B_S) proceeds as follow (it is assumed here that the target has g behaviour variables {b₁(1),…, b_g(1)}):

1. Unmark all the behaviours of both B_T and B_S. Create an empty list of matching behaviours of the source problem {BB}.

1. Take unmarked behaviour of the source problem b₂.
1. Set counter i=1.
2. If behaviour b₁(1) is unmarked
1. Compare the label of b ₁(1) with the label of b₂.
1. If they match (label(b_i(1))w label(b₂))
1. Add {b₁(1),b₂} to {BB}.
2. Mark b₂ is marked.
3. Go to III.
2. If i=g mark b₂.
3. Set i=i+1.
4. If i <=g repeat steps 1-4.

The value of SB(B_T,B_S) is then computed as the ratio of the difference between the total number of behaviour variables in B_T and the length of the list {BB}.

1. the hexagon is copied from the source to the target; Unmark all the branches.
2. If branch br which is attached to it is unmarked then copy it into the source;
1. if such branch in source has an oval attached to it then
1. if this oval is connected with target’s oval with dashed arrow this branch in target gets attached to this oval;
2. otherwise

S - the structure space,

D_- - the complete design state space,

D — the feasible subset of D ,

D^m— the feasible subset of the modified D ,

B^m- the behaviour space of the modified design,

S^m- the behaviour space of the modified design,

F^m- the function space of the modified design,

S_T — the feasible subset of the target design S,

S_S — the feasible subset of the source design S,

t -analogical transformation operator,

M-analogical mapping operator,

P-design prototype,

K_c - computational knowledge,

K_r - relational knowledge,

K_q - qualitative knowledge,

SB(B_T,B_S) - a function which measures the degree of similarity of behaviour spaces,

{E}- a list of matching structure elements in two design prototypes,

{B_c}-a list of behaviour candidates to be transferred from source to target.