The Design Process: A Computational Perspective
A Position paper submitted to NSF Workshop on Decision-Based Design

Vasant Honavar
honavar@cs.iastate.edu

Artificial Intelligence Research Laboratory
Department of Computer Science
Iowa State University
Ames, Iowa 50011-1040

The Ubiquity of Design

None of us would probably dispute that architects design buildings, VLSI engineers design computer chips, and so on. However, it is worth noting that engineers are not the only designers. Design is an activity that most humans (and even some animals) routinely engage in. However, different designers operate with very different design objectives, design tools, and consequently, different design outcomes. Indeed, as pointed out by Herbert Simon, the Nobel prize winning economist and one of the founders of Artificial Intelligence, any entity, be it natural or artificial, that devises courses of action aimed at changing existing situations into preferred ones (whatever they might be), can be said to engage in design activity [Simon, 1981].

It is highly improbable that the nature of cognitive activity that designs material artifacts is fundamentally different from that which devises an economic recovery plan, a novel proof of a mathematical theorem, a new drug with certain desired properties, or a new undergraduate engineering curriculum. Computation (loosely speaking, the execution of an algorithm) is the best metaphor that we currently have for understanding and modeling cognitive processes. Indeed, that cognition can be modeled by computation is the working hypothesis of artificial intelligence and cognitive science [Newell, 1990; Uhr and Honavar, 1994; Russell and Norvig, 1995]. Therefore, it stands to reason that attempts to understand, characterize, shape, and perhaps even replicate the design process should begin with an investigation of the intellectual, cognitive, and by implication, computational processes that underlie design in different domains. The remainder of the paper briefly explores the implications of this position.

Design as Search

The design process, from a computational perspective, essentially involves searching a design space. The design space, in AI terms, is a search space. It can be described by the 3-tuple (S,O,G) where S is the start state (which captures the existing state of affairs), O is the set of operators that can be used to transform a state into another, and G is a specification of the desired goal state (e.g., one that meets the design objectives). For example, in a theorem proving task (which involves devising a proof of a theorem, e.g., one that is stated in first order predicate logic), the initial state consists of the axioms, the goal state is the theorem to be proved, and the operators are the logically sound rules of inference. Notice how similar this task is to designing an economic plan or a new drug with certain desired properties. The result of the design activity, in each of these cases, is a path or a sequence of operator applications that transforms the initial state into a goal state. A variant of this formulation captures all the information about the design in the resulting state itself and the design task involves exploring the design space to identify a state that meets the design objectives. It is also possible to think of the design task in terms of its decomposition into hierarchy of (hopefully simpler) design subproblems all the way down to primitive design problems with known solutions. It is easy to extend this notion of design as search to design as optimization to deal with scenarios in which the objective of the designer is to come up with an optimal design or a near-optimal design. Regardless of the particular formulation used, design problem is fundamentally a search problem.

Like any problem that involves search in typically large spaces, design problems tend to be computationally hard in the absence of appropriate knowledge to guide search. Fortunately, search can be guided by knowledge that is at the disposal of the designer. This knowledge may be domain independent or domain specific and may take various forms. For example, such knowledge may be used to help narrow the scope of the search by effectively constraining the search to certain parts of the search space, or rank-ordering the alternatives available for exploration at any given stage of the design process in terms of their promise, etc. This knowledge itself may be acquired and refined by the designer through experience [Honavar, 1994; 1998a; Langley, 1995; Mitchell, 1997]. While knowledge is useful in constraining the search, it should be noted that a blind reliance on the known can prevent exploration of the unknown and hence hinder the discovery of novel and truly creative designs.

A critical issue in solving search problems is the choice of suitable representation language for describing the states in the search space as well as the operators used to search the space. It is well known in AI that these choices can have a major impact on the effectiveness and efficiency of search. For further discussion of this and related issues, the interested reader is referred to [Russell and Norvig, 1995].

Creativity involves not only exploration of domains, but modification and extension or transformation of domains by manipulation of domain-specific constraints or by other means [Boden, 1990]. AI explorations of creativity can shed light on creativity in design.

