Life in Wireframe

Here is a personal favorite of mine. L-system is short for Lindenmayer system, as in Aristid Lindenmayer the hungarian biologist who introduced this technique in 1968. L-system is related towards formal grammar mostly known for describing the growth process of plants. The growth algorithm itself is recursive and often pretty simple, but the result is far more complex. The very nature of the process makes the L-system categorized to self-similarity, meaning that even a small part of the plant is similar to it's whole structure.

The plant has its point of origin which never changes, however how the plant grow is formalized recursivly through a number of iterations where every iteration has one or several sets of rules which discribes the growthprocess. This is an important difference between L-system and formal grammar where there only is one rule.

There are many offsprings of Lindenmayers original L-system, but we for now only focus on one - The Fractal plant. I'm going to use the wiki example because I think it's self-explanatory.

variables : X F
constants : + −
start : X
rules : (X → F-[[X]+X]+F[+FX]-X), (F → FF)
angle : 25°

Here, F means "draw forward", - means "turn left 25°", and + means "turn right 25°". X does not correspond to any drawing action and is used to control the evolution of the curve. [ corresponds to saving the current values for position and angle, which are restored when the corresponding ] is executed.

Pretty life-like wouldn't you say? This is just an example of how L-system may be used, as I said earlier there are many variations. The emergent part is the simplicity, two rules howto draw lines produces this. If you look closely you can see the self-similarity in every branch. So what can we do next, well the video below is one thing.

I will return to L-system later to do some deeper analysis. For now ... as allways ... I leave it to you to find out more for yourself.

- Tobias

We come back to ant algorithms and now focus on where it can be applied. The most classic problem in computional mathematics is the traveling salesman problem. The problem is simple, but yet solving it is not.

Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

It's described in mathematics as a NP-complete problem, but I'll leave it up to you if you want to go down that road finding out exactly what that means. Anyone can connect every city with a single line, but how do you know if it's the shortest route? If you read the first article about ant algorithms you should get a "aha!" experince right about now. Ant algorithms or as it is also called ant optimization is perfect for these kind of problems.

Having a set of cities and X amount of ants with one task - visit each city once, you will achieve your goal simply by using the same stigmergy as when the ants collect food for their colony. The trail pattern will go from (2) to (3) and ending up as (4) as the pheromone decreases in strength on the trails with the longer distance. No real calculation, just nature finding its way.

If you are more interested in this technique and what it can do I recommend taking a look here for further studies. It's all about optimizations =)

- Tobias

Here is what I think is a interesting chapter. Yes I know, we are focusing in emergent behavior but I can't help mentioning genetic programming.

As the name reveals we are talking about genetics and evolutionary algorithms. I'm no expert in the area but I will do fairly understandable explaination on the subject. It does not follow a strict emergent behavior, but as you mess aorund you may accomplish something which you did not expect and genetical research is to this day a far more complex area than for me to be able to explain. We still don't know what will happen if we tamper with our genetical code. So we can tamper with our digital genetical code instead =)

As stated before genetic programming is founded from evolutionary algorithms which began in the 1950s. Since it is computationally intensive its was mainly used for solving fairly small problems, but as we got more and more computerized it has become possible to use in a wider range i.e quantum computing. But the most fun part of genetic or evolutionary programming must be when it's applied in creature evolution. Basicly you have a creature with some form o limbs, and as genetic programming is applied the creature learns through generations of evolution to "walk" or atleast transport itself fron point A to point B. Watch the video below and compare the creatures movements and limbs as it evolves through generations of mutations.



As you can see, from generation 1 to generation 1000 it has evolved to a more efficient creature. This is done by mutation of the creatures movements and limbs as it passes through one generation to another as i.e. father to son. But how? Well, I said I'm going to explain it as simply as possible which basicly can be done by this illustration of crossover-mutation.

Lets say A is the father and B is the mother. They have a child which consists of genes from both parents, but sometimes a mutation occures contributing to a new gene not from the mother nor the father. This is a part of one unpredictable aspect of "human" evolution. If we look at the videoclip above, the creature goes through a similar processe between every generation, programmed into it before it is "reborn" again.

- But wait!? you say .... how does it know what are good mutations and bad mutations? Well, for the simulation in the videoclip it must have something to compare the evolutions towards. It can be as simple as we stated earlier - getting from point A to point B as fast as possible. If a generation of creature is faster than its predecessors the mutation was an improvement and therefor better to spawn new generations from. The mutation can be applied to the limbs movements, shape, size you name it. The mutation and inheritage between generations can be done in many ways, but for now I only illustrate the crossover-mutation.

As Herbert Spence phrased after reading Charles Darwin's On the Origin of Species - Survival of the fittest. The strong survive while the weak perish and that is what genetic programming has adapted in this case. I can imagin that hunters thousands of years ago were fast and agile, simply because the short and slow ones couldn't catch anything or became dinner them selves in the hunting process =)

- Tobias

Yes you read it. Ants are a good example of emergent behaivor.

Have you ever been to the woods? If so, have you ever stumbled on a ant trail? How could these little creatures with almost no brain be able to find their way from the colony, get food and find their way back again. Well, simple realy ... if you can't think it, see it than smell it - pheromones. Ants use the environment to communicate with eachother and leave local pheromone tracks when wandering about. This is called Stigmergy. Notice "local" pheromone, because a pheromone does not say anything about where the food is or where the colony is. In mathematical terms, it's just a variable with a value.

We can embody a simple set of rules which is geneticly inprinted in a "farmer" ant. When it finds food it releases a pheromone when trying to find its way back to the colony. It's follows pheromone released by searching ants, the stronger the pheromone the closer to the colony(more ants). The pheromone it releases by it self (1) is attracting other ants which leads to that more ants finds the foodsource. They than also try to find their way back to the colony, creatinga trail in the process. When finaly finding the colony and again sets of finding food it has a pheromone trail to follow back to the food, consisting of pheromones by other ants.

Hence, the ants does not know where the colony or the food is. They are simple following the pheromones. The stigmergy happens to solve the task "given" to the ants. But, and this is a big but, the pheromone left by each ant decreases in in strength by time. This makes it possible for ants to determine if a trail is "hot" or "cold". Otherwise the trail would not just be one trail, it would be many since the ants can't determine which way is the shortest between the foodsource and the colony. The trail would look like (2) in the picture, well somewhat simplified anyway. Since the pheromone decreases over time the longer trails gets lower pheromone strength the ants will more and more follow the path with shorter distance between the foodsource and the colony (3).


So, simply by following pheromones the ants form a more complex situation than anticipated. Not strictly emergent as Boids, but still a algorithm engineered by nature. This may also explain why ant colonies all of a sudden are deserted. Maybe it's simply because the food started to be so far away that all ants scattered about to god knows where and started a new colony. How exactly would be fun to speculate, but some other time ...

- Tobias