Cognitive Processes and III-Defined Problems: A Case Study from Design

Introduction

All problems can be said to consist of translating some entity (A), into some other entity (B), which is specified in terms of goals to be achieved (A~ B). The major efforts of problem solving theory to date deal with problems where A, the initial problem state, ~. the operators available to alter the problem state, and B, the goals to be achieved, are specified, either explicitly or by some agreed upon formal conventionl. Thus detailed analyses have been made of how people determine chess moves, how they solve geometry, word algebra, and crypt­ ari thmetic problems, and how they solve logic proofs2. While some are less well-specified than others (in chess, the goals for evaluating a specific move are open to individual interpre­ tation), all of the tasks thus far analyzed have an operational formulation. Such problems are considered to be well-defined.

This paper describes efforts to extend the information processing model of problem solving to those problems where part of the problem specification is lacking. Of interest are those tasks where a formal language for describing the problem space, operators for moving through the problem space, or the precise expression of an acceptable goal state is not given. In such tasks, the problem solver must specify the missing information before search of the problem space is possible. Such problems can be called ill­ defined.

An example of ill-defined problems are the space planning tasks found in engineering, architecture, and urban design. Space planning can be defined as the selection and arrangement

* This work was supported by the Advanced Research Projects Agency of the Office of the Secretary of Defense (F 4460-67-C-0058) and is monitored by the Air Force Office of Scientific Research.

COGNITIVE PROCESSES AND ILL-DEFINED PROBLEMS: A CASE STUDY FROM DESIGN*

by Charles M. Eastman Institute of Physical Planning Carnegie-Mellon University

of elements in a two- or three-dimensional space, subject to a variety of constraints and /or eva lua­ tion functions. Space planning problems lack a well-specified language for their representation. The generative transformations available to the problem solver for manipulating a design are not known. Most such problems also lack a precise formulation of an acceptable goal state.

This paper presents a detailed analysis of one example of ill-defined problem solving. The problem is a space planning task commonly found in architecture, the selection and arrangement of elements in a room. Evidence from this analysis is presented which advances two hypotheses: (1) the major distinction between well- and ill­ defined problems is the assumed availability of a specification process for defining the problem space and goals of a problem. Ill-defined problems are subjectively specified; (2) if the specification process is the major distinction between well- and ill-defined problems, then a complementary hypothesis would be that the search processes used by humans to solve both t ypes of problems would be similar. The motives behind these efforts include gaining a better knowledge of those processes which society has traditionally called "creative." Such studies may also provide the foundations of a method for automatically solving ill-defined problems.

P~ychological Foundations

The psychological premises of these studies are similar to those involved in the work of Newell and Simon, E. B. Hunt, and many others who use information processing concepts to study concept formation and problem solving3. The best descriptions of these premises are found in Miller, Galenter and Pibram's Plans and the Structure of Behavior or in Walter Reitman's Cognition and Thought4.

The model proposed is as follows. Thinking is information processing. The sources of information may be the environment, the physio­ logical state of the individual, or his memory . Memory is interpreted as allowing independent recall of past environmental or physiological states and recall of past intermediate processing. Cognition--or thinking--is the resultant of specific information being brought together in a unique combinatorial sequence. In this light, a problem situation is unique because a specific response to a set of inputs is not directly available. At issue is the selection of appro­ priate inputs from memory or from the environment and the search for their possibly unique combi­ natorial sequence. The processing that cogni­ tion and problem solving involves can be modeled as a series of transformations generating a sequence of information states. The total number of states generated by applying all permutations of applicable information to all information states defines the total problem space. The means used to sequentially generate information states so that one is created that satisfies the problem goals is called the search strategy.

Information processing, whether it be in man or machine, can only be achieved when the rele­ vant information is in an appropriate processing language. Processing languages provide the operators necessary for combining information. Well specified processing languages include computer programming languages, algebra, symbolic logic, and other calculi. The processing lan­ guage used in human cognitive processes has not been identified. Human problem solving theory has proceeded on the assumption that the well­ specified processing languages listed above, since they are used by man, are partial subsets of the formal language internally available to him. Problem solving tasks have been analyzed in terms of the problem spaces and operations available in these languages. In the past, problem solving analysts have limited themselves to those tasks where some well-specified formal representation was available.

