42

If you ever needed proof to see that the world we live in a complex, and at the same time, that it is possible to draw extraordinarily elegant conclusions from math, you don’t have to go any further than one of fundamental elements of geometry, angles. In primary school, you are told about angles. In high school, you learn basic trigonometry and vector math. As an (engineering) undergraduate, you learn to analyze and apply these concepts to problems which incorporate change of angle with calculus. But at no time, do I remember having anyone offer a mathematical explanation for why the angles 2.n.pi+a , … , -2.pi+a, 0+a, 2pi+a, …, 2.n.pi+a (for all n, in the set of integers, and for all a in the set of real numbers) are equivalent.

It turns out that there is a (reasonably) simple explanation, and a branch of mathematics which can be used to describe such problems - group theory. In particular, the types of effects we see when working with angles can be explained by using the circle group. I’m going to leave most of the math to wikipedia pages mentioned at the bottom of the article.

I’m a programmer at heart, and so the circle group is of interest to me when I need to consider operations on elements of the group (addition and subtraction), or in particular, testing the equivalence of two values in the group, that is, answering the question - when are two angles effectively equal?

One possible approach is to bring both angles into a subset of the circle group, in which we can directly compare angles as real numbers. Typically, a reasonable subset of the circle group is either [0,2pi) or [-pi,pi), but any continuous range of length 2pi is fine. For testing equivalence, the simplest range is likely to be [0,2pi).

From a mathematical perspective, conversion of an angle to a value in the range [0,2pi) can be achieved by taking the modulo of an angle.

a’ = a mod 2pi

In (c-style) psuedocode, the same operation can be stated as:

angle angularModulo(angle a) {
	return a % (2 * M_PI);
}

There are a few caveats about this approach. The first is that the modulus operator in c is not defined for floating point types (angle cannot be double or float), instead it is necessary to use the fmod functions. The behavior of the fmod function is described in Annex F (F.9.7) of the c-standard (ISO/IEC 9899:1999) - and the results for negative angles are somewhat counter-intuitive.

As far as I can tell, a similar definition to the mathematical one can be archived by the following function.

double angularModulo(double a)
{
    if(a >=0)
        return ::fmod(a,2*M_PI);
    else
        return 2*M_PI + ::fmod(a,2*M_PI);
}

References
http://en.wikipedia.org/wiki/Angle
http://en.wikipedia.org/wiki/Euclidean_space
http://en.wikipedia.org/wiki/Orthogonal_group
http://en.wikipedia.org/wiki/Circle_group

One of the things I’ve really learnt to love about working on (most) linux variants are the UI’s for the shells. Remote access to linux through Putty, and the bash shell which comes with Ubuntu are lovely. I’ve seen some of my colleagues do some very smart things with color coded tabs which identify which remote machine they are logged into.

On windows, the default shell is almost unchanged from the DOS 6 days. No tabs, flakey auto-complete, hard on the eyes and worst of all, in the era of wide screen monitors and verbose compiler output, you can’t resize the window.

Tonight I finally found Console, a replacement UI for the standard cmd.exe, which does pretty much everything I want (after a bit of fiddling).

The only thing I couldn’t get it to do in a nice way was to run the visual studio variables script (which sets up your environment variables for the compiler). I did however end up with a two line batch file which does what I want.

call "C:\Program Files\Microsoft Visual Studio 9.0\VC\vcvarsall.bat"
start Console.exe

At the moment I’m in the process of moving house. I have a pretty big collection of books relevant to programming and engineering. My wife is so organised I’ve had to box most of my collection up, keeping out only a select few bits and pieces that I’ll need between now and when we move in mid-July.

The books on planning, control theory, game related AI and collision detection all have relevance (in varying degrees) for my current research – they’re out in case midnight inspiration strikes.

The C++ coding standards book is out because one of my roles at work lately has been offering advice in this area. The Algorithms in C++ book is out because I recently got stuck on some hairy graph theory problems (maximal paths through a flow network).

