When I look into the pond at my local park, there’s an amazing ecosystem of life at play. Algae covers the surface, and small fish come up to nibble on the meal. In the mud, bottom-feeding clams and large eels wait for prey.
My pond is only one example of the diversity of life on Earth. Just outside the city are dozens of lakes and grasslands, each with their own interconnected ecosystems. How did life emerge into so many coexisting species?
The answer is hidden in a property called open-endedness. In an open-ended world, innovation never ends. Instead, solutions create opportunities for more solutions. The algae create a food source for the fish. The fish create an opportunity for larger predators, who provide food for bottom-feeders when they die.
If you look closely, you can see open-endedness in many domains. In Ancient China, local farmers formed towns and villages, which became the foundation for feudal empires. The computers we use today are built off of semiconductors, which were discovered after research into radio waves.
The key feature of open-ended systems is that they never stop developing. Life will never be done evolving, and people will never be done creating new technology. As an AI researcher, this is a very useful property – it means we can train AI agents on potentially limitless tasks. It’s hard to imagine achieving general intelligence by classifying cats and dogs, but an AI that can invent increasingly complex technology would surely show us interesting behavior.
Cellworld
In this post, let’s explore basic open-ended principles through a cell-based gridworld.
When the yellow outline is full, a cell has enough energy to replicate, and will create a clone of itself in a nearby square.
Let's take a look at how this simple cell will behave when we set it loose in an 8x8 world.
Easily, the origin cell spreads everywhere. But once the world fills up, the simulation reaches its end.
This is a common issue when designing open-endedness: the world can reach a stable state, where no more progress can be made.
In our case, the problem is there’s no space. Let’s try introducing a death timer. A few seconds after being born, cells will die off. In addition, let's introduce a small chance for a cell to mutate its genome when duplicating.
Together, these changes define a search algorithm for new genomes. When a cell dies, there is an opportunity for a new cell to take its place. So if a cell has a mutation that lets it duplicate faster than its neighbors, its genome will become more prevalent.
Success! New genomes appear. Our search algorithm is working.
However, once Photo-rich genomes have spread, progress stops.
The problem here is a lack of peer dependency. The most crucial aspect of open-endedness is that solutions must create opportunities for more solutions. In other words, when new organisms appear, new niches must develop. Our lake is full of algae; now it’s time for the algae-eating fish to appear.
To try and see this effect, let’s introduce two more variations into Cellworld.
- Cells can mutate a Killer part, which will periodically kill nearby cells that do not share the same genome.
- Duplicator and Killer parts are now directional. For example, a cell with a Duplicator part in its upper-right quadrant will only be able to replicate up or right.
How will these changes affect the complexity of our little world? Let's take a peek.
So, that was a bit of overdramatization. But you have to admit, with just these two modifications, much more interesting stories emerge. Instead of a single optimal species, we now have a cycle, where a new species can potentially overthrow an older one.
The key here is that there is always an opportunity for new genomes.. When the world is full of Photo cells, a Killer cell can emerge. When the world is full of Killer cells, a new species can take over by attacking from the right direction.
In an open-ended world, solutions must create opportunities for more solutions. For worlds of interacting organisms, there are three key principles to sustain this behavior:
- Possibility Space: Organisms must have a large enough genome to describe arbitrarily complex behaviors.
- Peer Dependency: When new organisms appear, an environment must develop new niches.
- Search Algorithm: A procedure must find new organisms to fit new niches.
Since this Cellworld was fairly simple, both the possibility space and peer dependency of cells were limited, so we eventually stopped seeing novel behavior.
Further work can involve:
- What rules lead to greater peer dependency? Do we need more complex interactions, or perhaps some form of resource system? Can emergent symbiosis occur?
- Is mutation-based evolution the best search algorithm to fulfill new niches?
"Open-endedness: The last grand challenge you’ve never heard of", by Kenneth O. Stanley, Joel Lehman and Lisa Soros. This article is a great motivator for why we should care about open-endedness -- namely, its potential to create innovations that are too complex to be designed for directly. The article also gives an overview of past work in the field their reasonings.
"Identifying Necessary Conditions for Open-Ended Evolution through the Artificial Life World of Chromaria", by Lisa Soros and Kenneth O. Stanley. This paper gives a good foundation for finding the principles that allow open-ended evolution to occur. They propose a minimum criterion for survival, and define peer dependency as creating novel ways for new individuals to achieve this minimum criterion.
"Self-Organizing Intelligent Matter: A Blueprint for an AI Generating Algorithm" (Anonymous). This recent paper works with open-endedness in the neural network domain. They show an interesting formulation where cells are neural networks that can push/pull chemicals in a gradient around them.
Follow @kvfrans