Bayesian Classifier Answers the Question: "Is it art?"

The title is a joke, by the way. Although I would be interested to see what the results of such an exercise would be. "Statue of David... *beep*: ART!", "Justin Beiber's Music... *beep* NOT_ART!".

Almost as exciting as my 0-R Spam filter. Catches 100% of spam with a 97% accuracy rate! Oh mercy.

The reason that I mention Bayesian Classifiers is because I wanted to talk about machine learning. This is the other branch of artificial intelligence and what most people think of when the topic of Skynet is brought up.

Fear not though. Bayes rule, decision trees and rule based learning are actually pretty mild. They are simply statistical methods of attempting to classify data by using the results of previous observations. Mostly harmless.

However, today I'm going to talk about genetic algorithms.

A genetic algorithm is an abstract representation of a mathematical function. They can take many forms, such as a string of bits which might indicate the presence/absence of a set of inputs, or a literal mathematical function "y = cos(x) - 2*z". The range of variables which is represented by the function is called a genome.

This can get a bit hard to visualize, so I often just settle for imagining genomes as Taylor polynomials. Therefore, a single genome consists of "x = A*input1^a + B*input2^b ..." where the values of A and a can take any real number. If some of the inputs are simply a higher derivatives of other inputs, then any arbitrary function can be represented in this way. There is also a rather nice representation involving trees.

If we start off with a population of individuals with random valued variables in their genomes, then we can evaluate each function to see how well it 'fits' a set of training data. The individuals which produce the minimum mean squared error for the training data are declared the 'fittest', and are allowed to survive into the next generation.

This is where the 'genetic' part comes in. There are many ways of 'evolving', 'mutating' and 'breeding' individuals, but the easiest to understand is the asexual method. This means that all individuals except the best performer are killed off (ie, deleted) and then their places are taken by the offspring of the remaining individual. However, tiny random 'mutations' are introduced to each of the new individuals variables - such as doubling/halving the values of A or B, or incrementing/decrementing a or b.

Anyway, thats the 30 second version of genetic algorithms. They can be used to find a semi-optimal solution to many problems, provided you can throw enough generations at them. I have been working with a C++ implementation called GAlib. If you are interested, I highly recommend going through the examples.

Now, some of you may be wondering what all this has to do with robots (actually, most of you are probably already filling in the blanks and peeing your pants in terror).

I've spoken on several occasions about using Robobob as a platform to investigate dynamic balance and movement. I plan to represent the control state of the robot as a search tree, with the robot beginning at a starting node/state and attempting to plan a path of control actions to reach a goal node/state. To navigate the tree, I want to implement a greedy search heuristic which will choose which control actions are most likely to lead to the goal state.

Now here's the tricky part - I intend to implement the heuristic as an evolutionary algorithm which can then be rewarded or punished depending on the outcome of executing the control path on the real robot. ie, if the heuristic gets stuck or can't find the goal state, it will be disfavored whereas successfully reaching the goal will be favored. After a series of generations, I will be able to study the path planning method which has evolved from this process.

Cool? I hope so.

Terrifying? Definitely.

Robobob: Life of the party

Dancing robots have been around for some time now, I'll give you that. Generally they are simply scripted lists of moves which are synchronized (or not) to a particular song. It took some hard work, but I've managed to take a different approach:



This dance isn't scripted! It's being generated based on the music being played, which means that Robobob will dance in time with any music you care to play to him!

Well, most music. The tempo is detected using a Fast Fourier Transform, which can separate beats and bass-lines from the rest of the music. This works great for songs with a strong bass component, but doesn't work so well on music composed of higher frequencies or vocals.

Simply place your robobuilder on the nearest sub woofer though, and you should be in business!

Watch in amazement as your robotic buddy dances along (almost) in time to the beat!

Impress your friends with his funky dancing styles consisting of over TWO distinct moves!

Computers 103

The gnome is back! This time, he has a very important message for you about registers. Please give him your undivided attention, or there may be consequences. 0_o