Some of the books on the shelf (on pattern classification, dynamic programming and reinforcement learning), are there because they are potential areas for post-doc work related to robotics – eventually I’ll get a chance to do more of the chapter exercises.

The odd books out are perhaps the most interesting – three books on lisp, and a book on compiler design. Topics I feel strongly about at the moment. The work I’ve done over the last couple of years has left me unsatisfied with raw C/C++ and I’m exploring the possibility of translating a subset of lisp/scheme into C.

I’d be interested to see the diversity in some of the other blogger’s bookshelves.

This post is a record of the way I got flex and bison going on MinGW.

Firstly let me prefix this by saying that although mingw and msys are a great idea, and much better than I remember them to be, getting everything running is much harder than it should be.

1. Download and the core mingw installer from the sourceforge page (follow the links on the MinGW download page)
MinGW-5.1.4.exe

2. Add c:\mingw\bin to your path

3. On the sourceforge download page, under the category MSYS base system, open ‘current-release’ and download the MSYS installer.
MSYS-1.0.10.exe

4. Add c:\msys\1.0\bin to your path

5. Download the flex and bison packages, making sure not to get the source packages. You only need the executables from those packages and put them in the somewhere in your path (c:\mingw\bin seemed reasonable).

The topic of this post is generalising the concept of an image to arbitrary sizes and n-dimensions. Generalizing to multiple dimensions is relatively simple, requiring only a single contiguous block of memory, which needs to be allocated at run-time, rather than at compile time. To simplify the process of implementing the C++ samples, I’ve decided to use the vector class from the standard C++ library, which takes care of managing memory and producing correct copy constructors and assignment operators.

The code snippets presented here are intended to illustrate concepts rather than being production ready code. Only minimal error checking is used, no tests are provided and const correctness is ignored.

#include <vector>
 
class Image
{
public:
    Image(int width, int height)
    {
        this->width  = width;
        this->height = height;
        imageData.resize( width * height );
    }
 
    int get(int x, int y)
    {
        return imageData[ index(x,y) ];
    }
 
    void set(int x, int y, int value)
    {
        imageData[ index(x,y) ] = value;
    }
 
private:
    int index(int x, int y)
    {
        return y*width + x;
    }
 
private:
    int width;
    int height;
    std::vector<int> imageData;
};

The image class builds on the concept introduced last time of producing a one dimensional index from multiple co-ordinates (the index method).

For the sake of choosing a name, throughout the remainder of this post I’ll refer to an n-dimensional data set as a Space. The term space commonly appears in AI and engineering presentations, and has a formal mathematical definition. However, for our purposes, it’s sufficient to consider a space to be a discrete grid in n-dimensional space in much the same way that an image is a discrete grid in two dimensions. This class of space considered here could be more accurately considered a discretized compact subset of Euclidean Space.

Rather than continuing to pass each of the components of each co-ordinate of the space, it becomes convenient to bundle them into tuples (or n-dimensional vectors). Although there are better implementations for tuples (see boost::tuple). In this implementation I’m going to again use the standard C++ vectors, which requires an extra length test. The process for generating indices can be written as neatly in n dimensions as a sum of products.

#include <vector>
#include <cassert>
 
class Space
{
public:
    typedef std::vector<int> Tuple;
 
    Space(Tuple v)
    {
        xmax = v;
        dimensions = (int)v.size();
 
        int numElements = product(v,dimensions);

        data.resize( numElements );
    }
 
    int get(Tuple c)
    {
        return data[ index(c) ];
    }
 
    void set(Tuple c, int value)
    {
        data[ index(c) ] = value;
    }
 
private:
    int product(const std::vector<int>& v, int n)
    {
        int result = 1;
        for(int i = 0; i < n; i++)
        {
            result *= v[i];
        }
        return result;
    }
 
