Wednesday 24 October 2018

Automata, Chaos and Emergent Behaviour

This month's meetup was an introduction and tutorial by Peter Marks on automata, chaos and emergent behaviour.


Tutorial code examples and reference links are at http://art.spluko.com/ace/.


Key Themes

Rather than spend a long time trying to define the rather abstract idea of automata, Peter decided to briefly introduce it as a thing which evolves by following simple rules, and to develop the idea during the talk.

The word state is used to describe the current state of these "things". Again, this is an abstract idea, and could mean one of many things - state could be location, or colour, or size, or how healthy a thing is feeling.


These "things" could be pretty much anything, which gives us a lot of creative opportunities, rather than a cause for discomfort.


Peter set out the key themes we would explore during this journey through automata and their behaviour.

  • Iteration - the repeated application of rules, often mathematical rules

  • Multiplicity - Creating and evolving many automata. 

  • Interaction - Allowing the evolution of automata to depend on other automata, encoded again as the simple rules that define their next state.


Simple Example

Peter presented a simple example to illustrate the abstract idea of an automaton. He used a javascript class to define an object, the 'thing" which we will consider an automaton.

The automaton was named a Circle in his code, and it had two bits of state - a colour and a size. That's all that's needed to define a simple automaton - but we can't see it. We can add capabilities to this automaton to make it visible.  Peter added a javascript class method to draw this Circle object, and another to evolve its state. Drawing takes into account the automaton's state - colour and size.

The evolution is simple. Both colour and size are incremented at each step, and reset to a small value if they reach an upper limit, to prevent them from growing ever larger. Repeated application of these simple rules is the idea of iteration we set out above.

This all sounds like a lot of words for what is essentially doing simple things - but we're framing it in the context of automata.

Here is this simple automaton evolving - both in size and colour. The code is online at https://codepen.io/spluko/pen/WaZxyM.



More Than One Automaton

Peter then progressed to simulating more than one automaton. This is the idea of multiplicity we listed above.

Peter created 300 individual automata. Each of these 300 Particles, as he called them in code, have state and a way to evolve that state. A Particle was given two bits of state - a position and a velocity.

The position is used to determine where each Particle is drawn, and the velocity is used to determine how the position changes over time, using simple school-level physics. To make the simulation a little more realistic, gravity was also used to adjust a particle's velocity. You'll remember from school that gravity is a force, which directly affects velocity, which in turn affects position.

If school physics isn't exciting you, don't worry - the main point is having multiple automata, each evolving their state according to simple rules.

The following shows how 300 Particles move according to their own velocity and also the efffect of gravity. The code is online at https://codepen.io/spluko/pen/vVeJeW.


That is a rather nice fireworks effect!

Peter developed these simple simulations, for example to enhance the rules so the automata bounce off the edge of the canvas. You can find the code at http://art.spluko.com/ace/.


Chaos

Before proceeding to illustrate interaction between automata, Peter demonstrated numerical chaos.

Intuitively, we expect simple rules to generate simple behaviour. But in fact, some simple schemes result in apparently random and apparently unpredictable behaviour - chaos. Strictly speaking, numerical chaos is not random. The behaviour of a chaotic thing can be calculated. The key point is that it is not possible to predict future behaviour by following a trend - the behaviour is too erratic. Furthermore, two chaotic systems that have very very similar state, will diverge very quickly. Chaotic systems are very sensitive to initial state - and this is basis for the very common butterfly-effect analogy.

Peter's example of numerical chaos was very simple - simply taking a number and multiplying it by a large number, and then taking a modulus (remainder after division). The resulting number are very hard to predict as they follow no obvious pattern. In fact this scheme is the basis for many random number generators in computers. You can see an illustration of this randomness at https://codepen.io/spluko/pen/bmYjLg.

A more interesting simulation is creating automata which have a simple number as their state. The rule for evolution is simply to use that number to calculate another number to become its state. That calculation is the method for creating apparently random chaotic sequences above. As the automata evolve, these chaotic sequences can be used to define curves - which end up looking like scribbles.


You can find the code at https://codepen.io/spluko/pen/dqLOGg. The effect above is achieved by, in effect, darkening the canvas before drawing the next curve. Repeating this has the nice effect of making previous curves slowly disappear.


Interaction

Peter then introduced the final idea of interactions between automata. Up to now they've been evolving independently, each unaware and unaffected by other automata in the simulation. The slight exception to this was the balls bouncing off the edge of the screen - they took the environment into account as they moved.

Peter again implemented simple school physics to model the position and velocity of each automaton, drawn as balls. The rules for evolving the state are the same simple ones we saw before, position is changed according to velocity. In addition, a check for collision is made between balls and the edge of the canvas. Bouncing off the edge is relatively simple, the velocity is reversed. Balls colliding with each other also transfer their momentum according to school physics. We won't go into the details here as the main idea is interactivity, not a class on newtonian physics.

The following shows the rather satisfying, and also surprisingly realistic, simulation of bouncing balls. They start off as a simple Newton's Cradle. In theory the cradle would continue with its regular predictable movement forever. This simulation breaks down into chaos because one of the balls has its initial position shifted by a tiny tiny 1e-13 units. This shows how sensitive the system is to initial conditions. The code is at https://codepen.io/spluko/pen/wYvMzW.


This completes the key ideas of automata as abstract "things" having state which evolves according to simple rules, iteration, multiplicity, and interaction, with a nice detour looking at chaos.


Further Examples

Peter presented further examples of automata which better demonstrate how sophisticated the visual rendering of automata behaviour can be.

The following demonstrates the evolution of particles, determined by simple mathematical rules using only sine and cosine functions. The code is at https://codepen.io/spluko/pen/QZmwyp. Experiment by changing the parameters A, B, C and D in the code.


You can read more about these De Jong attractors here, here and here.

It is worth thinking a little more about this example. We have automata which follow very simple rules, yet their paths are chaotic. But out of that chaos appears a definite pattern - the emergence of order out of chaos.

Peter also extended the previous colliding balls simulation to include repulsion when balls are too close. This has analogies in atomic physics where atoms can attract but then repel when they get too close. You can see the code at https://codepen.io/spluko/pen/GYOwXo. In this example, the balls surprisingly arrange themselves into a circle because

A very compelling example of automata interacting is when the rules are similar to how flies or birds might adjust their flights in response to their neighbours. These flies behave as follows:

  • each one tries to fly towards the centre of mass of neighbouring boids
  • they try to avoid getting too close to other flies
  • they try to match the velocity of their neighbours
These are very simply rules, and they don't seem wrong if applied to birds of flies.

The resulting motion is pleasantly surprising flocking.


You can find the code at https://codepen.io/spluko/pen/ZqRyaE.


Conclusion

Peter succeeded in explaining automata as an intentionally abstract concept of "things" with state, which evolves through the repeated application of simple rules. He also set out and illustrated the key ideas for simulating automata:

  • iteration
  • multiplicity
  • interaction

Speaking to a few attendees, the feedback was really positive, indicating a desire for more sessions covering ideas and concepts.




No comments:

Post a Comment