Close
0%
0%

IQ Zero: Evolving Unprogrammed Robots

Clueless, broken robots thrive on Genetic Algorithms and Procedural Generation

Similar projects worth following
Exploring the intersection of Genetic Algorithms, Robotics and Procedural Generation, "Zero" is a robotic corollary of "General" AI. Instead of explicit instructions, productive behavior emerges from "random noise" by modeling Random Mutation and (Artificial) Natural Selection. Generous "genetic source material" is provided at minimal computational expense via run-time procedural generation techniques.

A diagram:
https://drive.google.com/open?id=0BxQ9XXT1zzMjX0dKS3luVl9STTg

Functional prototypes are running on the ATTiny85 in Arduino C, but I'm excited about the possibility of moving to the tiny PI Zero.

A video:
https://youtu.be/EIT9XGVJMeY
Descriptive, timelapse:
https://youtu.be/JnnouA6F_nM

See Details and Log fo

A Perfectly Stupid Robot

Okay so what do I mean this is a stupid robot? Glad you asked, here we go!

Imagine a traditional robot program, maybe something like:

Drive forward
If Light Sensor Left Turn Left
if Light Sensor Right Turn Right
Repeat

The instructions are pretty specific, and require the bot to know a lot about itself: How to operate the its motors to drive, how to read a light sensor, etc. It has to know what's connected to it, and how to use it correctly.

In contrast, Zero doesn't know nothin'. It has no idea what's attached to it, or how to operate those things. And it doesn't have any specific instructions at all. That sounds bizarre but this will start to make sense soon.

Here's is what one of its programs might look like as pseudocode:

Read from In Pin to In Register
Do nothing next, if Out Register greater than In Register
Increment Out Register by your age in ms
Add the value of In Register to Out Register
Write the value of Out Register to Out Pin

What could such formless nonsense even do? Well, that depends.

First clumsy steps of a young GA: Early Generations in "Box3"

Vegas is Easy

If the instructions ran when "In Pin" happened to be connected to a light sensor and "Out Register" (by sheer luck) held the previous value of the sensor...and the sum of the robot's age and sensor reading were a value appropriate for sending to a servo...and (again by luck) a servo was attached to "Out Pin"...

Then that servo would move in response to some sort of light stimulus.

That is a lot of sheer luck! Flipping 8 coins and getting all heads kind of luck. You'd have to flip them like, a billion times, right?

Let's do the math: The number of possibilities with one coin is 2^1 = 2 (heads and tails, one coin). So with 8 coins there are 2^8 = 256 possibilities - only one of which is all heads.

So if you flip 8 coins 256 times, you're almost certain to get all heads at least once. If not, then at least by your 512th flip. Unless something is very wrong with your coins, or your universe.

256 coin flips will take you a long time, but these days a $2 microprocessor on two on AA's can do about 16 million per second.

Getting lucky is pretty easy when you flip coins that fast.


50 generations later, IQ Zero sports some mad dribbling skills

Engineering with Chaos

But that can't work - throwing a bunch of dice in the air and simply hoping they fall in just the right way to make something useful?

You are absolutely correct: The first throw of the dice will probably produce nothing useful.

But Evolution isn't just random - its other engine is natural selection.

Once the GA has lived its life (its "fitness test"), it is scored on how well it performed. In the prototype, that is how many times it triggered a motion detector (its "fitness function").

Only the combination of random dice which performed best is chosen as the winner. Several copies of the winner are made, but each slightly changed by a random mutation in its DNA.

Repeat this process over and over and (tada) - Evolution on the ATTiny85.

Invisible Programming

What did I mean by "this is what its program might look like?" Don't I know?

No, I don't - I've never seen one of its programs. It would be almost impossible to interpret anyways.

Zero's "DNA" - most of which becomes its program - is a very long list of "random" data.

I've put random in scare quotes for those who know no such thing exists - certainly not in digital computers. No matter how you work it, everything digital is completely deterministic.

