2.1. Representation and meaning

A principal danger in research that is lead by software development is programmatic thinking. By programmatic, we mean the overly literal attention to representing and computing directly over the concrete entities in the problem at hand. To be fair to the field, almost all serious expert systems for design were built on two or three levels: a lower abstract inference engine, sometimes a midlevel representation of tasks and methods, and an upper representation of problem particulars. For example, R1 (McDermott, 1982) was built on top of OPS (Forgy, 1981), LOOS (Flemming, 1990) originally in OPS, and GENESIS (Heisserman, 1994) on a hybrid logic/solid-modeling substrate. Newell's knowledge level (1981) is perhaps the definitive argument for midlevel representation. Others were working in parallel; for example, Chandrasekaran and Johnson (1993) coined the term generic task to identify a representation level in which task types intervened between the domain and lower levels of implementation. Special attention was given to design tasks (Chandrasekaran, 1990). Their formulation grew out of work such as Brown's thesis (1984) and the subsequent book (Brown & Chandrasekaran, 1989). The first trap opens when the specific domain representation is taken too seriously. To put criticism close to home, the early thinking of researchers in the SEED-Config project (Akın et al., 1997) confused the knowledge level, involving such things as functional units, design units, and technologies, with underlying computations that could support it. The result of falling into this trap is to miss two crucial points: good representations are, in a deep sense, both intentional and partial, and good accounts of designing are given in terms of the most general constructs possible.

Consider how the term intentional, drawn from philosophy of mind, relates to designs. If we are committed to realizing designs as physical artifacts, then ultimately we are committed to their intentionality. That is, we are committed to the notion that designs are about other objects. A representation is intentional because it is a statement about another object. It need not be a complete statement, nor need it be the only statement. The latter is crucial: you can have multiple representations that are indistinguishable in terms of the information they convey without implying that their referents are the same or are distinct.

This level of indirection, the “aboutness” of designs, becomes a second trap when we conflate the properties of a design with the properties of its subject. This trap leads to overly literal interpretations of representation. This conflation has facets.

The first facet is that a designed object embodies phenomena beyond the reach of any particular representation. Thus, we do not find air flow around buildings accounted for in a typical building model, nor do we find explicit reference to nonstructural cladding in a structural design system, and especially seldom do we find represented the ineffable sense of space and light that is the hallmark of much fine architecture. Therefore, those aspects of its referent that it captures necessarily limit what we can do with a representation. Yet, as designers, we must constantly make decisions in just such explicitly unrepresented realms. Therefore, it is important that we are able to distinguish the unrepresented properties expressed by an instantiation of a design and the represented properties without confusion.

A second facet is that we use representations in distinct ways, which we label here strong and weak representation. Strong representation occurs when we imbue the representation with the ability to make algorithmic inference about its referent. A ubiquitous example is the now near-universal use of three-dimensional (3-D) modeling in architectural schools. The chief inference here is, of course, visualization. Students, and then designers, have found that the effort involved in building a 3-D model is more than offset by the ability to multiply render the resulting design. Another example, more prosaic, but perhaps even more ubiquitous, is the spreadsheet. With it the quick quantitative model of a budget, an architectural brief or a plan of work has become an essential part of much professional practice. Cognitive accounts of designing tend to focus on the strong aspects of a representation, as these are precisely the ones amenable to the constructive nature of the theory building at hand with its requirement for computationally executable theories. Weak representation happens when we use a representation as a reminder, hint, or framer of new insight. Situationist accounts of design focus mostly on weak aspects of representation, largely and precisely because the cognitivists have mostly ignored such.

A third facet is that, to use representations computationally, we must imbue them with exogenous properties, that is, ones that are manifestly not in the phenomena they purport to represent. We have to provide a set of operators by which we can change representations. We have to do this to use representations: the fact that designers work by search in a problem space means that they have to be able to alter representations and most such alterations do not follow the logic of physical objects represented. Good design representations are inherently about supporting change precisely to help designers move from idea to idea in their search.

Consider how the term partial relates to designs. Having a design representation does not mean you know all about a particular design. If you have a sketch in front of you, this is abundantly clear. It seems to be a lesson often lost on designers of computer-aided design (CAD) systems. Much hay has been made over the years through criticism that CAD systems force one to overcommit to particulars in comparison to sketches, which are claimed to be contingent in every respect. We argue that such criticism is sustained, and sustainable, because design representations are not thoroughly partial at every level. Partiality swims with intentionality. A design is about an artifact. That is no commitment to being all about the artifact, and especially no commitment to being as much about the artifact as it might some day become. Designs are inherently partial: we add to them and subtract from them as a routine part of doing design. Furthermore, aboutness harbors information that may itself be partial: representations may refer to the same or distinct objects. For instance, we might have two identical representations of a column in a building, each playing a role in some part of a structural system, yet these two representations might be identified as referring to a single structure in a future version of the representation. Such function sharing is one of the oft-cited sources of design innovation (Ulrich & Seering, 1992).