Problem solving analysis usually takes the form of studying how a problem solver treats a special task assigned him. Generally unreported in the literature, yet a common occurence in most actual experiments is the problem solver's difficulty in understanding the task exactly as it is conceived by the analyst. The problem solver's initial assumptions are different and require correction before the experiment can proceed. This problem points out the fact that problem solving analysis involves the comparison of two parallel processes. From the explicit problem statement both problem solver and analyst identify the goals to be achieved and elaborate them as needed. Both either assume or select a processing language to work in and within it devise various strategies for exploring the problem space thus created. The analyst can understand the problem solver's processes to the degree that he can find correspondence between the processes he has experienced and thus understands and those of the ~. Fruitful analysis requires the analyst to have processed significant portions of the problem space so as to maximize thes e correspondences. To further maximize such correspondences, only problems that allow the analyst to make strong assumptions about the goals and problem space used by the problem solver have normally been used. Yet the difficulties of the ~ in understanding the analyst's conception of the task emphasizes the variability in the processes by which tasks can be specified.

If the assumptions of parallel processes and the search for correspondences is applied to the specification of problem goals and a processing language, this aspect of processing also should be amenable to analysis. It need not be predetermined.

Like most studies of human problem solving, the method used in the studies reported here consisted of giving a Subject (~) a complex task

and recording his expressive behavior while solving the problem. Detailed records of sketches and verbal behavior were carefully collected. Other potentially significant behavior, such as facial expressions and looking at objects as a source of auxiliary input, were also recorded. Together, this information made up a protocol from which thP int ernal processing of the~ could be analyzed5.

The Task

A typical small scale space planning prob l em is shown in Figure I. It asks a Subject to redesign an existing room so as to make it "more luxurious" and "spacious" and sets bouqdaries for the solution in terms of cost.*

This particular task is ill-defined in at least two ways. No existing formal language can adequately represent space planning problems. While the informal representation for such problems is orthographic projection, the elements of this language, its syntax, and rulesfor generation or manipulation are unknown. These aspects of the representation are left to the problem solver to intuitively identify. Another ill-defined aspect of space planning problems in design is the identification of problem goals. The problem in Figure I is typical in that no specific information is provided as to what a satisfactory design should consist of. Generally, design tasks have as their explicit goal the specification of some physical entity in a form allowing construction. Left implicit are many criteria the specification must satisfy. It is assumed that the engineer, architect, or city planner solving the problem is familiar enough with it to know what specific elements are to be included in the design and their function. From his background, he is expected to be able to identify the goals which apply to various selection and arrangement possibilities.

Many protocols have been collected from this particular task. Some were presented in an earlier report6. A new protocol gained from this task is shown on the left side of Figure II (which continues for several pages). The S of the protocol was a twenty-six year old - industrial designer, who was attending graduate school. He had two years of professional design experience. Approximations of the figur es drawn by this ~ while solving the problem are included in the protocol. It is broken into sections, each of which corresponds to a protocol minute (PM).

* The particular task presented here, the design of a bathroom, was chosen because of its general familiarity to a wide diversity of people both within and outside of the design professions. Its use here was not to gain detailed information concerning the solution t o this specific type of problem but to learn more about the method by which a human deals with common yet ill-defined problems.

Essentially, the S presented here created an alternative design for-the bathroom by identi­ fying and satisfying goals from his own experience as to what a good bathroom design should be. Privacy, a neatly ordered appearance, adequate circulation and access, short plumbing lines, and low cost were the most evident concerns. While generally there was more emphasis on identifying design goals early in the protocol and on search for an arrangement at the end, both processes were highly intermixed. In all, five alternative bathroom designs were created and evaluated. Only two were completely developed. Figure III presents the general sequence of processing described in the protocol. All external process­ ing took place in a plan drawing representation, except for a short sequence which utilized a vertical section. The total processing time was forty-eight minutes.

Task Analysis

Ill-defined problems are without a predeter­ mined language or explicit goals. The initial requirement for analyzing ill-defined problems is identification of these aspects of the problem solver's processes. The general identification of goals and processing languages turned out to be straightforward for the example protocol and was achieved by scanning it for the following types of information:

1. All physical elements that were considered or manipulated during problem solving (what we call Design Units (DUs));
2. All information that was used to test or determine a design arrangement or selection of a DU, or any information used to derive such information. This information was assumed to identify the problem goals;*
3. All operations that produced new solu­ tion states. A solution state was considered to consist of the current arrangement of DUs and current informa­ tion about the problem. A change in either the arrangment or the information available was considered a new solution state.

