Compiling SRV-1 firmware under Windows – A Guide

In this tutorial I explain how a user of the SRV-1 Robot can compile the SRV-1 firmware and upload custom firmware into the robot .

After a long time of absence due to personal reasons I decided to take up the SRV-1 robot and get busy with the mazebot again. Picking up an old project after some months have passed is quite frustrating as you try to remind yourself of the whole process and trying to remember what’s what. But since I picked it up again I decided to write a sort of guide for compiling the firmware for SRV-1 under Windows and uploading it to the robot. I hope it can come in handy for other SRV-1 users.

First of all let’s start with what you will need. You will have to download:

Now that we have everything we need, let’s add some tools we will need from the blackfin toolchain to our System’s path. You do know what THE PATH is right?

  1. In any Windows System search for the “My Computer” Icon. (In the Start menu in Windows 7)
  2. Right click and select “Properties”
  3. Go to the “Advanced Tab” (Advanced System Settings for Windows 7)
  4. Right at the bottom there should be a button, “Environment Variables”. Click it.
  5. In the “System Variables” search for a variable named “Path”. Select it and click Edit.
  6. Add “;PATH_TO_THE_TOOLCHAIN/elf/bin” (without the ” ” of course).

Where for PATH_TO_THE_TOOLCHAIN you should enter the directory where you installed it.

Remember that when editing the path you need to add a semicolon (;) to separate each different directory. By adding the elf/bin directory of the toolchain to our system’s path we can now directly refer to tools such as bfin-elf-gcc (the gcc compiler for the blackfin processor) which reside in there. In general whenever you ask for something from inside a console command window all of the directories inside the “Path” are searched.

Now I would recommend copying mingw32-make.exe (remember that you should have downloaded it right?) into the “PATH_OF_SRV1FIRMWARE/blackfin/srv/ “, this is where the firmware source code is located. Of course instead of copying it to the same folder you can add the mingw32-make.exe container folder into the System Path following the six steps above. Whatever you choose the end result should be the same.

Now open a console command window.(Press the Start button and choose “Run”. Type “cmd” and press ENTER). Inside there navigate to the directory where the SRV1 firmware is located by using the “cd” command. (I assume you know basic DOS commands ). Having reached the directory of the firmware all you need to do to let the magic begin is to type:

mingw32-make

You should now be seeing a screen full of stuff. This is the compiler telling you what it is doing. Unless you wrote the code yourself then this should not matter to you. If all goes well then you should get something like this at the very end :

Adding DXE 'srv1.bin' ... [initcode 208] [jump block to 0x00000000] [ELF blo
ck: 32760 @ 0x00000000] [ELF block: 15008 @ 0xFF800000] [ELF block: 7520 @ 0xFF9
00000] [ELF block: 32960 @ 0xFFA00000] OK!
Done!

That’s it! You compiled the srv1 firmware under windows! See that .bin file? That’s your firmware.The .ldr file that’s generated from the .bin file is all we care about. As a side note, keep in mind that by issuing a command like: “mingw32-make clean” you effectively clean the project (deleting all the object files and the binary files). In case you want to recompile or if you just want to clean the folder from all those ugly .o files you can use it.

Now to get the freshly compiled firmware into the robot! For windows you can download a nice program called Tera Term to connect to the SRV-1. Assuming you are already connected with the robot open up Tera Term.

Remember to de-select the Telnet option as this will cause you trouble later in the transfer process. Enter “169.254.0.10” as the IP adress and “10001” as the port. Press ‘V’ and see if you get the Version String as a reply just to make sure that we are succesfully connected with the robot. If the connection is succcesfull then press ‘X’ to switch the robot to X-Modem Receive mode. You should be getting a string of CCCC characters now. This denotes that the robot is waiting for the file…

From inside Tera Term choose File–>Transfer–>XModem–>Send and select the “.ldr” file that you created just a while ago when you compiled the firmware. You should be seeing a transfer window that will be showing the transfer’s progress. When the transfer ends you should see something like:

 ##Xmodem success. Count: XXXX (a number)