A good representation to some degree must avoid these traps. It must not over commit to a specific and limited set of represented properties and feasible inferences. It should display some aspects of strong representation; otherwise, a significant part of the benefit of using a computer is lost. It must remain open to the weak uses of representation, or designers will resolutely suborn it to such. It must afford a disciplined notion of change; otherwise, it is not a design representation and certainly not a computable one. It must achieve a deep notion of partiality in how it represents designs.

2.2. Vastness

The domain of design imposes further conditions on representation that stem from the nature of the collections of design alternatives considered. In particular, design spaces are vast in the sense meant by Dennett (1995), namely, hyperastronomical in extent. For example, there are a finite but incomprehensibly large number of possible games of chess. Although almost all conceivable classes of designs are also vast, they remain a vanishingly small part of the entire design space, so that randomly selecting a worthwhile design is an event with a vanishingly small probability. Yet, without an oracle, we must begin at just such a random place and proceed to search.

In the analogous context of Darwin's theory of evolution, Dennett (1995) argues that expressiveness does not give an adequate account of possibility—the grade of possibility that matters is not whether a suitable artifact is expressible as a design, but whether a suitable design is accessible with reasonable effort to an explorer positioned somewhere in the design space. This line of reasoning can be expected to apply to other vast design spaces. Therefore, the explored fraction of a design space matters precisely because it decides the cost of accessing the unexplored designs.

Figure 1 demonstrates two dimensions of accessibility. Distance in the figure is a measure of derivational effort. Arcs link designs in the explored part of the space to designs not yet found. Following an arc expands the explored part of the space. First, effort counts. Design b will be more accessible than design a. Second, connectivity counts. Designs c and d gain an advantage over designs a and b through their connection to a larger number of already discovered designs.

The dimensions of design space accessibility. [A color version of this figure can be viewed online at www.journals.cambridge.org]

Vastness has other implications to the implied mechanism of search. Effort counts in other ways than making designs accessible along short paths. Design is time pressured; the fact of vastness of the space and finite human life guarantees this. The effort required to formulate a proposal is large relative to the time available for the entire process. Designs are precious productions and designers do return to them, to use them directly or to infer from them analogous structures and moves that can be applied to other designs. In terms of a design space, designers pull paths of actuality from existing designs and apply them to others in the space. In the time pressured world of designing, even partial and inconsistent designs find value as launching points into unexplored parts of the space. Designs themselves are important objects, irrespective of what they represent. That they are placed in the design space captures a position from which further exploration can be made. This is a corollary of the fact that accessibility is the measure of possibility: designs without physical interpretation or with poor qualities may be the basis for other realizable designs. Although this matter is also related to the expressiveness of the formalism, particularly whether it allows the description of abstract forms, the role of unsound designs derives from the importance of accessibility in the design space. Designs without satisfactory interpretations draw their utility from the designs that they make accessible either by forming a link in a chain of explored designs, or by providing a chain of exploration that may be reused by analogy.

2.4. Summary of designer action

We claim that the above features of design representations are invariants of the exploration view and are necessary properties of a useful design space representation. In summary, representations must avoid the programmatic pitfall, must be intentional and partial, are inevitably limited in scope, carry both strong and weak representational qualia, and have properties exogenous to the artifact represented. That representations are used in search in a vast space makes accessibility the primary criterion of utility, drafts unsound designs into a potentially crucial role, and points to contingent historical accounts of design history as the best record of design intent.

Simon (1980) long argued that the limits of cognitive capability would seldom surface in observing problem solving action. Humans work within their limits. Entirely absent from unaided human problem solving are strategies that require the storage of even modest numbers of problem states. Indeed, the absence of such strategies forms a profound falsification test for cognitive theories of problem solving. Discovery of a single instance of such a strategy would deeply challenge the entire edifice. Yet, design space exploration is precisely about supporting humans to do design work such that the overall system engages in patterns of exploration that are beyond unaided human capability.

We know that external memory, of almost any form, is a significant amplifier of action. What is not, and cannot be, clear from accounts of designer action alone is the utility of providing computational means for designers to surmount these biological limits. Can designer action be so amplified?

