Instructables

Scholarship contest idea: evolving navigation behaviors

I am interested in the evolution of complex navigation strategies. As a first step, I am using the Avida digital evolution platform (http://devolab.cse.msu.edu/software/) to evolve behavior that corresponds to chemotaxis in bacteria such as E. coli.

Although they are very simple organisms, bacteria like E. coli have served as model organisms for studying the molecular biology of behavior, and have been studied extensively. Such simple organisms provide a good starting point for evolving simple behaviors that may eventually serve as a platform for the emergence of more complex behavior. Chemotaxis is a simple orientation behavior, performed by many different organisms, involving moving either toward (positive chemotaxis) or away from (negative chemotaxis) the source of some particular chemical signal, by sensing and responding to the chemical gradient in the local environment.

The project I am proposing for the contest would port the software evolved in Avida onto the Create robot, and demonstrate the virtually evolved capability in the real-world environment. Since performing chemotaxis in air would involve dealing with turbulent dispersal of the chemical signal, I propose to use phototaxis or thermotaxis -- orientation to a light or heat source, respectively -- as an analog to chemotaxis. This will greatly simplify the experiments, since the problem will then be one of diffusion rather than turbulence. The robot will follow the light or heat gradient, tracking toward the source.

Several things will be necessary to accomplish this. In software, the virtual CPU instructions of Avida will have to be translated to the robot. Because of the runtimes for Avida experiments, the evolution would be done offline; the robot would run the program that is the result of evolution. Hardware implementation would include the addition of photosensors or infared sensors, to allow the robot to sense the light or heat gradient. Care will need to be taken, both in the digital evolution and in the robot experiments, to ensure that the real environment is similar enough to the digital environment during evolution, so that the evolved program can function in the real world environment.

Although tactic behavior has been implemented in robots in the past, to my knowledge it has never been done using digital evolution. An evolutionary approach has several advantages: 1) the finished program is discovered through evolution, instead of hand-coded step-by-step; 2) evolution may find novel ways of solving the problem that a programmer might not think of; 3) because of (1) and (2), the evolved solution may be more robust and adaptive than a top-down, engineered solution.

royalestel7 years ago
I've been somewhat interested in evolving algorithms since I read about them several years ago. Using neural networks sounds like a great approach. I am surprised to read you think it will be a small program. My understanding was that artificial neural nets were much slower than the real deal. Would love to see this, though! Good stuff!
Laura Grabowski (author)  royalestel7 years ago
The approach I am using doesn't actually use neural networks (at least not yet -- that may be coming later on). The underlying encoding is a genomic program, essentially an assembly-like code that runs on a virtual CPU. The "digital organisms" evolve their programs according to selection pressures that we can control. This is why the program itself will probably be relatively small. The algorithm I'm hoping the organisms will find is very simple; if I were writing in C, it would probably take a dozen lines or so. Of course, I don't really know what will happen, since evolution may find an unexpected solution (which is all part of the fun). The evolution itself will be done offline, and the robot will then use the evolved program. I have yet to deal with porting the evolved Avida program to the robot, but I still think that it's likely the translated program will fit onto the command module with no additional computational resources. Time will tell!

If you're interested in digital evolution, check out MSU's Devolab. The Avida software is available for free.

Thanks very much for your thoughts!
Well, that makes sense. So you will develop the algorithms by pitting them against a simulated environment and then try the best ones out with the actual robot? And you're welcome.
Laura Grabowski (author)  royalestel7 years ago
Yes, that's the idea. It can be quite interesting: the digital organisms sometimes find solutions that a human programmer would not think of. It is also very interesting to see how very simple algorithms can give quite sophisticated and effective behaviors, just like has happened in nature. And you're welcome, too, for the Devolab link!
By the way, the studies on the Devolab site are very interesting reading . . . thanks for the link!
NachoMahma7 years ago
. I have serious doubts that the Create has enough brain-power to process and/or store the "rules," even if the learning is done off-line. But I'm not very familiar with the Create (and I can't truthfully say I know enough to understand exactly what you're trying to do heehee).
Laura Grabowski (author)  NachoMahma7 years ago
I should think that the actual program will be relatively small, and will certainly not be rule-based at all. This is very simple behavior, and is performed by organisms with no brains at all. Even if space becomes a problem, there are several different options for either adding more on-board computational power or wireless connection to a computer (which would not be my first choice, since I would prefer an autonomous system).
. Well, if it can be done, you sound like you can do it. . The first computer I used (1972) had the old donut core memory (4K, IIRC), paper tape, and Hollerith cards (the only "monitor" was some blinky lights and the line printer) and I keep forgetting just how much power even "toys" have nowadays. LOL
I HATED paper tape. I used to handle rolls like 12 inches in diameter! The worst! I'm not sure I understand everything, maybe half, ok 1/10 of your proposal, but, are you talking AI type stuff? Cause Mousey the Junkbot does light avoidance/following just with the hardware. You can find the Junkbot on MAKE: and amazon.
Laura Grabowski (author)  SacTownSue7 years ago
Yes, this definitely could be considered AI. The behavior I'm talking about is not new in robots -- it has been done before in many ways -- it's the approach. The project would in some ways be a proof of concept. My eventual aim (although probably not by Aug. 31) would be to evolve more capabilities in addition to this one, with complex capabilities emerging from the simpler ones (I hope).
. Geez! Where do the young chicks hang out? ROFL
Laura Grabowski (author)  NachoMahma7 years ago
:) I did my first programming in FORTRAN with punch cards, so I know what you mean! Thanks for the feedback.
Kira_Koenig7 years ago
Well, I intend on using a low power, mini itx board, with like a 4gb flash drive. So if the program (if complete and is "plug/play" or close to it) is not larger than a few megs and stores the information (code) in the smallest possible form i.e kilobytes. Then I think it is plausible.
Kira_Koenig7 years ago
That is very interesting concept and would make programing less stressful. This concept may very well help me out with a few of my navigating / tracking problems. Like teaching it to track the moving heat source (a burglar) and not letting them go about in the house as they please. Man technology keeps getting better and better. Thanks, :D