Now we are sure that the binary firmware file transferred successfully.

Now to write this to the boot sector of the flash memory let’s issue the command “zZ”. It will take some time to reply but we should get a reply such as:

##zZ boot image write count:XXXX(a number)

Now the new firmware is safely written in the boot sector of the robot’s flash memory. All you have to do is restart the robot either by shorting the appropriate pins or by issuing a “$!” command.

Congratulations! Your have successfully compiled and uploaded firmware to the robot. For any additional questions you can email me at lefteris@realintelligence.net.

Have fun playing around with the code! 🙂

Genetic Algorithms and Sudoku Tutorial

This post contains a tutorial explaining what genetic algorithms are and how to implement one in the C++ language. An example application along with source-code for solving a Sudoku puzzle with genetic algorithms is also provided

This tutorial introduces the reader to genetic algorithms. They are algorithms based on the theory of evolution and are applied as optimization techniques in various fields. The tutorial will make a small introduction to how genetic algorithms work and the theory behind them and then back it up with an example program of trying to evolve a solution for a Sudoku puzzle. The tutorial source code can be found here, but to understand how it works it would be good to read on and see what each line of code does.

Tutorial Prerequisites

  • The reader should have a basic understanding of C/C++
  • The reader should know how to compile and run a program using any of the popular C compilers

Tutorial Goals

  • The reader will understand what genetic algorithms are and why they actually work
  • The reader will see how we can evolve solutions to problems by watching a sudoku solution evolve itself.

Tutorial Body

In this tutorial we will see what genetic algorithms are, how they work and the theory behind their operation. Moreover we will see an example of using genetic algorithms to solve Sudoku puzzles. As always the usual disclaimer applies. I can not promise that this is the best implementation of a genetic algorithm or a Sudoku solver but it is enough to let someone understand how to create one himself and to provide a good understanding of genetic algorithms.

Genetic algorithms are based on the theory of evolution, the theory which dominates nature and allows for the improvement of species in order to better adopt to their environment. Evolution works with the famous mechanisms of natural selection and survival of the fittest. We can not even question the efficiency of that mechanism, the results are all around us, even you and me. So why not try to create an algorithm which will use that efficient mechanism? That’s why genetic algorithms were created.

What is particularly interesting though is the way genetic algorithms mimic this mechanism of nature to solve problems, problems of any mangitude. The way they do it is by representing each potential solution with a chromosome as can be seen in the figure below.

A chromosome representation
A chromosome representation

A chromosome is a potential solution to the problem at hand. For example the perfect course schedule for an academic institution. The chromosome is usually an array of bytes like the one on the right but it can also be a matrix or even a graph! For our course schedule program the chromosome could contain the date-stamp of the lesson, the teacher and the nature of the class in 3 bytes. Then the whole schedule could be an array of these 3 type of bytes repeating themselves. What the genetic algorithm actually does then is initialize a population of these potential solutions, these chromosomes. The bigger the population, the better for us since there is more genetic diversity in our problem. You might be wondering, genetic diversity? What is he talking about? This is a computer program. Just have a little patience and you will understand what I mean soon enough

So, there we are having a population of potential solutions to our problem, all just generated randomly. None even close to being a good enough solution to what we want. But here is where, mimicking the mechanism of nature, we create a function called the evaluation function which plays the role of natural selection. This function assigns a fitness value to each and every chromosome in our population. This way we have a heuristic value telling us which solutions to prefer. Then trying to mimic nature’s mechanism again we allow our chromosomes to reproduce.

Chromosomes crossover
Chromosomes crossover

This is called recombination or crossover in genetic algorithm terms. We select the fittest chromosomes and some of the not-so fit just to keep the genetic diversity I mentioned above and allow them to reproduce. This, as we can see on the figure above, is done by setting the so called crossover points on the 2 parent chromosomes. We basically divide it into areas which will be transferred into the new children chromosomes. Then we perform the recombination by creating each child with combinations of their parent’s DNA divided where we set the crossover points. In addition in typical genetic algorithms there is a very small random chance for some individual ‘genes’ of a chromosome to suddenly change their values taking some other legal value. This is called mutation and the random chance is the mutation rate. What happens next is that we evaluate again all the new children generated from recombination and mutation with our evaluation function. Then always keeping in mind the genetic diversity of our population we choose the fittest ones to go to the next generation along with some of the not so fit ones.