Here, surely, is a case where the absence of evidence should not be taken as evidence of absence. Given the state of design space exploration work today, we have little evidence for amplification of designer action through supporting exploration. We also have little ground for arguing against such amplification. Having almost no systems that engage designers with multiple states, we can make only shallow and tentative inferences about their utility.

In closing our discussion about the domain that design space exploration intends to support, we would distance ourselves from some current debates in design research. Design space exploration takes a philosophical position that is neither cognitivist nor situated. As Bredo (1994) points out with equal relevance to both cognitivist and situationist ideologues:

3.1. Representational prowess

External memory use is near ubiquitous for designers, and representation of designs is a primary function for external memory. A good account of the history of commercial design computing can be built on events introducing new representational tricks. One such trick was solid modeling, the representation of the geometry of 3-D solid objects. At its inception, solid modeling was seen as a key support technology for a larger enterprise of supporting design with computers.²

3.2. Codification

Numerous authors, both designers reflecting on their work and scholars observing designers, note processes of codification of design moves. These vary in temporal extent from within a single design episode (Akın, 1986) through individual projects (Archea, 1987; Flemming, 1987a) to constancies and changes through the development of a life's corpus (Knight, 1981). Designers preferentially use past successful moves, their own or others, in future projects. One of the long promises of grammars is the ability to explicitly encode such moves.

Such encoding coheres with the ability of computers to be active with data. Most professional tools come with a programming language that can be used to extend the tool to automate tasks. Apparently, explicit codification of action is important. Very few such languages support the production-like character that we noted above as a feature of much designer communication on design process. A partial exception is the venerable AutoLISP, recently reborn as Visual Lisp, which at least has structures that make production-like expression relatively easy. Designers and firms do use these codification tools, although seldom to the degree that academic purists might prefer.

The main strategy for amplification in early grammar formalisms and interpreters was the codification of design moves as grammar rules. Those that went from formalism to implementation, and especially to those used by other than their authors (Akın et al., 1997; Flemming, 1978, 1987a, 1987b, 1989; Heisserman, 1994; Heisserman et al., 2000) made this codification active, and thus, at some level, dealt with design space. In every case except for SEED-Config (Akın et al., 1997) and SEED-LOOS (Akın et al., 1997), the strategy was minimal: the design space was represented either through a subset of the language of designs generated by a grammar or primarily through strands of derivation taken one at a time. Carlson's (1993) thesis presented a unique exception. He presented a formalism called grammatical programming and implementation (GRAMMATICA) for embedding grammars in a nondeterministic functional programming environment. Grammatical programming provides control mechanisms richer than grammar, subroutine-like mechanisms for dealing with complexity, and the ability to use transformations other than rewrite rules. Further, grammatical programming can apply to spaces of parametric, constrained designs. Carlson provided an ability to recursively enumerate languages of designs specified by statements in a control algebra over transformations. Figure 3 reproduces one of its outputs, a drawing of an early Gothic tracery.

A Gothic tracery generated as the output of a GRAMMATICA program.

Codification is, at least in part, a successful amplification strategy. But just how does it work for the designer? What assurances and efficacies does it provide?

Authors such as Flemming (1987a), Archea (1987), and Bruton (1997) describe a mode of work with rule systems, either used formally with an interpreter or informally as a metaphorical guide to action, in which the designer acts as author of the rule system. The account goes that the designers work in circles by making rules, using them, observing their actions, modifying the rules and reentering the circle by using them again. Bruton (1997) captures this process especially well in the title of his thesis: A Contingent Sense of Grammar. The measure of rule utility is what it generates now and perhaps in future contexts. In general, we cannot assure formal properties in the utterances of a grammar. We might like to think that generative design holds forth the promise of operating within a distinct space of possibilities, for example, the space of well-formed Gaudian surfaces, but we cannot guarantee this space. The space is implicit in the given rules, which induce appropriate designs or designs that can easily be ruled out. However, where do rules arise? When we presume that a generative system is restricted to a well-formed subset of the possible Gaudian surfaces, we do so on the basis of past moves in a freer design space. We have, in general, no device for ensuring either that we capture all well-formed Gaudian surfaces or that we do not generate ill-formed surfaces along with the good ones. All we can do is temper our expectations with experience in the more open context in which we, or others, built the rules. In this more fluid context, ultimately the unrestricted design space, a path records the co-option of design features and their assignments to roles. Rules ossify such experience. We have confidence in them to the extent that we can reinterpret the resulting designs ourselves, can follow the logic of the design space path or have enumerated enough outcomes to feel confident in future explorations. Each of these sources of surety is an illusion. Reinterpretable designs arise in weak representations that defer explicit commitments to the viewer and thus surrender potential ground for computational assistance. Understanding design space paths privileges the easily explainable over the creatively explored. Confidence in numbers is a simple recapitulation of the general logical error of induction of general laws from specific facts.