To generate a random value, most platforms require some sort of "seed" value for their PRNG (Pseudo Random Number Generator). The PRNG uses this seed and some weird formula to generate a long list of numbers that you would have have difficulty predicting.

But given the same seed, that formula will generate the same list of "random" numbers, in the same order, every time. Of course that's not random.

This can be real problem for applications that need random data, but for Procedural Generation techniques it...

Read more »

iqzero_bb.png

Simple example circuit. Again, "Zero" is intended to operate with no info about its construction, so the circuit is sort of irrelevant - but this is one example application.

Portable Network Graphics (PNG) - 175.84 kB - 02/24/2016 at 17:22

Preview
Download

  • 1 × Atmel ATTiny85 Arbitrates evolution and operates Zero's hardware on behalf of the GA
  • 1 × L.E.D. Simplistic system status only.
  • 1 × Any kind of sensor Type, operation or connection points irrelevant
  • 1 × Any kind of motors A good GA can work with whatever it inherits from its parents.
  • 1 × 3 to 6 volt power supply Or solar?

View all 6 components

  • OMG Finally an Update!

    Die, Master Monkey!12/20/2016 at 08:20 0 comments

    During a test run of some new code, I give a long update on this thing and it is - I think - an interesting story. For some reason it's on my other YouTube channel. Sorry about the reverb.

    Latest: I should be posting new, civilized code soon that - as always - won't care what kind of peripherals it has. And Happy Holidays Everyone!

  • IQ Zero Box 8 Run w/Timelapse

    Die, Master Monkey!03/16/2016 at 00:55 0 comments

    This run with the latest (ATTiny) version is a good illustration of the GA technique as it's applied in this project. Again the bot is scored on how well it stimulates the Passive Infrared Sensor (PIR) - usually by jostling the ball as much as possible. And as before, the values for its operations are pulled directly from the seed-controlled PRNG.

    More discussion after the vid.

    The clip fast-forwards through 35+ generations, and in that time the bot goes from using all of its servos all of the time to what appears to be a more efficient locomotive pattern that often bounces the ball violently.

    A few factors play into what behavior scores best:

    • PIR: Any motion sensed by the PIR will score 10 points per instruction cycle. A single event may trigger for up to 4 seconds.
    • Servo Cost: Each time output is sent to servos, a 2 point penalty is given.
    • Time: Each GA has only 4 seconds, so inaction is the most costly of all.

    Importantly, the GA does not approach some sort of "perfection" and stay there: It continues to mutate, constantly. This - again - is what excites me so much about these techniques: These kinds of robots could adjust constantly to changing demands, or opportunities.

    There is considerable work to be done still - I'm currently focusing on the following:

    • More stable convergence - Do a better job of identifying and keeping the positive aspects of successful GAs
    • More GA self-influence - They currently have surprisingly little control over their own code morphology. I'm expanding that.
    • More fitness tests - I score motion now because I can't score distance, altitude or light. The next item will help add more test sensors!
    • PI Zero Transition - I'm ironing-out a plan to put the Adafruit Contest's PI Zero in charge of a herd of "traditional" IQ Zeros. Clever angle, no?

    Stay tuuuuuuuunnnnnned!


  • Bot in "Box Arena"

    Die, Master Monkey!03/10/2016 at 22:09 0 comments

    Some better pics of the "Box Arena", where Zero is tasked with figuring-out how to stimulate the Passive Infrared Sensor by operating servos attached to the bottom of the box. See video of this in operation in an earlier post.

  • Bits Bots Beats - IQZero: Trash, Chaos and Computation

    Die, Master Monkey!03/04/2016 at 03:38 0 comments

    The project figured strongly in the latest episode of Twitch geek-and-beat-sesh "Bits Bots Beats" (Wednesdays 6pm GMT-8).

    Topics included:

    • Borrowing computer time
    • Is random always trash?
    • Is trash always useless?
    • Are useful things always designed?
    • Beats by RVNEZ

    Incidentally, a big update is in the works with a completely different model - stay tuned. Thanks for checking it out so far!

  • IQ Zero "Arm" Test

    Die, Master Monkey!03/01/2016 at 02:31 0 comments

    This Robot is "Armed"

    Yes, I still have to finish explaining the other half of The Big Diagram, but I wanted to share this quick dispatch from the lab. Forgive me also for typos and such, because (hey admins!) it is extremely difficult to edit articles here. Moving on...

    In this test, Zero is placed in charge of a crude two-servo armature and - again - scored on how often (and how efficiently) it stimulates the Passive Infrared Motion Detector. The "PIR" is partly obscured, forcing the Genetic Algorithm to discover a small range of effective motion.

    Here is an example of its performance within the first minute or so:

    It doesn't really succeed in triggering the sensor much, and spends much of its time outside the PIR's field of vision.

    A few dozen generations later, it's considerably more effective and seems to be generating "GAs" that at least focus their motion to the useful area.

    It's hard to be sure, but it might even be responding to sensor event by "bouncing" back to a clockwise extreme, then slowly creeping back toward the sensor.

    This is possible because some of the "commands" which can result from interpretation of its pseudo-random DNA can read like this:

    1. Read value of from InPin to InReg
    2. Skip next instruction if InReg > OutReg
    3. Write value of OutReg to OutPin

    Consider the following scenario, in effect at the time these instructions were executed:

    • InPin is attached to the PIR
    • OutReg is zero
    • OutPin is attached to the arm servo

    If this were the case, a zero would be sent to the servo if the value read from the PIR sensor were higher than zero. Zero degrees, being outside the range of the servo, would push the arm all the way clockwise.

    Conversely, if the PIR returned nothing (zero), InReg would not be greater than OutReg, and Step 3 would be skipped. No servo action would result.

    Actually this background is going to be useful in...

    Next Up: Chaos from Code Part II - Time, PRNGs and Fake Languages

  • Turning Chaos Into Code

    Die, Master Monkey!02/27/2016 at 21:14 0 comments

    Flattening Evolution

    Yay, finally a diagram! Opening it in a new window might make the following discussion easier. I'm going to start with the left-side, a simplified workflow of Zero's version of evolution.


    Firstly, let me disclaim that the Evolutionary model used in this project is simplistic in the extreme. That's mostly by design: It's on an ATTiny85, and that certainly demands we make the most of limited resources. More importantly, this is not a simulation of biological Evolution for research purposes but rather an emulation of only those mechanisms of Evolution which I deem conducive to emergent, productive behavior in a hardware control program (i.e. robot).

    In the diagram, think of the shapes as representing different forms Zero's program might take: Say, a rounded surface represents a sequence of code that increments one of its registers, and the blue-ness of a shape represents its likelyhood of that register being used as an analog output. Other colors and shapes represent other facets - and we'll get to where those come from in a bit.

    Imagine also that the number of shapes represent the complexity of the program. For instance, the pseudocode for one of the Generation 0 might be:

    Read From InPin to InReg
    Increment OutReg
    Repeat

    That's a very simple (and probably not very productive) program. If we checked its sibling we'd find something slightly different (we'll get to mutation, hold on). Something like:

    Read From OutPin to InReg
    Increment OutReg
    Repeat

    There's only one tiny difference (in bold), but there can also be several - or none. But siblings of one generation will tend to be very similar because they're all derived from the same (parent) DNA.

    Nature's a Playa

    I say siblings tend to be similar because mutations can have consequences to an organism that are benign, subtle or profound - depending on where the mutation occurs in the DNA and how that gene is expressed. Sheesh, is this helping explain anything? Okay, let's take another hypothetical Generaion 0 sibling:

    Read From OutPin to InReg
    Increment OutReg
    Increment OutReg

    Okay, this one too is "slightly different" - again only one line was mutated. It's harmless that "OutReg" is incremented again, as the program does nothing with it anyways. However, the replacement of "Repeat" (with anything else) will prove disastrous and this sibling will have the shortest robotic lifetime ever - a single execution.

    So while the diagram "fast forwards" through generations, but that doesn't mean only "time" can introduce big changes to an genetic line. Major changes to any part can happen suddenly through several mechanisms, just of one of which is illustrated above.

    In our particular implementation, the "seed" value provided to the PRNG is a crucial part of the DNA, but it is also subject to mutation: Since the PRNG generates all instructions for its program, the slightest change to it drastically alters the resulting offspring.

    If it seems to you that there is a high chance that mutations will result in unproductive behavior (i.e. "dead babies"), then you are paying attention and get a cookie! You are correct - and dying is not good performance. So those genes are not selected to go on to the next generation.

    That sounds a lot like two steps forward, one step back. Maybe two steps back, sometimes!

    It is - but Nature is also waiter. Not like "try the wine" but like - well you get it.

    And while time is the limiting factor in this process, time in Evolution is not time in the way watches measure it.

    {Sheesh, that's a lot for ya'all to read at once - I think I'd better pick this up in the next post, where I'll explain wth I mean time is not time that's crazy talk. Thanks for tuning in!}

  • IQ Zero in "Box3" Arena

    Die, Master Monkey!02/24/2016 at 19:51 0 comments

    Bot Versus Ball in Box of Doom

    Okay so there's no doom, but that's a catchy title, no? Placed in charge of bouncing a box with a ball in it to stimulate a motion detector, "Zero" quickly discovers a quite optimal technique requiring minimal motion, and doing quite a good job of letting gravity do much of its work!

    This is precisely the same code as in any other "Zero" - it has no idea what it's doing, only that when it happens to use this random seed with these combinations of values in the body it currently inhabits, it is often fed. It likes being fed, and it likes passing on its genes to future generations.

    "And that's all Skynet really was, son."

    Hmm, did I say there was no doom in this post?

    Yes I know, where's the diagram, on the way boss! :)

  • Zero Invents "Wheel Rowing"

    Die, Master Monkey!02/24/2016 at 19:04 0 comments

    Yeah I said the next post would be about the translation from PRNG-generated integer streams into actionable instructions for a Genetic Algorithm - but first, a video! Strapped-onto a toy car and left for a few hours, "Zero" seems to have invented a clever - if not particularly exciting - method of "rowing" one of the car's wheels, nudging it a few inches each time.

    Come to think of it, it's solution is pretty efficient, from an energy expenditure perspective.

    Understand that if we ran it again (and I have), it will come up with different solutions. And if that wheel broke it would figure something else out. That's why I'm so hot for this stuff - imagine, machines to which we can finally say "you're the expensive computer - you figure it out!" :)

    Right, so how does a glob of instructionspace DNA become a new way to push a wheel? Yes, I promised, okay next post but - with a diagram so - worth the wait. Here's a sneak peek:


  • Robot Cars and Robot Bikers

    Die, Master Monkey!02/24/2016 at 07:36 1 comment

    Hilariously, YouTube "related" one of my uploads about "IQ Zero" to this talk from Ben Goertzel (whom I've met, he's a cool cat) about Artificial (rather, Algorithmic) General Intelligence. His example about a car-driving program in a motorcycle perfectly illustrates what this project is about.

    (Omg you can just paste vids here?)

    So this is why the "components" list is empty, except for an Arduino-C compatible processor: The entire point of this project is to be able to plug IQ Zero into whatever - and have it just figure out how to make itself useful.

    PS I'm totally gonna' be posting video updates in these log things then, cause you don't get a description on links.

  • Hello Hackaday

    Die, Master Monkey!02/24/2016 at 07:03 0 comments

    Initial Post on IQ Zero Project

    I don't usually use project sites like this - guess I'm Old School already. But I wanted to enter the Adafruit PI Zero Contest so here I am!

    Actually "Zero" is one of many Genetic Algorithm projects I've got going - the continuation of my 10-plus-year experimentation in Evolution Computing. I wasn't originally planning on using it for the contest - my larger project "Internet Toybox" seemed the obvious choice.

    But I've been b struggling with some of the limitations of the (self-imposed) ATTiny85 platform I've been using for "IQ Zero". GA's don't technically require much processing power - and shouldn't if done right, in my opinion.

    But the limited runtime memory (which did lead to a brilliant innovation leveraging Procedural Generation) and slow random number generation at 16mhz has caused me to seriously consider adding an internal simulation phase to the system.

    Some quick background: Genetic Algorithms are traditionally explored, for the purposes of physical "organisms", in simulation. "Breve Creature Simulator" for example, with which I started, uses a physics-simulated 3D environment.

    But not every single moment of GA evolution is rendered - that would slow the simulation to "real time"! Instead, only the math is performed for most generations, and then - once in a while - a generation is rendered on screen.

    IQ Zero isn't a simulated organism - it's a real-world robot! To test 300 generations takes - well, 300 generations. To make this feasible, I've limited myself to goals ("fitness tests") which could be achieved by a fairly simple means - allowing me to give each individual "Zero" a fairly short life - 20 to 30 seconds, for instance.

    I can already see I'll want more complex behaviors: Longer, slower, more delicate motions and more awareness of the state of the environment. One way is to wait overnight.

    But another is a 1 GHZ processor on a board light enough to be carried by a 5-volt robot with no knowledge of its own arms and legs.

    So wish me luck on the PI Zero contest, and stay tuned for all the code, diagrams, docs and vids you can handle. Thanks for tuning in!

View all 10 project logs

  • 1
    Step 1

    Gather Ingredients

    • 1 x Microcontroller: Atmel ATTiny85, Arduino or compatible
    • 1 x Power Supply: Appropriate for controller (or USB power)
    • 1 x AVR Programmer (for ATTiny) or equivalent
    • One or more organs for your robot (See Note)
      • Servos, DC motors, actuators
      • Light sensors, motion sensors, sound sensors
      • Contact switches, capacitance sensors
      • Whatever you dream up!
    • Breadboard, perf board and appropriate hookup wires

    Special Beta Note: A PIR is Required for Expected Behavior

  • 2
    Step 2

    Load IQ Zero onto Controller

    Use your programmer to flash the latest version of IQ Zero to your microcontroller.

    Note: At the time of this writing, only the pins 0 through 4 and A1 through A3 will be accessible to the Genetic Algorithm.

    That will be more flexible, soon.

  • 3
    Step 3

    Connect Your Robot Circuit

    This is all up to you. As long as your connect the power and ground pins to your components properly, you can connect any sort of signal pins to any signal pins on the controller.

    Honestly it doesn't matter because if the component in question were on another pin, it just would find it eventually anyways.

    You may want to test your circuit with some simple code first, just to make sure it all works. Debugging a Genetic Algorithm is not for the weak of heart.

View all 5 instructions

Enjoy this project?

Share

Discussions

jacksonliam wrote 03/18/2016 at 19:05 point

This is really cool! Great writeups! 

I've been thinking about making some solar robots that hunt for light and avoid predators like the cat. 

I've wondered how to do things like "I have some light, I've previously had more, should I stay here or waste energy hunting for more light". Or "I'm getting a lot of light but getting attacked all the time, should I try to move somewhere I'll get attacked less?". 

And what patterns to move in (straight lines, random turns) etc. 

This sounds like it would be a great starting point for that and I'm following closely! 

  Are you sure? yes | no

Similar Projects

Does this project spark your interest?

Become a member to follow this project and never miss any updates