    int index(Tuple v)
    {
        // validate the size of the tuple
        assert(v.size() == xmax.size());
 
        int result = 0;
        for(int i = 0; i < dimensions; i++)
        {
            // check the current element is in range
            assert(v[i] < xmax[i]);
            result += product(xmax,i)  * v[i];
        }
        return result;
    }
 
private:
    int dimensions;
    Tuple xmax;
    std::vector<int> data;
};

Next time - generalising the concept of a discrete space to a continuous space, and adding a simple technique for interpolation.

One of the awkward things to do in C/C++ is work with multidimensional sets of data. One of the reasons that this can be such a challenge is that it involves pointers, and an understanding of what is going on inside the machine. This post is intended to be an introduction to a series of posts on multi-dimensional data sets.

The techniques proposed here will only work on a single contiguous block of memory (not multiple blocks, as would be the case for some dynamically allocated approaches).

Classic examples of a problems that requires multi-dimensional arrays are images or a terrain elevation maps (height maps) in two dimensions. In three dimensions, applications include voxels (volume pixels) commonly used in medical imaging, and multi-channel image (with separate red,green and blue components). Data sets of higher dimensions have applications in engineering and AI.

Initially I’m going to present code for working with multi-dimensional data sets in terms of a simple two dimensional image. As I go on I’ll generalise to higher dimensions and arbitrary sizes.

#define IMG_WIDTH  (10)
#define IMG_HEIGHT (10)
int img[IMG_WIDTH][IMG_HEIGHT];

Each element of the image can be accessed using the syntax below.

img[x][y] = value;
value = img[x][y];

However, although access to each of the elements of the image appears to occur in two dimensions, behind the scenes the compiler is converting your array index operations into pointer arithmetic, and accessing a one dimensional element. The following code demonstrates this concept.

// ptrImage is a 1d equivalent of img
int* ptrImage = &(img[0][0]);
for(int x = 0; x < IMG_WIDTH; x++)
{
    for(int y = 0; y < IMG_HEIGHT; y++)
    {
        std::cout << &(img[x][y]) << ” “;
        std::cout << ptrImage << std::endl;
        ptrImage++;
    }
}

The ordering of elements within memory is dependent on the type declaration (where the x-dimension was listed before the y-dimension).For an image of width ‘n’ and height ‘m’ the memory layout will be:

(x₀,y₀), (x₁,y₀), …, (x_n-1,y₀), (x_n,y₀), …, (x₀,y₁), (x₁,y₁), …, (x_n-1,y_m), (x_n,y_m)

An alternative to using array notation is to manually produce the offset from the start of the block of memory. In two dimensions this process can be completed with the following snippet.

// convert a 2d co-ordinate to a 1d offset
int f(int x,int y)
{
    return (y * IMG_WIDTH) + x;
}
 
// ptrImage is a 1d equivalent of img
int* ptrImage = &(img[0][0]);
for(int x = 0; x < IMG_WIDTH; x++)
{
    for(int y = 0; y < IMG_HEIGHT; y++)
    {
        // the equivalent of img[x][y]
        std::cout << ptrImage[ f(x,y) );
    }
}

As an aside, on modern CPUs the performance of algorithms operating on multi-dimensional structures is tightly coupled to the order in which elements are accessed - programs which sequentially access elements of an array are likely to perform better than a program which jumps around inside the array. Most good references to optimisation on the net will have recommendations on best practices in this regard.

Next time - generalising this concept to arbitrary sizes in n-dimensions.

One of my pet peeves is explaining why wireless networking is insecure to non-technical family and friends - everyone seems to know there are security risks, but no-one seems to have a good grasp on how to work around the problems.

WPA seems to be the best choice for security, but it relies on a key which is sufficiently strong which can be reproduced when necessary. I’m convinced one of the reasons wireless networks get hacked is because no-one can be bothered typing in a key that is 63 characters long.