In the cases of both single-fronted cottages (Woodbury et al., 1999), the historically dominant cheap housing in Adelaide, and Queen Anne houses (Flemming, 1987a, 1987b), we are permissive in the interpretation of features and create logically coherent design space paths. Each single-fronted cottage consists of a hall the length of one wall and a parallel collection of nearly identical rooms. These are generated by rules that attend to the geometric pattern alone. The assignment of roles to rooms is deferred to a later stage of rule application. The rules are constructed to apply in stages and this orderly filling in of design detail aids both rule creation and comprehension of rule application. The same overall structure is mirrored in Flemming's Queen Anne house grammar (Flemming, 1987a, 1987b), which has a similar deferral of functional assignment and goes through successive stages of completion with different rules acting at each stage.

The accounts generated in exploration are thus necessarily both constructive and contingent. It is not clear that you can provide a computationally tractable and humanly understandable mechanism that mimics set theoretical selection, that is, selection based on the interpretations of designs. In a constructive world, be it evolution or design, accessibility is the only sound concept for discovery. Accessibility derives not only from the operations at hand in the design representation, but also from the reuse of recurring patterns in the threads of actuality that trace out the explicit design space: the space of visited designs. Reuse of threads is the intuition behind, for instance, case-based reasoning. However, from a design space explorer perspective, the case lies not in the individual designs but rather in the design space paths embedded in an explicit design space.

3.3. The explicit space

Design space paths are embedded in both implicit and explicit design spaces. The former is the graph of all possibilities engendered by the codification system used. The latter is that subgraph that a designer, or a design organization, has previously visited. Ground in the explicit space is gained through designer work and it expands over time as a library of potentially recoverable, reusable and readaptable work. At least that is the theory. In practice, the storage and recall of past design states was, in 2005, hardly supported in any commercial system and hardly touched as an issue in research.

There are several reasons why the explicit space is important. Designers recall prior work and adapt it in new contexts. Design firms that invest in developing libraries of standard details are using a recall strategy. Designers may wish to replay paths previously discovered in a space, but in new contexts thus producing new results. This is the strategy behind systems, such as ArchiCAD, that provide procedural languages to write programs for adapting details to new contexts. Recall and replay are themselves important strategies worthy of their own sections in Sections 3.7 and 3.8, respectively. A third reason to be interested in the explicit space is that it contains alternative solutions to the design problem at hand. Alternatives are important because designs are inevitably evaluated along multiple criteria, only some of which are, or can be, captured in a given symbolic representation. They are also important because of the primacy of accessibility over possibility in making new discoveries in the implicit space. Last, they are important because the thread of actuality along which each develops is the best available carrier for explanations of design intent. Narratives of design intent provided by replay of thread, and embellished by commentary, themselves provide a basis for comparison and reflection on design possibilities.

Designers create alternatives as they work. According to Akın (2001), a main distinguishing mark of expert designers compared with nonexperts is the creation of comparatively more alternative problem formulations. Why alternatives? One part of the answer is revelation. Alternatives reveal things you have not considered, and thus suggest future avenues of exploration. Different alternatives reveal different avenues of exploration; they make new parts of design space accessible to future exploration. Further, different alternatives reveal not only oversights but also intangibles that cannot be considered formally in a symbolic representation. Another part of the answer is comparison. As a practical matter implied by finite capabilities and resources, including time, being available for any given design process, evaluation against criteria is an act of satisficing (Simon, 1955, 1956) according to which designs are accepted on the basis of their satisfying rather than optimizing performance against criteria. Important ground is gained though by satisficing against what is, or can be, known about the exploration so far. It is, rhetorically at least, better to claim that a design both satisfies criteria and is the best among those considered, than to simply make the claim that it satisfies.

As of 2005, available systems were resolutely based in a metaphor of the single state. One uses such a system to work on “a design” that one alters over time. The current design (one point and one point only in explicit space) is all that the system provides a user. Users of systems learn manual strategies of making versions, either through file copies or sometimes elaborate manual patterns of work with such structures as layers or groups, but systems themselves provide little or no systematic support for multiple states. Even such signal works as Chien's (1998) thesis builds design space navigation on a metaphor of a single explorer who is “located” at precisely one state at a time.

