A molecular collision model
of musical interaction
Peter
Beyls
Hogeschool Gent,
Belgium &
Computer Music Research,
School of Computing, Communications
and Electronics,
University of Plymouth, UK
peter.beyls@plymouth.ac.uk
Abstract
This
paper speculates on the potential of a limited set of interacting particles to
produce interesting temporal structures in a two dimensional world. Particles
exchange information locally though global complex behavior emerges
spontaneously. The imaginary physics of the world is described in an ensemble
of 2D arrays. An autonomous genetic algorithm continuously aims to optimize the
arrays in an effort to maximize diversity. In addition, an external user may
interfere in a subtle way; external gestures are integrated into the arrays in
proportion to their strength. A quite elaborate mapping scheme creates
relationships between complex system behavior and parametric MIDI events.
1. Introduction
The present paper formulates a generative
system featuring native internal dynamics open to disturbance by unpredictable
actions from an external user. It follows the general working hypothesis of
much Alife research; life-like phenomena can be studied by building distributed
systems composed of many interacting components. Complex global behavior
emerges spontaneously from a collection of simple local interactions between
the constituting elements. These elements vary widely in dimension and
character; consider for instance, communicating newsagents living on the
Internet, social forces between people in a given society or molecules engaged
in a chemical reaction. The behavior of such systems cannot be envisaged from a
critical analysis of its components; in particular, the mutual relationships
between components will force a global unpredictable functionality.
In addition, various cognitive abilities have
been characterized as distributed, self-organizing systems (Minsky, 85). The
fluid dynamics approach of (Hofstaedter, 95) suggests the study of cognitive
processes, including creative decision making, as processes of molecular
interaction. Again, coherent structures appear from the random flux of
continuous interactions amongst molecules. Our work adopts the metaphor of
colliding molecules as a first principle and thus also relates to recent work
in artificial chemistry (Dittrich, Ziegler & Banzhaf, 01).
Our
application proposes a model of musical man-machine interaction based on the
real-time interpretation of particles interacting in a closed container. The
container may be either of imagined toroidal shape or feature reflective walls.
The internal physics of the system, i.e. what happens when any two particles
collide, is represented in a 2-dimensional array. The array instructs particles
to move in particular directions. The user interferes with this innate behavior
by modifying the array through physical gestures. The user does not exercise
explicit control but rather disturbs the expression of an otherwise autonomous,
internal physical law. The basic idea here is to synthesize families of waves
of variable coherence and periodicity. The complexity of the waves follows a
law and the user has only limited and indirect instrumental control over the
quality of the wave propagation process.
2. Motivation
The
present experiment grew from earlier work with cellular automata (Beyls, 04).
CA are idealized systems to study complexity in natural and synthetic phenomena
but as models they are discrete both in time and space. However, one could
actually interpret embedded particles in CA as interacting molecules (Hordijk,
Crutchfield & Mitchell, 96). This work interprets domain borders of
space-time diagrams in one-dimensional automata as particles. Still earlier work by Ed Fredkin suggests CA
as models of ballistic computing. The billiard ball model has great musical
potential since its novelty consists in focusing on the detailed evolution in
time of an individual microscopic state – in contrast to studying macroscopic
quantities based on a statistical distribution of states (Toffoli & Margolus,
86). This collision model successfully performs logical operations using
mirrors as routers.
Now,
in an effort to generalize, we may think of particles as responsive objects of
arbitrary complexity and even equip them with some form of long-term memory.
Consider, for instance, people meeting and interacting in a public space.
Social behavioral patterns will surface spontaneously. However, the work
described here takes the atomic route to complexity engineering; the objects we
use feature a single instance variable – the angle of movement -- and cannot
remember former actions (no memory).
Related work
The
discipline of artificial life has spawned many incarnations of distributed
computational models. According to the field of application we speak, for
instance, of particles, molecules, agents or artificial creatures. Particle
systems have a long history in the computer simulation of complex natural
phenomena. They are instructive, early examples of studying complexity by
considering relationships amongst small buildings blocks – in contrast to using
differential equations. More recent work by (Reynolds, 87) describes the
flocking of birds (boids) as an emergent process. The Swarm simulation
environment developed at the Santa Fe Institute (Minar, Burkhart, Langton &
Askenazi 96) is also a significant example.
The
swarm and boids ideas was recently adapted for musical purposes by (Blackwell
& Bentley, 02). Swarmmusic is an interactive music improviser. It maps the
positions of particles/boids to positions in MIDI space. An external human
improviser may act as a temporary target for the swarm. Style-scripts provide
additional parametric control over the nature of the interaction thus further
conditioning the musical output.
Earlier work of the present author has addressed the potential of
real-time man-machine interaction in virtual worlds. Four different agents
oriented systems aimed at interactive composing are documented in (Beyls, 97).
3. Formal definition
For
our purpose, a molecular system is characterized as a tuple {M, R, A}
where M is a finite and fixed size collection of basic molecular
building blocks and R denotes all possible interaction rules. A
specifies an algorithm incorporating additional parameters conditioning how and
when the rule R will be applied. Note that the interaction vessel itself
is assumed to remain fixed, it is of no qualitative concern to a formal
description.
We
consider the density of molecules to be fixed (8 in our implementation) and,
for clarity; we shall modify a molecular feature (the angle) instead of
changing the concentration and/or type of molecules.
The
system activity is formally summarized as:
The algorithm A
is equivalent to S, a sensitivity matrix. It holds numerical values
expressing a threshold for interaction between any two types of molecules to
take place.
The
vessel contains 8 molecules defined by M. All molecules move in a
direction defined by their momentary angle. The state space of angles is
discrete and has a resolution of 30 degrees, so relative angles range between 0
and 11 to cover full circle. Note that angles are spread out evenly in that
circle. Note also that the angles resolution has a very strong impact on the
potential temporal complexity of the system as a whole; higher resolution will
expand the state space in an exponential way. (This will be addressed in future
implementations).
Interaction
rules R are also described explicitly as regular arrays of 12 by 12 elements.
The angles of interacting molecules receive specific interpretation. Both
angles are interpreted as to index locations in the array -- to retrieve the
new values of both respective angles. The array is a simple and compact way to
represent how 12 different types of molecules potentially interact. The state
space of all possible matrix rules is huge (12 expt 144 is a 156 digit number!)
and thus considered virtually infinite.
The
effect of the rule array is qualitative control over molecular collisions. Now,
interactions between molecules become effective when their physical distance is
less than their mutual interaction threshold defined by array S. When
interacting, both molecules will update their angle. For clarity, sensitivity
values S are symmetric in the current implementation, though
unequal sensitivity values would certainly add higher degrees of non-linearity
to the system.
4. Implementation
The array
The
above figure shows the systems architecture. The central 2-dimensional array
acts as a lookup-table rule, which molecules in the vessel address. Interacting
molecules modify the vessel as a whole thus conditioning posterior
interactions. This creates a complex dynamical system; a simple simulated
universe is tightly coupled with the expression of a virtual physics defined in
an array. For simplicity, we assume the initial conditions (molecular
positions) to be random. Also note that we are dealing with a non-reversible
system (Prigogine, 84). The future is captured in a deterministic device (the
array) though the global system behavior may appear to feature chaotic
attractors.
Once
set in motion, the couplings between rule array and the vessel -- completely
disconnected from the user -- may orchestrate the sustained synthesis of
interesting waves for hundreds of generations. The array values (0~11) are
mapped to 12 different colors in a private GUI (see fig. 3)
Fig. 1. Global system architecture.
Observe the two loops incorporating the user.
The user
The
actions of the external user speculate on the possibility to issue qualitative
control over this global behavior albeit in an unusual, indirect way. A user
provides gestures in 2D space; consider MIDI input of a sequence of (pitch,
velocity) events interpreted as a trajectory (x, y) in 2-dimensions. The
current implementation uses mouse input; the user draws some gesture (limited
to maximum 100 coordinate pairs). The gesture is analyzed instantaneously when
a mouse-up event occurs; analysis includes relative length, angularity,
traversed distance, total surface used and acceleration/deceleration. Given a
fixed sampling rate, we obtain information about the character of a gesture,
and consequently, about the motoric personality of a given user.
Now
a gesture modifies the current array plus some of the other arrays in the pool.
The amount of change plus the number of arrays modified is stochastically
proportional to the total length of all segments in a gesture. In addition, the
change in an array is computed following an interpolation algorithm. That is,
the previous contents of an array strays partially into the future. Therefore,
arrays also function as long-term memories.
Fig. 2 Prototypical example: two objects interacting according to
their current angle of movement. Thinly drawn arrows denote angles at time
T, thick arrows denote angles at time (T+1).
The vessel
The
simulated vessel is the environment holding molecules moving in a given
direction at constant speed. At every cycle, every molecule checks whether any
other molecule is within its sensitivity range. If positive, the angles of both
objects are viewed as (x,y) pointers in the array. The retrieved value (0~11)
will set the new angle (0~330) of that molecule. In case we are dealing with
asymmetric affinities, some of the neighbor molecules will change their angle
if their sensitivity is high enough. When more than two molecules are within
interaction distance, all neighbors will be evaluated sequentially, the last
value retrieved will finally affect the new angle. The sensitivity between any two angles is expressed in a 12 by 12
sensitivity array. However, most of the experiments reported here use a fixed
sensitivity value for all angular affinities.
The pool
There
is a small critical mass of 8 arrays, one of which is copied into the currently
exploited array. A background algorithm switches continuously between the
arrays when the ‘delta flag’ is true. During every time frame, the specific
array also traces the quality of its performance; it counts the total number of
interactions plus the number of unique instances of angles-histograms
encountered (see Fig 5. History track of angularity histograms). The fitness of
the array will be directly proportional to the diversity in histograms. Arrays
are chosen at random conditioned by the number of times they were chosen
before; the selection probability is inverse proportional to the number of
times used in the past. All arrays are visualized in a graphic user interface
(see fig. 2), small arrays on top are selected by pointing and the two numbers
separated by a colon indicate respectively the nr-times-selected and the
accumulated total fitness.
Fig. 3 Rule array selector and
visual feedback interface. The user implicitly steers a complex dynamical system from the
observation of the cumulative effect of (1) rule array selection and (2)
rule modification, as described above. The user’s evaluation is purely
subjective; one tries to discover relationships between global system
behavior and spontaneous user activity.
The genetic algorithm
When
the ‘Xover’ flag is set, an autonomous genetic process will act in parallel.
The genetic interpretation and action is straightforward: arrays are viewed as
genotypes subject to standard crossover and mutation operators. The arrays are
first sorted according to fitness, the two fittest are considered parents in
the breeding process yielding 8 fresh arrays. A small amount of mutation helps
prevent premature convergence into a more or less uniform pool.
So
both the user and the GA contribute to the interactive development of
interesting, propagating structures. Actually, a particular type of man-machine
cooperation emerges; the GA clearly aims optimization by creating arrays that
often look quite similar; they converge to some spot in genetic space. On the
other hand, user activity both selects and modifies some arrays, often
profoundly disturbing the GA instantiated structures. The system thus
permanently fluctuates producing patterns of variable regularity. User
initiated actions have two effects; they tend to favor short-term disorder
while also influencing long-term behavior since some of the modified arrays
will survive in the next generation. Machine initiated activity can be
described as background autonomy according to the single criterion of global
system fitness.
The
general advantage of the genetic approach is twofold. First, it allows managing
the external effect of complex processes without fully understanding the
internal machinery orchestrating them. Second, genetic algorithms may generate
constructive material that could not be anticipated by an external observer --
so they function as generators of surprise in an otherwise stable system.
For
musical continuity, we rely exclusively on the arrays. The system as a whole
exhibits a certain inertia; arrays are modified by interpolation and the
genetic activity spawns offsprings that inherit features of their parents as
they were living in the previous generation. In other words, the perceived
melodic continuity is an implicit byproduct of the global systems behavior – it
does not result from any form of melodic memory. Consequently, coherent melodic
form issues from the accumulative forces of explicit physical gesture and
implicit genetic evolution.
5 Mapping procedures
The
mapping process defines an imagined relationship between an abstract pattern
generating system and an evolved, elusive cultural system we call music. It is
the most crucial yet the most difficult component of any generative music
generator. We could view molecules as interacting harmonics articulating some
complex sound, we could view the molecules as controlling a black box sound
synthesis algorithm of arbitrary complexity. However, we shall try to map
system dynamics into a melodic sequence with given tonality. The mapping
process avoids momentary absolute values and favors using the first derivate of
the current situation. In other words, the variable distances between molecules
rather than their position are considered. The mapping proceeds as follows:
(defmethod create-melody-slice
((self cawp))
;; only 1 situation of max 7 events
(clear-events (melody self))
(loop with position-distances =
(position-distances self)
with angle-distances =
(angles-distances self)
with interacting-lists = (mapcar
'interacting-p
(subviews self))
with all-durats = '((4 2 2) (16 8 8)
(2 1 1 2 1 1)
(8 2 2) (8 1 1 1
1))
with durats = (take all-durats
(mod (loop for el
in interacting-lists
sum (length
el)) 5))
with ahist = (angles-histogram self)
with maxv = (apply 'max ahist)
with posmaxv = (position maxv
ahist) ;; 0 to 11
with countv = (count maxv ahist)
;; min/maj
with tonaltype = (if (zerop (mod
(apply '+ ahist) 2)) 0 1)
with scale = (nth (+ posmaxv
tonaltype) 24-scales) ;; global
with st = 0 ;; start-time
with chan = 0 ;; midi channel
with d ;; event duration
initially (format t "~a ~a ~a ~a
~a ~%"
ahist posmaxv countv
tonaltype scale)
for i from 0
for cell in (subviews self)
for interact in interacting-lists
for p in position-distances
for a in angle-distances do ;; a is
signed
(setq d (/ (take durats (+ a i)) 10))
(setq chan (if (< p 100) 0 1))
(when interact ;; length of list > 0
(cm::insert-object ;; insert timed midi event
(cm::new
cm::midi
cm::time st
cm::keynum (+ 36
(*
12 (round (/ (point-v (view-position cell)) 40))) ;; octave
a) ;; angle
cm::amplitude (if (plusp a)
(+ 100 (random 20))
(+ 60 (random 20)))
cm::duration d
cm::channel chan)
(melody self)))
(unless (< p 100) (incf st d)))) ;; conditional chord
The
method create-melody-slice, sent to a CAWP object (acronym for continuous
automaton wave propagation), creates consecutive short melodic sequences.
The physical configuration of the cells is significant, though we avoid reading
and interpreting the structural pattern as if it were a conventional musical
score. Note we are dealing with two different but parallel timing processes.
The first one concerns the internal clock controlling the timing of the simulation
including the real-time visualization. Timing is set by the user -- up to about
10 updates per second. The second process handles MIDI events at a much slower
pace; both processes are concurrent though not synchronized. The melody object
sends a message when it has finished playing its current contents, this
triggers the create-melody-slice method and this process repeats
indefinitely. One could say that the mapping procedure occasionally samples the
current situation of a virtual world. The (dis)similarity of the melodic output
will thus reflect how much the world changes from one generation to the next.
Let’s address the mapping algorithm in detail.
The
position-distances and angle-distances are the first derivate of
the respective instance variables, angle-distances are signed values. Interacting-lists
holds a list of all the current neighbors of every cell, if any.
All-durats is a local library of relative duration units, a short
stylistic ensemble of building blocks to be exploited by the algorithm. Durats
is the selected element from that library; the selection pointer equals the
total sum of all neighbors of all cells, modulo 5 (i.e. number of sublists in
all-durats). The local variable ahist is the current angles-histogram,
12 elements wide of which Maxv holds the angle that is most expressed in
the current situation and posmaxv is the position 0~11 of that value in
the histogram. Countv is the number of times the maxv value
occurs in the histogram, it says a lot about how specific that value is and, in
addition, it is a hint to the diversity of the histogram.
Our
system is built inside a larger framework for musical experimentation (written
in Lisp -- Digitool MCL 4.2) that provides many resident composition, pattern
processing and analysis tools, including tonality libraries of arbitrary
complexity. However, the current implementation builds on Western tonality and
uses a simple global variable 24scales holding all major and minor
scales in all pitch-classes. These libraries are precomputed for computational
efficiency. The algorithm decides on major tonality if the sum of all values in
the current histogram (modulo 2) is even, else it is minor. A specific scale is
then retrieved from the scale library using a combined influence of pitch-class
(set by posmaxv -- very
conveniently in the range 0~11) and tonality.
The
algorithm now loops through the various lists; the position-distances are
considered at a threshold of 100, a value derived by trial and error. For
instance, if the distance between two consecutive cells is less than 100
pixels, MIDI events will sound on channel 1 (a value of zero in the program)
else on channel 2. In addition, the
same mechanism exercises a grouping of events, controlling the start-time of
new MIDI events. Thus, chords are always sounding on channel 1.
Finally,
a new MIDI event is instantiated on the condition that the cell under
consideration is actually interacting, if not, a rest is implicitly generated.
The pitch of the event combines 2 forces: octave position follows the vertical
position of the cell and the signed angle value adds an interval (-11 to +11)
to derive the final pitch. The sign of the current angle-distance conditions the
loudness of new events.
The
figure above shows a short score excerpt of a typical molecular interaction
sequence. The global, uniform sensitivity in this example is 15 pixels. We
notice the complex interlocking of rhythmical patterns. A point attractor is
passed through starting at measure 15. The expressive qualities follow
exclusively from the interpretation of a small group of objects moving in 2D
space.
6. Experimental results
The
complexity of the temporal patterns varies widely; given fixed and uniform
sensitivity, it is directly proportional to (1) the number of different angles
at any moment in time and (2) the number of cells that change value at every
cycle.
Our model is
considered a tool to experiment with interesting temporal changes – not so much
to help construct artifacts with a given finality. We focus on qualitative
descriptors such as stability, diversity, sensitivity and relational affinity.
Our model is built as a synthetic world with private physics, an imagined micro
society. Most important, it expresses non-linear relationships between its
components. This implies coherent yet unpredictable behavior; minute external
disturbances can indeed entail massive consequences. From the work of
[Prigogine & Stengers, 84] we know that order can arise spontaneously out
of disorder through the process of self-organization. This principle is scale
invariant, it holds for ant societies as well as galaxies – we shall bring it
into play it in terms of an abstract social system.
Fig. 4. History track of physical
position and direction
Our
experiments prove that social constructions occur spontaneously. For instance,
given the right initial conditions and the right rule array, a few cells will
cluster and move as a group, incidentally, similar to gliders in a 2D cellular
automaton. At every process cycle, the net effect of all cells executing a
private rule will be a coherent cluster of cells moving in a single direction.
Now, a cell approaching the cluster may interact with its closest component and
implicitly reconfigure the previous social construction. In other words,
collective cycle attractor behavior is destroyed temporarily. According to the
rule, communicating particles may simply bounce symmetrically, act as a
catalyser in a group reaction or engage in circular motion… Many complex
temporal patterns emerge that could be described formally using the notion of temporal
profiles. A profile would capture the rule and the initial conditions and
would then consider the cell’s trajectories and perhaps interpret them as a
collection of tightly coupled breakpoint-envelopes. These envelopes could very
well control a Fourier synthesizer, the result would be the expression of
social control amongst harmonics. This idea awaits further implementation.
Figure
4 documents 600 cycles of an interaction process with 8 molecules in a
container without reflecting walls. A single random rule matrix is used. The
sensitivity matrix holds random values in the range 1 to 30. There is no
gestural input from the user, so the internal dynamics develop in isolation, as
a closed system. Green and red lines respectively denote x and y coordinates and
blue lines show the momentary angles. The gray patches indicate when a
particular molecule is actually engaged in interaction. The gray patches at the
top of each graphic pane make it possible to detect chain reactions.
Qualitative oscillations of angle values are clearly observed. So there is
evidence that this type of complex dynamical systems may support modeling wave
propagation. According to the contents of the rule array, the waves may either
sustain or lead to a single angle value, the latter being equivalent to point
attractor behavior.
Fig 5. History track of angularity
histograms.
Figure
5 shows 12 data tracks in time, 600 generations long, each track represents an
angle from 0 to 330 in steps of 30 degrees. Angle histograms are computed at
the end of every process cycle; this provides information of which angle values
are in use, reflected in the density of the track (1) in addition to how many
instances (2) of these angles are being used, reflected in the thickness of the
track. The sensitivity array is uniformly filled with a fixed value of 15,
which means a global sensitivity value of 15 pixels.
A
subtle user gesture at around generation 400 slightly modifies the current rule
and forces a new type of waves to appear. First, past behavior is gradually
acknowledged and second, amplitude and periodicity gradually build up towards a
regular pattern. After a few generations, the internal dynamics will modulate
that pattern and it will evolve according to the nature of the modified rule.
One could say this constitutes a second kind of macroscopic behavior; waves
appear to interact as bigger constellations; in effect, a neat example of
emergent behavior.
7. Conclusion and outlook
This
paper documents early experiments with an object oriented collision model
supporting musical experimentation in real-time. It can be considered a
continuous cellular automaton, a form of ballistic computing or an example of
artificial chemistry. Anyway, the key notion here is emergence.
Interesting temporal structures appear from the expression of a simple rule
captured in a 2D array. These structures are thought of as propagating waves.
The role of the user is quite subtle; one does not tweak a series of black-box
global variables, in contrast, one shares forces with a genetic algorithm
acting in parallel. So implicit autonomous actions as well as explicit user
activity steer the relationships of an ensemble of objects moving in a 2D
virtual world. Imagine a virtual physics of which the expression and evolution
is partially controlled by an external user.
The
system acts successfully as a generator of interesting waves of variable
periodicity, even when operating according to the following constraints:
(1)
a fixed and uniform sensitivity range for all cells,
(2)
a fixed step size for all cells
(3)
a fixed density and energy of cells,
(4)
a discrete and small set of potential actions i.e. only angles change
(5)
no changes introduced by angle inversion when bouncing a reflective
wall, and
(6)
genetic background activity is switched off.
It
proves that the economy of expressing simple angular relationships in an array
does indeed suffice to support interesting, non-linear dynamic behavior.
However, further work is needed to classify families of automata and to study
the impact of initial conditions. Automatic classification could even be
addressed in an unsupervised offline algorithm since complexity criteria are
explicitly available.
The
work documented here is implemented in Macintosh Common Lisp using the
functionality of the MIDI drivers in Common Music (Taube, 97). Our
implementation challenges Lisp for real-time work. No doubt, Lisp is the most
powerful symbolic programming language yet it has trouble coping with the
pressure of real-time control – to the best of our knowledge, just one effort
aims to connect the universal power of Lisp with the optimized number crunching
efficiency of Max/MSP [Garton]. More work is needed to design robust
multi-purpose, concurrent computational environments using symbolic programming
languages.
References
Dittrich, Ziegler & Banzhaf. Artificial
chemistries, A review. Dittrich, Ziegler & Banzhaf. 2001
Beyls,
P A survey of agents based real-time interactive systems. Proceedings of
the ICMC97, Thessaloniki, ICMA, San Francisco, CA, 1997
Beyls,
P Cellular automata mapping procedures. Proceedings of the ICMC04,
Miami, ICMA, San Francisco, CA, 2004
Blackwell,P
& Bentley,P.Improvised Music with Swarms, Proceedings
of Congress on Evolutionary Computation 2002. [BLBEC2]
Minar, N,
Burkhart, R, Langton, C. and Askenazi, M, The Swarm Simulation System: A
Toolkit for Building Multi-Agent Simulations SFI Working Paper nr.
96-06-042, 1996
Minsky, M. The society of mind,
Simon and Schuster, NY 1985
Toffoli, T. & Margolus, N. Cellular
Automata Machines, MIT Press, 1987
Prigogine, I. & Stengers, I Order
out of chaos, Bantam Books Inc 1984
Hordijk,
W. Crutchfield, JP & Mitchell, M Embedded particle computation in
evolved cellular automata, PhysComp96, New England Systems Institute, 1996
Garton,
B. Maxlisp encapsulates CLISP within the Max/MSP
real-time music environment. See: http://music.columbia.edu/~brad/maxlisp/
Reynolds, C. Flocks,
Herds, and Schools: A Distributed Behavioral Model Computer Graphics
(Proceedings of SIGGRAPH ’87) 21: 25-34. 1987
Taube, H. An introduction to
Common Music, Computer Music Journal, Vol 21, nr. 1, 1997