This week’s BEACON Researchers at Work post is by University of Texas at Austin postdoc Joel Lehman.
Something that both fascinates me and drives my research is the creativity of natural evolution. If you asked me to solve a particular problem, I could probably come up with a few possible solutions. And maybe if inspiration struck, one or two of those solutions might be unconventional. But single-digit numbers don’t begin to compare with evolution’s creative drive. In fact, the number of species currently living on Earth is estimated to be around 9 million. Put another way, natural evolution currently has in its working inventory nine million working solutions to the problem of living. However, many more solutions evolution has contemplated but eventually discarded through extinction.
One way I like to think about natural evolution relates to some kind of vast closet. If you stick an ordinary bicycle into this enormous closet, close the door, and come back in five billion years, it’s very unlikely that the pile of rust that greets you will surprise you in any way. The magic of evolution is that if it was put into the closet for five billion years, the closet might well be teeming with surprises upon its reopening.
The diversity of life on Earth is what leads us to expect to be surprised by the outcome of this thought experiment: Life on our planet has been evolving for a similar amount of time, and there are many incredible species that have evolved. The archerfish hunts its prey (generally insects) by shooting them with a compressed stream of water; and these fish are remarkably accurate, rarely missing, and their aim impressively factors in how water refracts light. Woodpeckers have evolved cushioning in their brains, to keep their skulls safe while hammering away at trees. The bee orchid deceives male bees into attempting to mate with it by mimicking the female bee shape and scent. There are numerous other examples of surprising adaptations — but you get the point: Natural evolution is a profoundly creative process.
Ordinarily we associate creativity with human innovators or artists, and not with processes far removed from human oversight. So what fascinates me in particular about natural evolution is that it gives such a divergent example of creativity. Evolution’s creativity does not result from human influence. In this way, what motivates my research is the hope that examining what enables natural evolution’s creativity might lead to creating more creative algorithms. In other words, my research centers on trying to bottle up the essence of natural evolution’s creativity in a computer program.
The idea of a creative algorithm might at first seem like a contradiction because our experience with computers is generally that they do only what we tell them to do, which is the exact opposite of creativity. When someone acts mechanically without thinking, we actually might call them a computer or a robot. However, a computer program is at heart just some kind of formal recipe, and there might exist a recipe for creativity. In fact, researchers in the field of evolutionary computation have created many such creative recipes called evolutionary algorithms, which are computer programs inspired by natural evolution, and are often applied to solve engineering problems.
My personal interest lies not so much in solving particular engineering problems as in having an algorithm continually generate an increasing diversity of cool things, some of which may surprise me. This goal is sometimes called open-ended evolution, and contrasts with the more practical focus of many other researchers of making evolutionary algorithms better at solving problems. Of course, both perspectives are interesting in their own right for different reasons.
An algorithm I created with my Ph.D. advisor Ken Stanley, when working towards my dissertation, is called novelty search. Novelty search is inspired by one particular facet of natural evolution, its tendency to accumulate novel forms over time. That is, natural evolution generally tends to spread through niches and becomes more diverse. Inspired by this tendency, the algorithm attempts to explicitly create things that are different from what it’s made in the past. Instead of evolving things that are increasingly better at achieving some predefined goal, which is how evolutionary algorithms are often applied, it evolves things that are novel in some way when compared to previously evolved things. In other words, the algorithm is constantly struggling to innovate.
What’s interesting about the algorithm is that striving towards novelty often produces meaningful results. You might think that if you applied such an undirected algorithm to some problem domain it might just produce an unending parade of useless but perhaps trivially different things. However, producing novelty often requires learning things. For example, we may have more confidence that a pro skateboarder will be better able to invent a truly novel skateboard trick than someone who’s never skateboarded before, because the pro skateboarder has plenty of useful skateboard-related information in his or her brain.
In a similar way, imagine applying novelty search to evolve robots that can navigate through a maze. This is a common sort of task in a field called evolutionary robotics. At first, robots might just crash into walls; and if particular crashes had not yet been encountered by novelty search, they would be rewarded — that’s what the algorithm does, it rewards doing something different without any eye towards practicality. However, to be novel after some time might require learning about how to drive in a straight line and react to walls in the maze. In fact, surprisingly it’s been shown that in some mazes searching for novel robot maze navigators can yield better results than the more direct approach of simply searching for robots better at reaching the end of the maze. A similar result was achieved when evolving biped robots learning to walk. That is, in one experiment, rewarding simulated biped robots that attempted to walk or fall in a novel way proved more effective than rewarding them directly to walk further. And in my favorite experiment so far, a variant of novelty search evolved a wide diversity of lumbering virtual creatures in a single run, perhaps a step towards an algorithm more resembling in outcome natural evolution.
What I find most interesting about these results is that they show the potential of driving algorithms through creativity. Of course, the kind of creativity that novelty search produces is primitive when compared to human creativity or natural evolution. And as you might guess, there remain many open questions and much work to be done to create highly-creative computer programs. But these are the kinds of questions that I love to ponder, and that I am lucky enough to be able to explore as a BEACON post-doc.
For more information about Joel’s work, you can contact him at joel at cs dot utexas dot edu.