In design space, the primary view is of the space, in which states participate as members. Displays and interactions involving multiple states are in the set of elements from which interfaces to design space explorers will be built. There are facets to this broad claim.

A design space provides access to multiple points in explicit space. Interdesign comparison, multidesign interaction, and marking important places in the space are likely elements of interactions.

Interdesign comparisons potentially allow a designer to grasp possibilities within a region or on a front of explicit space. The SEED-Config (Woodbury & Chang, 1995; Akın et al., 1997) and discoverForm (Carlson & Woodbury, 1994) interfaces each provide negative examples of why interdesign comparison is important. SEED-Config provided separate windows in which alternatives could be visited, a window for a current design node and a layout of the nodes in its design space. One of these windows is shown in Figure 4. Clicking on a node produced a view of the design at that node in the current window. A combination of a specific key and a click opened a new window on the design of the clicked node. Designs were not well juxtaposed; the distance both in graphic space and interaction work between displays of designs made comparisons cumbersome.

A design node window in SEED-Config. Such windows could be opened on any state in a design space. Once opened, they were not visually linked to the design space in any way. [A color version of this figure can be viewed online at www.journals.cambridge.org]

The SEED-Config authors knew this well. When they prepared explanations of the system for publication (Akın et al., 1997) they crafted both abstracted examples of the interface using its metaphor of isolated views (Fig. 5) to explain development along a path, but also included a view of a set of designs from design space (Fig. 6). We interpret this inclusion as implicit admission of the need for better interdesign comparisons.

The presentation of SEED-Config (adapted from Akın et al., 1997). An abstracted view of the separate windows provided by the interface explains development of a design along a path. [A color version of this figure can be viewed online at www.journals.cambridge.org]

Presentation of a set of designs produced by SEED-Config as a coherent whole (reprinted with permission from Akın et al., 1997). The interface to SEED-Config had no analogous view. [A color version of this figure can be viewed online at www.journals.cambridge.org]

DiscoverForm is another negative example. Its main goal was immediacy in the interface. This is reflected in its declared primary principle of interaction, noted by Carlson and Woodbury (1994, p. 126) as “All changes to the motifs and clones are reflected immediately in the patterns that they generate.”

Again we see an implicit admission that interdesign comparisons are important. Figure 7, which reproduces figure 2 of Woodbury (1993), shows two paths of exploration from an initial, symmetric tree. Carlson and Woodbury's (1994) figure 18 (not reproduced here) shows an exploration of a binary tree as a cycle through a rotation. Both of these diagrams were manually prepared and both illustrate the importance of making connections among states. Neither could be accessed as a whole in the discoverForm interface, and it is granted that such was not the goal of discoverForm.

An exploration in discoverForm (Woodbury, 1993) showing two paths of development. Changes to both cloning rule and motif are used freely throughout.

Comparisons can be symbolic as well as visual. Woodbury et al. (2000b) argue for comparing representations based on information specificity. This yields a variety of comparison operators including equivalence, inclusion, commonality, difference, and consistency. In turn, this calls for a representation in which computation can play a role larger than state visualization in preparing comparisons of states for designer interaction.

Multidesign interaction labels the idea that, by making changes to an abstract state, a designer can effect changes to several more concrete states. Alternatively and equivalently in information terms, if a set of states share a feature or parameter, changing that feature logically changes all of the dependent states. To our knowledge, this strategy has received no explicit attention. The SEED-Layout system did have an ability to update prior states as a side effect of the finalization process in which a layout was dimensioned according to current constraints (U. Flemming, personal communication, 2003).

Marking prior places, or landmarks, in an exploration is a recurrent theme in research on navigation in complex information spaces. Chien (1998, p. 32) lists it as the first of four principles for designing navigation support in generative systems. Strong (1998, chap. 3) makes a similar argument in his thought experiments on cyberspace navigation. These are just two examples from many. Interestingly, they both use the same root examples of wayfinding in architectural and urban spaces (Lynch, 1960; Passini, 1984). In the current argument, the privileged place of accessibility over possibility in a vast design space provides an analytic argument for landmarks. Exploration work against the implicit space is a precious commodity. Such work itself can produce a set of states sufficiently large that the principle of accessibility over possibility becomes recursively relevant. By marking states with special exogenous meaning, users add a grade of accessibility to their explorations. It is interesting to note that this strategy has been found lacking in bookmark systems in Web browsers. Bookmarks quickly proliferate and themselves need organization. In these the recursion is carried a step further: bookmarks can themselves be classified into simple recursive labeled containers.

