ACSA
AGENCY GP: Agent-Based Genetic Programming for Spatial Exploration
PETER TESTA
Department of Architecture, Massachusetts Institute of Technology
UNA-MAY O'REILLY
Artificial Intelligence Laboratory, Massachusetts Institute of Technology
SIMON GREENWOLD
Emergent Design Group, Massachusetts Institute of Technology
back to Publications Main
Abstract
Background & Motivation
Genetic Programming
Advantages of GP
Agents
Advantages of Agents
Maya
Language and Representation
Figures
Interruption, Intervention, and Resumption
Layers of User Interactivity
Future Work
Acknowledgements
Sources
Abstract
AGENCY GP is a prototype for a system using genetic programming [GP]
and software agents for architectural design exploration. Its software
structure is noteworthy for its integration into a high-end three dimensional
modeling environment, its allowance for direct user interruption of
evolution and reintegration of modified individuals, and its agent-based
evaluation of fitness.
Background and Motivation
AGENCY GP is the software arm of a larger project called AGENCY currently
under way at MIT's Emergent Design Group.
The project seeks architectural responses to the radical transformation
that business organizations are currently undergoing. The pace of organizational
change is being driven by the rapid development of commercial technology,
global markets and reengineered institutions. This constant need to
change gives rise to organizational structures that are no longer stable,
but continuously adapting to their shifting environments. Such structures
can be said to be "emergent" and describe many of today's commercial
and governmental organizations.
Vertically structured office buildings no longer provide the model
for most businesses. With the advent of widespread use of telecommunications,
information technology, and corporate reorganization in the 1990's,
new forces are actively reshaping the architecture of office buildings.
There is a shift in the United States toward research and development,
management and finance, consultancy, and the culture industry, productive
activities less prone to standardization and bureaucratization. Driven
by the demand to improve office productivity, businesses and organizations
have begun to experiment with a variety of alternative officing methods.
However, there exist no working models of an intelligent adaptive architecture.
The AGENCY project focuses on application-oriented basic research to
develop new design software that generatively models the complex interactions
of physical space and information technology within emergent organizations.
Using the research software this project will generatively design and
test spatial systems and work environments.
We have chosen genetic programming to address these challenges because
the strengths of the model are well matched to our system's desired
characteristics. First, we are aware of the impossibility of modeling
emergent organizations deterministically. To try to design a deterministic
algorithm for the creation of workspaces would certainly fall victim
to our inability to name every constraint the problem entails. Therefore
we look to the stochastic, self-organizing solutions Aritificial Life,
and in particular GP affords, to construct solutions that are consistently
sensitive to complicated interactions that a user need not explicitly
codify. Second, we are interested in the genetic model's ability to
offer a user an entire population of solutions to peruse and potentially
to revaluate. The process we are involved in is not a simple optimization
with a single goal, but has many potential fruitful avenues of exploration.
The multi-tracked exploratory process of population evolution provides
a designer multiple alternatives with which to interact at any point.
Our goal is to develop GP as a design partner, offering options that
would otherwise not come to light.
AGENCY GP integrates three technologies with entirely separate pedigrees-genetic
programming, software agents, and Alias|Wavefront's Maya-to form a single
system for design evolution.
Genetic Programming
Genetic programming is a methodology for machine learning that grew
out of the field of genetic algorithms. The genetic algorithm [GA] model
takes as its organizing metaphor, the biological processes of evolution.
The system begins by creating a population of "individuals" each represented
by a "genotype." In the case of GA, the genotype typically consists
of a fixed-length string of symbols, which can be decoded and expanded
into a phenotypic individual in the same way that a biological genotype
is phenotypically expressed in an organism. These individuals then undergo
a simulated process of evolution (Koza). The natural process of sexual
reproduction allows for the recombination of genes from one generation
to the next by the "crossing-over" of genetic material. This allows
for dramatic differentiation of offspring from parents. An analogous
method of crossover occurs within the GA system's population as pairs
randomly mix their genotypes to breed a subsequent generation of individuals.
Mutation of an individual's genotype is also a common occurrence in
reproduction, and it occurs randomly.
However, as in natural selection, not all individuals have an equal
probability of transmitting their genes to the next generation. A population
of individuals' phenotypes are ranked by their "fitness," and the associated
individuals are selected to breed in rough proportion to their fitness
ranking. Fitness can be calculated by any consistent measure. In the
case of AGENCY GP, fitness is derived from the combined efforts of multiple
software agents.
The control loop for a GA system begins by creating an initial population
of randomly generated genotypes. Then the genotypes are interpreted
to produce phenotypes, which are ranked by fitness. A new population
is created by the breeding and mutation of individuals, and the old
population is discarded. Although all of the genetic operations that
produce one generation from the previous are stochastic, the pressure
of selection is assertive, and the result of multiple generations is
a population that is on average, far fitter than its predecessors. GA
is of wide application to problems of multivariate optimization.
Genetic programming [GP] is an extension of the genetic model, in which
the genotype is expressed as a variable-length list or tree of commands
in a simple language. The phenotype then represents the execution of
those commands. When genomes in GP are mutated and crossed over, commands
are inserted or deleted in the genotype or their parameters are changed.
Much of the success or failure of an application of GP depends on the
design of the internal language that constitutes the genotype. In the
case of AGENCY GP, we have developed a language that operates on primitive
shapes and combines them with others to build up more complicated designs
that constitute the individuals in a population.
It is worth noting that typically in a GP system, it is difficult or
impossible for a user to halt evolution, directly modify an individual,
and resume evolution-a procedure known as "interruption, intervention,
and resumption" [IIR]. This is because in languages which contain conditional
structures, it is not possible to map changes backwards from phenotype
to genotype. The cascade of compounding consequences that determines
the course of the genetic program destroys the potential for a one-to-one
mapping of genotypic to phenotypic feature. The language we have developed
for AGENCY GP, however, is non-branching, simple enough that it will
allow for IIR.
Advantages of GP
We chose GP to be a foundation of Agency's software model because several
of its characteristics fit well with the exploratory role we hope Agency
will fill. That GP offers a population of designs means that a designer
using the system is always presented with multiple alternatives from
which to proceed. There is not a single iteratively improved candidate
design.
The GP model also provides a constant process with which to interact
rather than a simple product. In fact, the evolutionary process does
not have a specific end product, nor will a GP effectively find a globally
"optimal" solution to a problem with as many variables and constraints
as ours. The process will, however, continue to explore new designs
as long as a user wants to watch it run. It will be possible for a user
to exert control at several levels, from direct manipulation of an individuals'
phenotypes, to nudging the course of evolution by changing its parameters.
That the genetic regeneration process is fundamentally non-purposive
and stochastic means that designs will be generated and evaluated that
do not fit a designer's preliminary notions of good fitness. Should
such designs consistently find favor with evaluating agents, the user
will be forced to reevaluate assumptions about what makes a design worth
considering.
Agents
The second software technology we integrate into AGENCY GP is the software
agent. Agents are defined differently in different sources, but general
definition we are using is "a component of software and/or hardware
which is capable of acting exactingly in order to accomplish tasks on
behalf of its user" (Nwana, 1996). Agents-based models are finding application
in fields that require distributed attention and interaction, such as
electronic commerce, system administration, network management, and
information retrieval (Milojicic, 1999). Agents are autonomous processes
that can identify themselves, run concurrently, and interact with each
other and their environment. Agents can be supportive of one another,
neutral, or antagonistic. There may be multiple instances of the same
agent scattered widely-this might be a good way intelligently to collect
data from a massive unindexed source like the Internet-or each agent
may have an entirely different instruction set.
We chose to implement our fitness evaluations by means of distributed
software agents inhabiting the candidate designs. Once the designs have
been interpreted from genotype to phenotype, multiple agents are instantiated
to test the designs for various criteria. Some agents may represent
actual users of the space, while others will be interested in issues
such as fire-code compliance, or energy efficiency. Virtually any criterion
for evaluation can be coded and dropped in as an agent to our framework.
We can specify that workspaces require a certain quotient of natural
light or that circulation spaces desire width enough to allow for conversation.
Using agent-based evaluation, we will able to model management structures
and determine their influence on potential designs. An agent may represent
the pattern of a group, its needs for privacy, meeting space and collaborative
surfaces, or it may undertake the concern of management structure or
productivity. Agents will individually and collaboratively rate the
design, and their feedback will be incorporated into a measure of overall
fitness.
Advantages of Agents
What agent-based fitness allows for is a modular structure for the integration
of multiple criteria for fitness. We have abstracted the agent structure
so that new agents may be developed and employed for new applications
without rewriting the entire AGENCY GP system. In fact, we are free
to write agents that have non-spatial concerns. For instance, we may
implement an agent whose interest is organizing teams of workers. The
spatial effects of such an abstracted agent cannot be determined in
any way other than to run the system under this agent's selective pressure.
Since the descriptive language and representation of the individual
designs is spatial, the system effectively translates non-spatial constraints
into spatial hypotheses. This agent-based evaluation of fitness is well
suited to expressing the conflicting, non-linear, multi-level spatial
requirements of emergent organizational structures.
Maya
We are implementing our software as a plug-in extension of Alias|Wavefront's
Maya package, a leading tool for the creation and visualization of complex
virtual environments. Maya is of widespread use in the fields of three-dimensional
animation for film and broadcast, but has only recently begun to see
broad application to explorations of morphology such as AGENCY GP. Maya's
open architecture allows for software developed using all modern high-level
languages features to exploit the power of its inbuilt library of three-dimensional
operations. Any three-dimensional form is expressible in terms of Maya's
available spatial transformations and Boolean operations. The Maya platform
allows us to abstract the representation of three-dimensional forms
so that we can operate freely on them without concern for the complexity
of the underlying geometry. The internal language that we have developed
for evolution in the GP system manipulates spatial constructs at the
same level that a designer does when working in a three-dimensional
modeling system. Therefore the individual commands of the language are
meaningful to and useful by designers, ensuring the efficacy
of IIR.
Language and Representation
Our implementations of the GP's main generational loop, selection, mutation,
and crossover are conventional. The individuals in the population are
fairly complicated structures, each containing enough information to
describe a complete design. We use a combination of Maya and C++ objects
for the internal representation. A user begins the process with a Maya
scene with one or more closed NURBS (non-uniform rational b-spline)
curves selected. These curves should be coplanar but may be of any closed
form and may intersect. This initial set of curves acts as the seed
for all subsequent evolution.
Figures
Fig. 1. NURBS
Curves in Maya
In the interpreted phenotypic representation, such curves will be extruded
into space.
Fig. 2. NURBS Curves Extruded Into Space
When the AGENCY GP is invoked from within Maya, a C++ object is permanently
attached to each NURBS curve in a design. This C++ construct contains
evolvable values pertaining to the shape and architectural function
of the region the curve encloses. The object also contains an evolvable
sequence of operations in our GP language to be applied to this curve.
Each curve is given a height of extrusion and treated as a NURBS surface
extending from an evolvable starting height into space.
The operations in our language are simple but powerful transformations
of these NURBS surfaces. The images below demonstrate the operations
of our language applied to the lefthand NURBS surface from the scene
in figure 2.
Fig. 3. TRANSLATE (X, Y)
Fig. 4. ROTATE (DEGREES)
Fig. 5. SCALE (X, Y)
Fig. 6. CUT (START, STOP)
These operations form the core commands of our language. Mutation may
consist of addition or deletion of an operation, or the change of a
parameter. Execution is strictly linear; there is no facility for conditionals
or branching. This simple program structure contributes to our ability
to implement IIR.
We are counting on these surfaces to intersect with each other in ways
we cannot predict. Each Boolean operation we apply-intersection, union,
or subtraction-forms a new enclosed surface, which may be assigned its
own architectural function.
Fig. 7. Boolean Intersection
Fig. 8. Boolean Subtraction
Each individual in a population, therefore, is comprised of several
separate Maya/C++ objects each of which carries a NURBS surface, certain
evolvable values, and a list of operations. That we never directly query
or modify the low-level geometry of the Maya objects, but allow Maya
to perform all needed transformations and Boolean operations is what
makes the language high enough level to be useful for the direct intervention
of a designer.
Interruption, Intervention, and Resumption
Once a population has been ranked by fitness, the AGENCY GP becomes
open to IIR. The entire population of interpreted designs is available
for viewing by the user, who has several options. It is possible simply
to re-rank individuals and allow evolution to continue, or to take a
candidate design and apply one or more operations from our language
to an arbitrary number of the NURBS surfaces that comprise it. The transformations
applied will be added to the list of operations in the internal representation
of the individual. By providing the basic operations of three-dimensional
modeling through our language we enable designers to make targeted modifications
of designs before allowing evolution to continue.
Layers of User Interactivity
IIR and specifying the seed design are the most direct modes of user
interaction with the system. However, there are several other layers
of user interactivity built into AGENCY GP. A designer is free to control
what and how many pre-existing agents to deploy to evaluate designs,
or how heavily to weight each agent's findings. Agents may also have
controls of their own which allow a user to direct their activities.
We have also specified and documented several C++ interfaces so that
users may write their own modules for inclusion into AGENCY GP. Users
are encouraged, for instance, to write agents with concerns specific
to their use of AGENCY GP.
Future Work
We are currently in the process of implementing agents for the design
of office spaces. This in itself implies a program of research, which
will determine what are fruitful metrics by which to analyze designs.
We are certain to learn through study and experiment the capabilities
and limitations of our approach. Once we have created a body of agents,
the AGENCY GP itself becomes a platform for research. We will be able
to determine, for instance, what agents are difficult to satisfy simultaneously.
By looking at patterns of IIR and users' preferencing of agents, we
can also determine which agents are working at cross-purposes with human
designers, and thereby draw inferences about the nature of our own preferences.
Acknowledgements
Jason Rolfe
Ian Ferguson
Nina Chen
Omar Khan
Sources
Hyacinth S. Nwana, "Software Agents: An Overview," Knowledge Engineering
Review, Vol. 11, No 3, (Sept 1996): 1-40.
Dejan Milojicic, "Mobile Agent Applications," IEEE Concurrency, Vol.
7, No. 3, (July-Sept 1999).
John R. Koza, Genetic Programming: On the Programming of Computers by
Means Of Natural Selection (Cambridge: MIT Press, 1992).
|