1. INTRODUCTION
Computational design exploration with description formalisms can be
explicitly modeled as a form of movement in a structured space of designs.
The design space exploration complex presented by Woodbury and Burrow is
one such formalism.
In their Keynote Article, Burrow and Woodbury explain the three
premises underlying the metaphor of exploration. All three have important
ramifications for the work presented in this paper. The first premise
posits that the cognitive limits of humans in representing and searching
problem spaces can be addressed by modeling designer action as a form of
exploration. The second premise posits that a model of design space
exploration can amplify designer action through formal mechanisms. The
final premise is that the representation of computational exploration is
feasible. The need to account for and understand the nature of designer
action, amplification of design activities, and the feasibility of
encoding formal and structured spaces remains a significant research
problem. Woodbury and Burrow present two propositions, namely, the primacy
of design space in this discussion, and secondly, the need to support
computational amplification.
In the context of this framework for computing exploration, namely,
the need to develop a better understanding of what we mean by design space
(as opposed to a search or solution space) and how human designers can
communicate, control, and coordinate the formal process of exploring such
structured space of designs, this paper will address these issues through
a discussion of interaction paradigms for designing, Grice's model of
rational conversation and mixed initiative.
The formal machinery of design space exploration is explained in the
literature (Burrow & Woodbury, 1999;
Woodbury et al., 1999, 2000) and is relatively well understood and
exemplified in the work of Woodbury and Burrow. However, the problem of
incorporating this formal machinery with designer action for amplifying
human intention remains an open one.
Interaction paradigms provide a mechanism for introducing human design
intent into computational exploration. Several paradigms for
human–computer interaction during design exploration have been
proposed in the literature (Kochhar, 1994).
These are classified as manual, semiautomated, automated, and cooperative,
reflective of the degree and extent of the division of labor between human
and machine. However, with the shift of emphasis implied by the work of
Woodbury and Burrow, this neat division of labor model of design
interaction is not sufficient to address the complex issues of designer
action and amplification. For example, the mimicking of manual human
action, such as sketching or sculpting as an interaction model, while
compelling, is unsuitable for design space exploration. Manual action
necessarily deals with singleton states, not collections or threads of
states.
In our research, the mixed-initiative interaction paradigm presents a
more fine-grained division of labor, allocating and sharing control over
the same task jointly between the user and the system, allowing for
multiple threads, recovering from conflict through disambiguation and many
other strategies for interaction known from conversational structure. This
paper argues that a useful starting point for addressing this problem lies
in conceiving the interaction between the formalism and the designer as a
rational conversation and proposes a model of dialogue. The concept of
mixed initiative is known from studies of human dialogue, applied
artificial intelligence, and the design of autonomous goal-directed
systems (Ferguson & Allen, 1994; Allen et al., 1996). Such a paradigm provides a
systematic exposition of how communication, coordination, and control
strategies enable a designer to interact with a formal system.
The need for a fine-grained division of tasks, acquiring, sharing, and
relinquishing initiative requires a model for synchronizing the input and
output modalities between the designer and the exploration formalism. An
interaction model addressing these requirements has been proposed in the
literature (Datta & Woodbury, 2002). The
central feature of this model is the maintenance of exploration structure
based on conversational dialogue and its computational representation.
This paper describes the representation of dialogue between the
designer and state, structure, and moves in the formalism. It presents a
visual notation for representing dialogue through abstract examples of
exploration tasks that are specifically machine or human driven in an
asynchronous fashion. It describes examples of dialogue integration, where
the two distinct modalities are combined in a single frame, in a
synchronous fashion. It concludes with a discussion of the results from
the modeling of the nature of dialogue in design space exploration.
1.1. Background
The representational device of feature structures (Knight, 1989; Kasper & Rounds,
1990) and attribute value logic (Pollard &
Moshier, 1990; Franz & Jrg, 1994)
known from linguistic theories of generation and from the constraint
programming literature underpin the notation for modeling language in
Carpenter's typed feature structures (Carpenter,
1992). As a representation, typed feature structures are similar to
frame-based (Minsky, 1975) and terminological
knowledge (Borgida et al., 1989) representation
systems. The analogy between feature structures and knowledge
representation schemes comes from associating a collection of features or
attributes with each node or frame. Each feature represents a slot label
and the arcs themselves point to the fillers, creating a network of
associations. Feature structures comprise a set of nodes, each of which is
labeled by type information. Most knowledge-based systems underpinned by
symbolic representation support the “matching of
descriptions.” This operation, called unification in the field of
deduction systems provides the “addition and multiplication”
of descriptions.
A transparent exposition of the modalities of the formalism in a
visual manner is one way of expressing and integrating the input and
output modalities of both user and formalism. This approach is similar to
the work of Piela (1989) in the ASCEND modeling
system (Piela et al., 1993). ASCEND provides a
visual and direct manipulation interface for developing and testing
incremental constraint programs in the domain of process engineering. In
the ICE project (Zeller & Snelting, 1995;
Zeller, 1997) an interactive front end enables
the user to construct configuration threads through the addition and
modification of configuration constraints. The Oz Explorer (Schulte, 1997) is another visual constraint
programming tool for supporting the user driven development of constraint
programs. A tree visualization of the constraint problem is the central
metaphor for exploration of any constraint node in the tree. The user can
tailor and program user guided search engines over this tree for the
development of constraint programs. FEGRAMED (Kiefer
& Fettig, 1995) employs a fully interactive front end that
presents the user with a customized view of feature structures. This
feature structure editor can be used for developing and maintaining
feature structures in constraint-based systems.
1.2. Dialogue requirements in design space
exploration
The theory of design space exploration (Woodbury et
al., 1999) posits an explicit formal substrate for computing
exploration that employs and develops extensions to Carpenter's typed
feature structures (Carpenter, 1992) to
represent and reason over intermediate states, exploration moves, and an
ordering over explored states.
First, the formalism supports the representation of an exploration
state that retains the feature structure properties of intentionality and
partialness. Types, features, and descriptions taken together provide
well-founded support for representing problem and solution states. The
state representation supports useful formal properties such as
intentionality, partialness, and structure sharing. Second, the inference
algorithms over this representation support a principled notion of
exploration moves that enumerate partial states under a subsumption
ordering. Moves are operators that can generate new states, and navigate
and modify existing states. Third, the exploration formalism supports
several movement operations over state and space. Underpinning the
exploration of partial satisfiers is an ordering based on subsumption.
The entities of state, structure, and move identified above are
formally represented using typed feature structures as the formal
substrate as follows:
1.2.1. Dialogue with exploration states
The formalism supports the representation of an exploration state
through the concepts of types, features, descriptions, and feature
structures. The formalism represents exploration states through three
elements from the feature structures machinery. These elements are a type
hierarchy, a set or sets of feature structures, and a description language
for specifying constraints on types and structures. Types comprising
T stand for domain knowledge of the allowable universe of
discourse expressed in terse form. Structures from F represent
exploration states, in this case, physical and conceptual attributes
associated with the design of buildings. Descriptions from D are
constraint expressions in a formal attribute-value description language.
Descriptions are used for problem formulation, constraints on types, and
generated structures.
1.2.2. Ordering of exploration structure
The structure of exploration is represented through the ordering
relation of subsumption. The concept of an ordered design space underpins
the description formalism. In it, the collection of exploration states is
ordered by the relation of subsumption over exploration states (feature
structures). Subsumption as a formal inference operation is widely used
for reasoning.1
For example, description
logics (Lambrix, 1996) provide a reasoning
operation called subsumption. Subsumption also provides a powerful tool
for case-retrieval and standards processing (Hakim
& Garrett, 1993).
The subsumption ordering relation
can answer what superclass a given class has according to its set of
attributes. In the context of the exploration formalism, subsumption is a
relation of implication that relates more specific to more general states
of exploration. Thus, like inheritance over types, subsumption defines a
partial ordering over exploration states (feature structures). This
ordering of feature structures is represented as a directed graph. The
hierarchical graph defined by subsumption over feature structures is such
that a child node may have more than one parent node. The exploration
formalism provides a structuring relation based on subsumption to order
collections of exploration states. This ordering relation provides an
invariant structure to the design space. Here, the subsumption relation
may be seen as a generalization relation. Thus, in a given design space
structured by subsumption, a subsumer state expresses a generalization
over the subsumed state. In it, two design states (and recursively their
subparts) are related if one subsumes the other, that is, if one contains
strictly less information than the other. This subsumption-based design
space structuring mechanism is reported in Burrow's thesis (
Burrow, 2003). The key feature of this structuring
mechanism is that the subsumption relation captures a more generic
relation than the derivation relation that structures the spaces of
designs generated by a grammar. A detailed view of this formulation is set
out in (
Woodbury et al., 1999).
1.2.3. Algorithms for computing exploration moves
Exploration moves are cast in terms of moves in a design space upward
or downward in an information ordering. The formalism provides a set of
operators, namely, incremental π-resolution (Burrow
& Woodbury, 1999), indexing and reuse, design unification,
design antiunification, and hysterical undo (Woodbury
et al., 2000) for the generation of new exploration states,
modification of existing states, and movement between states.
Given this representation of state move and structure in a description
formalism, the requirements for user interaction with the design space
exploration are addressed.
2. CONVERSATIONAL MODEL OF DIALOGUE
The key notion underpinning the model of dialogue is conversational
structure. This establishes a shared representation of discourse that
enables the participants (human and computational) in the dialogue to
negotiate, reference, and confirm mutual understanding.
A conversational model of dialogue enables the possibility of extended
interaction (Allen, 1999) between the user and
the system. Grice's (1975) maxims of
rational conversation is one such formulation.2
The literature on conversational structure is large and is
review is beyond the present scope. It suffices here to have a model
suitable for organizing mixed-initiative interaction with a computer. For
this, rational conversation is a good model and Grice an
exemplar.
Admitting Grice's conversational maxims is one way
of achieving a tight coupling of user actions with the formal substrate
and implementing a model of dialogue.
Grice (1989) observes that human dialogue is
characterized by rationality, cooperation, common purpose, and direction.
He states,
Our talk exchanges do not normally consist of a succession of
disconnected remarks, and would not be rational if they did. They are
characteristically, to some degree at least, cooperative efforts; and each
participant recognizes in them to some extent, a common purpose or set of
purposes, or at least a mutually accepted direction.
Based on the above observation on human conversation, Grice formulates
a set of conversational maxims. The first is quality, implying
truthful and accurate information. The second is quantity,
neither more nor less information than is required for the dialogue. The
third is relation: only information appropriate to the task is
considered. The fourth is manner: clear and unambiguous
information is necessary for conversation. Grice's model of rational
conversation forms the basis for addressing communication, coordination,
and control issues in the interaction model.
Given a sound representation of communication and coordination, it is
necessary to address the sharing of control over the thread of
exploration. An incremental model of turn taking between the user and the
formalism enables both participants in dialogue to acquire, shift, and
allocate control of the exploration process. The dialogue layer must
support a robust structure of turn taking between the user and the
formalism. Incrementality and turn taking enable the best joint
interpretation of input and output modalities between the designer and the
formalism during exploration.
3. THE FEATURE NODE REPRESENTATION
A common symbolic representation is proposed for supporting the
modalities of input and output during mixed-initiative exploration.
Exploration dialogue between the user and the formalism is represented
through a visual representation of a feature node.
The dialogue layer must support communication and coordination between
the designer and the formalism. Representing the input and output
modalities of dialogue between the user and the formalism is a key
requirement of mixed initiative in the dialogue layer. The user or the
formalism must be able to communicate and coordinate the input and output
modalities during dialogue. The input and output modalities of the
description formalism are clearly defined in the terms of the formal
substrate. Descriptions and partial satisfiers, the base representation of
input and output from the formalism are given, ipso facto, in
terms of feature structures. The dialogue layer must provide an account of
the input and output modalities of the designer. A common representation
that can unify both modalities of exploration is necessary.
The conception of a design state is made transparently visible to the
user through a visual feature node, VNode. Through the construct of the
visual feature node, a principled formulation of mixed-initiative
conversational structure can be established between user and formalism.
These properties of a VNode are based on Grice's (1989) model of rational conversation. The relationship
between the domain contruct of an exploration state and the visual feature
node is shown in Figure 1. Here, the
representation of dialogue based on rationality, cooperation, common
purpose, and direction through the visual feature node is addressed.
Mapping domain layer constructs to the dialogue layer through the
visual feature node.
The concept of a visual feature node enables a principled formulation
of dialogue representation. As shown in Figure
2, the visual feature node, VNode provides a common frame for
representing mixed-initiative dialogue in the interaction model. Two
distinct views are mapped onto the same representation. First, the results
of exploration initiated by the description formalism are available as
partial satisfiers (incorporating types, features, descriptions) of a
VNode. Second, the representation of the results of user manipulation are
available as feature nodes (incorporating problem states, choices, and
functions, interaction history) through the extrinsic attributes of the
VNode.
The elements of the visual feature node map onto the domain layer
constructs. The intrinsic attributes represent the formal
features along which the exploration may proceed. The extrinsic attributes
represent designer moves.
3.1. A visual notation
The visual notation expresses the input and output modalities from
both the user and the formalism. The visual notation extends the
representation of attribute-value feature structures.
The attribute-value matrix or AVM notation visually describes feature
structures. A visual feature node maps the intrinsic and extrinsic
attributes of a feature node, FNode onto elements of the AVM notation.
This mapping annotates the visual feature node with the type, feature
names, feature values and coreferences taken from the underlying partial
satisfier. The connection between a visual feature node, VNode and an
FNode is given as follows:
The VNode composes and aggregates elements of the underlying
representation. As shown in Eq. (1), a VNode can be decomposed into an
FNode. The link between the visual notation and the underlying
representation is expressed with a dot notation. In an FNode, the values
of a feature may be atomic, complex, or another feature node. The value of
a feature node FNode, is given either by a feature-value pair or
feature-value map. The smallest element of the visual feature
node is the feature-value pair. The feature-value pair represents the
relation between a feature and its value. This is shown in Figure 3.
(a) A feature-value pair and (b) a feature-value map are shown. The
pair attributes:property is indicated by a coreference tag,
indexed by the number 1, to a node outside of the diagram fragment
shown.
The feature-value map specifies the relation between a feature node
and its subnodes. For example, in Figure 3, the
feature-value map represents the functional relationship between the
geom and its value. A feature-value map is enclosed by the
delimiters “[” and “]” and annotated by
the type label drawn from its partial satisfier. In the example, the
partial satisfier is of type, geometry. Feature nodes support recursive
containment. Thus, the value of a feature node may be another feature
node. The attribute-value notation is easily adapted for a visual
representation of a feature-value map as follows: the feature-value map
can be conceptualized as a recursive container of entities of type
feature-value pair. In Figure 3, the
feature-value pair represents the functional relation between the feature
mass_el and its value, which is minimally the type
massing. The value of mass_el may also be complex, such
as a query description, resolution step, or function application or
external complex datatype. The value of mass_el may also be
another feature structure.
In a visual feature node, VNode, two or more paths can share the same
information. This is called structure sharing. Paths engaging in
structure sharing are called reentrant. Shared structure in a visual
feature node is represented by coreferences, also called
tags. The coreference n denotes an index value where
n is the identity of the node that is shared between one or more
feature structures. Coreferences and their denotation by indices is
straightforward in the avm notation. As shown in Figure 4, reentrancy, or structure sharing is
indicated by reference tags such as 1. The slots are the features and the
values are written next to them.
A visual feature node incorporating coreference notation. The shared
feature structure of type property is indicated by the coreference tag,
indexed by the number 1.
A model of turn taking is proposed for synchronizing the modalities of
action available to both the user and formalism during exploration.
Through interaction with the intrinsic and extrinsic attributes of a
visual feature node, the user and the formalism are able to acquire,
relinquish, shift, and allocate initiative during the exploration
process.
3.2. Choices
The notation supports user choices in the VNode through the
representation of alternatives, resolution steps, and function
applications.
The notation incorporates the operators of the description language:
conjunctions and disjunctions. Conjuncts and disjuncts
in feature structures are denoted using the same notation as feature value
pairs. In place of the feature labels, the labels conjunct and
disjunct are used, with the values as feature structures. This
common representation can be scaled to represent the conjunction of
disjuncts and the disjunction of conjuncts. In linguistic attribute-value
formalisms (Pollard & Sag, 1987; Pollard & Moshier, 1990), conjuncts and disjuncts
are denoted by special delimiters, such as “{” and
“},” and their edge names are either omitted, suppressed, or
obscured. This is not necessary in this interactive representation.
An example of a conjunct of disjunctive visual feature nodes is shown
in Figure 5. User interaction is necessary to
resolve the structures associated with the features mass_el and
geom of the feature structure of type entity. The
disjunctive nodes of type disjunct are represented as a feature-value map.
Each feature-value map is accessed by a feature conjunct, of type
conjunct. Each feature-value map has four possible disjuncts, which are
represented as a feature-value pair, whose features are defined by
disjunct n where n is an index over
disjuncts.
An example of a conjunct of disjunctive visual feature nodes. The
disjunctive nodes are accessed by a node of type conjunct and represented
as a feature-value map and each disjunct is represented as a feature-value
pair, whose features are defined by disjunct n where
n is an index over disjuncts.
The user can choose a single conjunct for each of the features of the
node entity shown in Figure 5. For example, if
the designer selects the disjuncts disjunct_2 and
disjunct_7, shown in Figure 6, as the
appropriate values of mass_el and geom, respectively,
the node that results will carry the structure shown in Figure 6. Through the dialogue layer construct, VNode,
it is possible to expose the internal representation of descriptions
(problem states), partial satisfiers (solutions), and alternatives
(choices) for user interaction. Because the VNode is recursively defined,
a collection of choices and user interaction history is expressed as a
collection of visual feature nodes. Thus far, the notation has shown how
the intrinsic attributes of a feature node FNode can be visually
represented for direct manipulation by the designer. It is also possible
to represent the attributes of a FNode that are extrinsic to the
formalism, using the same notation.
The resultant visual feature node arising out of the resolution of
disjunctive nodes by user interaction.
For example, a function can be represented in the visual feature node.
Functions can be encoded within the feature-value map representation such
that the functor annotates the feature-value map and the arguments are
features. An example of the duality of a function and its arguments with a
feature node representation is shown in Figure
7. This representation allows the feature structure to encode
traditional command languages found in geometry-based design systems. The
specification of a command or function then returns a value, which can be
atomic, complex, or a feature structure. The use of feature structures to
encode functions can also be used to pass commands.3
Encoding a function as a feature-value map. The function append
(X, Y) which concatenates values can be represented as
the feature-value map of type append and the two features arg1
and arg2. The features, arg1 and arg2 encode
the values X and Y as two feature-value
pairs.
The expressiveness of feature structure command representations needs
to address the possibility of cyclic feature structures and structure
sharing. A cycle arises when following a nonempty sequence of features out
of a node leads back to that node, which is a useful property in the
finite modeling of knowledge (Carpenter, 1992,
pp. 51–52). A recognition mechanism is necessary to interrupt
infinite loops in a visual feature node representation for commands. The
restriction on commands is that structure sharing is not considered a
valid part of the command syntax. If coreferences do occur, the structures
they represent are copied uniquely within each command.
Another way of visualizing functions within feature structures is to
encode the functional definition as the value of a feature-value pair. In
this scheme, for a function append(X, Y) with two
arguments, a type function exists, such that its value is a
function definition with the syntax append(X, Y).
An example of a procedural function in visual form is shown in Figure 8. User interaction on this node involves three
possible behaviors. First, the application of the function to an
appropriate node results in a new node, consistent with the application.
Second, the unification of a functional node with an appropriate feature,
results in a new feature structure, following the laws of unification for
typed feature structures. Third, the function can be unfolded into its
constituent subparts following the interaction defined above and its
values subject to exploration. An example of the latter is shown in Figure 9. The unfolding of a functional representation
shows that the feature node representation of the function
translate(a, b, c) is of type translate and the
arguments are the three feature-value pairs, tx, ty, and
tz.
The function translate(a, b, c) is
represented as a feature-value pair and contained within a visual feature
node, with feature transform and value translate(a,
b, c).
An unfolding of a functional representation shows the feature
structure notation of the function translate(a, b,
c). The type of the function is translate. The arguments are
unfolded into the three feature-value pairs, tx, ty, and
tz.
3.3. Interaction with visual feature nodes
The visual feature node representation is extended to incorporate
behaviors that admit user level actions extrinsic to the formalism.
Interaction with a large collection of visual feature nodes requires
functionality for panning, zooming in and out of context, search, and the
expansion of tags. Visual feature nodes are nested entities. User
navigation of a large collection of feature nodes is enhanced by
functionality for zooming in and out of nodes, imploding nested nodes, and
the expansion of coreference tags. If the nesting is very deep or broad,
panning functionality provides the ability to scroll through the whole
feature node. Zoom and implode interaction behavior provide functionality
for controlling depth nesting. By using this functionality the user can
fold (implode) and unfold (zoom) feature nodes. The user obtains
information about substructures of a node by zooming into them. Further,
zooming into the selected substructure enables a reorientation of context
such that the selected node becomes the new root node of
exploration. An example of unfolding substructures by user interaction is
given in Figure 10.
An example of an imploded feature node hiding the contained
substructures. The symbol + indicates that the substructures of the
feature-value map of type entity are closed. User interaction on this node
is necessary to open these hidden structures.
3.3.1. Zooming and imploding nodes
Feature nodes can be nested recursively to arbitrary levels containing
many substructures. The interactive mechanism accounts for folding the
nested substructures of a feature-value map to hide their underlying
notation and for unfolding the imploded structure to see the details of a
feature value map. In the visual representation, this is realized by
allowing users to open or close substructures visually through the symbol
+ (Fig. 11)
Another example of an imploded feature node. The symbol + indicates
that the feature-value map of type property and geometry contains nested
subnodes that can be unfolded by user interaction.
The unfolding symbol + shows up in two different situations. A
restriction may be placed on the depth of display of a feature-value map.
Any substructure in a feature-value map that exceeds that depth, is
represented by the symbol +. This is automatically managed by the dialogue
layer and the nesting levels set through preferences. The user can also
manipulate the feature-value map interactively. The feature-value map will
be shown as folded, until it is explicitly unfolded. Thus, the + symbols
on the feature-value map coming from depth restriction are generated and
removed dynamically while the user navigates a feature structure. In
contrast, the maps that are unfolded manually need explicit interaction to
change their display. This enables the user to control the level of detail
shown, while zooming and imploding very large feature node
collections.
Pan functionality is provided by enclosing the feature structures in
scroll bars. This is a standard means for providing canvas real estate.
User interaction with the scroll bars allows context to be shifted
horizontally and vertically.
3.3.2. Interaction with coreference tags
Path equality in structures is one of the oldest information
structuring concepts in computational design, the first instance being
Sutherland (1963). This notion is captured
through structure sharing between feature structures at the formal
substrate.
From the perspective of the designer, path equality in the underlying
formalism is visually displayed through coreference tags. Thus, the
appearance of coreference tags in the visual representation indicate nodes
that are strictly structure shared partial satisfiers. In the context of
exploration, these correspond to entities that are feature values that, by
definition, are feature structures.
Coreference tags are used in two ways, both shown in Figure 12. First, a coreference is used to annotate a
feature-value pair that structure shares a feature-value map. Second, it
is used to simplify the visual representation of partial satisfiers, by
simple substitution of the shared feature-value map by the coreference
tag, denoted by n. The coreference tag can be substituted by the
partial satisfier it denotes by user interaction. If the partial satisfier
is represented, the coreference appears outside the feature-value map, as
shown in the value of properties. If the coreference is used to
refer to the partial satisfier, it appears inside the feature-value map as
shown in the value of attributes.
An example of substitution of a feature-value map with a coreference
tag 1. The coreference tag is an index to the nested partial satisfier of
type property that is shared by the features properties and
attributes.
The user can move within a collection of nodes using the find
operation. Search for a nested node using the find operation is supported
by the use of tags. A successful search results in the matching
feature-value pair being panned into focus. The user can specify the
find function to search only for features, types, coreferences,
or atomic values. In the case of coreference search, the tag number is
used to locate the partial satisfier corresponding to the specified tag.
This is useful in dialogue situations when structure shared partial
satisfiers are widely separated. Tags mark structure shared nodes and
these can be expanded in situ following the general convention of
appearing in the first location in which they are introduced. When tag
expansion occurs during dialogue, the coreferences are updated and the
partial satisfiers that they represent are redisplayed. These extensions
are discussed in the next sections.
4. INTEGRATION OF DIALOGUE
The second requirement, dialogue integration, combining two modalities
into a common frame, is described in this section. Having defined the
visual feature node, its representation and its support for interaction,
it is now possible to address how this construct supports dialogue
integration.
Dialogue integration utilizes the unification operation. Unification
is an appropriate basis for mixed-initiative integration as it can combine
complementary input or redundant input from both modalities of
exploration. Further, in the case of contradictory inputs, unification can
rule out the possibility of integration. A feature node consists of a
collection of feature-value pairs. The value of a feature may be an atom,
a variable, or another feature-value map. When two maps are unified, a
composite map containing all of the feature specifications from each
component structure is formed. This is subject to the restriction that any
feature common to both feature structures must not clash in value. If the
values of a common feature are atoms, they must be identical. If one is a
variable, it becomes bound to the value of the corresponding feature in
the other feature structure. If both are variables, they become bound
together, constraining them to always receive the same value. If the
values themselves are feature structures, then the unification operation
is applied recursively.
4.1. Supporting partiality
As shown in Section 3.1, a visual feature node (VNode) inherits key
behavioral properties of typed feature structures. Thus, given the
well-defined semantics of types, features, and descriptions, the visual
feature node supports partiality of input and output. The representation
framework of visual feature nodes, type annotated frame delimiters,
feature-value pair/feature-value map, and coreference tags carry the
specification of partial information. Partial information during dialogue
provides the opportunity for both user and formalism to underspecify,
relying on the extension of dialogue through turn taking. A partially
specified exploration move is represented as an underspecified visual
feature node. In this situation, a subset of feature-value pairs is not
instantiated, following the intentional nature of feature structure
representation. Instead, they are assigned a certain type, corresponding
to the semantics of the move. This bears explanation through an example of
turn taking on a partial specification.
An example of supporting partiality in mixed-initiative dialogue is
explained in Figure 13. In this example, a given
description can be integrated with a massing of type geometry, the
resultant is assigned an underspecified location feature, whose value is
required to be of type point. The description, massing, is assigned to the
visual feature node shown. In this scheme, it is possible to state during
exploration that there exists an entity of massing with three features
properties, object, and location.
The visual feature node for an underspecified entity of type massing.
Substructures can be shared in a visual feature node. For example, the
properties of massing are the same as the attributes of
geometry. Further, the specification of property can be changed either
through the properties of massing or through the
attributes of geometry.
In the visual feature node representation, it is possible to specify
the features properties of type property and object of
type geometry but not the feature location, which is assigned a
generic type, point. Thus, the visual node captures the idea that there
exists a geometric object of type massing and that its feature
location is constrained to be of type point. Given the
equivalence of structures and descriptions, the underspecified visual
feature node shown in Figure 13 can be
interpreted as a formal command for the generation of massing elements.
More importantly, the possibilities for locating the massing element are
open to mixed-initiative specification by the user's action on a
visual feature node or through the resolution of formal constraints.
This is explained in Figure 14 with another
underspecified feature node of type command, whose feature
location is constrained to be of type point with specified
coordinates. Note that this is only true under the assumption that feature
nodes can carry maximal values such as the coordinates of a location.4
In the design of GENESIS, Heisserman (1991, p. 133) notes that the inability to specify an
intensional model of geometric information remains a major drawback for
interactive systems for generative design.
It follows from the
above, that if “massing” from
Figure
13 is compatible with command from
Figure
14, the unification of the two will provide a feature structure
whose location feature
location will result in the more specific
of the two values. To be compatible in type, the result must be the meet
or a subtype of the meet of the two argument types. Hence, the result of a
typed unification is a more specific feature structure or atom drawn from
the type hierarchy. Thus, in a mixed-initiative scenario, the user might
provide a location value for an underspecified geometry generated by the
formalism. Alternatively, the user might specify a geometry for which the
description formalism provides one or a number of possible locations in a
current problem state. Through turn taking, both the location and geometry
of an element in a solution state can be resolved.
The visual feature node for an underspecified entity of type
command.
4.2. Supporting structure sharing
Structure sharing is another fundamental property of typed features
that plays a significant role during mixed-initiative dialogue. Visual
feature nodes enable the user to develop specific exploration paths in
great detail and then provide the resultant feature structure to the
generator (Fig. 15). The generator can reuse the
resultant feature structure multiple times in other feature node contexts
through structure sharing. Recall that feature nodes compose feature
structures (Section 3.1). Thus, at the visual feature node level, dialogue
constructs can take advantage of structure sharing in their underlying
feature structures.
The substructures can be shared in a visual feature node. For example,
the properties of massing are the same as the attributes
of geometry. Further, the specification of property can be changed either
through the properties of massing or through the
attributes of geometry.
Feature structures can be shared across a design space. By reusing
shared feature structures, the user can converge information from other
exploration paths into the current path of exploration. This bears
explanation. For example, there may be two bathrooms in two distinct house
designs that are identical. The feature node collections that represent
the exploration steps of the first and second designs are distinct paths
in the satisfier space. The problem states and choices made by the
designer in both paths are also distinct states. However, a portion of the
solution state, subsequent to exploration, is identical, in this case, the
bathroom design.
In design space, this fact would result in the existence of two
distinct feature structures containing the same information (feature
structures are intensional). The feature node allows the designer to
structure share the bathroom solution of the second design with the first.
Once this equivalence is declared, the exploration structure of the first
is converged into the exploration structure of the second design. It is
important to note that two distinct visual feature nodes can represent two
distinct exploration threads in satisfier space. Through structure-sharing
dialogue, feature structures can be shared, reused, and converged in
design space.
In Figure 13, the properties of
massing are the same as the attributes of geometry. Further, the
specification of type property can be reformulated either through the
feature properties of type massing or through the feature
attributes of type geometry. During exploration, the generative
component can instantiate a massing element, with an unspecified feature
orientation. Subsequently, the user might specify an orientation
by direct manipulation, by drawing an arrow that has a value direction for
its feature angle. The process of typed feature structure
unification enables the explorer to structure share the value of feature
angle of the feature structure of type direction with the value
of orientation. Thus, when the two features are unified
successfully, the resultant feature node of massing has a new value for
the feature orientation. This value is now given by the more
specific value of the feature angle. Note that the property of
structure sharing can be nested. Feature nodes are recursively contained
through the feature-value map and feature-value pair relations of the
notation. Structure sharing and its representation using coreference tags
presents the notation with the ability to avoid redundant
substructures.5
In the design of GRAMMATICA,
Carlson (1993) notes that the ability to detect
and represent duplicates remains a major challenge for interactive
exploration of design spaces.
4.3. Supporting dialogue disambiguation
Mutual disambiguation is another property supported in the visual
feature node. An exploration move that is partially specified is open to
multiple interpretations. In such a situation, a collection of many
feature-value pairs may be available for unification. For example, if a
given description can be integrated with a massing of type geom,
it can be assigned an underspecified location feature, whose
value is required of be of type geom as shown in the previous
discussion of partiality in Figure 13. In the
description node, massing can also be assigned a feature node of type
location from a number of sources. For instance, the location might be
constrained to be adjacent to a previously created entity of massing.
Thus, it is possible that there exists not one, but a number of feature
nodes of compatible type with type massing with the feature,
location. The dialogue layer provides a mechanism for mutual
disambiguation, such that it is possible to specify the feature
location of any compatible type at the current state of
exploration to disambiguate the choice. Given multiple options for
interpreting the value of the feature node of type location shown in Figure 13, a disambiguation process is a necessary
attribute of dialogue to resolve nondeterminism. The same process of
dialogue disambiguation applies to disjunctive nodes. Given a number of
possible alternative choices, the designer can disambiguate a disjunction
by interaction with the visual feature node representing the
disjuncts.
For example, in a user-driven query, the formalism might compute a
range of possible feature nodes that are extensions of type location. The
dialogue layer makes them available to the user as a collection of visual
feature nodes. Alternatively, for an explorer-driven step, for instance, a
command to create an entity of type massing, the type location can be
disambiguated by the user through interactive browsing of the current
state, selection of a current point, command input, structure sharing, or
a constraint specification.
It follows from the above that when conflicts or multiple choices
arise during exploration, mixed initiative in the dialogue layer can
provide for mutual disambiguation through the visual notation.
In the visual feature node, this process of disambiguation is mutual.
It can be interpreted either as a formal command for the generation of
massing elements by the explorer or a user-driven process wherein the
possibilities for locating the massing element are open to exploration
through the specification by the user's action on the visual feature
nodes.
Figure 16 shows a feature node of type
massing, whose feature location is constrained to be of type
point. The feature value can be resolved either by the user or by the
formal generator. It follows that if the location feature of massing is
compatible with one or more locations of compatible location, the
unification of the two can be resolved through a process of mutual
disambiguation.
(top) The feature node of type massing with two options location and
command for disambiguation of feature location. (bottom) The
feature node showing location after disambiguation.
In the example of disambiguation shown here, there are several partial
interpretations: one for massing, and two for location. Because either of
the two locations might be equally valid for the unification to succeed,
only a process of mutual disambiguation can isolate the valid choice of
location. The dialogue layer allows either of the above and does not
distinguish between the modality of exploration, direct specification by
the user or constrained search by the generator. In each case, the
unification-based integration strategy ensures that mixed-initiative
exploration compensates for exploration nondeterminism through type
constraints on the values of features. Further, the restrictions imposed
on these values ensure that the exploration maintains integrity and
consistency during the process of disambiguation.
5. DISCUSSION
The introduction of conversational structure through mixed initiative
to design space exploration enables the designer to maintain exploration
freedom, preserves the underlying structure of exploration, and permits a
finer granularity of dialogue. The characteristics of the model of
dialogue presented here can be summarized as follows:
- Maintenance of exploration freedom: The dialogue model maintains
freedom for incorporating the intentional actions of the designer at any
state of exploration. The visual feature node provides a unified model for
representing the set of problems, subproblems, problem revisions, and
associated designs that a designer actually considers. Problems need not
be fixed. Designs can be partial or complete with respect to the initial
problem formulation. A designer may make varied choices that imply
different kinds of design space operations.
- Preservation of order: The dialogue model enables order preserving
exploration. The structure of exploration is represented through the
ordering relation of subsumption. The concept of an ordered design space
underpins interaction between the designer and the description formalism.
In it, the collection of exploration states are ordered by the relation of
subsumption. Exploration moves are cast in terms of moves in a design
space upward or downward in an information ordering. Mixed initiative
provides a principled way for keeping track of additions, deletions, and
other forms of change as the exploration progresses without negating the
underlying subsumption ordering of possible states.
- Granularity of dialogue: The dialogue model permits a finer
granularity of interaction between the designer and the formalism. It
supports incrementality and turn taking in the process of exploration
dialogue. Through incrementality, emphasis is shifted from the final
results of exploration to its intermediate constructive steps. Through
turn taking, the formal movement algorithms are made accessible to the
designer. The incremental, turn taking model of interaction permits a
sound treatment of exploration nondeterinism, where disjunctions in
description queries, alternative constraints, conflicts, and errors can be
resolved by user intervention.
6. SUMMARY
This exposition of interaction with formal systems for design support
has focused on conversational structure as a model of dialogue. However,
as Woodbury and Burrow show, integrating human users and computational
formalisms remain a key problem for design space exploration. As borne out
by the examples in their paper, the visual feature node presented here
demonstrates the case for designer action but remains a limiting case for
exploration. The visual feature node representation must allow for what
Woodbury and Burrow term “amplification.”
The two requirements posed in developing the above dialogue model,
dialogue representation and dialogue integration, are addressed through
the development of an intrinsic and extrinsic logic for unfolding the
components of the visual notation. The feature structure representation
and its interaction logic are brought together through the construct, the
visual feature node. Framed by Grice's maxims of conversational
rationality, the designer is able to participate in a limited dialogue
with the description formalism to construct problems, navigate solutions,
make choices, and record the history of exploration.
As Woodbury and Burrow state, the design space must be admitted as a
primary object of research in the field. To do so, the configuration,
structure, and visualization of design space requires further work and
need to be addressed. The findings at this stage also indicate a clear
demarcation between the discrete modes of thinking about generative design
(rules, types, features) and continuous modes of manipulation known from
interaction with real-world geometric design problems. This is hinted at
on several occasions in Woodbury and Burrow's paper, but no clear
direction has emerged. Dialogue needs to be extended from a conversational
mode (as described in this paper) to a language designers understand best,
visual representations, and geometry. Thus, although some advances have
been made in understanding joint responsibility over discrete moves
between highly structured states, a clear formulation of mixed initiative
(the rationality of dialogue between a formalism and a human designer) in
the joint exploration of nontrivial design geometry remains an open
problem.
ACKNOWLEDGMENTS
The author acknowledges the continuing contribution of Robert Woodbury
(Simon Fraser University, Canada), Tengwen Chang (Ming Chuan University,
Taiwan), and Andrew Burrow (RMIT University, Melbourne) in the development
of the interaction model for design space exploration reported in this
paper.
