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 mother

module, and applying the same transformation to all the modules in the successor in order to

produce the appropriate child modules (Figure 1).

 

wpe2A.jpg (21192 bytes)

 

 

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

 

 

wpe2B.jpg (15029 bytes)

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

 

wpe2C.jpg (17849 bytes)

 

 

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.

 

 

 

wpe2D.jpg (12470 bytes)

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 +,

 

wpe2E.jpg (53662 bytes)

wpe2F.jpg (28096 bytes)wpe30.jpg (28096 bytes)

wpe31.jpg (63274 bytes)