I hope you are enjoying these comics. I will be making more of them, but I am also working on upgrading Robobob. I think you will be pleasantly surprised, so check back soon!

Computers 102

For your amenity, the next installment of "inside your CPU" is avaliable below. If your screen is big enough, you shouldn't even need to scroll. The previous issue can be even be found here. Convenience!!

(If you don't get the joke in the last panel, it is because the "take one down" action will eventually set the zero flag in the status register, but the "pass it around" line will never set the zero flag. The branch instruction can only know about the results of the operation immediately before it, so the gnome will eventually die of alcohol poisoning. THINK OF THE GNOMES!)

In other exciting news, the source code I used to make this video is now avaliable. You can find it here. There are a few improvements and bug fixes.

Computers 101

I'm taking a little hiatus from the epic how to build your own robot series for a few reasons.

Firstly, there is a LOT to cover. I'm writing this as a sort of trial run for how I might explain it to first year university students, and as we all know - firsties are only marginally more intelligent than the rats they experiment on. With so many topics to cover, I'm faced with either giving 10 second "just take my word for it" style advice, or deviating from the topic every paragraph to explain the reasoning behind the statements I've just made.

The other problem is that it isn't fun to read. It's very technically dense and wordy, and I feel that if I can't hold the reader's interest then there isn't much point in me spending all this time explaining it. After writing the how to choose servos article, I really felt that I should have introduced it with an earlier article about exactly how they worked and what they were used for.

So to remedy this, I've decided to take a different approach to the rest of the series. Before I start spouting off about software and microcontrollers and interrupts, I'm going to give you some background on the subject in general – just so that everyone is up to speed when I use terms like instruction set, word size or stack overflow.

What's more, to keep things interesting the lessons will take place in funky 8-bit comic style! Enjoy!

It's not a bug, it's a feature

Mystery solved!

Here is a quote from the avrlibc documentation (which I probably should have looked at earlier):

In order for these functions to work as intended, compiler optimizations must be enabled, and the delay time must be an expression that is a known constant at compile-time. If these requirements are not met, the resulting delay will be much longer (and basically unpredictable), and applications that otherwise do not use floating-point calculations will experience severe code bloat by the floating-point library routines linked into the application.

This describes exactly the symptoms I was experiencing - if the function was passed a constant, it worked flawlessly. If I was using a value fetched from program memory, then the compiler was unable to determine how many NOPs should be performed and the delay was unpredictable.

I don't really know why the library function requires prior knowledge of how long a delay should last. All a spin loop does is keep the processor busy for a set number of cycles. If you need longer, you can simply put another loop around the first loop to multiply it's effects. Sure, without careful calculations you can lose your nanosecond accuracy, but when you are working in the millisecond range it is usually unimportant if you are off by a few clock cycles.

If you want the best accuracy, you should be using a timer or counter interrupt anyway...

..but that's a story for another night. I don't intend to be using spin loops for future versions anyway.

Thanks to the people who emailed me and suggested that I might be accidentally passing the value of the pointer to the function, instead of the dereferenced value. That would also explain the strange behaviour, but it would also have shown up in the compiler output.

In other news - what's up with the horrible popup?

If you don't live in Australia (or perhaps even if you do) you might be unaware that the Australian government is considering introducing mandatory filtering of internet sites.

Much like draconian airport security, national identity cards and racial profiling, this filter is supposed to be being put in place for our "protection". Because apparently Australians can't be trusted with unregulated free speech and freedom of information.

I understand that some people are willing to sacrifice their personal liberties for the comforting feeling of saftey, but the problem is not with the filter as it exists now, but what it could become.

First they came for the communists, and I did not speak out—because I was not a communist;
Then they came for the trade unionists, and I did not speak out—because I was not a trade unionist;
Then they came for the Jews, and I did not speak out—because I was not a Jew;
Then they came for me—and there was no one left to speak out.

Bear necessities

I was recently stumbl'dupon - which was appreciated. I'm glad to know that people out there are finding my work useful.

Along with the increased traffic came several requests for the source code for some of my more interesting achievements.

I am, of course, more than happy to provide it - you may have noticed that source code is one of those things which I often promise but seldom deliver.

However, there is a good reason for my apparent reluctance to upload my work as of late, and it can be fairly accurately summarised in two words: self confidence.

For some reason, programmers have an ingrained tendency to look at any code written by someone other than themselves and immediately write it off as garbage.

In some cases, this is probably just good old fashioned hubris. But my current working theory is that in programming there are so many levels of mastery and so many potential solutions to any problem. Code using paradigms which are advanced and unfamiliar seem needlessly complicated, while basic (but probably equally effective) methods of performing a task are often written off as trivial and inelegant.

So I tried to be understanding. Sure, I might not have done it that particular way myself, but with a positive mindset I could see the logic behind most of the design decisions.

But try as I might, I kept having to resort to ugly hacks to get the code to do what I wanted while still maintaining it's original functionality. After awhile, I had to sacrifice the default behaviour altogether. Eventually, I found myself rewriting huge sections of code in order to make even the most basic functions work reliably. But I figured that I had come this far with the official code, and it would just take me too long to find an alternative.

Until I saw this:

ISR(TIMER1_OVF_vect) 
{
    if( gFrameIdx == gNumOfFrame )
{   // are we at the end of the scene ?
           gFrameIdx = 0;
        RUN_LED1_OFF;
        F_PLAYING=0;                        // clear F_PLAYING state
        TIMSK &= 0xfb;                      // Timer1 Overflow Interrupt disable
        TCCR1B=0x00;
        return;
    }
    TCNT1=TxInterval;
    TIFR |= 0x04;                            // restart timer
    TIMSK |= 0x04;                            // Timer1 Overflow Interrupt enable
    MakeFrame();                            // build the wCK frame
    SendFrame();                            // send the wCK frame
}

void MakeFrame(void)
{
    while(gTx0Cnt);            // wait until the transmit buffer is empty
    gFrameIdx++;            // next frame
    SyncPosSend();            // build new frame
}


//------------------------------------------------------------------------------
// Start sending the frame
//------------------------------------------------------------------------------
void SendFrame(void)
{
    if(gTx0Cnt==0)    return;    // return if no frame to send
    gTx0BufIdx++;
    sciTx0Data(gTx0Buf[gTx0BufIdx-1]);        // send first byte to start frame send
}

void SyncPosSend(void) 
{
    int lwtmp;
    BYTE CheckSum; 
    BYTE i, tmp, Data;

    Data = (Scene.wCK[0].Torq<<5) | 31; // get the torque for the scene

    gTx0Buf[gTx0Cnt]=HEADER;
    gTx0Cnt++;       

    gTx0Buf[gTx0Cnt]=Data;
    gTx0Cnt++;       

    gTx0Buf[gTx0Cnt]=16;  // This is the (last ID - 1) why is it hardcoded ?
    gTx0Cnt++;       

    CheckSum = 0;
    for(i=0;i
        if(Scene.wCK[i].Exist){    // if wCK exists add the interpolation step
            lwtmp = (int)Scene.wCK[i].SPos + (int)((float)gFrameIdx*gUnitD[i]);
            if(lwtmp>254)        lwtmp = 254; // bound result 1 to 254
            else if(lwtmp<1)    lwtmp = 1;
            tmp = (BYTE)lwtmp;
            gTx0Buf[gTx0Cnt] = tmp;
            gTx0Cnt++;            // put into transmit buffer
            CheckSum = CheckSum^tmp;
        }
    }
    CheckSum = CheckSum & 0x7f;

    gTx0Buf[gTx0Cnt]=CheckSum;
    gTx0Cnt++;            // put into transmit buffer
} 

That was probably a bit on the long side. But here's a quick tip for programmers working on embedded systems - if it's too long to post on your blog, it's too long to put in AN INTERRUPT!

Interrupts need to be short. When an interrupt fires, everything else is put on hold until the RETI (return from interrupt) instruction is performed. If your code spends too long in an interrupt, you risk missing other important events such as sending instructions to servos, receiving serial transmissions, or responding to any other interrupt.

What's worse: since all these events have been put on hold when the RETI instruction actually is received, all these issues now have to be dealt with at once. It's not easy to predict what order they will be handled in either. This can lead to unpredictable behaviour which is very hard to debug.

So to summarise: bloated interrupts = bad.

To return to my original point, I had been doing some very dodgy things in order to just get the darn thing to work. Things like arbitrary delays in the middle of functions (to make sure that whatever interrupt was expected had time to get itself sorted out), and lots of polling to ensure that the state of the program was predictable before I went and altered the global variables (of which there were many). Plus a not insignificant amount of arcane deep magic.

Not the sort of work I wanted to put my name on.

All that stuff I said about respecting other people's code remains valid, but only if it's actually doing what it is supposed to. So after a short meditation, I realised something very important: I didn't need all this stuff. 

I had a very specific goal in mind, and 90% of the code I was having to circumvent was simply getting in the way. I only needed a few basic functions to achieve what I needed to do - and at this stage I was spending far too much time patching things up instead of fixing the problem at the source.

With this in mind, I've begun working on a very simple library of functions which will deal with the simple, low level things that I am trying to achieve - without all the non-essential tasks getting in the way. With any luck, I will be able to make far more frequent source code updates now, since the releases will be far more minimalist and focused on a specific task - instead of trying to be a replacement for the default firmware.

Until next time - keep it simple.

One step at a time

Happy New Year Everyone!!

I'm back from a short holiday down to the Melbourne Cricket Ground to watch the Boxing Day test. It was very relaxing, but now that I have returned I have lots of robot news to share!

Firstly, despite being unable to find wCK gears anywhere in the southern hemisphere, I have sort of fixed the broken knee servo. Thanks to an emergency surgical field graft, he can now walk fairly normally but has lost the use of his right arm. Apparently I'm not the only person who is having problems with the plastic gears. If you are concerned about damaging your own servos, I suggest you set them to the lowest torque setting. Note that 4 is the LOWEST torque setting, and 0 is the HIGHEST - the manual could probably be more forthcoming on this point.

Now that he's up and mobile again, I've resumed work on getting him to keep his balance while standing.

Whenever I start work on an ambitious project, I find that the only way to keep on track is set myself small targets along the way. I am always coming up with ideas that are easy enough to design, but take far longer to implement - and more than a few of them have fallen by the wayside because my eyes were bigger than my stomach.

So having small, short term achievements keeps me motivated to move on with the long term goal. A very simple method of controlling complex systems (particularly when computing power is limited) is called discrete state-space control. Rather than trying to model the system and predict how it will behave, the system is manually broken down into a discrete set of inputs and outputs. Then, using some very basic rules, the behaviour of the system can be described in very simple terms like: if A, then B.

In the case of the robot trying to maintain it's upright position, you can simplify things by firstly holding most of the joints rigid. Using the feedback information from the ankle servos (04 and 00), you can predict if the robot is tilting too far to the left or right. Then, depending on which state the robot is in, it can take the appropriate action to regain it's balance. Simple, no?



In the video, you can see the robot measuring the angular velocity of it's ankles, and detecting when it's balance is being compromised. It simply steps away from the force to maintain it's stability - just like a human would.

Right now, it only work for left and right - simply because the canned robobuilder animations for forwards and backwards consist of several steps, meaning I will have to write my own motions.

I should probably start putting together my own library of poses anyway, since I'm not too happy with the default ones. The walking and turning motions have a real problem on many surfaces - polished wooden floors are the best so far, but far from perfect.



Here you can see that the robot is having problems moving in the right direction with the stock SidewalkRight/Left actions, to the extend that he goes the wrong way! Because he was off centre to begin with, one foot is carrying most of his weight, so he pushes against the ground and towards my hand.

Code will be available soon, once I've cleaned it up a little and found a nice place to upload it. I think that robosavvy has personal file space for it's members, so I will see if I can make the files public.

If I only had a brain

As promised, I have made some changes to the robobuilder source files so that movement commands execute properly.

The problem seemed to be that the wCK transmit interrupt was being disabled prematurely, before all of the instructions could be sent. General defensive programming practice on behalf of the designers meant that any function which placed commands into the transmit buffer intentionally waited patiently until the buffer was empty. This avoided accidentally fragmenting the instructions due to the limited size of the buffer, but meant that the program would just freeze up if (for whatever reason) the transmissions were not being sent.

With a little debugging, I identified the MakeFrame() function as the culprit, which was causing the program to get stuck waiting for the transmit queue to clear, but since the interrupt was disabled it stayed in an infinite loop. Simply placing a few lines inside the while loop making sure that the interrupts were enabled fixed the problem.

I also made a few other aesthetic changes - mostly making things more readable by replacing "magic numbers" with the names of registers. For the uninitiated, A |= (1<<X) means 'set' bit X in register A, while A &= ~(1<<X) will 'clear' the bit. The header file iom128.h in avr-libc contains the names of all the registers.

Overall, the code here is a very good starting point if you want to start messing around with your robobuilder's brain. However, the functions do a LOT of polling, which should be replaced with interrupt based timing control if you plan to implement more complicated functions.

The files can be found here. I apologise for the horrible free hosting service. Be sure you click on the "Free" tab before you hit download.

My next goal is to figure out how the recharging procedure works, and give the robot some sort of power management routine. Perhaps eventually he will be able to detect when his batteries are dying and go recharge himself.

Debugging robots for fun and profit

More astute readers who followed the procedure in my last post may have noticed that it didn't actually work.

That's not to say that the instructions were wrong - those are still the steps to build the robobuilder C source files and upload them to the RBC. The problem was that the code which I linked doesn't actually do what it says on the side of the box, so to speak.

The execution of the code posted on the robosavvy forum (which is primarily an english adaptation of the official code) should result in the robot performing the RIGHTPUNCH action when the PF1 button is pressed. However, when the files are built and installed on the robot, no amount of button pressing will elicit a response from the robot.

I'm working on producing an updated version of the code which is nice and flexible, which I will upload here when I'm satisfied with it. In the meantime, for those of you playing along at home, I thought I would share a quick debugging procedure known only to a secluded group of embedded systems programmers.

There are on-chip debuggers available for the AVR family of microcontrollers, however I don't have one. There are also situations when the debugger causes more problems than it solves - ie, by hogging certain pins on the board, or restricting the flow of real-time interrupts. The poor mans solution to this is to set up a quick method of stepping through your program and seeing where it gets to and where it gets stuck. The easiest way of allowing your program to communicate back to you is using the onboard LEDs.

#include "macro.h"
#include "main.h"

WORD gDebugMode = 1;

void Debug(BYTE code)
{
if(gDebugMode)
{
CHK_BIT7(code)? RUN_LED2_ON : RUN_LED2_OFF; //Green
CHK_BIT6(code)? PF1_LED2_ON : PF1_LED2_OFF; //Red
CHK_BIT5(code)? PWR_LED2_ON : PWR_LED2_OFF; //Green
CHK_BIT4(code)? PWR_LED1_ON : PWR_LED1_OFF; //Red
CHK_BIT3(code)? PF1_LED1_ON : PF1_LED1_OFF; //Blue
CHK_BIT2(code)? RUN_LED1_ON : RUN_LED1_OFF; //Blue
CHK_BIT1(code)? PF2_LED_ON : PF2_LED_OFF; //Yellow
CHK_BIT0(code)? ERR_LED_ON : ERR_LED_OFF; //Red
}
return;
}

The input to this function is just a number you can assign to a particular error/state code: ie, Debug(3) would have the error and PF1 LEDs lit, while DEBUG(0) turns all the LEDs off. Combined with the use of the _delay_ms(1000) command, you can sprinkle these throughout problem areas and observe how your code branches or if it gets stuck anywhere.


The ordering of the LEDs may seem arbitrary, and it can be a little hard because the ordering zig-zags upwards from LSB (error) to MSB (power), and then zigs back down again. The reasoning behind this is because I wanted to make the lower numbers easier to read, since three of the LEDs have two possible colours. Hence, it's just normal binary for error values up to 2^5 = 32, and only mildly more complicated for bigger numbers.

C is for cookie

The robobuilder kit comes with a suite of tools which can be used to easily create poses and moves. Unfortunately, the overall impression they gave me was that they were useful for little more than making the robot dance. There were some useful features, such as being able to record the current pose of the robot and save it to a file, so I will probably play around with them later.

One of the most attractive features of the robobuilder system is that the firmware can be reprogrammed in C. If that doesn't send shivers down your spine, the rest of this post will probably be over your head. Go watch tv until the grown-ups are finished talking.

The tools to customise the robobuilder firmware are available for download. It comes with a 70 page PDF tutorial which walks you through the process of using the CodeVisionAVR IDE to customise the example builds included. The CodeVision IDE is not free, but I would recommend following the official procedure if: a) You are new to the C language or microprocessor programming and b) you use Windows.