The information that was identified is listed in Figures IV and V. These listings give an inter­ pretation, in verbal form, of all information which evidence suggests was processed during the problem solving described in the protocol. Much of it was never verbalized, but was only silently applied in some manipulation within the problem. Other information was mentioned but its use never verified. This information has not been listed.

* In our terminology, a constraint is a function applied to a solution state and returns a boolean evaluation. An evaluation function is a function whose value continuously varies with its state. A goal is the general name for both evaluation functions and constraints. A consideration is information used to derive a goal.

Corresponding to each section of the protocol and to its right is a detailed description of the processing that transpired, coded in terms of the information listed in Figures IV and V.

Our knowledge of design methods allows us to correctly anticipate orthographic drawings as the processing language used in searching for a satisfactory arrangement. This intuitively defined language seemed to be automatically assumed by the ~· Alternative formal descriptions of the operations, element, and syntax of orthographic projection have been developed and presented elsewhere 7. They will not be elaborated here. The operations and language used in the selection of DUs and identification of goals was not orthographic projection, but took quite a different form.

Even though the protocol did not present search and problem specification processes as disjoint processes, the following discussion initially considers each separately. This approach allows existing knowledge about each of these processes to be brought to bear on the protocol. Following individual consideration, their interactive and confounding effects are considered.

Goal and Design Unit Specification

Given the partial specification of a problem, a problem solver has available at least two means to complete it. He may: (1) disambiguate the given specification and attempt to identify subtle or implicit information within it, or (2) re­ identify the problem using his own perceptions of the initial situation. Both approaches are used in design. The first approach predominated in a previously presented protocol, gained from the same task used here B. The~ in the included protocol, in contrast, chose to re-identify the problem.

In order to understand the processes by which the ~ specified DUs and goals for the problem, an attempt has been made to intuitively reconstruct two portions of his specification process. The sequence in which information is expressed has been identified so as to suggest what kinds of processes may be generating it. In recording the sequences of processing, simple diagrams are used. They should not be considered literal models of the internal data structures being accessed, but may be serve to suggest some properties of those structures.

In an early part of the protocol, the ~ is told that the design he is to generate should respond to the needs of children (see PM2). Soon afterwards, he recognizes a need to store bath­ towels and children's dirty clothes. He also relates dirty clothes to the location where they are cleaned - the washroom - and wonders about the distance between it and the bathroom. He suggests that temporary storage for dirty clothes might be needed. Much later (PM21), this line of thought is picked up again and the recognition made that a clothes hamper would be a positive component of the design. This information is gen­ erated when the utilization of storage space is being considered. The sequence of associations made i s pre sented in Figure VIa.

What seems to transpire here is a sequence of thinking ending with the identification of a particular Design Unit relevant to the problem.

Another example of an association process is seen at the very end of the protocol (PM47). Earlier, the~ was told that the window was of the operable variety and that it contained frosted g lass . The S in the current sequence is considering the detail design of the storage cabine t located in front of the window, While working on the cabinet, he identifies that it may be difficult to close the drapes in the win­ dow. This seems to have been achieved by recog­ nizing the distance between the clear floor area and the window . See Figure VIb.

In both these sequences, information from the environment (e . g. , from the Experimenter, the original design, or from the problem state­ ment) is r e lated to original information gen­ erated by the ~. No other source for this new information is possible. In both examples, several piece s of information are generated and related with those that are given before informa­ tion of specific relevance to the problem is gen­ erated . The first sequence identifies a new DU; the second identifies a constraint. The two examples are the longest sequences of related information that produce design information. Thus they are the most explicit. Sequences of unitary length are common (see PMS, PMll, PMlS, PM33).

The proces ses which produce such informa­ tion might best be considered and examined for pot ential modelling as information retrieval processes operating on a large base associatively s tored memory. The given problem information i s the initial queries into the system. Some­ times a desired access is not initially made; only further inputs al l ow isolation of relevant design infor ma tion. Mos t further input s ar e ga ined from cues ident ified while processing other parts of the problem. By mi xing informa­ tion retrieval with arrangement processes, new access quer i es can be identified and used to reinformce those made with the originally avail­ able information . These addit i onal cues seem to al l ow accesses t hat no single inference making capability could match.