I am not a security expert, but this is the approach I’ve been using for a while. No guarantees that it is suitable for your network or hardware.

The python snippet uses the hash of an object to seed a random number generator before producing a n digit hexadecimal code suitable for use with wireless networking. This is perfect for python because most objects are hashable, particularly strings.

import random
 
def generateWPA(obj,n = 63):
    assert(n >= 8)
    assert(n < 64)
    hc = hash(obj)
    random.seed(hc)
    lst = [ random.randint(0,15) for i in range(n) ]
    acc = 0
    for i,v in enumerate(lst):
        acc += (16**i * v)
        code = hex(acc)[2:]
        if code[-1] == ‘L’:
            code = code[:-1]
    return code

Drawing scientific diagrams can be a real pain in the neck.

You want them to look good enough that they don’t look terrible when compared to other diagrams you see published in comparable places.

Thankfully MATLAB to the rescue. Obviously the jpeg’s for the web don’t do the full postscripts justice, but at least this way everyone can look at them. I’d appreciate advice if anyone knows how to make wordpress upload and display full sized images. [Edit: finally fixed this problem, just ended up hacking the html in the wordpress editor to look right].

[u,v] = meshgrid([0:0.1*pi:2*pi],[4:0.5:10]);
patch(surf2patch(v.*cos(u),v.*sin(u),v,v));
shading interp;
lighting gouraud;
view(3);
camlight;

[x,y]=meshgrid(-10:10,-10:10);
M=x;
N=-y;
quiver(x,y,M,N)

One of the things that really frustrated me when I’d finished my robotics degree at Swinburne and I’d spent a little bit of time working on my research was that we’d really been taught very little in the way of modeling practical systems. By practical I mean something beyond basic control theory type modeling, which is great for things like radar dishes, temperature controllers and very basic robot arms, but pretty much useless for anything else that’s interesting (like wheeled vehicles or aircraft).

Most of the time in undergraduate robotics the that fact that you don’t have an accurate model of a robotic vehicle is fine - typically because by the time you get around to doing anything with a vehicle the semester has finished, but also student built vehicles tend to move at reasonably constant speeds (low accelerations), which allows simple kinematic models.

However, in some cases you really do want a reasonably high fidelity models - particularly when your vehicle undergoes large sudden changes of velocity (high accelerations), or when you want to know what interactions your wheels are having with the surface they have been placed on (friction effects), or when you’re attempting to accurately control the position and velocity of a robot in a rapidly changing environment.

One of the things that has driven my concern about this was one one robotics team attempt to use ODE (a rigid body physics engine) to simulate wheeled vehicles for a final year software project and nearly end up failing because using raw ODE to create models is so hard. Don’t get me wrong, ODE is fantastic, but being able to do practical work with it is a bit of an art - partially because you need practice, and partially because the API gives you so much flexibility. So anytime I find anything vehicle simulation related I tend to take notice.

After watching a fantastic video on the Microsoft Channel 9 today with the physicist Brian Beckman, I’m finally coming to the realization that undergraduate robotics students aren’t taught how to accurately simulate wheeled vehicles because it’s hard - so hard that it’s still an active area of research.

In the video Beckman discusses a short clip of rigs of rods a truck game created using a soft body physics simulator. What’s significant about the rigs of rods approach is that building and prototyping trucks is easy, you supply a list of vectors and connections between vectors which are spring/dampers. Although the simulation isn’t particularly accurate at the micro level, it lets you do some really cool things like plastic deformation and breaking into pieces if sufficient force is supplied. I think this is a direction that I’d love to take the game physics article on SwinBrian

As nice as postscript is for generating log videos, it gets really tedious drawing one off pictures with it. After a bit of hunting around I found Inkscape, which is cross platform and much better than DIA - although they have slightly different applications.

I also realized that firefox renders SVG (Scalable Vector Graphics), which is Inkscapes native format without having to install a plugin.