If, like me, you fall into neither of the above categories, I suggest you save your money and have a go at using the avr-gcc compiler and/or WinAVR (which is just a Windows implementation of avr-gcc).

But first, a short rant.

When did motherboard manufacturers stop including serial ports?! I know that they are an aging technology, but they are damn useful. And you, robobuilder - you knew this all along but you didn't ship with a USB adapter or anything. I'm very disappointed. So here I am, forced to write code on the only computer in the house with a serial port - an old Dell Latitude D600. It runs Ubuntu 9.04 and was being used as a media centre PC, but I've since commandeered it in the name of the robot uprising. FYI, all of the robobuilder tools and software will run under WINE.

If you are compiling your code in linux, you will need to install avr-gcc and avr-libc. For reasons unknown, avr-gcc will not detect that avr-libc is installed and include it's headers when you compile. If you get an error message like:

error: avr/io.h: No such file or directory

You may need to copy the contents of /usr/lib/avr/include to /usr/lib/gcc/avr/4.3.2/include.

This robosavvy thread contains a port of the official robobuilder example source files which use the standard avr-gcc headers (also, comments in english!). Details about converting headers to gcc can be found at the avr-libc page. This is the skeleton code you need to edit. Use the command:

avr-gcc -mmcu=atmega128 -I. -g -Wall -Os -c main.c

