In the last couple of months I began to get a bit frustrated, technically speaking. The big programming project that I've been working on for the last year has finally come to an end - now we need to find some customers for it before we decide what to do next. So I scratched my head and decided that maybe it would be interesting to find out more about robotics.
A week later I'd read a lot and decided what I wanted to do to get started. I sent off an order to Trossen Robotics (there are of course quite a few suppliers, but these people seem to have a very good range) for a few bits and pieces from the Phidgets range, which are a great way to do robotics direct from a regular PC. I also ordered a Pololu 3pi, to get some quick experience with embedded programming. The 3pi is a small, round (10 cm across) robot made for following lines, with two independently-powered driving wheels, some infra-red sensors to see the lines, a microcontroller, some buttons and LEDs, and a tiny display.
I was amazed by how easy it is to work with the 3pi. I've never done anything with tiny microcontrollers before - my day job involves embedded programming too, but with a 400 MHz PPC with 1GB of memory, comparable to a PC. The 3pi has an Atmel 328p, which has 2 KBytes of DRAM and 32 KB of flash to hold the program. Compared to the PDP-8 I worked on in 1973, this is luxury. But when you're used to writing complex frameworks in C++ with Boost, it takes a bit of a mental gear-change.
Atmel provides a really excellent C compiler, actually GCC, and an IDE, loosely based on Visual Studio. It takes less than half an hour to download and install them, download the examples from the Pololu site, and be up and running. Then it was off to Office Depot (which I hate - never shop anywhere with "Depot" in the name - but they are just around the corner) for some paste board and black tape. Within a couple of hours I had my 3pi running round mazes, using the sample code.
"Every schoolboy knows" that if a maze has no loops in it, you can solve it by just turning left (or right) at every opportunity, until you reach the goal. So the interesting challenge is to solve mazes that do contain loops. The wall-hugging strategy will never actually get stuck in a loop, but it won't find the goal either, except by chance. (Actually it does kind of loop, because eventually it gets back to the start of the maze, and since it can't recognize that, it just starts over).
Solving looped mazes requires knowledge of absolute position. (If you have a useful upper bound on the size of the maze, I believe you can do it without such knowledge, but it's a lot harder to figure out how, and will take a lot longer to find a solution). If you know where you are, then you know when you reach an intersection you have already been to, assuming you have enough memory to keep track. (Remember, only 2 Kbytes of DRAM). The 3pi has no explicit position measurement, not even encoders on the motor shafts. The only way to track position is to integrate the motor speeds. It took me about a week to come up with working code to do this. It would be much easier to do in floating point - but the cost in both code space and computation time is unacceptable. I absolutely hate doing scaled integer math, it's a constant trap of overflows and underflows and just plain getting it wrong. But it's the only way.
Once I eventually got the code to work, I was surprised by how little of the available compute power it took. According to the simulator that comes with the Atmel IDE, keeping track of position every 10 mS takes about 0.5mS, i.e. 5% of the CPU. That's good, because it leaves plenty for doing other things, such as following a line, and keeping track of the maze structure.
Although the IDE includes a simulator, in the end I had to get the code working with Visual Studio as well, so I could get a "brain dump" of the computations at every 10 mS interval without having to step through them with the debugger. It's very easy to do this - just create Visual Studio and Atmel IDE projects in the same directory, and they work off the same source files. Of course a few #ifdefs are required to get things to compile in both environments.
One complication I ran into is that the motor speed response is not linear with the applied voltage - which is not a surprise. At lower voltages, a greater proportion of the power is used to overcome friction. Also, the two motors are not absolutely identical, so if you apply the same voltage to both of them, the 3pi gradually curves around. I wrote some code to calibrate the motors, which for the moment is a manual process although it would be a lot better to automate it. With the motors calibrated, it looks as though it should be possible to get a position estimate that is reliable to within about 1%. That should be good enough for mazes up to a couple of meters across.
That's about as far as I've got, at the moment. I'm now in the middle of writing the code to actually solve the maze. This is logically tricky but at least it doesn't involve any fixed-point math. More on that later, if and when I get the whole system to work.