3.4. Implication and “implicature”

Construction of design space paths is a main task for design space exploration. At any state along a path, or in design space in general, exploration is largely conditioned by knowledge about both the present state and states reachable from that state by path traversal. Thus, an important property of a representation, be it of a state or a space of states, is what can be reliably inferred from it. Inference has long been a principal strategy for constructing design support tools. Arguably, it was the motivator for projects as early as Sketchpad (Sutherland, 1963), in which the designer was to build a geometric framework of which implications could subsequently be explored.

Implication as a strategy has exemplars in such common tools as renderers, animation packages, and spreadsheets. In renderers, a model is created and subsequently explored via renderings taken with different viewpoints, camera settings, lighting configurations, and material choices. Animation systems support a simulacrum of end-user experience of a design through automation of camera models over time. Spreadsheets implement a small step toward design space. In a spreadsheet, the structure is a cascade of equations that allows users to quickly see the implications of changing the independent variables at the top of the cascade. Designers such as Jay Parrish (personal communication, 2003) further use spreadsheets by developing codified, yet informal, models by which values in a spreadsheet are taken as parameters by which a design state, for example, a stadium is defined. Spreadsheets are an exemplar of the long-standing strategy of design parameterization, which, in 2005, is in revival in architecture through adaptation of such systems as CATIA (2003), and development within the AEC community of new systems, for example, Generative Components (Aish, 2002, 2004; Aish & Woodbury, 2005).

Deferral is the flip side of implication. Under some circumstances, it is worth designer effort to build a representation through which decisions can be deferred. Deferral only works when a representation supports some capability for implication. A typical use of parametric systems is to develop an example design that can then be adapted to fit a particular geometric context. Such adaptation stands in contrast to the extensive rework that must be done to modify a complex design that is represented in a strictly nonparametric modeler, as demonstrated in Figure 8.

A model of a theater created using a conventional solid modeler (form[bull ]Z). Considerable manual work is required to change the model from its original state on the left to a variant state on the right. This is despite the model being specifically crafted to take advantage of the operations provided by the modeling system. Reprinted with permission of Tristan d'Estree Sterk, The Office for Robotic Architectural Media (www.ofram.com), 2003. [A color version of this figure can be viewed online at www.journals.cambridge.org]

The resulting ability to make rapid changes along a limited range of variation is the primary argument for parameterization. Deferral strategies can also be found in the design and use of conventional CAD systems. For instance, assignment of logical material types throughout a design allows for rapid refinement of material properties when rendering from the design, In practice, rendering is an iterative process of changing material properties, lighting, viewpoints, and rendering settings. Figure 9 demonstrates the effect of this type of deferral. The appearance of a design can be quickly changed simply by reassignment of material properties, not in the design, but in a table of materials. Deferred decisions may be taken either automatically, for example, in parametric design systems, or manually, for example, in user choices within rendering systems.

A model of a house by Australian architect Max Pritchard. The model was created as part of a suite of teaching exercises (Woodbury et al., 2001; Adelaide University, 2002) aimed at learning the tools provided by CAD systems. It is configured so that changes to the properties of solids in the model can be easily made and propagated throughout the model (by permission). [A color version of this figure can be viewed online at www.journals.cambridge.org]

For very good computational reasons, most automatic implementations of a deferral strategy involve situations in which the deferred decisions are linked to the design through deterministic, if not continuous, functions. Nondeterministic choice is much harder to support and there are few exemplars (but see Harada et al., 1995). Paths in design space inevitably capture nondeterministic and discrete changes; this is how the structure of a design develops. Nondeterminism creates branch points; discrete change can greatly alter what can be inferred from a design.

Implication has different meanings for design states and exploration paths. The implicature of a design state is what can be inferred about that state from its representation. A representation of a state may allow certain decisions to be deferred, that is, decided at some later time. In contrast, the implicature of a state along an exploration path is the other states and their implicatures that can be accessed by exploration from the given state. What can be implied along an exploration path is thus affected by the properties of designs that are preserved along the path. Unfortunately, what can be inferred along a path is limited in most design space explorers.

Grammars and their variants are perhaps the most common strategy for implementing generative systems, at least in the building domain. A grammar comprises a representation, a collection of rules, and an initial state. Used as a design space explorer, its sentential forms stand for the design space and its language to designs that are understood, in some sense, to be complete. Rules are typically defined as a left-hand side and a right-hand side. A rule match occurs by finding the left-hand side in a state. A rule application removes the left-hand side and adds the right-hand side under conditions determined by the rule match. A rule can thus map between arbitrary places in design space. In an extreme case, an entire design could be erased by its removal in the first part of a rule application and an arbitrary design put in its place.