to compile the source. I do recommend the -Os flag, since there is only 128kB of flash memory on the chip. You may still get some error messages at this stage - I did.

The names of header files are case sensitive in gcc, so check that the names of the #includes match the filenames:

#include "macro.h"
#include "main.h"
#include "comm.h"
#include "dio.h"
#include "math.h"

This should get rid of the remaining compile errors. Next you must link the files together using:

avr-gcc -o main.elf -mmcu=atmega128 main.o comm.o dio.o

If you get linker errors at this stage, check that you used the same -mmcu values for both compiling and linking (otherwise, gcc will try to link to code intended for different platforms).The final step is to convert the instructions to hex using the command:

avr-objcopy -j .text -O ihex main.elf main.hex

The .hex file created from this step is the actual firmware which will be written to the atmega128 chip. To upload it to the robot, simply run the "RBC Firmware update tool", and connect the robot using the (shudder) serial cable. Select the appropriate .hex file, and click the "Click Here" button. Now, press the reset button on the robot, and let the download finish.

To start the custom program, press the PF1 button. BEWARE! If you've made a mistake in your code, your robot will spaz out like an epileptic kid during a fire drill! To prevent damage itself and nearby life forms, either hold it by the head or make sure it is on the floor before testing it. Also note that unless you've specifically prevented such actions, the robot has no idea of it's own kinematics - meaning that it is quite likley to try and put it's arms through it's body when trying to scratch it's back. Be ready to kill the power if you want to prevent damage to the servos.

Now that I have some skeleton code to play with, over the next few days I'll experiment with various useful functions of the chip, like loading pre-built motions and getting data from the IR remote.