This evolution keeps going on for generations, and as a result in each generation we have chromosomes which tend to be fitter and fitter matching our criteria of the perfect solution more and more. Unfortunately here is what we previously referred to as ‘genetic diversity’ comes into play. You see while this evolution continues for generations we reach a point where all recombinations and mutations of the parents produce offspring a lot worse than the parents and hence they do not go to the next generation. That is because we have reached a local optima, a point in the evolution of our species where the recombination of our genetic material just can’t produce better results. This is a very important problem with genetic algorithms and which we will see in the source code example that is about to follow. There are ways out of course, such as detecting these local optima and injecting new genetic material into our population or implementing directed mutation.

But let’s see an actual source code example. For this tutorial I chose to create for you a genetic algorithm Sudoku solver. It will showcase both the strengths and the weaknesses of genetic algorithms as we will very soon see, not to mention that for sudoku fans it will be pretty interesting. Of course in terms of speed and efficiency it can not even be remotely compared to any decent Sudoku solver, since genetic algorithms have the big disadvantage of being slow and computationally expensive. So here is our representation of any sudoku puzzle in code:

    int sudokuRepresentation[] = {
    5,3,X, X,7,X, X,X,X,
    6,X,X, 1,9,5, X,X,X,
    X,9,8, X,X,X, X,6,X,
 
    8,X,X, X,6,X, X,X,3,
    4,X,X, 8,X,3, X,X,1,
    7,X,X, X,2,X, X,X,6,
 
    X,6,X, X,X,X, 2,8,X,
    X,X,X, 4,1,9, X,X,5,
    X,X,X, X,8,X, X,7,9
    };

Wherever there is a X we consider it a variable and the other numbers are the given information about each Sudoku. This particular one is taken directly from Wikipedia’s sudoku page. Each solution is represented by an array of ints( a pointer to int in code). The size of that array is the number of unknowns in the Sudoku puzzle. So for that particular puzzle above we would have a 51 integers array for our chromosome. Each one representing a potential Sudoku solution.

The classes which were made to represent these in the source code are two. One is of course the chromosome class, representing our chromosomes and the population class which contains all the information about all our chromosomes and their genetic parameters, such as crossover points and mutation rate. As can be seen in the code box below the chromosome contains an evaluation function and its solution representation. On the other hand the population contains all of its chromosomes in a vector and its starting setup, meaning the initial Sudoku puzzle configuration. In addition the population contains a roulette wheel. This as we will see is our selection mechanism to select chromosomes for reproduction

 
 
    class Chromosome
    {
    public:
    int* representation;
    int size;
    int fitness;
    int penalty;
    //constructor and destructor
    Chromosome(int unknowns);
    ~Chromosome();
    //operator overloading just so we can assign chromosomes in the population
    Chromosome& operator=(const Chromosome& c);
    //the evaluation function
    void evaluate(int* startingSetup);
    //helper function to get the offset of the chromosome
    //when seen in the whole filled sudoku puzzle
    void getChromoOffset(int pos,int* setup,int &offset);
    };
 
    class Population
    {
    private:
    //our starting sudoku puzzle
    int* startingSetup;
    //the population count
    int populationNumber;
    public:
    //the actual chromosome population
    std::vector<Chromosome*> genePool;
    //this is our selection method
    //a roulette wheel selection
    std::vector<int> rouletteWheel;
    //constructor
    Population(int populationNumber,int* rules);
    //performs Selection of chromosomes, recombinations
    //and mutations and creates the next generation of solutions
    void selectAndRecombine(int crossoverpoints,int mutationRate,bool newMaterial,bool superMutation);
    //Returns the fittest chromosome in our population
    Chromosome* getFittest();
    //prints the solution to the sudoku puzzle that the
    //parameter chromosome reperesents
    void printSolution(Chromosome* chromo);
    //clears the given population gene pool
    //since memory leaks are bad
    void clearPool(std::vector<Chromosome*>& a, int size);
    };