In certain domains stronger guarantees on design space exploration are possible. Flemming (1987b, 1989) implemented rectangular layouts in such a way that the spatial relations between rectangles in a layout are invariant along an exploration path.

3.5. Speed

The finiteness of human existence puts intellectual curiosity at odds with time. In a rushed life the speed at which we can do things is important, as are the moments of silent reflection bought by speedy action. Standard accounts of human–computer interaction, for example, Card et al. (1983), place speed and accuracy as primary criteria against which to evaluate interactions with systems. When exploring design spaces, one measure of speed is against the unfolding of paths in design space. The focus here is not the time taken to compute a particular path, but rather the time taken to consider and make the choices along the path. That is not to say that efficiency in computing paths is not important, indeed it is a primary concern in developing a design space explorer representation. For example, Heisserman (1991) went to great lengths in his thesis to ensure that the rule matching and invocation mechanisms were efficient as computations. Rather, once you have an efficient mechanism, making choices will inevitably dominate the speed at which exploration can occur. There are at least two dimensions of choice. The first is simple consideration of the choices available at a given point in a path. There may be many such choices and it is common that authors of generative mechanisms pay considerable attention to reducing the choices available at a given time; for example, this is one of the primary practical uses of labels in shape grammars. The other dimension is one of anticipation. Exploration is contingent: we cannot know the range of possibilities that lie in front of a given partial path. That said, indications are important. For example, discoverForm employs a limited domain comprising a one-rule set grammar in which a path is uniquely determined by choice of motif, branching factor, and affine transformation (Carlson & Woodbury, 1994), but trades on providing rapid anticipation of path choice.

In comparison, the SEED-Config interface was dismal in looking forward to likely effects along paths. The user was resolutely pinned down to local choices of rule application and had to manually explore from a particular point to gain some insight on likely future productions.

Harada and colleagues (Harada, 1997; Harada et al. 1995) showed an alternative approach. In essence, she put a grammar interpreter inside a physically based modeling interaction loop. When, in the midst of a user interaction, a parametric design reached a limit state along which no change was possible, the grammar interpreter performed a limited exploration and made a representational change using a principle of least disturbance of the interface. All this happened quickly within one interaction cycle. The resulting system was responsive to user input and resulted in a user strategy of dragging objects to explore possibilities. Harada did not record the space of possibilities explored, so did not provide explicit assistance in forming an impression of what might be possible from a particular point in design space.

3.6. Backup

Newell and Simon (1972, p. 826) note that humans use very limited backup strategies, and this is directly due to cognitive limits. In particular, people do not use search and scan strategies in which they consider a large number of alternatives and proceed from the prior alternatives that seem most promising at a given time. To some extent external media, teams, and assiduous librarianship can overcome these limitations, but such occurrences are relatively rare probably due to the time and expense involved. Synthetic problem solvers, on the other hand, are often designed with large fast memory structures, which make possible relatively profligate use of strategies employing backup. Almost all commercial CAD systems provide an undo command, essentially a backup along a single thread of development. One has only to work with and without such a limited form of backup to realize the degree to which even such a modest feature enhances work. In essence, having backup reduces the costs of recovery from a mistake to zero. The resulting sense of play is palpable. What is not clear is how to structure interaction with a large number of backup states. Yet, the number of potential backup states is not limited to those available along a single derivation thread. Woodbury et al. (2000a) describe hysterical undo as an operation that permits backup along paths not previously taken to a particular state. Chang and Woodbury (2003) demonstrate that user choices of Boolean operators in a conventional solid modeling system provide the basis for a form of backup that picks an expression of operators apart in a variety of ways. Both point to richer amplification strategies based on generalized backup mechanisms.

3.7. Recall

Backup implies proximity, either in derivational distance or in terms of design episode. We backup to prior states in a process. Other states may be every bit as interesting in a present context: but they may be unrelated by time, task, derivation, or author. Recall is the metaphor for such distant access.

