The Artificial Life of Plants
Przemyslaw Prusinkiewicz, Mark Hammel, Radom´ir MĪ ech
Department of Computer Science
University of Calgary
Calgary, Alberta, Canada T2N 1N4
e-mail: pwpjhammeljmech@cpsc.ucalgary.ca
Jim Hanan
CSIRO - Cooperative Research Centre for Tropical Pest Management
Brisbane, Australia
e-mail: jim@ctpm.uq.oz.au
Abstract
In these notes we survey applications of L-systems to the modeling of plants, with an
emphasis on the results obtained since the comprehensive presentation of this area in The
Algorithmic Beauty of Plants [61]. The new developments include:
a better understanding of theoretical issues pertinent to graphical applications of L-systems,
extensions to programming techniques based on L-systems, and
an extension of the range of phenomena expressible using L-systems.
Keywords: L-system, fractal, plant, modeling, simulation, realistic image synthesis, emer-gence,
artificial life.
1 Introduction
In 1968, Aristid Lindenmayer introduced a formalismfor simulating the development of multicellu-lar
organisms, subsequently named L-systems [36]. This formalism was closely related to abstract
automata and formal languages, and attracted the immediate interest of theoretical computer sci-entists
[67]. The vigorous development of the mathematical theory of L-systems [70, 27, 66] was
followed by the application of the theory to the modeling of plants [18, 17, 16, 31, 42, 56, 61].
In the present notes we survey recent results, current work, and open problems pertinent to this
latter domain. In this context, we emphasize the phenomenon of data base amplification [71], that
is the possibility of generating complex structures from small data sets, and the related notion of
Figure 1: Illustration of the concept of rewriting applied to modules with geometric interpretation.
A parent module is replaced by child modules in a sequence of transformations '
2 The modular structure of plants
L-systems were originally introduced to model the development of simple multicellular organisms
(for example, algae) in terms of division, growth, and death of individual cells [36, 37]. The range
of L-system applications has subsequently been extended to higher plants and complex branching
structures, in particular inflorescences [18, 19], described as configurations of modules in space
(Problem 2.1). In the context of L-systems, the term module denotes any discrete constructional
unit that is repeated as the plant develops, for example an internode, an apex, a flower, or a branch
(c.f. [4, page 284]) (Problem 2.2). The goal of modeling at the modular level is to describe the
development of a plant as a whole, and in particular the emergence of plant shape, as the integration
of the development of individual units (Problem 2.3).
3 Plant development as a rewriting process
The essence of development at the modular level can be conveniently captured by a parallel
rewriting system that replaces individual parent, mother,or ancestor modules by configurations of
child, daughter,or descendant modules. All modules belong to a finite alphabet of module types,
thus the behavior of an arbitrarily large configuration of modules can be specified using a finite
set of rewriting rules or productions. In the simplest case of context-free rewriting, a production
consists of a single module called the predecessor or the left-hand side, and a configuration of
zero, one, or more modules called the successor or the right-hand side. A production p with the
predecessor matching a given mother module can be applied by deleting this module from the
rewritten structure and inserting the daughter modules specified by the production’s successor.
This process requires finding an
occurrence map ' that transforms the predecessor into the mothermodule, and applying the same transformation to all the modules in the successor in order to
produce the appropriate child modules (Figure 1).
Figure 2: Examples of production specification and application: (a) development of a flower, (b)
development of a branch, and (c) cell division.
Three examples of production application are shown in Figure 2. In case (a), modules located
at the extremities of a branching structure are replaced without affecting the remainder of the
structure. In case (b), productions that replace internodes divide the branching structure into a
lower part (below the internode) and an upper part. The position of the upper part is adjusted to
accommodate the insertion of the successor modules, but the shape and size of both the lower and
upper part are not changed. Finally, in case (c), the rewritten structures are represented by graphs
with cycles. The size and shape of the production successor does not exactly match the size and
shape of the predecessor, and the geometry of the predecessor and the embedding structure had to
be adjusted to accommodate the successor. The last case is most complex, since the application
Figure 3: Developmental model of a compound leaf, modeled as a configuration of apices and
internodes.
of a local rewriting rule may lead to a global change of the structure’s geometry. Developmental
models of cellular layers operating in this manner have been presented in [11, 12, 15, 61]. In
these notes we focus on the rewriting of branching structures corresponding to cases (a) and (b).
(Problem 3.1).
Productions may be applied sequentially, to one module at a time, or they may be applied
in parallel, with all modules being rewritten simultaneously in every derivation step. Parallel
rewriting is more appropriate for the modeling of biological development, since development takes
place simultaneously in all parts of an organism. A derivation step then corresponds to the progress
of time over some interval. A sequence of structures obtained in consecutive derivation steps from
a predefined initial structure or axiom is called a developmental sequence. It can be viewed as the
result of a discrete-time simulation of development (Problem 3.2).
For example, Figure 3 illustrates the development of a stylized compound leaf including two
module types, the apices (represented by thin lines) and the internodes (thick lines). An apex
yields a structure that consists of two internodes, two lateral apices, and a replica of the main apex.
An internode elongates by a constant scaling factor. In spite of the simplicity of these rules, an
intricate branching structure develops from a single apex over a number of derivation steps. The
fractal geometry of this structure can be viewed as an emergent property of the rewriting rules.
At first sight, Figure 3 resembles fractal generation using a Koch construction. We will see,
however, that there are important differences between these two processes.
Mandelbrot [48, page 39] characterized Koch constructions as follows:
One begins with two shapes,an initiator and a generator. The latter is an oriented
broken line made up of N equal sides of length r. Thus each stage of the construction
begins with a broken line and consists in replacing each straight interval with a copy
of the generator, reduced and displaced so as to have the same end points as those of
the interval being replaced.
Mandelbrot introduced many extensions of this basic concept, including generators with lines of
Figure 4: A comparison of the Koch construction (a) with a rewriting system preserving the
branching topology of the modeled structures (b). The same production is applied in both cases,
but the rules for incorporating the successor into the structure are different.
unequal length (pages 56–57) and with a branching topology (pages 71–73) (Problem 3.3). All
these variants share one fundamental characteristic, namely that the position, orientation, and scale
of the interval being replaced determine the position, orientation, and scale of the replacement
(a copy of the generator). In models of plants, however, the position and orientation of each
module should be determined by the chain of modules beginning at the base of the structure
and extending to the module under consideration. For example, when the internodes of a plant
elongate (as is the case in Figure 3), all the subtended branches are moved upwards in response.
Similarly, when the internodes bend, the subtended branches are rotated and displaced (Figure 4b).
A Koch construction cannot capture these phenomena, because it operates under the assumption
that the parent modules determine all aspects of their descendants (Figure 4a). In contrast, in a
developmental model of a branching structure the position and orientation of the descendants are
determined by the subtending modules. The difference between these two cases is illustrated in
Figure 5.
The information flow taking place during the development of a branching structure can be
expressed directly in the geometric domain, using a proper modification of the Koch construction
(Problem 3.4). A different approach was proposed by Lindenmayer [36, 37] and is essential to
the resulting theory of L-systems. The generated structures and the rewriting rules are expressed
symbolically using a string notation. The geometric interpretation of these strings automatically
captures proper positioning of the higher branches on the lower ones.
The basic notions of the theory of L-systems have been presented in many survey papers [39,
40, 41, 43, 44, 45] and books [27, 56, 61, 66, 70]. Consequently, we only describe parametric
L-systems, which are a convenient programming tool for expressing models of plant development.
Figure 5: Information flow in a Koch construction and in a developing modular structure. In the
Koch construction, information flows only fromthe parent modules to their descendants (continuous
line). In the developmental model, positional information flows along the paths from the root to
the apices of the branches (dashed line).
4 Parametric L-systems
Parametric L-systems extend the basic concept of L-systems by assigning numerical attributes
to the L-system symbols. This extension was implemented as early as the 1970’s in the first
simulator based on L-systems, called CELIA (and acronym for CEllular Linear Iterative Array
simulator) [3, 26, 27, 38], as a programming rather than theoretical construct. Our presentation
closely follows the formalization introduced in [57, 61] (see also [25, 58]) (Problems 4.1, 4.2).
Parametric L-systems operate on parametric words, which are strings of modules consisting of
letters with associated parameters. The letters belong to an alphabet V , and the parameters belong
to the set of real numbers <. A module with letter A 2 V and parameters a1; a2; :::; an 2 < is
denoted by A(a1; a2; :::; an). Every module belongs to the set M = V <
,where <
is the set
of all finite sequences of parameters. The set of all strings of modules and the set of all nonempty
strings are denoted by M
= (V <
)
and M
+
= (V <
)
+
, respectively.
The real-valued actual parameters appearing in the words correspond with formal parameters
used in the specification of L-system productions. If is a set of formal parameters, then
C() denotes a logical expression with parameters from ,and E() is an arithmetic expression
with parameters from the same set. Both types of expressions consist of formal parameters
and numeric constants, combined using the arithmetic operators +,