But let us delve a little deeper into the tutorial’s code. I will not show the evaluation function’s code here since it is pretty simple, all it does is count the numbers the chromosome breaks the three Sudoku rules and assign penalties. Each chromosome is given a penalty point for each rule broken and for each rule which it upholds fitness is added to it. I gave each rule equal fitness and penalty values since to tell the truth I am not that familiar with Sudoku. Maybe some Sudoku experts think differently. If so please email me so I can correct it or even better change the macros which define the penalty and fitness values in the code yourself and see the results.

Let’s see now some snippets from the most important function in all of the tutorial, the function which performs selection, recombination and mutation and creates the next generation of solutions:

 
 
    ...
    //evaluating the genePool
    for(int i = 0; i < popSize; i++)
    {
    (genePool.at(i))->evaluate(startingSetup);
    }
    ...
    ...
    //creating the roulette wheel according
    //to the fitness of each chromosome
    for(int i =0 ; i< popSize; i++)
    {
    if(!injectNewGeneticMaterial)
    {
    prFitness = cFitness;
    cFitness +=(genePool.at(i))->fitness;
    for(int j=prFitness/ratio;j&lt;cFitness/ratio;j++)
    {
    rouletteWheel.push_back(i);
    }
    ...
    ...
    //Choosing parents depending on their portion of the roulette wheel
    //random number from 0 to roulettesize-1
    Parent1 = genePool.at( rouletteWheel.at( int((rouletteSize*rand())/(RAND_MAX + 1)) ) );
    if(!injectNewGeneticMaterial)
    {
    //random number from 0 to roulettesize-1
    Parent2 = genePool.at( rouletteWheel.at( int((rouletteSize*rand())/(RAND_MAX + 1)) ) );
    }
    ...
    ...
    //Performing recombination
    for(int s = 0; s<= crossoverpoints; s++)
    {
    if(s != crossoverpoints)
    {
    destination = Child1->representation;
    if(s%2 == 0)
    source = Parent1->representation;
    else
    source = Parent2->representation;
    memcpy(destination+offset,source+offset,(points.at(s)-offset)*sizeof(int));
    destination = Child2->representation;
    if(s%2 == 0)
    source = Parent2->representation;
    else
    source = Parent1->representation;
    memcpy(destination+offset,source+offset,(points.at(s)-offset)*sizeof(int));
    offset = points.at(s);
    }
    else
    {
    destination = Child1->representation;
    if(s%2 == 0)
    source = Parent1->representation;
    else
    source = Parent2->representation;
    memcpy(destination+offset,source+offset,(chromoSize-offset)*sizeof(int));
    destination = Child2->representation;
    if(s%2 == 0)
    source = Parent2->representation;
    else
    source = Parent1->representation;
    memcpy(destination+offset,source+offset,(chromoSize-offset)*sizeof(int));
    }
    }
    points.clear();
    ...

The above code consists of three snippets. As can be seen in the first snippet we can see how each chromosome gets evaluated by invoking its evaluation function.

Then a little later down in the code comes the second snippet. This shows how the roulette wheel is created. It is quite simple. Basically we get the whole population’s fitness and get the total fitness’s ratio to the RAND_MAX value(the maximum value that can be returned by rand(). Subsequently we assign a part of the roulette to each chromosome proportionate to their fitness’s level when compared to the total fitness. That way all chromosomes can still be selected, but fitter individuals have a higher chance of doing so.

Then in the third snippet is the actual recombination code. As we can see the 2 children are actually created by the 2 selected parents genetic code recombined in ‘s’ crossover points, a number given as a parameter from the start.

That was the essence of the code, there are some other details of course but you can see it for yourself by downloading the .rar file. What is important is that you understand the concept of a genetic algorithm.

Let’s see though how does the algorithm fare when running and trying to evolve the solution to a Sudoku puzzle. As was already mentioned traditional genetic algorithms are really slow when compared to more conventional solving algorithms and especially in a Sudoku puzzle’s case which has only one and unique solution this applies even more. After some experimentation I concluded that a population of 2000 and 14 crossover points was a very nice genetic setup. The population size if of utmost importance since a small population does not have enough genetic material from which a good solution can be evolved. As for the number of crossover points this is a unique characteristic of the Sudoku puzzle. The number of crossover points used in a typical genetic algorithm is 1-3. In our case though since a Sudoku has only one and unique solution exchange of genetic material must be performed in as many parts as possible so as to avoid the local optima problem. Take a look below to see the main code of the tutorial where we can see the program’s logic and how ti evolves the generations of our solutions.

 
 
    Population pop(populationN ,(int*)sudokuRepresentation);
    int fitness = 0;
    int generations = 0;
    int mutation = 100;
    int samePenaltyCount = 0;
    int prPenalty = 999;
    int backTrackCount = 0;
    int penalty = 99;
    while(penalty > 0 )
    {
    if(samePenaltyCount > 15)
    {
    samePenaltyCount = 0;
    pop.selectAndRecombine(crossoverPoints,mutation,true,true);//100/32765 seems to be nice
    backTrackCount++;
    }
    else
    pop.selectAndRecombine(crossoverPoints,mutation,false,false);
    printf("Best Fitness in generation %d is %d with backtracks: %d \n\r",generations,(pop.getFittest())->fitness,backTrackCount);
    penalty = (pop.getFittest())->penalty;
    if(penalty == prPenalty)
    samePenaltyCount++;
    else
    samePenaltyCount = 0;
    prPenalty = penalty;
    printf("The penalty of the fittest one is %d \n\r",penalty);
    pop.printSolution(pop.getFittest());
    generations++;
    }

One can easily spot the option for backtracking. That is if the algorithm is stuck at the same fitness level for 15 generations the algorithms performs a super mutation hence almost totally changing the population. I count these as backtracks. Below is the output:

Best Fitness in generation 57 is 4860  with backtracks: 0
The penalty of the fittest one is 0
5  3  4     6  7  8     9  1  2
6  7  2     1  9  5     3  4  8
1  9  8     3  4  2     5  6  7

8  5  9     7  6  1     4  2  3
4  2  6     8  5  3     7  9  1
7  1  3     9  2  4     8  5  6

9  6  1     5  3  7     2  8  4
2  8  7     4  1  9     6  3  5
3  4  5     2  8  6     1  7  9
Process returned 0 (0x0)   execution time : 40.859 s

This is the result of a run of the algorithm. This is a good run, in fact one of the best runs. There were no backtracks and it found the solution in 40 seconds. Unfortunately this is not the typical run. In a typical run it might do 1 backtrack, or even 2. That is because the algorithm gets to a point where it just can’t improve the chromosomes anymore. Moreover in some very hard Sudoku puzzles it might not be able to find a solution in a sufficient amount of time and might need to do many backtrackings. Backtracking is not something that genetic algorithms usually do. I added it just so it can solve it faster. There are other more advanced genetic techniques such as directed mutations which would target the genes which cause the problem whenever we get stuck in a local optima. Through these mutations we would be able to change the problematic genes until they take the form we want. Other more exotic ideas involve wars between different populations, parallel genetic evolution (running on many processors) e.t.c.

Of course such techniques are out of the scope of this tutorial. This tutorial’s goal was to give an introduction to genetic algorithms and give an educating, comprehensive and interesting example of their use. I hope that you found it useful and that something was learned by reading this tutorial. Remember that a Sudoku puzzle is not the best example to give for genetic algorithms since it has only one solution but it is good enough to demonstrate a practical example of genetic algorithms. You can find the source code here. I hope you find it useful and please email me at lefteris *at* refu *dot* co for any comments/suggestions or constructive criticism. See you in the next tutorial!