Using analogy to extend the behaviour state space in design
John S. Gero and Vladimir Kazakov
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.
1. Introduction
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.
2. An analogy-based creative design model
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).
Usually analogical problem solving in design is used when a routine design fails to yield a satisfactory design solution. For the given target design it consists of finding and retrieving an analogous source design from a design archive which is then adapted to suit the requirements of the target design. Thus, in terms of the S-B-F framework the analogy-based designing process includes three steps:
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:
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.
3. Analogical design retrieval process
3.1 DESIGN PROTOTYPES
We assume that the design state space is represented using design prototype P (Gero, 1990)
P={F, B, S, Ex, K_{c}, K_{q}, K_{r}},
where
Ex = a finite set of exogenous variables which describe external conditions,
F = a finite set of function variables,
K_{c } = computational knowledge,
K_{r} = relational knowledge,
K_{q} = qualitative knowledge,
S = a finite set of structure variables.
Since the proposed algorithm does not affect the function spaces F, we omit the F part of design prototype which describes the function space. Each design variable has a label and a range of valid values associated with it. We assume that the labels which are used to code design prototypes in a system are standardized and codified so that a simple label comparison could be used to identify similar labels. Otherwise some kind of linguistic analysis based on a hierarchical term structure needs to be used in a system to find and compare generalized meanings of labels, etc.
During source retrieval, mapping and transformation the proposed algorithm uses only part of the information which is kept in design prototype. Namely, it uses the structure and behaviour and the relational knowledge. We represent these parts of a design prototype as a structure + behaviour graph, Figure 8 or as a set of two tables, Table 1. We assume
Element |
label |
attribute |
relation |
label |
e_{1} |
***** |
|||
a_{1 }(1) |
***** |
|||
a_{2 }(1) |
***** |
|||
r_{1} |
***** |
|||
r_{2} |
***** |
|||
e_{2} |
***** |
|||
a_{1 }(2) |
***** |
|||
a_{2 }(2) |
***** |
|||
r_{2} |
***** |
dependencies |
|||
behaviour |
label |
e_{1 } |
e_{2 } |
b_{1} |
string |
no |
yes |
Table 1. Part of design prototype required by the algorithm in the form of two tables. First table represents the structure and the second one contains dependencies of behaviours on structure elements.
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}.
3.2 STRUCTURE MATCHING AND STRUCTURE SIMILARITY MEASUREMENT
Basically two types of similarity are recognised - surface similarity when two problems have the same attributes and structural similarity when they have the same underlying casual dependency network (Holyoak and Koh 1987; Thagard et al. 1994). The proposed algorithm is based on the evaluation of a surface similarity between two design structure spaces or, more accurately, between their design prototypes. The surface similarity can be defined in many different ways. We define it as proportional to the maximal total number of matching structure elements in two design prototypes. The corresponding function, which measures this similarity, is defined as
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_{1}} from P_{T} and {e_{2}} from P_{S }. Element {e_{1}} has k attributes {a_{1}(1),…a_{k}(1)} and l relations {r_{1}(1,..),…r_{l}(1,..)} associated with it. Similarly, element {e_{2}} has p attributes {a_{1}(2),…a_{p}(2)} and q relations {r_{1}(2,..),…r_{q}(2,..)} associated with it. We define that two structure elements {e_{1}} and {e_{2}} match if the following condition holds
NS(e_{1},e_{2})= _{ }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_{1}} and {e_{2}} 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_{1}} and {e_{2}} and whose labels match label{r(1)}w label{r(2)}. Note, that the maximal value of NS(e_{1},e_{2}) 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_{1},e_{2}) 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_{1}, and e_{2}); and the other when it uses the NS(e_{1},e_{2}) 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_{1}), e_{S}(j_{2}),},…, ({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.
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 _{j}SIM(P_{T},P_{S}(j)),
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}.
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.
3.5 TRANSFER OF BEHAVIOURS AND TRANSFER OF STRUCTURES INDUCED BY IT
Then for each behaviour from the list of candidates we compute the ratio of matched structure variables it depends on to the total number of structure variables it depends on. Then we try to pass the behaviours which have the highest values of this ratio. The assumption behind this choice of preferences of new behaviours to be added to the target problem is that it is more probable that the behaviours which strongly depend on the matched structure variables would require less additions and modifications to structure (see previous section) and would be more `` more useful.
The behaviour-candidates to be passed to the target problem should be also evaluated with respect to their similarity to the behaviour variables which are already present in the target problem. The comparison can be executed by finding the closest superordinate in some hierarchical tree of knowledge labels. The behaviours which are judged to be ``too" similar by this procedure should be rejected from the list of possible new behaviours. The reason for this is clear — we assume that it is more likely that ``different" new behaviours would be useful.
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.
If a target’s design variable has a matching source design variable then the range of the corresponding variable in the modified target design is a union of both of their ranges.
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_{2 } and b_{3}. But the source’s b_{2 } is actually similar to the target’s b_{2 } - they both are distance-based and belong to the same taxonomic tree. Therefore we are left with only one behaviour candidate b_{3 } to be added to the set of target’s behaviours. In order to support it, new attribute a_{5 }- analogous of the source’s attribute a_{5 }- is added to the lists of attributes of the structure elements e_{2} and e_{3}. 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_{3} — 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_{1}, b_{6}}. But b_{1 } (foldability) is similar to the b_{1} (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_{6 } depends have matches among elements of target’s b_{6} , the adding of b_{6 } 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.
The use of analogy in designing has been largely restricted to expending the structure space of designs. The effect of this is to introduce the capacity to produce designs that could otherwise not have been produced. In one sense this matches the notion of creative designing. Given that designing within the S—B—F framework provides the potential to be creative not only in structure space but also in behaviour (and function) space, this paper has presented an approach to the expansion of the behaviour space — an expansion which produces new behaviours in an analogous manner to the expansion of the structure space when using analogy as the expansion process. There could be one of two effects of this expansion. The behaviour space could be expanded without any requirement that the structure space be expanded or the behaviour space could be expanded with a consequential expansion of the structure space.
In the first case different structures can be produced from the same set of structure variables. The differences are driven by the different behaviours the designs now have to exhibit. These designs are novel in the sense that they may involve values of structure variables which would never have been chosen without the additional behaviours. Thus, this process maps onto that of innovative designing. These new designs, however, are unlikely to have been produced using the original behaviours
In the second case different structures can be produced because new structure variables have been introduced as well as new behaviour variables. Both the new behaviours and the new structures drive the differences. The new structures that have been introduced into the target are directly related to the new behaviours. Thus, this process maps onto that of creative designing. These new designs, however, are likely to include those, which could never have been produced with the original behaviours and original structures.
Let us note that approach is routinely used in drug design (Dean, 1995), where molecular similarity (structure similarity in design science terminology) provide a useful lead in the search for bioactive molecules with appropriate properties.
Acknowledgments
This work is directly supported by a grant from Australian Research Council, computing resources are provided through the Key Centre of Design Computing.
Gero, J.S.:1990, Design prototypes: a knowledge representation schema for design, AI Magazine, 11(4): 26-36.
Gero, J.S.:1996, Creativity, emergence and evolution in design, Knowledge-Based Systems, 9, 435-448.
Gero, J.S. and Kazakov, V.: 1998, Adaptive expansion of search spaces using emergent features, Proceedings of AI’98 (to appear).
Qian,L. and Gero,J.S.,: 1996, Function-behaviour-structure paths and their role in analogy-based design, AIEDAM, 10, 289-312.
Goldschmith, G.: 1994, Visual analogy in design, in R. Trappl (ed), Cybernetics and Systems `94, Singapore World Scientific, 507-514.
Logan, B. and Smithers, T., Creativity and design as exploration, in J.S.Gero and M.L.Maher (eds), Modelling Creativity and Knowledge-based Creative Design, Hillsdale, NJ, Lawrence Erlbaum, 139-175.
Navinchandra, D.: 1991, Exploration and Innovation in Design, New York, Springer-Verlag.
Yi-Luen, E. and Gross, M.D.: 1995, Drawing analogies, in Kalisperis,L. and Kolarevic, B. Ed. Proceedings, Association for Computer Aided Design in Architecture, Seattle.
Dean, P.M. (ed):1995, Molecular similarity in drug design, Chapman Hall,Glasgow.
Prieditis, A.(ed): 1988, Analogica, Morgan Kaufmann, Pitman, London.
Keane,M.T.: 1988, Analogical Problem Solving ,Ellis Horwood, Chichester.
Carbonell, J.G.:1986,Derivational analogy: a theory of reconstructive problem solving and expertise acquisition, in, Michalski, R.S., Carbonell, J.G. and Mitchell, T.M. (eds) Machine Learning: An Artificial Intelligence Approach, Tioga, Palo Alto, California, pp. 137-161.
French,R.:1995, The Subtlery of Sameness: A Theory of Computer Model of Analogy-Making, Cambridge, Mass.: MIT Press.
Mitchell,M.:1993, Analogy-making as perception: a computer model, Cambridge, Mass.: MIT Press
Thagard,P., Holyoak, K.J.,Nelson,G. and Gochfield,D.: 1994, Analog retrieval by constraint satisfaction, Artificial Intelligence, 46, 259-310.
Holyoak,K.J. and Koh,K.: 1987, Surface and structure similarity in analogical transfer, Memory and Cognition, 15(4), 332-340.
Keane, M.: 1988, On retrieval analogues when solving problems, Quarterly Journal of Experimental Psychology, 39A, 29-41.
Meller,R.D., and Kai-Yin Gau.: 1996, Facility layout problem: recent and emerging trends and perspectives, Journal of Manufacturing Systems, 15 (5), 351-366.
Zimmerman,G.: 1997, CAD tools for VLSI design, http://galway.informatik.uni-de/projects/
Appendix A.
STRUCTURE MATCHING ALGORITH.
The algorithm consists of external and internal cycles. The internal cycle is encapsulated as a building block in the external cycle. The internal cycle constructs a set of matching attributes and relations for two given elements. The external cycle produces the set of matching elements. The external cycle has the following structure:
Function NS(e_{1},e_{2}(k)) is calculated also sub-optimally in a greedy fashion. We assume that the element e_{2}(k)) has p attributes {a_{1}(k),…a_{p}(k)} and q relations {r_{1}(k),…r_{q}(k)} associated with it. The corresponding algorithm has the following structure:
C. If i=q mark r_{1}.
Appendix B.
BEHAIOUR MATCHING ALGORITH.
The computation of SB(B_{T},B_{S}) proceeds as follow (it is assumed here that the target has g behaviour variables {b_{1}(1),…, b_{g}(1)}):
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}.
Appendix C.
MAPPING AND TRANSFORMATION.
The following algorithm is used to pass new behaviour and its structure support from source to target:
This process yields a complete self-contained and self-references modified graph of the target problem is built which contains the new behaviour and the minimal number of all its attributes and relations that are needed to support it.
Appendix D.
Table representation of VLSI design prototype
element |
label |
attribute |
relation |
label |
e_{1} |
board |
|||
a_{1 }(1) |
width |
|||
a_{2 }(1) |
length |
|||
r_{2} |
inside |
|||
r_{3} |
inside |
|||
e_{2} |
cell |
|||
a_{1 }(2) |
width |
|||
a_{2 }(2) |
length |
|||
a_{3 }(2) |
position x |
|||
a_{4 }(2) |
position y |
|||
a_{5 }(2) |
heat production |
|||
r_{1} |
no intersection |
|||
r_{2} |
inside |
|||
e_{3} |
cell |
|||
a_{1 }(3) |
width |
|||
a_{2 }(3) |
length |
|||
a_{3 }(3) |
position x |
|||
a_{4 }(3) |
position y |
|||
a_{5 }(3) |
heat production |
|||
r_{1} |
no intersection |
|||
r_{3} |
inside |
dependencies |
||||
behaviour |
label |
e_{1 } |
e_{2 } |
e_{3 } |
b_{1} |
dead area |
yes |
yes |
yes |
b_{2} |
network length |
yes |
yes |
yes |
b_{3} |
temperature stability |
yes |
yes |
yes |
Table representation of disposable napkin design prototype
element |
label |
attribute |
relation |
label |
e_{1} |
layer |
|||
a_{1 }(1) |
width |
|||
a_{2 }(1) |
length |
|||
a_{3 }(1) |
material |
|||
a_{4 }(1) |
thickness |
|||
e_{2} |
layer |
|||
a_{1 }(2) |
width |
|||
a_{2 }(2) |
length |
|||
a_{3 }(2) |
material |
|||
a_{4 }(2) |
thickness |
|||
e_{3} |
layer |
|||
a_{1 }(3) |
width |
|||
a_{2}(3) |
length |
|||
a_{3 }(3) |
material |
|||
a_{4 }(3) |
thickness |
dependencies |
||||
behaviour |
Label |
e_{1 } |
e_{2 } |
e_{3 } |
b_{1} |
foldability |
yes |
yes |
yes |
b_{2} |
absorption |
yes |
yes |
yes |
b_{3} |
weight |
yes |
yes |
yes |
b_{4} |
cost |
yes |
yes |
yes |
b_{5} |
hyper-allergenic |
yes |
no |
yes |
b_{6} |
disposability |
yes |
yes |
yes |
Table representation of the nappy design prototype
element |
label |
attribute |
relation |
label |
e_{1} |
layer |
|||
a_{1 }(1) |
width |
|||
a_{2 }(1) |
length |
|||
a_{3 }(1) |
material |
|||
a_{4 }(1) |
thickness |
dependencies |
||||
behaviour |
Label |
e_{1 } |
e_{2 } |
e_{3 } |
b_{1} |
wearability |
yes |
yes |
yes |
b_{2} |
absorption |
yes |
yes |
yes |
b_{3} |
weight |
yes |
yes |
yes |
b_{4} |
cost |
yes |
yes |
yes |
b_{5} |
hyper-allergenic |
yes |
no |
yes |
B_{6} |
washability |
yes |
yes |
yes |
b_{7} |
gas penetration |
yes |
yes |
yes |
Table representation of facility layout design prototype
element |
label |
attribute |
relation |
Label |
e_{1} |
building |
|||
a_{1 }(1) |
width |
|||
a_{2 }(1) |
Length |
|||
r_{2} |
Inside |
|||
r_{5} |
Inside |
|||
e_{2} |
activity |
|||
a_{1 }(2) |
width |
|||
a_{2 }(2) |
length |
|||
a_{3 }(2) |
position x |
|||
a_{4 }(2) |
position y |
|||
r_{1} |
no intersection |
|||
r_{2} |
inside |
|||
r_{3} |
aspect ratio |
|||
r_{4} |
area |
|||
e_{3} |
activity |
|||
a_{1 }(3) |
width |
|||
a_{2 }(3) |
length |
|||
a_{3 }(3) |
position x |
|||
a_{4 }(3) |
position y |
|||
r_{1} |
no intersection |
|||
r_{5} |
inside |
|||
r_{6} |
aspect ratio |
|||
r_{7} |
area |
dependencies |
||||
behaviour |
label |
e_{1 } |
e_{2 } |
e_{3 } |
b_{1} |
dead area |
yes |
yes |
yes |
b_{2} |
travel load |
Yes |
yes |
yes |
Appendix E.
Nomenclature.
S - the structure space,
B - the behaviour space,
F - the function 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,
SIM -the real function which measures the degree of similarity of two structure spaces.
t -analogical transformation operator,
M-analogical mapping operator,
P-design prototype,
Ex - a finite set of exogenous variables which describe external conditions,
F -a finite set of function variables,
K_{c } - computational knowledge,
K_{r} - relational knowledge,
K_{q} - qualitative knowledge,
S- a finite set of structure variables.
SB(B_{T},B_{S}) - a function which measures the degree of similarity of behaviour spaces,
NS(e_{1},e_{2})- a function which measures the degree of similarity of two structure elements,
{E}- a list of matching structure elements in two design prototypes,
{BB}-a list of matching behaviours in two design prototypes,
{B_{c}}-a list of behaviour candidates to be transferred from source to target.
This paper is a copy of: Gero, J. S. and Kazakov, V. (1999) Using analogy to extend the behaviour state space in creative design, in J. S. Gero and M. L. Maher (eds), Computational Models of Creative Design IV, Key Centre of Design Computing and Cognition, University of Sydney, Sydney, Australia, pp. 113-143.