Doughnut delivery is the dream of every office, and what better way to have them delivered than, in true futuristic style, on the back of a robot. My dream for a week was to make that a reality.
Ok, so the brief was a bit vaguer than that (“make something cool”), and my plan was a little more serious sounding. Using the Lego Mindstorms NXT (http://mindstorms.lego.com) I planned to make a remote controlled car, which could map out the office and navigate in real time. The robot should either build up a map as you drive it around, or have a preprogramed map already installed; it should be able to then navigate around the map, finding the best route back to where it started.
The first step was to decide on how I was going to program the NXT brick. I considered Lego’s drag and drop program builder, but it seemed too limiting. How could I possibly program a path finding algorithm in it? Then I found this (actually someone else in the office found it… but I am going to take the credit here). It contains an example of sending commands direct to the NXT, over Bluetooth, using C#. Commence programming.
I decided to use the A*path finding algorithm, you can find a great explanation of it here. The map would simply be a text file, with the size of the map, and then a series of 0’s and 1’s. 1’s for passable terrain and 0’s for impassable terrain, for example a wall. The A* algorithm would simply use the map, and find the best route from one destination to another. The A* algorithm is a bit time consuming, so the program only calls the algorithm once, and stores the route (as opposed to calculating it at every step).
Next I decided to run all of the code on a Windows Phone, using it as the controller for the NXT car. So I set about creating an app that would calculate the best route, and then interface with the NXT car to drive along the route. First I made a few buttons to simply move the NXT car (think remote controlled car). These allowed me to work out the best design for the car, as I hadn’t yet built it at this point.
I also realised at this point that I would, in the program’s current state, have to draw the map by hand. I deemed that to be far more work than I had time to do, so I added some functionality that would create a map as you drive the car around. Essentially, everywhere you drive the car would be set as passable, and everything else would be impassable.
The last part of my plan was to get the route found by the A* algorithm to determine the commands sent to the NXT car. Simple enough in itself, but a new problem had arisen. The NXT car did not necessarily turn by exactly 90 degrees. It would occasionally overshoot or undershoot and, as there was no on-board sensor that could tell the program how far it has turned, it could not compensate. I updated the car design with a new, snazzier, look.
This made the problem less pronounced, but still applicable. We tested the car on some laminate flooring, where it worked perfectly, and deemed the problem to be friction. Unfortunately this was at the end of the week, and with no time to fix the problem; we had to leave the project there.
So the final program runs on a phone, connecting via Bluetooth to the NXT car. It creates and stores a map as you drive it, and then (assuming it is on a surface such as laminate flooring) it will find its way back to the start.
Not quite doughnut delivery, but an interesting project nonetheless.