Only a few insights are offered as t o the de tail structure of this system. Some evidence suggests that the major e l ements of the retrieval system are physical elements (e ,g ., DUs, people - most generally , nouns). These are the aspects of the information that are expr essed most often and which seem to gain e laboration from further processing. The s tructure be tween these nodes cannot be identified from the protocol data. Most r easonably, they would be verb and preposi­ tional phrases . Such a s tructure i s supported by r ecent work reported in the psychological litera­ ture. 9

The DUs identified by the ~ took one type of organization during one phase of processing, only to take another later on. These different defi­ nitions were not disjoint, but rather overlapping in a set-theoretic manner . For example, during major portions of the protocol the toilet-tub was manipulated a s a single element. La ter, though, it was trea t ed as two separate elements , At one point the bathtub was further decomposed into its components. Each e lement thus had the possibility of being broken into the e l ements of which it was a set. The hierarchical decomposi­ tion thus produced is shown in Figure V.

The purpose of composition or decomposition of DUs is essentially one of search efficiency. Decomposition widens the solution space by a l­ lowing a greater number of primitive DUs to gen­ erate a greater number of design alternatives . This is useful when the current solution space is too restrictive to easily find a solution. Alte rnatively, composition narrows the sear ch space. Composition is especially app licable to sets of DUs which are relatively non-interact ive with others and can be arranged so as to sat i sfy the bnteractive goals or constraints within the set~ The bathtub-watercloset combination in the protocol is an excellent example of the use of composition. An information retrieval system useful for design problem solving would need the capability of composing and decomposing DUs.

The issue possibly raised here and elsewhere as to whether information is stored discre tely in the agglome r ated concepts used in the given de­ scription and protocol analys is is easily r esolved . In all memories known, a trade-off exists between the alternatives of explicitly storing large amounts of data and possessing a process that dynamically generates the information when it is needed. If this trade-off exists in a memory, then the modelling of that memory can r e flec t this trade-off also. It may be most exped i ent at any level of model building to assume that in­ formation is explicitly stored. But a sing l e node in a model at one l evel of organization may r epre sent a whole pattern of process ing at anothe r level. The only requirement t ha t is logically imposed is that information processing, at some point , pass through the s tate defined as a discrete element in any model. The va l ue of t he particular points chosen is determined by the parsimony of the description allowed.

The implications ga ined from the analysis of thi s and other protocols i s that human performance in r e trieving information f r om memory for applica­ tion to ill- defined problems i s quite limited. In space planning, a retrieval rate of one piece of applicable information per minute was excep­ tional. The size of memory required to intelli­ gent ly so lve a class of ill-defined problems is only now becoming known. That size seems to be sma ller than expected . The eventual development of automated problem solvers may actually benefit from a memory even more limited than the size implied as necessary from human protocols. The controlled input of new information could delimit the data base to verified information, eliminat­ ing much questionable data. An initial explora­ tion of an automated design retrieval system has been made by Moran.ll More extensive models of memorie s capable of the kinds of retrievals re­ quired here ~ave been developed by Green et al and Quillian,12 No model of memory developed thus far can perform, both in speed and diversity, in a manner similar to that described in the pro t ocol . No model has yet been proposed that take s advantage of auxiliary inputs gained from inte rvening processing. The interaction of search and retrieval processes may offer major be ne fits to large base associative memories.

Search Processes in Design

When faced with the problem of arranging e lements in a predefined space according to some part ially s pecified goals, a ll designers thus far tested have used a modus operandi for generat­ ing solutions that included as its main activity the sequential se l ec tion of both a location and a physical e l ement to be l ocated. If the DU could be located in the proposed location and an evaluation of the current total configuration was success f ul, then a new e l ement was added to the design . If the evaluation failed, the current e l ement or another was manipulated. Such opera­ tions can be viewed as transformations in a prob­ lem s tate space according to the traditional search paradigm. Examples of this sequence are evident in Figure III as sequences of intermixed tests and operations .

Space planning aspects of design problems seem to fall within the transformational paradigm of heuristic search according to the following formu lation. A apace planning problem can thus be defined as a

a space,

a set of elements to locate in that space. (Some elements rna~ be defined as any member of a set .),

a set of constraints delimiting acceptable solutions and possibly evaluation functions to be achieved,

a se t of operators for manipulat­ ing elements within the space, and

fer}= the current des ign state .