Backup and recall comprise a necessary substrate on which exploration action grows. Normal design, and this in the sense of a large majority of design work, proceeds from the known to the unknown. Designers work on and through prior work. They make steps by modifying and adapting prior work until it becomes new and fresh. Although rarely employing carefully recorded sketches, designers sometimes make leaps from what they know to a new synthesis (Wright, 1945). Sometimes, and such moments are often recounted as memorable events, they combine two or more knowns into a hitherto unknown. In such a model recall is that action that draws precedent into play. The precedent may be the work of anyone: the designer, a colleague, another distant design professional, or it may be a vernacular production. It might even be a natural phenomenon. That precedent is valuable is easily seen in the regular and prolific publication of professional journals and picture books on architecture. That it is used can be seen by the presence of such publications, numerous photographs, and found objects that tend to collect in design offices. Devices for organizing such precedents are widely known and sometimes used: the office catalog, library, and CAD symbol collection are all examples.

In the context of design space exploration then, an important amplification might be the ability to recall what you or someone else has done before. Such recall is, of course, one of the aspirations of the complex of work labeled case-based design. As we have argued elsewhere, and without disparaging the prior work on cases (Woodbury et al., 1999), considering the design space seriously leads to different conclusions on formalizing and implementing the functionality of cases. We will return to this issue in the discussion of representation and computation below.

Recall must operate on both wholes and parts, with the parts being more important than the wholes in practice. The chance of reusing an entire office design is significantly less than that of reusing a window detail.

A corollary of recall is knowing when you have been in a particular area of design space before. This is a generalization of the duplicate detection problem in generative systems in which it is important either to recognize when you reach a prior design or to avoid ever doing it at all. Knowing when you are in the neighborhood of things you tried before could save a lot of work.

What is not clear is how recall can be made to work. This can be seen in difficulties encountered in recall in a much, much smaller space than the ones under consideration here: the World Wide Web. A major current issue here is searching. It is bluntly clear that current search tools are inadequate to the task on the Web at large; further, the available ways of storing and recalling even the relatively small number of bookmarks generated by a single person are hardly better. There is some light, though, in such systems as CZWeb (Fisher et al., 1997), which provided a way of organizing and communicating bookmarks such that they related visually to the logical structure of the browsed Web sites and to a user's choices about appropriate visual layout.

3.8. Replay

Once you have recalled, how do you use the recalled thing in a new context? In a professional context, the question might be “How do we use this detail we have found in our library?”

To this question, conventional CAD systems have a definitive answer: copy and paste. The standard CAD system representation is an extreme of declarativeness: it simply describes a set of geometric and attribute objects. These generally have an independent existence and can be simply put into a new context. The user has the entire responsibility of properly relating the inserted objects to what is already in the design, and this responsibility is typically not onerous. Most CAD systems, and most styles of using them, veer to the weak end of a weak to strong representational spectrum. Relatively few properties of the designed object are maintained formally in the representation. Examples include dimensions in working drawings, and polygon integrity and material properties in models used for rendering. Copy and paste works: it has become a near-universal user interface device across a wide range of system types. However, it is fragile; it is challenged by the slightest hint of interobject relations. Consider spreadsheets, an exemplar of which is Excel. The underlying abstract data structure of most spreadsheets is a unidirectional constraint network in which links between nodes model the propagation of the value of a source node into the equation that, in its turn, computes the value of a sink node. Using copy and paste is tricky in spreadsheets, as all users of these systems quickly discover. The usual metaphor is that, within the formula of a cell, a reference to another cell is made either in absolute or relative terms, or a mix of the two. When doing copy and paste, the user must be aware of, and must control, which reference style he or she has used. Users of spreadsheets develop an idiom of use, which might be labeled copy paste and patchReferences,³

In contrast, most of the representations used in generative design systems and demonstrations have a stronger character and this seems to be required by the codification of designer experience in the design generator. For example, shape grammars for design corpora universally make profligate use of labels to carry intentional information (Stiny & Mitchell, 1978, 1980; Chiou & Krishnamurti, 1996). This style of programming seems idiomatic: grammars in systems such as GENESIS (Heisserman 1991, 1994) and Grammatica (Carlson 1993) make extensive use of those systems' analogues of labels. The information states of these labels are typically fragile; they relate to specific places in a generation process.

The natural analogue to copy and paste in generative systems is copy and apply path where a path is a sequence of design states related by rule application or other moves to a start state in a design space. Copying a path copies not the design states, but the moves that generate the state sequence from the start state. Applying a thus-copied path is to reexecute the rule applications from a different start state (Fig. 10).

Path reuse can either be through the recognition of homologous pattern in the ancestry or analogous pattern in design form. In both cases the ability to reuse known paths is crucial in enabling design space exploration. [A color version of this figure can be viewed online at www.journals.cambridge.org]

Path reuse has been a bête noir of generative systems. To our knowledge, no grammar-based generative system has implemented it, despite considerable discussion of it among developers. Yet, is it a key amplification point for design systems.