Alrium

Alrium is an effort to create a working, complex artificial life simulation environment.

This is a design paper for the project and its implementation.

Description

I built a very simple artificial life simulation environment called AIrium. Since a friend mistakenly called it Alrium, I decided to adopt the mistaken name for this new take at building such a simulation.

This new iteration of the project focuses on solving the problems of the first:

• documentation: having an actual model to follow
• variety in creature body and mind structure
• removing evolution limits (such as brain size)
• allowing different species to mate and produce possibly stable children
• speed: trying to get the simulation to be as fast as possible on consumer grade hardware
• multiplatform: allowing many platforms to execute the simulation
• concurrency: try to enable the maximum concurrency when simulating the world, to the point that multiple networked computers may collaborate and work together to simulate a world faster or help each other into achieving meaningful results faster.

Possible Applications

• studying evolution dynamics
• discovering new approaches at common problems by looking at how the simulated machines solved them
• learning how to create the environment necessary for a specific kind of evolution to take place
• having fun designing such a world and implementing a simulator for it
• having fun manually designing and creating structures
• having fun looking at machines interacting with the world and each other
• bragging about having designed and implemented such a simulation
• figuring out wether it would actually work
• distributing a creative alternative to a fish tank
• distributing an interactive game where the objective is to evolve the smartest creatures

World

The world is a matrix where each cell is either empty or occupied by a structure. Every structure occupies only one cell.

Structures and Creatures

• a structure is a matrix where each cell is either empty or occupied by a Block.
• each adiacent Block can be connected.
• the blocks make up both the body and, if the blocks are connected, the mind.
• structures can move in the world, but can't occupy the same space of another structure.

A structure with an operational mind governing the body is called a creature or machine.

There are four kinds of blocks:

• neuron blocks make calculations
• action blocks let a structure do something
• sensor blocks let a structure know something about itself or anything else
• resource blocks can be interacted with, causing some effects

Signals

• a signal is a floating point value. Each block stores a signal.
• a signal is always between -1 and 1 included.

Connection

• Each block can be connected to every other adiacent block (diagonals too), so each block has 9 input connection weights: one for each neighbor and one for itself.

• A connection is a weight, which is a floating point number. All connections are inputs.

• A neuron block's output is its adiacent blocks's current stored signals multiplied by the appropriate weight.

• the weight (or connection) is a floating point number between -1 and 1 included.

• If the connection is 0, then there's no connection

• if the connection is not 0 then there is a connection

• if the connection is 1 then there is a full positive connection, meaning the source value passes intact to the destination

• if the connection is -1 then the exact opposite of the input value passes to the destination

• the highest abs(val) where val is the connection/weight is, the stronger the connection

  \ | / v v v ######### -> # block # <- ######### ^ ^ ^ / | \

• assuming the block in the drawing is at (2,2), it will be connected with: (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)

• this drawing doesn't include the recursive connection the block has with itself

A signal can be any floating point value between -1 and 1.

• any signal higher than 1 will be considered to be 1
• any signal lower than -1 will be considered to be -1

Neuron (Processing) Blocks

• new neuron blocks contain the 0 signal (null signal).
• neuron blocks store a signal until it is changed. The signal is calculated again at every iteration of the simulation
• a neuron block's signal is the sum of all the incoming values, divided then by the sum of all the weights.
  • an incoming value is the signal coming from a connection multiplied by the connection weight.

Action (Output) blocks

They take an input signal and act by doing something, for example:

• they move the body in space
• they eject something
• they change color
• they interact with other structures
• they "eat" a block
• nothing (can be useful to stop signals from passing through)

Sensor (Input) blocks

They give adiacent blocks a signal.

Some examples:

• they communicate how far is the first structure in a straight line
• they communicate the amount of structures in relation to blank spaces in an area (popularity in an area)
• they communicate the color/type/activity of the first block in a straight line
• they communicate information about the presence of a particular kind of structure in a direction
• they communicate information about the structure itself, like integrity of adiacent blocks

Generated signals are floating point numbers ranging from -1 to 1 included.

Combined (Input+Output) blocks

They act as Sensor blocks and Action blocks at the same time.

Examples:

• a "mouth" block that can communicate wether food is available to eat and can receive eat commands at the same time

Reproduction and evolution

This requires two action blocks:

• the egg block
• the fertilizer block

machines can of course have both blocks, or even multiples of them.

• the egg block leaves a structure behind, an egg. This egg will either be fertilized or deplete energy and die.
• the fertilizer block can be used on egg structure to fertilize them

Hatching

When the egg hatches, a structure is born. The structure is built using a combination of the father's and the mother's blocks, then a mutation is applied to the result.

Energy

This requires some new blocks:

• the battery block (first mentioned resource block)
• the energy drain block
• the generator block
• the stomach block
• the energy drain block sucks energy from a structure's batteries.
• the battery block stores energy and emits the current level to its connections
• the generator block uses up a lot of energy, then gives back slightly more
• the stomach block can be used to eat blocks from another structure. It then uses some energy to digest the blocks, providing it back with an extra amount after it's done.

Consumption

• each action block uses up a moderate amount of energy when activated
• each sensor block uses up a small amount of energy when activated

Fitness of a structure

The fitness is calculated by dividing the creature's total harvested energy by the creature's total consumed energy.

A creature with a fitness lower than or equal to 0 has all its batteries depleted. Then, it is either revived by being charged somehow, or it can't do anything and no mind activity can take place.

This method to calculate fitness has many problems:

• What if a creature donates energy to others of the same species? It gets counted as energy consumption, thus decreasing fitness
• What if a creature couldn't harvest energy because the environment wasn't ideal?
• What if a creatures scored hugely because the environment was just perfect for huge scores?