Each transfor ma tion consists of a triplet consis ting of the current .des ign state, an e le­ ment to be operated upon, and an operator. Each transformation is made in an environment defined by a ll or a set of the goals to be achieved . Thus

The problem i s to locate the elements within the space in an arrangement that satisfies the con­ straints and optimizes the evaluation functions.

Obviously needed is a process or method that selects an appropriate operation and an ap­ propriate DU on wh ich to operate. Highly diverse methods are pos sible. Algorithmic methods include lists or stacks of Design Units or operators . Mor e comp l ex operations usually include feedback from the current or past states of the problem. Processes that include such feedback are called heuristics. 13

The protocol included here, like others analyzed, show f ew examples where all combinatorial possibilities are exhaust i vely searched. Instead , all protocols showed reliance on a wide varie ty of heuristics. By a heurist ic is meant a r e lation between some part of the current prob­ l em s tate and some part of the desirable next s tate . Most mode l s of heuristics have framed them as produc tions in a Markov system.1 4 The production takes the pattern of

If the left hand side of the condition is met, then the right hand side i s applied t o determine or partially determine the next transformation to be made. In the heuristics found in design prob­ l ems , the left hand side i s commonly a single DU or a constraint, or possibly a doublet made up of both a constraint and a Des i gn Unit. The right hand side is commonly an ope rator, a Des i gn Unit, or both. Examples of heuristics used in the ac­ companying protocol are Cl9, which looks for uses of empty space, and C24, which identifies space for locating towe l racks. C19 has as its left hand component a test which checks for the exis­ t e nce of a space bounded on three sides and ad­ jacent to the major space in the room. When a situation exists that meets these conditions , the right hand side of the production searches for any DU that may make use of the identified space. The left hand condition for C24 is the existence of a bathtub or sink. The right hand side search­ es for empty vertical wall space . Upon finding it, a towel r~ck is located. It may be repeatedly applied. The value of heuristics is that they orient the range of possible future solut~on states in directions that have been found empir­ ically to be fruitful.

A schematic flow chart of the process out ­ lined in the above formulation and described in the protocol is shown in Figure IX. This process corresponds close~ with other formulations of heuristic search} Heuristic search is not the only search process used in space planning. Oc­ casionally, generate and t es t and hill-climbing have been observed in protocols. But the main process relied on in the intuitive solving of space planning problems seems to be the one out­ lined here. Great individua l variations with in this general paradigm exist, in terms of the heuristics used and in the definition of the search space, as specified by the composition and decomposition of DUs.

The Confounding of Specification and Search

Throughout the protocol, search and specifica­ tion operations were highly intermixed. No clear cycling or other separation of activities was identified. The value of such intermixing for retrieval processes has already been proposed. But intermixing is not without i ts costs. Con­ founding of r e trieval proce sses also r esult.

An exceptional example of confounding is shown in PM7. At this point in process ing the S is at a particular solution state that will be achieved again. At this state he asks for in­ f ormation about the minimum distance between a wall and the front of a sink. Looking in Graphic Standards (an architectural reference), he finds a wide variety of other information, This infor­ mation distracts him from his original search and his processing takes off in another direction, Much later (PM37), the ~ has the same solution state represented and asks the same question as he did earlier , This time he gains the informa­ tion he desires and generates a particular new state, In this example, new information destroyed a search sequence originally developed by the ~. It was only fortuitous that he was able to pick up the same solutiort state later, It seems that the control system monitoring search and retriev­ al processes is fallible - at least in some prob­ lem so l vers - and that this intermixing of pro­ cesses places demands on processing that can lead to errors. Other examples of confounding have been observed , though they are rare, Designers seem familiar with such aimless processing, hav­ ing such names for it as "playing with the prob­ l em", "daydreaming", etc, The implication is that significant overhead costs accrue from ef­ fectively mixing search with specification.

Conclusion

In this study, ill-defined problems such as those found in architectural space planning were shown to be tractable in analysis if they were separated into their information retrieval and search aspects. The task of operationally speci­ fying a problem was proposed as the major dis­ tinction between ill- and well-defined problem solving. Some suggestions as to the structure and capabilities of an automated problem speci­ fication system have been made, Also presented is a formulation of the search aspect of space planning problems. It is suggested that the search and specification processes together can completely depict a large number, if not all, of those problems now classed as ill-defined, By further delineating the specification and search processes of problem solving, greater intelligence and creativity may be allowed to be built into future computer programs,