Design as Decision-Making

There are at least two key places in which decisions of the designer play a key role in the design process and consequently, its outcome. First, the designer plays a central role in the specification and interpretation of design objectives. This involves decisions involving choice among alternatives as well as tradeoffs among multiple (often conflicting) objectives. This is true even if the design objectives are handed down to the designer because ultimately it is the designer who makes use of the design objectives during the design process, and hence consciously or unconsciously interprets them. For instance, an architect asked to design a new convention center with a specified capacity and an approximate budget has to make several major decisons regarding the architectural style, tradeoffs between aesthetics, functionality, and cost, etc. This might involve assigning different utilities to different objectives and combining them into some figure of merit. Utility theory and decision theory [Keeney and Raiffa, 1976; French, 1988] provide formal models of rational choice and decision making using multiple objectives under uncertainty. The designer also, consciously or subconsciously, effectively decides on the design space to be explored (and the operators to explore it with) during the design process. Emerging theories of knowledge representation in artificial intelligence and cognitive science while necessarily tentative and incomplete, offer useful insights into this process. In any event, the decisions made by the designer in this phase of design have profound consequences on the outcome of the design process.

Second, the designer, having committed to a set of design objectives, and a design space and operators, has to make a second set of decisions. One of these involves the choice of a search strategy to use in exploring the space. For example, the designer might employ a random generate and test approach to design; or a systematic search through the space (e.g., using breadth-first search); or a systematic search guided by an appropriate heuristic function that determines the order in which alternative paths are explored (or not explored) during search based on their perceived promise; or a randomized search that combines or alters promising partial solutions to generate other candidate designs to be evaluated (e.g., genetic algorithms). Additional decisions might involve dynamic changes to the search strategy based on the information gained during search; incrementally modifying a previous design to meet new objectives or versus developing a new design from scratch; sharing incomplete or partial designs with other interested parties in order to obtain feedback; etc.

Design as Distributed Problem Solving

In practice, design is almost always a collaborative activity that involves multiple individuals. Each designer or domain expert typically brings specialized knowledge or skills to the design process. Recent research in Artificial Intelligence [Minsky, 1986; Wooldridge and Jennings, 1995; O'Hare and Jennings, 1996; Bradshaw, 1997; Honavar, 1998b] has begun to develop computational models of intelligent agents, inter-agent communication, distributed, and collaborative problemsolving. An intelligent agents are entities that perform a set of tasks on behalf of a user with some degree of autonomy. Intelligent agents in general, and heterogeneous multi-agent problemsolving systems in particular, provide a useful paradigm for exploring, modeling, and perhaps even replicating complex design activities of groups and organizations. In particular, such a framework would facilitate study of communication, collaboration, partial knowledge, and uncertainty in the design process.

Summary

Design is a cognitive activity that all humans, many animals, and to a limited extent, intelligent machines, engage in. Given the ubiquitous nature of design activity, it appears highly improbable that the underlying cognitive processes involved domains are fundamentally different. Since computation offers one of the most useful metaphors for modeling and even engineering cognitive systems, it makes a lot of sense that exploration of design as a cognitive process should start with a computational characterization of the activities involved. Some natural implications of this position lead us to explore design in terms of computational and information processing processes involved in search, decision-making, and distributed problemsolving.

References

1. Boden, M. A. The Creative Mind. New York, NY: Basic Books. 1990.
2. Bradshaw, J. (Ed). Intelligent Software Agents. Cambridge, MA: MIT Press. 1997.
3. French, S. Decision Theory: An Introduction to the Mathematics of Rationality. New York: Ellis Horwood. 1988.
4. Honavar, V. Toward Learning Systems That Integrate Multiple Strategies and Representations. In: Artificial Intelligence and Neural Networks: Steps Toward Principled Integration.. Honavar, V. and Uhr, L. (Ed). Boston, MA: Academic Press. 1994.
5. Honavar, V. Inductive Learning: Principles and Applications. In: Intelligent Data Analysis in Science. Cartwright, H. (Ed.) London: Oxford University press. 1998a, To appear.