The conclusion is that this system is far too complex to consider fitness evaluation.

Complexity of a structure

The point of structure complexity is to try and approximately figure out how computationally expensive it is to compute an itearation of the simulation for the structure.

The complexity of a structure is:

• if the fitness is > 0: the sum of the complexity of all its blocks.
• if the fitness is <= 0: 0, because there is nothing to compute if the structure has no energy.

Block complexity evaluation is covered in the Parallelism section.

Primordial world

The world should be composed of a variety of huge, small and anything in between energy farming or storage structures.

Even better, there should be structures generating energy and shipping it off in space.

Primordial creature

Since we can't expect that interesting machines pop up from nothing in our simulation, we need to design one. On Earth, it took billions of years for something to show up, but we want to speed things up a little bit.

This machine needs:

• to search for energy sources
• to find energy sources and get there
• to use energy sources to fill up batteries
• to successfully create fertilized eggs

From there, maybe something smarter can show up. It is essential that the user can save a machine at any time, even early in an implementation. We don't want to lose good machines!

Interface

It is very important to give the user the ability to see the world in motion.

The interface should be structured akin to the following guidelines:

• a world navigation screen
  • lets the user create an empty structure (needs at least 1 block)
• structure navigation screen
  • ability to save the structure to file
  • has a small selected block sidebar with block informaton
  • lets the user clear cells or set a block to them
• block navigation screen
  • provides all info about the block and signal activity information
  • lets the user view all connections and edit them
  • lets the user edit the block type, preserving the connections

A sidebar has controls to handle simulation speed and pausing and other information such as:

• current CPU load.
• available energy in the world and amount being generated
• population information

Implementation

The rust programming language is quite suited for a variety of reasons, namely:

• it is a fast language, well suited for performance intensive tasks
• it has a package manager that allows a programmer to focus on writing the code, not desiging infrastructure, build systems, or coding functions already available in popular libraries
• it produces native, multiplatform binaries
• it obviously supports all the required features for the implementation of the simulation

But most importantly:

• it is built with a focus on type safety, concurrency and thread safety
• it's impossible to compile a thread unsafe concurrent program with the rust reference compiler

However, it has also some issues:

• there is no GUI toolkit or game engine or anything similar advanced enough to ensure smooth cross platform user interface development
• I don't know the rust programming language very well (not a big problem though)
• its lower level nature (compared to java) would make development slower
• it's very hard to write a multithreaded program in rust due to the compiler being extremely limiting by refusing to compile programs with a chance to cause segfaults or race conditions
• no structure/object/class inheritance
• I honestly don't think I can implement this simulation in a multithreaded and/or parallel computing friendly way using rust.

That's why I ultimately chose to use Java. It's a language I know very well, that has most of rust's features necessary for this project without the problems.

Simulation iteration evaluation algorithm

• MT: manager/main thread, controls the flow, HIGHEST PRIORITY
• WT: worker thread, evaluates a simulation iteration for one or more structures
• AT: applier threads, applies actions and writes the new stored signal into the current stored signal for all blocks

One tick is evaluated using the following algorithm:

1. MT
   • rebalances the WTs work load, evaluating it based on structure complexity
   • assignes newborn structures to the workers
   • starts all the workers
2. WTs work, MT waits until they are done
3. MT assigns actions returned by all the WTs to a number of ATs
   • tries to balance the ATs' work
   • groups events from creatures that interact with each other together, keeping it thread safe but as distributed across threads as possible
4. ATs work, MT waits untile they are done

It's probably not as fast as it gets, but it should be decent

Structure iteration evaluation algorithm

1. the new stored signal of each block is calculated
   • if the block is a neuron block, calculate its new stored signal using immutable references to the other blocks and the connection values.
   • if the block is an input block, run its logic to figure out what its output should be
   • if the block is an output block and it should perform an action, add it to the action queue
     • an action is a function or method and a list of parameters to pass to it (if it takes parameters)
   • This new stored signal is stored in a special variable without overwriting the current stored signal so that the process can be easily accomplished in multithreading execution environments.

Note: the bigger a machine, the slower it reacts to inputs because signals need more time to travel through the body

Multithreading and Parallelism

The first AIrium wasn't built with concurrency in mind, it was only added later with average results.

This time, concurrency was baked into the project since its first design: when evaluating an iteration of the simulation for a structure its output is just a list of actions that the structure wants to perform on itself or the environment.

The world simulation can be parallelized down to the single block of a structure, then their actions can be applied to the world sequentally.

Note: Even the action application could be evaluated in parallel by grouping structures together, putting each action into a group. if an action concerns both Structure A and Structure B, then they are related and actions concerning one of A or B should go in the same group. The problem is that this kind of classification is already a big problem of its own, expecially considering that a fast grouping algorithm is essential to fullfull the high performance needed in this implementation. Thus, I think it's better to avoid trying to parallelize action evaluation for now.

Another problem the first version of AIrium had was when new creatures where created by the artificial selector. That was because computing a child creature requires a lot of iteration, memory accessing and random number generation. This is slow and a big problem that will need to be addressed expecially in environments with structures producing a high amount of eggs. The solution I'm thinking of using is to not try to compute the child structure right away, but save a copy of the parent structures' inside the egg, then slowly build a child when evaluating the egg blocks.

There's also the Block complexity (evaluation speed) variety. Ideally, to be able to compute how complex a structure is, we have to know how complex blocks are. But, the higher the complexity, the higher the computational time. So ideally, we need to know, approximately, how much time does a block need to be evaluated.

A possible improvement is Smart block evaluation. It consists in not evaluating a circuit if no action blocks are affected by it.