Revision of 1993 Article on

INTELLIGENT COMPUTER-AIDED DESIGN

for the

Encyclopedia of Computer Science and Technology
(Eds.) J.G.Williams & K.Sochats

by

David C. Brown

AI in Design Group
Computer Science Department
WPI, Worcester, MA 01609, USA

Phone:   (508) 831-5618
FAX:     (508) 831-5776
Email:    dcb@cs.wpi.edu


September 1998



INTELLIGENT COMPUTER-AIDED DESIGN

1. INTRODUCTION The increasing complexity of the artifacts being designed, and the use of new technologies, materials and methodologies, all indicate the necessity for more computer support for design activity. This fuels the need for better understanding of the design process, of design representations, of software-based design tools, of designer-tool interactions, and of designer-designer interactions (as tools may help there too). There are many activities that we refer to as Design. We normally consider it to be "synthesis". However, a design task can involve much "analysis" too. Design is an intelligent human information-processing activity requiring many skills and much knowledge. Design problems can be solved by individuals or by teams. They may take minutes or years. Design occurs in a wide variety of domains, ranging from the design of a Nuclear Power Plant to that of a mounting bracket, and from a computer to a ship. In this article we will refer mostly to mechanical design, in order to provide focus. Given this enormous variety of problems and domains, it is important to try to define what is meant by design. The general design process is often characterized as mapping needs to function to structure. It is carried out using many different types of reasoning and many different sources of knowledge. In general, design is the process of specifying a description of an artifact that satisfies a collection of constraints. These constraints may arise from a variety of sources. The constraints may be imposed by the problem, the designer, the manufacturer, the user, or by natural laws. They reflect the desired function of the artifact, the available resources (e.g., money), the physical limitations of the materials (e.g., strength), the demands on the artifact from the environment in which it will be used (e.g., maintainability), the manufacturing processes required, general design criteria (e.g., simplicity), and the design process itself. The term "constraint" usually means something which is either satisfied or not. For the definition above we need to extend the meaning to include "softer" restrictions such as preferences. In addition, there are usually special objectives to be met, such as to minimize cost, weight, or area. These act throughout the design process, and can be used for evaluation of the design. Not all of these varied requirements need be specified initially. It is a characteristic of many design problems that new constraints emerge as decisions are made. In fact, the original requirements may be so vague as to be unable to guide the design process or to provide clear evaluation criteria that can be used to determine the success or failure of the resulting design(s). This early reasoning about requirements, and their subsequent refinement, can be thought of as framing the main design reasoning activities. 2. REASONS FOR STUDY Because Design is an ill-structured activity requiring intelligence, it is a suitable topic of study for AI. Simon [1969, p. 83] even goes as far as to say that "the proper study of mankind is the science of design". A fundamental hypothesis shared by most AI in Design researchers is that there are core reasoning 'skills', and types of knowledge, that are common across domains [Maher & Gero 1990]. That is, although design problems in different domains require different domain knowledge -- such as knowledge of equations, components, and analysis techniques -- there are underlying similarities in the form of that knowledge and in the way that it is used. For example, design in any domain requires "selection". If we can describe the essential characteristics of this reasoning skill, including the knowledge used and the process, then this can be more easily implemented for any domain [Punch et al 1995]. Of course, different domains and different design problems will require a different mix of knowledge and reasoning. For example, designing a mechanism might require a lot of spatial reasoning in three dimensions, whereas designing a circuit might require relatively little. Investigating this fundamental hypothesis will result in a better understanding of what designing actually is. This should then allow us to build useful Intelligent Computer-Aided Design (IntCAD) systems. Systems can range from autonomous design tools, that when given requirements will produce designs, to design aids that interact with a human designer (or designers) to support their design activity. Systems have been built for very many different domains, including VLSI circuits, graphical interfaces, electronic circuits, protein purification processes, bridges, elevators, computers, air cylinders, aluminum alloys, construction sites, molecular genetics experiments, copier paper paths, and high-rise buildings (see [Tong & Sriram 1991a, 1991b] and [Sriram & Tong 1991] for most of these systems). 3. HISTORY Computers have contributed to design for quite a while by providing analysis tools (e.g., the Finite Element Method), data-bases (e.g., of drawings and components), and computer-aided drafting/drawing tools. The latter is what one naturally thinks of when CAD is mentioned, as such tools have been under development since the early 1960s. Their progress runs parallel to that of Computer Graphics [Foley et al 1990]. Two dimensional drafting tools, and 3D display of objects as "wire-frames", were followed by Raster Displays. The capability to display a shaded image, along with developments in Geometric Modelling [Mantyla 1988], allowed designers to consider objects on the screen as "real". They were able to concentrate on decisions about objects rather than about drawings. This is much closer to Computer Aided Design, as opposed to Computer Aided Drafting. Since its inception, CAD has gradually been concerned with representing increasing amounts about the objects being manipulated. Geometric information has moved from 2D to 3D, and from planar to curved surfaces. Information about surface finish and color has been added. Geometric and Topological models specify the structural relationships between components. Descriptions of form features can be included. Application-specific information, such as material properties or manufacturing requirements is also useful. Thus CAD representations have gradually been moving closer to being a Knowledge Representation, to include all aspects of knowledge about the designed object. Suitable additions would be precise part-whole relations [Winston et al 1987], the representation of function [Umeda & Tomiyama 1997], and design rationale [Lee 1997]. Researchers are concerned with what needs to be represented to support IntCAD systems, and with what progress has been made in IntCAD systems over the last ten years [Brown 1997]. An additional type of information that has been added to CAD systems is the Constraint. Constraints restrict the possible values of parameters. In 2D, a constraint might be added to require that two lines be maintained at a certain angle. In 3D, one could constrain two solids to always touch. When constraints are used, a single change can propagate through constraints to produce new values for many other parameters, effectively generating a whole new design. Thus, constraint satisfaction provides a Parametric Design capability, (i.e., the system "designs" values for some parameters). Companies such as Cognition and ICAD were able to base commercial products on this idea. With these developments, CAD has gradually turned from being mainly concerned with object representation towards some consideration of the design process (i.e., Design Process Knowledge as opposed to Design Object Knowledge). As most designers can be considered to be experts, knowledge-based systems that design can be considered to be Expert Systems. Initially, most of the Expert Systems research was concerned with Diagnosis, and tools and techniques with which to build diagnostic systems. Now, design has become an important area to study, with a burgeoning literature [Gero 1985] [Hong 1986] [Gero 1987] [Rychener 1988] [Brown & Chandrasekaran 1989] [Finger & Dixon 1989a, 1989b] [Gero 1989] [Coyne et al 1990] [Gero 1990] [Maher & Gero 1990] [Dym & Levitt 1991] [Green 1991] [Sriram & Tong 1991] [Tong & Sriram 1991a] [Tong & Sriram 1991b] [Brown et al 1992] [Gero 1992] [Gero & Sudweeks 1996] [Brown & Birmingham 1997] [Brown 1998] [Gero & Sudweeks 1998]. Other books and papers can be found in the Bibliography. Expert Systems technology has allowed many new, practical applications. For example, in addition to systems that produce designs, systems can be built to check design decisions for conformance with standards or with company guidelines. Systems can be used to extract features, to select materials, to discover design flaws and suggest corrections, and to evaluate the manufacturability or constructability of the design. 4. ROLES FOR KNOWLEDGE-BASED REASONING IN DESIGN These applications hint at the many roles that knowledge-based techniques and systems can play during design. Some of them are presented below. Each provides a particular function, and can be implemented in different ways using AI techniques. Abstraction can be used to discover of which more general design the current (partial) design is an example. This might lead to a better understanding of which design plans or analysis methods to use. Abstraction also supports the use of analogical reasoning. Acquisition can request and integrate new design knowledge. Analysis which is often numerical, is needed to understand the properties (such as strength) of the design or of subcomponents. Association allows related concepts to be discovered, and supports analogical reasoning. Basic Synthesis produces values for attributes, such as color or length, by calculation, or by decision. Classification can be used to categorize the requirements or the current state of the design in order to decide what sort of method or analysis might be used. Conflict Resolution occurs after a conflict has been detected during designing. This might be as simple as a constraint failing, or as complex as two design agents disagreeing about a design decision. Resolution may require retraction or negotiation. Criticism compares a portion of the design against a standard, or some preferences, and points out the ways in which it is lacking. When design requirements are used this can be called "verification". Decomposition divides a design problem into smaller more manageable subproblems. Estimation can be used to produce design values which are roughly right, in order to discover more about the design problem. Evaluation uses the results of analysis, or some aspects of the design, to provide an estimate of quality or the degree to which it meets some design goals (e.g. low cost). Execution follows the instructions given in a design plan. Extraction can be used to find features of the design that can be used for analysis or evaluation. Generation of acceptable candidate values that can be used for the design might be done by Constraint Satisfaction. Guidance provides the designer with a methodology to be followed and can enforce it. Interpretation maps data into concepts that are relevant for the design activity. For example, data resulting from analysis can be interpreted to allow evaluation. Learning can improve the resulting designs, or can improve the design process, making it more efficient (such as in Knowledge Compilation) or more knowledgeable. Memory allows a design history to be maintained that captures the intent or rationale of the designer. It can be used to remember successful methods or designs as cases for case-based reasoning. Negotiation provides a way for a team of experts, or expert systems, to arrive at a design which is acceptable to all parties. Note Making occurs when a designer makes a mental note at some early stage of the design to do or check something later during the design process [Adelson & Soloway 1985]. It might correspond to forming a new constraint. Notification is used to communicate the consequences of a design decision in order to affect other portions of the design (such as via Constraint Propagation or Constraint Posting). Optimization usually numeric, can produce the best values for design attributes, relative to some criteria that can be evaluated. Patching can be used to modify an existing design after flaws have been found in it. Planning the design process, in order to design subcomponents in an appropriate order, for example, is a vital part of design in general. Prediction is often needed to determine the consequences of a design decision. It might be done by Qualitative Reasoning or some other form of Knowledge-based Simulation. Presentation of selected information about the current state of the design, or about standards, for example, is important for assisting the human designer. Recomposition takes finished designs for subcomponents and composes them into a component design. Redesign modifies an existing design in response to conflict, a poor evaluation, or changing requirements. Refinement occurs when a description (e.g., of a function) is mapped to a less abstract description (e.g., of a class of mechanisms). Retraction allows previous design decisions to be discarded. This could be done using some form of Backtracking. Reuse by Analogy, or its weaker cousin Case-based Reasoning, can reduce effort and increase quality by reusing past methods or designs. Simplification of the problem can be carried out by abstraction (for example, by ignoring details or "relaxing" less important constraints), or by noticing regularities [Balazs & Brown 1998]. It might also be done by combining constraints (as in Constraint Subsumption [Tong 1987]). Suggestions generated after criticism, from scratch or by retrieval, can provide information to guide the patching, or any other redesign activity. Selection is a major component of configuration. It can also be used to pick an appropriate plan or analysis method. 5. APPROACHES TO DESIGN STUDY The IntCAD research community now consists of CAD researchers, who use AI techniques to expand the capabilities of CAD systems; AI researchers, who study design knowledge and reasoning; Engineers, who are eager to use smarter tools; and Cognitive Scientists, who study how designers think. Consequently, the literature on AI in Design is spread quite widely. Finger and Dixon [1989a, 1989b], from a mechanical engineering point of view, describe design research as falling into several categories. These include: Descriptive Models, Languages, Representations, Environments, and Computer-based Models. Descriptive Models of the design process are concerned with the "processes, strategies, and problem solving methods designers use." These efforts include collecting protocols from designers, building cognitive models that could mimic the human designer, and collecting and analyzing design cases. Such studies have revealed, for example, the importance of drawing in design and the many roles, such as "memory aid", that it plays [Ullman et al 1990]. Languages and Representations research includes the representation of form, of function and behavior, and of features. Work on Environments attempts to build systems that aid the designer during the design process by providing an integrated set of tools. Computer-based models research is concerned with how the computer can design or assist with designing. AI-based design research is mostly associated with the Languages, Representations and Computer-based models categories. 6. TYPES OF DESIGN In books and papers about design problem-solving we find many terms for types of design, including: Preliminary, Conceptual, Functional, Innovative, Creative, Routine, Embodiment, Parametric, Detailed, Redesign, Non-Routine and Configuration. However, there seems to be a general acceptance of the rough classification of design into routine, innovative, and creative, where each class has less known in advance by the designer. In routine design both the knowledge sources and the problem-solving strategies are known in advance. In innovative design, only the knowledge sources are known in advance. While in creative design neither are known. For Routine design, everything about the design process, including the knowledge needed, must be known in advance. This does not mean that either the specific design solution, or the pattern of use of the knowledge (i.e., the design trace) are completely known in advance. The underlying thesis is that design tasks become routine due to learning brought about by repetition of similar problem-solving. That is, routineness is a direct reflection of experience. Routine designs are done more efficiently, and possibly with better results. In fact, this three class model is much too simple. The level of experience with a certain type of design can be reflected by a position on a Routine --> Non-Routine axis with "very experienced" at one end, and "very inexperienced" at the other (see Brown in [Waldron & Waldron 1991]). An orthogonal Conceptual --> Parametric axis can be used to show the abstractness of the decisions being made. Types of design are points in the space defined by the axes. By Conceptual design we mean that the kind of things being decided at that point in the design are abstract (i.e., conceptual). For example, that the design requirements can be satisfied by an object providing a particular function. By Parametric design we mean that the things being decided are values for a prespecified set of attributes. Another way of classifying design problems is to divide them into those that have subtask ordering decided a priori, those that know the dependencies in advance, but order them during the design, and those for which the dependencies between subtasks are both discovered and ordered during the design [Balkany et al 1990]. We would expect routine problems to belong to the first type, and very non-routine problems to belong to the third. In Dixon's taxonomy of design problems [Dixon et al 1988], the levels are named Functional, Phenomenological, Embodiment, Attribute, and Parametric, depending on whether function, physical principles, general class of solution, type of object, or parameter values are decided at that level. Clearly, these levels correspond to portions of the Conceptual --> Parametric axis. In general, design activity can start at any level of abstraction and finish at any more specific level. Usually, the larger the gap between the level of the specification and the desired level for the design, the harder the design process is. Dixon states that Conceptual design is often used to describe moving from the Function level to the Embodiment level. He considers Preliminary design to be an extension of conceptual design to another level of specificity, i.e., to Artifact Type. Parametric design goes from Artifact Type level to the Artifact Instance level. As we move along the Conceptual --> Parametric axis less structure needs to be decided during the design process. In Configuration, which is a restricted form of design, the components of the designed object can only come from a predefined set [Mittal & Frayman 1989] [Wielinga & Schreiber 1997] [Brown 1998a]. They are selected and arranged together to satisfy some requirements. Each component describes the connections which it allows. It is usually not possible or practical to predetermine all possible configurations [Barker & O'Connor 1989]. Often, artifacts are configured according to a known functional architecture, and certain components can be predetermined as "key". These assumptions help to prune the search for a configuration. Depending on the complexity of the problem, the components may or may not need to have values provided for parameters. For example, a layout (or floor-planning) problem may just be concerned with spatial arrangement, but a resistor may need to be given a resistance value. Note that no new components are used, and a component's connectivity is not changed. Rough Design is an attempt to learn something additional about the design problem by deciding some aspects of the design and then evaluating that partial design. In a more routine design situation, "those values on which much of the rest of the design depends" are known by the designer and can be decided and checked first [Brown & Chandrasekaran 1989]. Other senses of "rough", other than "incomplete", are "abstract" and "approximate". Interval arithmetic may be able to contribute to approximate design [Navinchandra & Rinderle 1989]. Abstract designs are hard to evaluate. However, Tong [1987] suggests that information about "potential bottlenecks with respect to some resource" (such as the number of components needed) might be gathered by the formation and execution of abstract design plans. Redesign problems are concerned with changing prior design decisions. This includes modifying an existing design in response to changing requirements, and making changes to decisions already made, during the design process, as a result of failing constraints. For example see [Daube & Hayes-Roth 1989] [Goel & Chandrasekaran 1989] [Brown 1985] [Steinberg & Mitchell 1985] and Marcus et al (in [Tong & Sriram 1991a]). This can involve using suggestions about suitable changes, that are either prestored or generated by analyzing the situation. Suitable changes can be found by classifying the current situation and mapping to stored changes [Klein 1991] or by negotiation [Sycara 1991]. A record of the reasons for the prior design decisions (i.e., a design history) is also useful [Lee 1997]. A particular form of parametric redesign is Iterative Redesign, where an initial (but complete) heuristically generated design is modified one parameter value at a time [Orelup et al 1988] [Ramachandran et al 1988]. After each modification an evaluation step leads to a suggestion about which parameter to change next and in which direction. This hill-climbing approach can be controlled by meta-knowledge to try to ensure that it keeps improving its solution and approaches a global optimum. This is a form of the "Propose and Revise" method for parametric design. 7. CHARACTERIZING THE DESIGN PROCESS One goal of AI research in design is to try to characterize the design process in enough detail that systems can be built more easily, that design knowledge can be acquired more easily, and that design tools can be matched to design problems. At some level of abstraction, the description above of the possible roles for knowledge-based reasoning in design could be used to provide a vocabulary with which to describe design activity. The challenge is to fully describe each function, to characterize the knowledge each uses, to describe their inputs and outputs, to list their alternative implementations (using AI methods), and to discover distinctive patterns of use. Many people would agree that the general flow of design can be characterized by something like Requirements Formulation + Synthesis + Analysis + Evaluation. There are very many similar models in the design literature. Unfortunately, this characterization is too abstract and does little to help us build computer models. For example, analysis could be done by many methods, such as quantitative simulation or qualitative simulation. Tong [1987] provides an analysis based on characterizing certain kinds of design as Incremental Refinement, where specifications can be converted to implementations (i.e., a design) "directly", via multiple refinements, possibly using "abstraction levels" and "decomposition", with details being provided by Constrained Inference, and corrections being provided by Debugging" . Chandrasekaran [1990] attempts to characterize a large family of design tasks as: Propose + Critique + Modify. Each "subtask" can be carried out by different methods. For the Propose subtask he discusses Decomposition + Solution Composition, for recursively reducing the problem, and Case Retrieval and Constraint Satisfaction for solving the problems or subproblems. In a similar proposal, McDermott (see [Marcus 1988, p. 225]) argues that there are a set of methods "where each method defines the roles that the task-specific knowledge it requires must play and the forms in which that knowledge can be represented" [p. 228]. His Propose + Revise method first extends the design, then identifies constraint violations, suggests potential fixes, selects the least costly fix to try, tries the fix, identifies resulting constraint violations, if there are any it loops to select another fix, and if there are none it tidies up and loops to extend the design again, until it is completed. This is a method to achieve constraint satisfaction. He also suggests an Extrapolate-from-a-similar-case method. Note that the other form of Propose and Revise, used for parametric design, proposes a complete design at each iteration. Balkany, Birmingham & Tommelein [1991] make a "knowledge-level" analysis and comparison of several design systems -- that is, they attempt to isolate the behavior of each system from techniques used to implement that behavior. The systems are AIR-CYL [Brown & Chandrasekaran 1989], M1 [Birmingham et al 1992], PRIDE (see Mittal & Araya in [Tong & Sriram 1991a]), VT (see Marcus et al in [Tong & Sriram 1991a]), and SightPlan [Tommelein et al 1991]. For each system, they characterize its action in terms of sequences of "mechanisms", such as: extend-design, find-constraints, test-constraints, suggest-fixes, select-fix, modify-design, find-constraint, test-constraints, propagate-changes, test-if-done. This sequence, from the VT system, corresponds to McDermott's Propose & Revise method. A completely different approach to characterizing design describes the possible types of knowledge involved and their relationships. It is an attempt to provide a knowledge-level description that removes explicit reference to the design process, but which allows explanation of types of design by referring to patterns of knowledge use. Examples of approaches that tend to be more in this style include [Smithers 1998] [Brazier et al 1994] [Bernaras 94]. 8. USING AI TECHNIQUES In this section we will discuss how some AI techniques might be used to implement functions that play roles in the building of design systems. Others have already been mentioned above. Other examples can be found from the sources in the bibliography. 8.1 Knowledge Representation: In design, many types of knowledge can be used, not all of which can be alluded to here. Knowledge about things, knowledge about design requirements, and knowledge about processes are all useful. Knowledge about both the object being designed (e.g., 3.45 cm long), and general object knowledge (e.g., all #26 flanges have a 3:2 height-to-length ratio) needs to be represented. Frame representations are popular. The basic knowledge about components concerns geometry and topology. Taxonomies of components and Part-Subpart descriptions need to be represented. Other information that needs to be stored are attributes such as color, hardness, material, and surface finish. Properties of material must be available. Ontologies [Borst 1997] provide a clear specification of the concepts used in a domain and the relationships between them. They can be used to facilitate knowledge sharing and reuse: for example, to allow communication between design agents that have been developed separately. Features can relate to form and to function [Dixon et al 1989]. Descriptions of function and behavior [Umeda & Tomiyama 1997] [Ulrich & Seering 1989] are useful during conceptual design, for criticism, and for reasoning about mechanisms [Pu & Badler 1988]. Functional hierarchies are useful for reducing search during configuration [Mittal & Frayman 1989] [Birmingham et al 1992]. Knowledge about the capabilities of processes are important if the design system needs to select an appropriate method. This can be as simple as picking a prestored plan [Punch et al 1995], or as sophisticated as reasoning about which design method is most likely to be able to produce the desired outcome. Other knowledge can be about which decision should take priority [Stefik 1980], how to decompose a problem [Liu & Brown 1994], or what tradeoffs might be made between conflicting goals [Tong 1987]. 8.2 Constraint Satisfaction: Constraints can be used to maintain consistency, prune search and to record interactions between subproblems. They can express many things, including design heuristics, basic equations, material compatibility, and physical limits on components due to strength or manufacturing. Many constraints refer to parameters with numerical values (e.g., L < 12), but reference to symbols is possible (e.g., M = one-of{Brass Steel Wood} ). Adding constraints to the design as a result of making decisions is "constraint formulation". The creation of new constraints from old is "constraint subsumption". Decisions can be communicated by "constraint propagation", or by propagating acceptable values. Propagation enables a "least commitment" strategy. There are several approaches to "constraint satisfaction", i.e., finding values that satisfy a set of constraints. Many problems can be solved using these methods [Stefik 1980] (see Steinberg in [Tong & Sriram 1991a]; Bowen & O'Grady in [Gero 1990]). In some design problems, variables and constraints emerge during the design [Mittal & Falkenhainer 1990]. The use of constraints to handle large design problems has been criticized as being too computationally expensive, and not a good model of human problem-solving. However, recent work attempts to address this by grouping constraints and by organizing them hierarchically. 8.3 Search: In general, design cannot be completely modelled by a standard heuristic search, as evaluation functions are not always available, and as, at best, several search spaces are required -- such as possible plans, possible configurations, and possible combinations of parameter values. In addition, not all problems have fully specified requirements that can act as goals or goal recognizers for a search. However, despite the often exploratory nature of conceptual design, much of design can be described as search. The maintenance of consistency during the search for a design can be handled using Truth Maintenance methods. These are especially useful in situations where assumptions are made during the design. Chronological or Dependency-Directed Backtracking can be used. Dependencies between design decisions can be explicitly recorded and used for backtracking, but they can also serve as a form of design history, for possible subsequent redesign or case-based reasoning. They can also serve as the basis for a Truth Maintenance System (TMS). 8.4 Learning: Some researchers, especially those interested in automatic generation of design tools, have used a learning mechanism with a simple search to learn problem decompositions, or with Generate & Test to improve the generator by moving knowledge from the Test back into the generator (see [Tong 1990] for references to these and other systems). These are examples of Knowledge Compilation systems, which learn in order to increase efficiency [Keller 1991] [Brown 1991]. Other work on learning in design includes: the learning apprentice, LEAP, which learns design "refinement rules" by generalizing the user's input (see [Tong 1990]); the Designer-Soar system that learns to design algorithms [Steier & Newell 1988]; and Bridger, which learns to classify designs for reuse [Reich 1991]. Duffy [1997] provides an overview of research into learning in design. 8.5 Case-based Reasoning (CBR) & Analogy: The direct or analogical use of previous designs or design plans can reduce search and improve quality by taking advantage of stored experience [Maher et al 1995] [Maher & Pu 1997]. Mostow [1990] discusses the replaying of design plans, and compares some systems, including BOGART and ARGO (see Mostow et al, and Huhns & Acosta in [Sriram & Tong 1991]), according to how cases are represented, stored, retrieved, and adapted. Case-based design is also discussed by Sycara et al, and by Goel (see both in [Sriram & Tong 1991]). Gero (see [Maher & Gero 1990, p. 26]) proposes that design cases and all other design knowledge be organized into Schema for efficient access during design. Goel [1997] provides an overview of the use of Analogy in design, while Maher and Gomez de Silva Garza [1997] give a similar overview of CBR. Besides cases that record designs, cases that record design history (and perhaps rationale [Lee 1997]) are also common. An engineering view of design history keeping can be found in [Chen et al 1990]. 8.6 Qualitative Reasoning: During the design process qualitative reasoning techniques can be use to reason about space, flows -- such as heat, fluid or force -- and, more generally, behavior. Required motions can determine shape [Joskowicz & Addanki 1988], shape can be used to derive behavior (see Joskowicz in [Weld & de Kleer 1990, p. 597]), and objects can be checked for fit [Carney & Brown 1989]. Innovative design is possible by mapping a network of qualitative interactions between quantities onto physical structure [Williams 1990]. In order to organize and move easily from one model of an object to another (e.g., from a heat flow model to a kinematic model) the use of a Metamodel [Tomiyama et al 1989] and a Graph of Models have been proposed (see Addanki et al in [Weld & de Kleer 1990, p. 546]). Selection, construction and revision of an appropriate model is also an important issue (see Nayak in [Brown et al 1992]) [Pos 1997]. 8.7 System Architectures: Blackboard-based architectures are useful for the integration of many sources of knowledge, such as in building design (see Sriram et al in [Tong & Sriram 1991b], and Schmitt in [Yoshikawa & Holden 1990]). Rule-based or Grammar-based [K.Brown 1997] methods are often used for individual sources of knowledge. Groups of multiple, autonomous knowledge-based systems can be used to build Multi-Agent Design Systems (MADS) [Lander 1997]. These systems may also incorporate legacy systems such as databases and solid modelors. These systems allow distributed and asynchronous designing, such as can be found in Concurrent Engineering design teams. MADS architectures include those that have the agent relationships decided a priori, and those that are organized dynamically: by making bids for tasks, for example. Manager agents or facilitators may be included to supervise other agents and to support communication between agents, respectively. Standardized communication is helped by the use of ontologies [Borst 1997]. 9. SAMPLE SYSTEMS Most of the well-analyzed systems are the earlier systems, for routine tasks. Besides systems already mentioned, XCON [Barker & O'Connor 1989] and VEXED (see Steinberg in [Tong 1990]) deserve study. Some systems have been generalized to provide expert system shells. These include DSPL from AIR-CYL, EDESYN from HI-RISE [Maher 1988], and EVEXED from VEXED. Other systems for less-routine design include, MOLGEN [Stefik 1980], DONTE [Tong 1990], DESIGNER [Kant 1985], EDISON [Dyer et al 1986] and AM [Lenat & Brown 1983]. More recent work can be found by looking at the papers in the AI in Design proceedings books (e.g., see [Gero & Sudweeks 1998]), by following the references in [Brown & Birmingham 1997], and via the world wide web [Brown 1998]. 10. RESEARCH ISSUES In such a complex and poorly understood area as design, there are many research issues. In addition to basic work on representing features, function and other aspects of design objects, it will be necessary to devise ways to integrate these types of knowledge, and integrate them with more 'traditional' representations (such as solid models) so that reasoning processes can exploit them fully. Languages are needed with which to express an expert's knowledge of design. Both Learning and Knowledge Acquisition [Marcus 1988] for design systems are vital. The use of Neural Networks needs to be studied further, for use in design situation classification or prediction. The use of Genetic Algorithms (in conjunction with Grammars, for example) and Simulated Annealing is very promising. More work is needed in creative design [Gero & Maher 1991] [Goel 1997]. This requires doing much more reasoning at "design time" about what to do and how to do it. Consequently, representing and reasoning about goals, dealing with alternative designs, reasoning about resources, analogy, problem decomposition, evaluation of partial designs, dynamic constraint satisfaction, functional reasoning, using multiple models, combining quantitative and qualitative reasoning, model-based reasoning, and reasoning about failure, all become major issues. Large design problems will require cooperative, and perhaps distributed, design problem-solvers, as well as negotiation. The use of multi-agent design systems raises issues about team formation, learning, and architectures that scale up to larger design systems. Integrating human designers into such systems, and using the resources available on the world wide web provide additional challenges. 11. RESEARCH CENTERS Papers presenting overviews of the work at the Carnegie Mellon University, Rutgers University, the University of Sydney, Worcester Polytechnic Institute, the University of Illinois, Edinburgh University, North Carolina State University, and Wayne State University can be found in [Gero 1989] and [Gero 1990a]. Other major centers include the University of Tokyo, the University of Massachusetts, MIT, the University of Michigan and the Engineering Design Research Centers in the UK. These, and many others, can be found on the world wide web [Brown 1998]. 12. BIBLIOGRAPHY B. Adelson & E. Soloway, "The Role of Domain Experience in Software Design", Trans. on Software Engineering, IEEE, Vol. SE-11, No. 11, 1985, pp. 1351-1360. V. Akman, P. J. W. ten Hagen & P. J. Veerkamp (Eds.), Intelligent CAD Systems II: Implementational Issues. Springer-Verlag, 1989. M. E. Balazs & D. C. Brown, "A Preliminary Investigation of Design Simplification by Analogy", In: Artificial Intelligence in Design '98, (Eds.) Gero & Sudweeks, Kluwer Academic Publishers, 1998. A. Balkany, W. P. Birmingham & I. D. Tommelein, "A Knowledge-level Analysis of Several Design Tools", Artificial Intelligence in Design '91, Proc. 1st Int. Conf. on AI in Design, Edinburgh, Scotland, Butterworth-Heinemann Publishers, 1991. V. E. Barker & D. E. O'Connor, "Expert Systems for Configuration at Digital: XCON and Beyond", Communications of the ACM", Vol. 32, No. 3, March 1989, pp. 298-318. A. Bernaras, "Problem-Oriented and Task-Oriented Models of Design", Artificial Intelligence in Design '94, (Eds.) Gero & Sudweeks, Kluwer, 1994, pp. 499-516. W. P. Birmingham, A. P. Gupta & D. P. Siewiorek, Automating the Design of Computer Systems: The MICON Project, Jones and Bartlett, 1992. W. N. Borst, Construction of Engineering Ontologies for Knowledge Sharing and Reuse. Ph.D. Thesis, SIKS, Dutch Graduate School for Information and Knowledge Systems, University of Twente, the Netherlands, 1997. F. Brazier, P. van Langen, P. van Ruttkay & J. Truer, "On Formal Specification of Design Tasks", Artificial Intelligence in Design '94, (Eds.) Gero & Sudweeks, Kluwer, 1994, pp. 535-552. D. C. Brown, "Failure Handling in a Design Expert System", Computer-Aided Design Journal, Special edition, (Ed.) J. S. Gero, Butterworths, Nov. 1985. D. C. Brown, "Compilation: The Hidden Dimension of Design Systems", Intelligent CAD, III, (Eds.) H. Yoshikawa & F. Arbab, North-Holland, 1991. D. C. Brown, "Which Way to KIC?", Knowledge Intensive CAD, Volume II, (Eds.) M. Mantyla, S. Finger & T. Tomiyama, Chapman & Hall, 1997, pp. 291-294. D. C. Brown, The AI in Design Webliography, http://www.cs.wpi.edu/Research/aidg/AIinD-hotlist.html, CS Dept., WPI, Worcester, MA 01609, 1998. D. C. Brown, "Defining Configuring", http://www.cs.wpi.edu/~dcb/Config/EdamConfig.html, AI EDAM special issue on Configuration, (Eds.) Darr, McGuinness & Klein, 1998a. D. C. Brown & B. Chandrasekaran, Design Problem Solving: Knowledge Structures and Control Strategies" . Research Notes in Artificial Intelligence Series, Morgan Kaufmann Publishers, Inc., 1989. D. C. Brown, M. Waldron & H. Yoshikawa (Eds.), Intelligent Computer-Aided Design, North-Holland, 1992. D. C. Brown & W. P. Birmingham (Eds.), Special double issue on "AI in Design", IEEE Expert: Intelligent Systems & their Applications, March/April, May/June 1997. K. Brown, "Grammatical Design", IEEE Expert, Vol. 12, No. 2, March/April 1997. S. P. Carney & D. C. Brown, "A Continued Investigation into Qualitative Reasoning about Shape and Fit", (AI EDAM) Journal, Vol. 3, No. 2, Academic Press, Nov 1989, pp. 85-110. B. Chandrasekaran, "Design Problem Solving: A Task Analysis", AI Magazine, Special issue on AI based design systems, (Eds.) Maher & Gero, AAAI, Vol. 11, No. 4, Winter 1990. A. Chen, B. McGinnis & D. G. Ullman, "Design History Knowledge Representation and its basic Computer Implementation", Proc. 2nd ASME Int. Conf. on Design Theory and Methodology, J. Rinderle (Ed.), Chicago, IL, ASME, DE-Vol. 27, 1990, pp. 175-184. R. D. Coyne, M. A. Rosenman, A. D. Radford, M. Balachandran & J. S. Gero, Knowledge-Based Design Systems, Addison-Wesley Publishing Company, 1990. F. Daube & B. Hayes-Roth, "A Case-Based Mechanical Redesign System", Proc. 11th Int. Jnt. Conf. on AI, IJCAI-89, Morgan Kaufmann Publishers, Vol. 2, 1989, pp. 1402-1407. J. R. Dixon, J. J. Cunningham & M. K. Simmons, "Research in Designing with Features", Intelligent CAD, I, H. Yoshikawa & D. Gossard (Eds.), North-Holland, 1989, pp. 137-148. J. R. Dixon, M. R. Duffey, R. K. Irani, K. L. Meunier & M. F. Orelup, "A Proposed Taxonomy of Mechanical Design Problems", Proc. ASME Computers in Engineering Conf., San Francisco, CA, Vol. 1, 1988, p. 41-46. A. H. B. Duffy, "The 'What' and 'How' of Learning in Design", IEEE Expert, Vol. 12, No. 3, May/June 1997. M. G. Dyer, M. Flowers & J. Hodges, "EDISON: An Engineering Design Invention System Operating Naively", AI in Engineering, Computational Mechanics Publications, 1986, Vol. 1, No. 1, pp. 36-44. C. L. Dym & R. E. Levitt, Knowledge-Based Systems in Engineering, McGraw-Hill, Inc., 1991. S. Finger & J. R. Dixon, "A Review of Research in Mechanical Engineering Design, Part I: Descriptive, Prescriptive, and Computer-Based Models of Design". Research in Engineering Design, Vol. 1, Springer International, 1989a, p. 51-67. S. Finger & J. R. Dixon, "A Review of Research in Mechanical Engineering Design, Part II: Representations, Analysis, and Design for the Life Cycle". Research in Engineering Design, Vol. 1, Springer International, 1989b, p. 121-137. J. D. Foley, A. van Dam, S. K. Feiner & J. F. Hughes, Computer Graphics: principles and practice, 2nd Edition, Addison-Wesley Publ. Co., 1990. A. Goel, "Design, Analogy, and Creativity", IEEE Expert, Vol. 12, No. 3, May/June 1997. A. Goel & B. Chandrasekaran, "Functional Representation of Designs and Redesign Problem Solving", Proc. 11th Int. Jnt. Conf. on AI, IJCAI-89, Morgan Kaufmann Publishers, Vol. 2, 1989, pp. 1388-1394. V. Goel & P. Pirolli, "Motivating the Notion of Generic Design within Information-Processing Theory: The Design Problem Space", AI Magazine, AAAI, Vol. 10, No. 1, Spring 1989, pp. 19-36. J. S. Gero (Ed.), Knowledge Engineering in Computer-Aided Design, North-Holland, 1985. J. S. Gero (Ed.), Expert Systems in Computer-Aided Design, North-Holland, 1987. J. S. Gero (Ed.), Artificial Intelligence in Design, Proc. 4th Int. Conf. on Applications of AI in Engineering, Cambridge, UK, Computational Mechanics Publications & Springer-Verlag, 1989. J. S. Gero (Ed.), Applications of AI in Engineering V, Vol. 1: Design, Proc. 5th Int. Conf. on Applications of AI in Engineering, Boston, MA, Computational Mechanics Publications & Springer-Verlag, 1990. J. S. Gero (Ed.) Artificial Intelligence in Design '92, Kluwer Academic Publishers, 1992. J. S. Gero & M. L. Maher (Eds.), Modelling Creativity and Knowledge-Based Design, Proc. Wkshp. on Modeling Creativity and Knowledge-Based Creative Design, 1989, LEA Publishers, 1991. J. S. Gero & F. Sudweeks (Eds.) Artificial Intelligence in Design '96, Kluwer Academic Publishers, 1996. J. S. Gero, & F. Sudweeks (Eds.), Artificial Intelligence in Design '98, Kluwer Academic Publishers, 1998. M. Green (Ed.), Knowledge Aided Design, Academic Press, 1991. S. J. Hong (Ed.), IEEE Computer, Special issue on Expert Systems in Engineering, Vol. 19, No. 7, 1986. L. Joskowicz & S. Addanki, "From Kinematics to Shape: An Approach to Innovative Design", Proc. 7th Nat. Conf. on AI", AAAI, St. Paul, MN, Morgan Kaufmann Publishers Inc., Vol. 1, 1988, pp. 347-352. E. Kant, "Understanding and Automating Algorithm Design", Trans. on Software Engineering", IEEE, Vol. SE-11, No. 11, Nov. 1985, pp. 1361-1374. R. M. Keller, "Applying Knowledge Compilation Techniques to Model-Based Reasoning", IEEE Expert, Special issue, Knowledge Compilation: A Symposium, A. K. Goel (Ed.), Vol. 6, No. 2, April 1991, pp. 82-87. M. Klein, "Supporting Conflict Resolution in Cooperative Design Systems", IEEE Trans. on Systems, Man and Cybernetics, Vol. 21, No. 6, Nov/Dec 1991, pp. 1379-1390. S. E. Lander, "Issues in Multiagent Design Systems", IEEE Expert, Vol. 12, No. 2, March/April 1997. J. Lee, "Design Rationale Systems: Understanding the Issues", IEEE Expert, Vol. 12, No. 3, May/June 1997. D. B. Lenat & J. S. Brown, "Why AM and Eurisko Appear to Work", Proc. Nat. Conf. on AI, AAAI-83, Washington, D.C., 1983, pp. 236-240. J. Liu & D. C. Brown, "Generating Design Decomposition Knowledge for Parametric Design Problems", Artificial Intelligence in Design '94, (Eds) J. Gero & F. Sudweeks, Kluwer Academic Publishers, 1994, pp. 661-678. M. L. Maher, "HI-RISE: An Expert System for Preliminary Structural Design", Expert Systems for Engineering Design, M. D. Rychener (Ed.), Academic Press, Inc., 1988, pp. 37-52. M. L. Maher, M. B. Balachandran & D. M. Zhang, Case-Based Reasoning in Design, Lawrence Erlbaum Assoc., 1995. M. L. Maher & J. S. Gero (Eds.), AI Magazine, Special issue on AI based design systems, AAAI, Vol. 11, No. 4, Winter 1990. M. L. Maher & A. Gomez de Silva Garza "Case-Based Reasoning in Design", IEEE Expert, Vol. 12, No. 2, March/April 1997. M. L. Maher & P. Pu (Eds.), Issues and Applications of Case-Based Reasoning in Design, Lawrence Erlbaum Assoc., 1997. M. Mantyla , An Introduction to Solid Modelling, Computer Science Press, Inc., 1988. M. Mantyla, S. Finger & T. Tomiyama (Eds.), Knowledge Intensive CAD, Vol.2, Chapman & Hall (IFIP), 1997. S. Marcus (Ed.), Automating Knowledge Acquisition for Expert Systems, Kluwer Academic Publishers, 1988. S. Mittal & B. Falkenhainer, "Dynamic Constraint Satisfaction Problems", Proc. 8th Nat. Conf. on AI, AAAI Press & MIT Press, Vol. 1, 1990, pp. 25-32. S. Mittal & F. Frayman, "Towards a generic model of configuration tasks", Proc. 11th Int. Jnt. Conf. on AI, IJCAI-89, Morgan Kaufmann Publishers, Vol. 2, 1989, pp. 1395-1401. J. Mostow, "Design by Derivational Analogy: Issues in the Automated Replay of Design Plans", Machine Learning: Paradigms and Methods, (Ed.) J. Carbonell, MIT Press & Elsevier, 1990, pp. 119-184. D. Navinchandra & J. Rinderle, "Interval Methods for Concurrent Evaluation of Design Constraints", Proc. of the ASME Ann. Conf., Symposium on Concurrent Product and Process Design, 1989. M. F. Orelup, J. R. Dixon, P. R. Cohen & M. K. Simmons, "Dominic II: Meta-Level Control in Iterative Redesign", Proc. 7th Nat. Conf. on AI, AAAI, St. Paul, MN, Morgan Kaufmann Publishers Inc., Vol. 1, 1988, pp. 25-30. A. Pos, Automated Redesign of Engineering Models, Ph.D. Thesis, SIKS, Dutch Graduate School for Information and Knowledge Systems, University of Twente, the Netherlands, 1997. URL: http://wwwis.cs.utwente.nl:8080/~pos/thesis.html P. Pu & N. I. Badler, "Design Knowledge Capturing for Device Behavior Reasoning", Artificial Intelligence in Engineering: Design, J. S. Gero (Ed.), Elsevier, 1988, pp. 37-56. W. F. Punch, A. K. Goel & D. C. Brown, "A Knowledge-Based Selection Mechanism for Strategic Control with Application in Design, Assembly, and Planning", International Journal of Artificial Intelligence Tools, Vol. 4 (3), Sept. 1995, pp. 323-348. N. Ramachandran, A. Shah & N. A. Langrana, "Expert System Approach in Design of Mechanical Components", Proc. ASME Int. Computers in Eng. Conf., San Francisco, CA, 1988. pp. 1-10. Y. Reich, "Design Knowledge Acquisition: Task Analysis and a Partial Implementation", Knowledge Acquisition: An International Journal of Knowledge Acquisition for Knowledge-Based Systems, 1991. M. D. Rychener (Ed.), Expert Systems for Engineering Design, Academic Press, Inc., 1988. H. A. Simon, The Sciences of the Artificial, MIT Press, Cambridge, MA, 1969. T. Smithers, "Towards a Knowledge Level Theory of Design Process", In: Artificial Intelligence in Design '98, (Eds.) Gero & Sudweeks, Kluwer Academic Publishers, 1998. D. Sriram & C. Tong (Eds.), Artificial Intelligence in Engineering Design: Volume II -- Models of innovative design; Reasoning about physical systems; Reasoning about geometry. Academic Press, 1991. M. Stefik, "Planning with Constraints (MOLGEN: Part 1 and Part 2)", Artificial Intelligence, Vol. 16, No. 2, 1980, pp. 111-169. D. Steier & A. Newell, "Integrating Multiple Sources of Knowledge into Designer-Soar, an Automatic Algorithm Designer", Proc. 7th Nat. Conf. on AI, AAAI, St. Paul, MN, Morgan Kaufmann Publishers Inc., Vol. 1, 1988, pp. 9-13. L. I. Steinberg & T. M. Mitchell, "The Redesign System: a Knowledge-based approach to VLSI CAD", IEEE Design & Test, February 1985, pp. 45-54. K. Sycara, "Negotiation in Design", In: Computer Aided Cooperative Product Development, D. Sriram, R. Logcher & S. Fukuda (Eds.), Lecture Notes Series, Springer Verlag, 1991. P. J. W. ten Hagen & T. Tomiyama (Eds.), Intelligent CAD Systems I: Theoretical and Methodological Aspects Springer-Verlag, 1987. T. Tomiyama, T. Kiriyama, H. Takeda & D. Xue, "Metamodel: A Key to Intelligent CAD Systems", Research in Engineering Design, Springer International, Vol. 1, No. 1, 1989, pp. 19-34. T. Tomiyama, M. Mantyla & S. Finger (Eds.), Knowledge Intensive CAD, Volume I, Chapman & Hall (IFIP), 1996. I. D. Tommelein, R. E. Levitt, B. Hayes-Roth & T. Confrey, "SightPlan Experiments: Alternative Strategies for Site Layout Design", Journal of Computing in Civil Engineering, ASCE, Vol. 5, No. 1, January 1991, pp.42-63. C. Tong, "Toward an Engineering Science of Knowledge-Based Design", Artificial Intelligence in Engineering, Computational Mechanics Publications, Vol. 2, No. 3, 1987, pp. 133-166. C. Tong, "Knowledge-Based Design as an Engineering Science: the Rutgers AI/Design Project", Applications of AI in Engineering V, Vol. 1: Design, J. S. Gero (Ed.), Proc. 5th Int. Conf. on Appl. of AI in Eng., Boston, MA, Computational Mechanics Publications & Springer-Verlag, 1990, pp. 297-319. C. Tong & D. Sriram (Eds.), Artificial Intelligence in Engineering Design: Volume I -- Representation: structure, function & constraints; Routine design. Academic Press, 1991a. C. Tong & D. Sriram (Eds.), Artificial Intelligence in Engineering Design: Volume III -- Knowledge acquisition; Commercial systems; Integrated environments. Academic Press, 1991b. K. T. Ulrich & W. P. Seering, "Synthesis of Schematic Descriptions in Mechanical Design", Research in Engineering Design, Academic Press, Vol. 1, No. 1, 1989, p. 3. D. G. Ullman, S. Wood & D. Craig, "The Importance of Drawings in the Mechanical Design Process", Computers and Graphics, Vol. 14, No. 2, 1990, pp. 263-274. Y. Umeda & T. Tomiyama, "Functional Reasoning in Design", IEEE Expert, Vol. 12, No. 2, March/April 1997. M. Waldron & K. Waldron (Eds.), Mechanical Design: Theory and Methodology, Springer-Verlag, 1995. D. S. Weld & J. de Kleer (Eds.), Qualitative Reasoning about Physical Systems, Morgan Kaufmann Publishers, 1990. R. Wielinga & G. Schreiber, "Configuration-design problem solving", IEEE Expert, Vol. 12, No. 2, March/April 1997. B. Williams, "Interaction-based Invention: Designing Novel Devices from First Principles", Proc. 8th Nat. Conf. on AI, AAAI Press & MIT Press, Vol. 1, 1990, pp. 349-356. M. E. Winston, R. Chaffin & D. Herrmann , "A Taxonomy of Part-Whole Relations", Cognitive Science, Vol. 11, 1987, pp. 417-444. H. Yoshikawa & D. Gossard (Eds.), Intelligent CAD, I, North-Holland, 1989. H. Yoshikawa & T. Holden (Eds.), Intelligent CAD, II, North-Holland, 1990. H. Yoshikawa & F. Arbab (Eds.), Intelligent CAD, III, North-Holland, 1991. SELECTED CONFERENCES International Conference on AI in Design. International Conference on AI in Engineering, Computational Mechanics Institute. International Conference on Computational Models of Creative Design. International Computers in Engineering Conference, ASME. International Conference on Design Theory & Methodology, ASME. NSF Design & Manufacturing Systems Conference. IFIP WG 5.2 Working Conferences. SELECTED JOURNALS Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AI EDAM), Cambridge University Press. AI in Engineering, Elsevier Science Publishers. Concurrent Engineering: Research and Applications Journal (CERA), Technomic Publishing Company Inc. Engineering Applications of Artificial Intelligence, Elsevier Science Publishers. International Journal of Design Computing, http://www.arch.usyd.edu.au/kcdc/journal/, University of Sydney. Research in Engineering Design, Springer-Verlag New York Inc.
David C. Brown Worcester Polytechnic Institute September 1998